Dick Karp gave a 1-hour invited talk in two parts. First he gave a short version of "Why TCS is important to other sciences." This is a sermon that ought to be delivered to deans, and to non-theory folks in CS.
- TCS points out the computational nature of natural and social processes, and provides a language for their descriptions analogous to Math providing equations that describe phenomena and methods to manipulate equations.
- TCS alters world views in other areas, providing paradigms to understand and to model.
- Biology: cell process regulation.
- Learning: (in humans, animals) paradigms, models and algorithms from Computational Learning Theory
- Molecular self-assembly
- Strategic Behavior of companies
- Physics: Quantum Mechanics and quantum computing.
- Math: too numerous to mention, algebra, Fourier techniques, Social sciences: web, data for social interactions and behavior, etc.
Janos' Comment: I think it is important to emphasize that CS contributes more than a passive lens: we are not a tool, but a partner.
The second part of Karp's talk was a set of examples from Computational Molecular Biology, illustrating some of the contributions/research accomplishments. He gave 5 examples of "Algorithmic Challenges in Computational Molecular Biology." [Many are associated with Berkeley because Karp is quite familiar with these]
- Sequencing Genomes. He talked mostly about Myers' contribution to shotgun sequencing. His algorithmic ideas were crucial to the success of the technique, which, against biologists' expectations, became the standard. The technique: extract many random sequences of the genome, of known fixed length, 2, 10, 50, 150 kb pairs. read 500-1000 nucleotides from opposite ends computationally assemble the genome. Myers came up with several tricks the do NOT work for arbitrary sequences, but take into account the domain. Had to use biological knowledge.
- Parametric Sequence Alignment. The Needleman-Wunsch algorithm (aka dynamic programming) gives best alignment of two sequences (DNA fragments) given scores for matching letters, mismatches, or matching a letter with a space (modeling insertions/deletions). What if these costs are not known? Clever algorithm by Pachter and Strumfels, using polytopes for this parametric problem
- Inferring Evolutionary History (Daskalakis, Mossel and Roch, STOC 06)
- Genetic Variation Zhihong Ding, Vladimir Filkov, Dan Gusfield: A Linear-Time Algorithm for the Perfect Phylogeny Haplotyping (PPH) Problem
- Regulation of Gene Expression (ran out of time)
Nguyen, Ong, Vadhan: Statistical zero-knowledge from any 1-way function. Omer Reingold liked this. I did too. They prove that 1-way functions (in some sense the weakest crypto assumption) is sufficient for giving a zero-knowledge proof—under new definitions. The usual one is that soundness is statistical (absolute) and zero-knowledge is computational (guaranteed only about polynomially bounded adversaries). This paper inverts the roles, answering a question proposed in 1992. The proof technique is new.
Assaf Naor presented two difficult and impressive results, showing that problems of embedding one metric space in another have a deep mathematical background, and interesting CS applications. The papers have difficult proofs that may well be worth studying.
Santosh Vempala presented a great result (with Laci Lovasz) showing how sampling log-concave functions is related to optimization problems.
I found the results on derandomization, and hardness amplification quite interesting (section 4B) and was convinced of the virtues of smoothed analysis (concurrent section 4A). Ryan O'Donnell gave a beautiful presentation of new nonapproxability results in session 5A, and I learned that honest majority is easier in a quantum setting in session 5B.
Highlights of the business meeting:
Machtey Award for Best Student Paper: Nicholas J. A. Harvey for Algebraic Structures and Algorithms for Matching and Matroid Problems.
Stats: 243 submissions, 71 accepted (~30%), ~220 attendees.
SODA 387/139 36%
ESA 215/55 26%
STOC 280/78 27%
CCC 85/28 32%
STOC 07 will be at FCRC in San Diego. Hotel will cost 129/139 single/double. Dates are June 11-13 for STOC, June 8-16 for FCRC.
FOCS 07 will be in Providence, RI. Program chair is Alistair Sinclair. Location is the new Renaissance Hotel, currently under construction.
FOCS 08 will be in Philadelphia.
Our community received a number of prizes, previously reported here: Jon Kleinberg, Nevanlinna Prize, Danzig Prize to Eva Tardos, and co-winners of the Fulkerson Prize: Manindra Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P", Annals of Mathematics, Volume 160, issue 2, 2004, Pages 781--793. and Mark Jerrum, Alistair Sinclair and Eric Vigoda, "A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries", J. ACM, Volume 51, Issue 4, 2004, Pages 671--697. Neil Robertson and Paul D. Seymour, "Graph Minors. XX. Wagner's conjecture", Journal of Combinatorial Theory, Series B, Volume 92, Issue 2 , 2004, Pages 325--357. (not really TCS, but we'll claim it!)
There was a new proposal by Umesh Vazirani: let us have no paper proceedings. Instead, let the papers be submitted (perhaps as little as one week before the conference) to a website. This would allow postponing submissions by perhaps 2 months, and would get extra benefits (cheaper registration, text searchable, available everywhere.
A lively discussion ensued. The economics of the proposal are unclear: would it decrease attendance? Should we worry about the economics? Some people like having the paper version at the conference. Making the "electronic proceedings" have page numbers, formatting, etc. would still imply text processing and editing. On the other hand, an electronic version would have substantial advantages. Would IEEE let us do it? What about libraries who paid for the proceedings?
It was pointed out that the IEEE electronic library is unreasonably expensive, and many institutions do not have it. A quick vote was taken, and results were inconclusive. Many wanted a CD with the proceedings. About an equal number of people wanted proceedings with CD as no proceedings and electronic versions only.
Our leaders promised to study the matter.
Finally the NSF report. Bill Steiger is going back to academia, in August. He was warmly thanked for his efforts for the community. I will give a detailed report tomorrow.