Monday, May 17, 2004

Randomized Blogspace

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."


  1. Rocco neglected to mention the cryptic yet stylish "Theory Lions" tee-shirts made available to all attendees.

    What's the backstory on these shirts?

  2. The lion is the mascot of Columbia University

  3. It basically turned out to be a debate about the success of theory, in a crowd of theoreticians. No surprise, everyone thought theory was doing pretty well.

    Karp is not an aggressive or argumentative person. Many outsiders would argue better that the achievements of theory are not very significant and not very relevent, especially considering the amount of time and effort put into them.

  4. That theory has had no significant results is
    an extreme view - one could debate theory's
    impact on practical computer science but in
    terms of significant results there are many
    fantastic achievements that any scientific
    discipline would be proud of.

  5. I am still a student with very strong interest in theoretical computer science. I do have to admit I have a hard time convincing people getting into theory is not a bad choice. I get the same arguments over and over ("nobody is asking for a solution to ... =?= ...") and even other computer scientists seems to question the relevance of theoretical work. How do professional scientist handle these comments?

  6. Answer to the students who asked:
    "how professional scientists handling it?"
    They form mutual admiration societies that collectively
    ignore the issues.

  7. Who do most people do mathematics? Not because they think it is eminently practical but because there is beauty in it that that draws them into it and won't
    let go. Same with some theory. For the student who
    asked as to why one does theory - mainly because it
    strikes you as interesting and beautiful. Relevance
    is nice but not necessary for doing something. Whether one should get paid for it is a different matter.

  8. Before the embittered and hostile taint our online mutual admiration society, let me respond to some criticisms that seem to be coming up on this thread:

    1. Almost all work done in a computer science or computer engineering department is "theoretical work". Even though they have more grant money slushing around and gads of relatively easy to land tenure slots, all those systems, database, VLSI CAD and architecture people are still writing a bunch of papers that few people read (just like us, and all other academics). Relatively few of their works make an impact on practice.
    Case in point: I know a guy who does the university outreach for a major chip manufacturer. He tries to bring innovations from university research to their product. Now, some of the embittered ex-theoreticians out there might think "those academics doing architecture/VLSI CAD are really doing practical work, sure beats tweaking gadgets in PCPs", but this guy gets nothing but derision for his efforts. His peers say "It's all theoretical, it will go nowhere. Think of your career and stop this outreach nonsense".

    2. We (the TCS community) are the ones who are being honest about what we do. We say it's theoretical, and we mean it.

    3. Ultimately (good) TCS is doing what a good theory should do: addressing what is possible with computation, and developing a framework to explain it all. Maybe the going is a little slow for some who wanted to prove P != NP years ago, but, hey, that's just how it goes.

  9. These criticisms are exactly what the Kanellakis prize was founded to handle. It's given every year to a result in theoretical computer science that has had a significant impact on practitioners. Of course, this leaves open the criticism that all of these theorists are only producing one practical accomplishment each year, but I would like to think that the Kanellakis prize results aren't the only ones that have had an impact (although I must admit that there are vast numbers of papers that will only be looked at by theorists, and a significant number that will never be looked at by anybody).

    By the way, it was Prabharkar Raghavan who commented that practitioners consider all areas of university computer science departments, and not just theory, as "academic research."

    Peter Shor