Janos Simon continues his reports from Berkeley.
Dick Karp gave a 1hour 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 nontheory folks in CS.
Highlights:

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.
Examples:
 Biology: cell process regulation.
 Learning: (in humans, animals) paradigms, models and algorithms from Computational Learning Theory
 Molecular selfassembly
 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.
Karp also gave examples of where convergence between CS and other
areas benefited both disciplines including
Belief propagation, error correcting codes and constraint satisfaction.
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 5001000 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 NeedlemanWunsch 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 LinearTime Algorithm
for the Perfect Phylogeny Haplotyping (PPH) Problem
 Regulation of Gene Expression
(ran out of time)
Some other interesting talks I heard:
Nguyen, Ong, Vadhan: Statistical zeroknowledge from any 1way
function. Omer Reingold liked this. I did too. They prove that 1way
functions (in some sense the weakest crypto assumption) is sufficient
for giving a zeroknowledge proof—under new definitions. The usual
one is that soundness is statistical (absolute) and zeroknowledge 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 logconcave 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.
By comparison
SODA 387/139 36%
ESA 215/55 26%
STOC 280/78 27%
CCC 85/28 32%
Deadlines: CCC
Dec 3, program Chair Peter Bro Miltersen,
STOC Nov 20 (no joint submissions to CCC)
STOC 07 will be at FCRC in San
Diego. Hotel will cost 129/139 single/double.
Dates are June 1113 for STOC, June 816 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
cowinners of the Fulkerson
Prize:
Manindra
Agrawal, Neeraj Kayal and Nitin Saxena, "PRIMES is in P",
Annals of Mathematics, Volume 160, issue 2, 2004, Pages 781793. and
Mark Jerrum, Alistair Sinclair and Eric Vigoda, "A
polynomialtime approximation algorithm for the permanent of a matrix
with nonnegative entries", J. ACM, Volume 51, Issue 4, 2004,
Pages 671697. Neil Robertson and Paul D. Seymour, "Graph
Minors. XX. Wagner's conjecture", Journal of Combinatorial
Theory, Series B, Volume 92, Issue 2 , 2004, Pages 325357. (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.