Summary | Rationale | Powerpoint | JPG Slide | JPG Image | Credits | Comments | All Nuggets
Theoretical computer science has led the practical and technological development of the field since Turing conceived of a general purpose computer and its power and limits long before it existed. While far more diverse today, and serving numerous technologies and applications, TCS must stay united to flourish and be even more useful to the field.
Why should there be a theory of CS division at NSF? One can easily make the argument that CS has many research areas, each of which with a spectrum between theory and practice, and the division should according to these, with each area having a "practical" and "theoretical" component. Thus distributed computing should have its separate theory component, security/cryptography should have their, and so with quantum computing, programming languages, optimization, graphics, etc. etc. This viewpoint may allow for a small complexity theory program, whose practical value is doubtful, but seems to serve some higher purpose.
This viewpoint misses a central insight and huge opportunity -- the remarkable unity of theoretical computer science. The culture and tradition of studying the power and limits of different computational models has created an extremely elastic language, fit to describe and analyze an ever increasing number of diverse technologies and applications. Indeed, TCS does have many subgroups of different interests, but these communicate and collaborate freely due to that language. And much more -- ideas created in one often migrate to another, seemingly remote one, for dramatic effect and progress. There are many examples, but two will suffice here.
One is the notion of "superconcentrator", developed in the 70s by Valiant to prove lower bounds on circuit size. 25 years later it inspired Spielman to give the first error-correcting codes of optimal parameters of rate and distance, with optimal (linear time) encoding and decoding procedures -- a central problem of the field left open by Shannon 50 years earlier.
Another is the evolution of ideas between many subdisciplines, starting with cryptography and interactive and zero-knowledge proofs, in which removal of assumptions introduced multi-prover systems, in which program-testing ideas of random self-reducibility brought computational complexity to create proof verification in constant time, which impacted optimization by providing the first general method to prove intractability of approximation.
These migration of ideas between subcommunities needed the interaction and collaboration of theorists of all types, successfully facilitated in particular by the field's leading conferences, FOCS and STOC.
References - two talks Avi gave on related issues
http://www.math.ias.edu/~avi/TALKS/STOC04.ppt
http://www.math.ias.edu/media/FCRC.ppt
Put a slightly more detailed explanation here, which can be aimed at a general computer scientists.
Avi Wigderson
List ideas for possible images. You can also upload images you've found using a command like this Δ.
