Spring 2008 - Research Seminar - 0368-4126-01
"The algorithmic lens - computational perspective in the sciences"

Lecturer: Julia Kempe
Time and place:  Mondays 11-13h, Kaplun 319
Remarks: This seminar will be held mainly in English. For the seminar poster see here [pdf].

Announcements:
[2.6.] Next week is Shavuot - no seminar on 9.6.
[22.5.] speaker's schedule is now finalised
[12.5.] Change in lecture hall for 19.5. - Shenker 114 (Physics)
[4.5.] I will meet with the students who present, on the Thursday preceeding their talk.
[3.5.] projects are up now, choose your project soon, and we need a volunteer for May 12 (who has the first pick on the topics)!


Syllabus: In this seminar we will look at the question: "What is Computer Science?". Over the last decades computer science has played a larger and larger role in various fields like Biology, Economics, Physics, the Internet, Social Science... Perhaps one way to view Computer Science is as a way of thinking, or as a "lens" with which to study various disciplines. And adopting the algorithmic worldview is already changing the sciences: mathematical, natural, social and life. 

We will look at examples and evidences of this (look at the list of possible topics). More precisely, we will read papers that explain something new using an algorithmic or computational approach. Our topics will be wide, from games on networks (like the internet) to biology (how does evolution work), from physics (quantum computing) to economics (e.g. social choice). Nonetheless some of the papers will be quite deep and/or technical.

Students are expected to read and present a paper or a small set of papers on a topic. The preferred language is English, however we will try to accomodate if there are problems with this.

Grading: will be based on student presentation of papers

Prerequisites: a curious mind and willingness to learn something new, some knowledge of algorithms, computational complexity and basic computer science

Possible topics: (will be completed)

Physics: how does Nature "compute"?

• quantum computing - Feynman: use quantum machines to simulate quantum effects
• cellular automata and the laws of physics
  
• statistical mechanics: phase transitions and their connection to mixing times of random walks
  

Biology: several mysteries in biology can be productively approached as algorithmic problems: evolution, the brain, ...

• evolution of internal conflicts in the brain
• DNA computing
• evolution and algorithms
  

Internet: how did it  evolve and how do we interact on it - the internet is the first computational artifact that was never designed

• how did the internet grow - the small world phenomenon "six degrees of separation"
  
• how to players interact - games on networks
• mechanism design
  

Economics: how to markets work, how do parties agree, how do selfish agents interact

• Non-cooperative games, Nash equilibria
  
• Arrows theorem about social choice
• Auman's theorem "Agreeing to disagree"
  

Projects:
Choose one of the projects below, read and study the paper(s) given and prepare a 1h30min lecture about the material. The order of the topics is not important. In some exceptional cases, students can propose papers that fit the theme of the seminar and can present those papers after consultation with me.

Physics and Computing

• Quantum Computing: Feynman's original paper as well as a subsequent paper by Deutsch. In this paper Feyman first develops the idea of what later become known as a quantum computer. Deutsch takes up the idea and gives the first toy problem in which a quantum computer succeeds over a classical one.
• Cellular automata to model nature: recent cellular automata survey and references therein. Studies which processes can be modeled by cellular automata. You need to pick one of the references in this paper and study it in more detail.
  
• statistical mechanics: phase transitions and their connection to mixing times of random walks "Mixing in Time and Space for Lattice Spin Systems - A Combinatorial View" (see also a small news release about the work of Sinclair and others)
  

Economics

• Non-Cooperative Games: Nash's original paper (Nash subsequently won the Nobel Prize for his work related to this paper. You might have seen the movie about Nash "A Beautiful Mind".) . The subsequent complexity theoretic paper decades later by Chen and Deng "Settling the Complexity of Two-Player Nash Equilibrium"  (computer scientists considered this paper important enough to give it the FOCS best paper award in 2006). This project studies the notion of Nash equilibria and how efficient it is to find them. Nash equilibria appear in economics, and in many other places.
  
• Complexity of agreement: Scott Aaronson's  complexity theoretic paper on Aumann's theorem  (In 2005 Aumann became part of the illustrous circle of Nobelists in economics. He is also a deeply religious man. If you want to read something more entertaining about Aumann, check out the "Interview with Robert Aumann" by his former student Sergiu Hart [short version]). Studies complexity questions associated with Auman's theorem on "not agreeing to disagree".
  
• Social Choice and Boolean functions, Arrows theorem: (this project is only for those who took Oded Regev's Analytical Methods in Computer Science) - Ryan O'Donnell's lecture notes 12,13 based on what you learned in that course, you need Boolean analysis
  

Internet

• mechanism design: Noam Nissan's survey paper and/or Archer and Tardos'paper on "Truthful Mechanisms for One-parameter agents"
  
• the growth of the web and six degrees of separation: "The diameter of the world-wide web", "Emergence of scaling in random networks", "Power-law distribution of the world-wide web", "Error and attack tolerance of complex networks", "Network Theory - the Emergence of the creative Enterprise" and "Quantifying Social group evolution" - short Science and Nature articles by Barbasy. Studies the structure of the web and other networks.
  
• Small world phenomena: Kleinberg's "The small world phenomenon - an algorithmic perspective", Science article "The structure of the web" and a short AMS survey. Studies how the web grew and which topologies give rise to the small world phenomenon.
  
• Interaction on Networks: games on networks, the price of anarchy and so on - "Computing in Games" by Tardos and Vazirani and "How bad is selfish routing" by Tardos and Roughgarden, another paper on algorithms and the internet by Christos Papadimitriou  . Studies decentralized interactions on the internet and how much worse it is compared to central planning. Connection to approximation algorithms.
  

Biology

• Population genetics: "A computational view of Population Genetics"  Applies methods of probability theory (random walks, mixing times) to study of how the genetic make-up of populations changes.
  
• DNA computing: the original paper by Adleman (a survey by Kari can be found here), its further formalization "On the Computational Power of DNA" and "Using DNA to solve the bounded Post  Correspondence Problem", and a follow up breakthrough result (news release here) from the Weizman group, you could also focus on "The Computational Power of Gene Rearrangement" by Kari et al. (this project can be for two people speaking in two sessions). DNA computing was initiated by Adleman and is still a booming area of research. The idea is to use the basic processes happening with DNA to do computation. It is a little bit the inverse direction from the perspective we take in this seminar, but might suggest that after all genetics is more computational than we thought.
  
• Complexity of Gene Placement: paper by Goldberg et al. Gives complexity theoretic and algorithmic results on gene placement.
  
• Algorithmic explanations for genome halfing: the original article by Hannenhalli and Pevzner "Transforming Cabbage into Turnip", Pavel Pevzner's more recent article, and references therein (Pavel Pevzner is one of the pioneers of bioinformatics, read his essay on "Educating biologists" which also fits our seminar theme!)  Note that this topic fits somewhat less into the framework of our seminar, as it gives an algorithm for analysing genome rearrangement - however, the new perspective (looking at permutation distance) advanced this subject.
• Internal conflicts in the brain: Livnat-Pippinger paper, appendix and Fig. 3, 4 , 5. Complexity-theoretic explanation of systematic errors by the same authors. Tries to find complexity theoretic reasons of why the brain is managed by internal conflicts and why there are systematic errors.
  
• Self assembly (biological and other): One of the earlier papers by Rothemund and Winfree "The program-size complexity of self-assembled squares" and a follow up paper. Studies the complexity of self assembling (both for crystals and DNA, for instance) and determines the computational power of self-assembling configurations.
  

Course outline (will be updated throughout the semester):

Date	Topics	Speaker
5.5.	General overview (see "Is the Thrill Gone" by Arora and Chazelle, and "Through the lens of Computation")	Julia Kempe
12.5.	DNA computing [pdf of Yifat's lecture]	Yifat Felder
19.5.	Self assembly [pdf of Saar's lecture]	Saar Yahalom
23.5. (Friday)	no lecture
26.5.	Growth of the web and six degrees of separation [pdf of Jonathan's lecture]	Jonathan Berant
2.6.	Internal conflicts in the brain [pdf of Ori's lecture] [scribe of the proof on the board]	Ori Folger
16.6.	Mechanism design [pdf of Omer's lecture]	Omer Ran
23.6.	Nash equilibria [pdf of Lior's talk]	Lior Peleg
30.6.	Cellular Automata [pdf of Eran's lecture]	Eran Meir
7.7.	Complexity of Agreement [pdf of Niko's talk]	Niko Farhi