*A report from Theory Day co-organizer Rocco Servedio*
On Friday May 14 a special Columbia/IBM Research/NYU
Theory Day was held
at Columbia University in New York City. The New York area theory days
started at Columbia in 1982; this one was a special event to mark both the
25th anniversary of the CS department at Columbia and the 250th
anniversary of Columbia University.

More than 280 attendees came out to hear four talks by outstanding
theorists:

- Richard Karp (UC Berkeley):
*Current Challenges in
Computational Genomics: Haplotyping*
- Shafi Goldwasser (MIT/Weizmann):
*Proving Hard-Core
Predicates using List Decoding*
- Prabhakar Raghavan (Verity/Stanford):
*Finding Information in
Networks*
- Peter Shor (MIT):
*Quantum error correction and fault tolerant
quantum computation*

The day ended with a panel discussion on "The Future of CS
Theory." Avi
Wigderson (IAS) joined the four speakers for the panel, which was
moderated by Mihalis Yannakakis (Columbia). Here is a brief summary of
what was said.

Mihalis started things off by observing that over the past 50 years CS
theory has enjoyed outstanding successes and has had tremendous impact on
computing. Indeed, some of the successes were so profound that they gave
rise to whole new fields of computer science (databases, security) that
are no longer thought of as "CS theory". Mihalis asked each of the
panelists to briefly give their views on the future of CS theory. Some
highlights of what they said:

Avi observed that CS theory can (and should) have more impact
on early education, starting in high school or even earlier. We can give
important insights into fundamental ideas such as adversaries, randomness,
learning, recursion, games, proofs, and "getting things done
efficiently"
(which Avi referred to as "the oldest profession in the
world"). He also
highlighted some specific goals for CS theory at this point, which
included showing that BPP ≠ NEXP; coming up with non-natural proof
techniques for circuit lower bounds; discovering new types of quantum
algorithms; developing a general theory of what types of algorithms can
give optimal approximation ratios; and proving that SL = L and that
MATCHING is in NC.

Dick Karp warned against taking anyone's advice or predictions too
seriously. That said, he advocated for a healthy balance between
foundational questions at the core of CS theory and new questions that
arise from the role of computation in the world and the sciences. He
highlighted three areas of interest for the future: (1) the study of
large scale distributed systems such as the Web, incorporating ideas from
economics and game theory; (2) connections with areas of natural science,
ranging from statistical physics to quantum mechanics to biology; and (3)
the "new face" of AI in which stochastic and graphical models and
statistical inference are playing a big role.

Peter also commented on the perils of predicting the future; we
sometimes tend to think that there will be no more revolutionary ideas
simply because we don't know what those ideas will be. But such ideas
will come along from "out of the blue" as they always have.
He noted that
while past predictions for the future of CS theory have tended to be on
the doom and gloom side, things have actually turned out pretty well --
there are interesting jobs and demand for theorists in industry; theory is
more and more noticed and used by practitioners; and rather than becoming
increasingly recondite and inward-looking, theory is building stronger
connections with mathematics, physics, and other disciplines.

Prabhakar observed that what we think of as CS theory is really
two main thrusts of work with some overlap: there is the theory of
computation as an inherent phenomenon (i.e. when we study MOD 17 gates and
what they can do even though nobody will ever build one), and the theory
of computation as it is practiced (i.e. most of the world's cycles are
spent making a billion people happy rather than crunching data for a few
thousand scientists). The Web is a paradigmatic aspect of the second
thrust; he noted that in this area economic factors may play a role at
least as important as traditional resource bounds like time and space.
Prabhakar also stressed the importance of backing up claims of practical
relevance for our work (and, on an unrelated note, mentioned this weblog
in a slide entitled "Randomized Blogspace".)

Shafi observed that CS theory is having an increasing impact on
classical mathematics such as coding theory, number theory, and signal
processing. On the other hand, we are also dedicating more energy (and
having more success) in solving problems in the real world -- both of
these trends are good signs for the field. She advised researchers to
follow their own tastes and interests rather than anyone else's
recommendations when it comes to "the next big challenge for the
field."

After these statements the floor opened up to questions and discussion
with the audience. A brief summary:

One questioner noted that the theoretical models of parallelism
from 20 years ago don't correspond to how large distributed systems work
now, and asked whether a similar phenomenon could be taking place with
quantum computation -- are we studying the right model? Some panelists
responded that while we aren't likely to end up with quantum computers
that correspond exactly to quantum circuits, it seems likely that
algorithms developed for the quantum circuit model will prove useful
if/when we do get quantum computers in one form or another.

There was quite a bit of discussion about the role of CS theory
in the undergraduate curriculum and what undergraduate CS majors should
know about theory. Some panelists opined that NP-completeness,
undecidability, models of computation, and algorithms are core topics that
even high school students perhaps should know. A view emerged that there
is real (potential) widespread interest out there in the "gems" of CS
theory, and that we should do a better job of explaining what is
fascinating and beautiful about our field to students.

In response to a question about the future status of the P=NP
question, some panelists observed that other great research communities
(mathematics, physics) have tussled with unsolved questions for centuries.
We seem to be stuck right now, but on the bright side we have some
understanding (natural proofs, for instance) of why we are stuck --
perhaps mathematicians should step back and think about why the Riemann
hypothesis is still unresolved.

To close, here are three quotes lifted more or less verbatim from the
panel discussion (but left anonymous here):

- "The future for DNA computation is dim" (in response to the
question "What is the future for DNA computation?")
- "Polynomial time computation is a complex object to understand."
- "We are so much closer to understanding each other's talks than
the mathematicians are."