Discovering the Cyber-Transformations

If memory serves me well, I have attended all STOC and FOCS conferences since STOC 1997 in El Paso, except STOC 2002 in Montreal (for visa problems), which should add up to 21 conferences. In most of those conferences I have also attended the "business meeting." This is a time when attendees convene after dinner, have beer, the local organizers talk about their local organization, the program committee chair talks about how they put the program together ("papers were submitted, then we reviewed them, finally we accepted some of those. Let me show you twenty slides of meaningless statistics about said papers"), organizers of future conferences talk about their ongoing organizing, David Johnson raises issues to be discussed, and so on. The SODA drinking game gives a good idea of what goes on.

A fixture of business meetings is also a presentation of the state of National Science Foundation (NSF) funding for theory in the US. In the first several conferences I attended, the NSF program director for theory would take the podium, show a series of incomprehensible slides, and go something like "there is no money; you should submit a lot of grant applications; I will reject all applications because there is no money, but low acceptance rates could bring us more money in future years; you should apply to non-theory programs, because there is no money in theory, but don't make it clear you are doing theory, otherwise they'll send your proposal to me, and I have no money. In conclusion, I have no money and we are all doomed."

Things hit rock bottom around 2004, when several issues (DARPA abandoning basic research, the end of the NSF ITR program, a general tightening of the NSF budget at a time of increased student tuition, a change in NSF accounting system requiring multi-year grants to be funded entirely from the budget of the year of the award, ....) conspired to create a disastrous funding season. At that point several people in the community, with Sanjeev Arora playing a leading role, realized that something had to be done to turn things around. A SIGACT committee was formed to understand what had gone wrong and how to repair it.

I don't know if it is an accurate way of putting it, but my understanding is that our community had done a very bad job in publicizing its results to a broader audience. Indeed I remember, in my job interviews, a conversation that went like "What do you do?" "Complexity theory" "Structural complexity or descriptive complexity?" "??". (I also got a "What complexity classes do you study?") And I understand that whenever people from the SIGACT committee went to talk to NSF higher-ups about theory, everybody was interested and the attitude was almost "why haven't you told us about this stuff before?"

For various reasons, it is easier at NSF to put funding into a new initiative than to increase funding of an existing one, and an idea that came up early on was to fund an initiative on "theory as a lens for the sciences," to explore work in economics, quantum mechanics, biology, statistical physics, etc., where the conceptual tools of theoretical computer science are useful to even phrase the right questions, as well as work towards their solution. This idea took on a life of its own, grew much more broad than initially envisioned (so that the lens thing is now a small part of it), received an appropriately cringe-inducing name, and is now the Cyber-Enabled Discovery and Innovation (CDI) program, that is soon accepting its first round of submissions.

Thanks to the work that Bill Steiger put in as program director in the last year and a half, and to the efforts of the SIGACT committee, the outlook for theory funding is now much optimistic.

At the FOCS 2007 business meeting last Monday, Bill talked about the increase in funding that happened under his watch, Sanjeev Arora talked about the work of the committee and the new funding opportunities (of which CDI is only one). In addition, as happened a few times in the last couple of years, Mike Foster from NSF gave his own, generally theory-friendly, presentation. Mike is a mid-level director at NSF (one or two levels above the theory program), and the regular presence of people in his position at STOC and FOCS is, I think, without precedent before 2005. (Or at least between 1997 and 2004.)

The NSF is relatively lean, efficient and competent for being a federal bureaucracy, but it is still a federal bureaucracy, with its quirks.

A few years ago, it started a much loathed requirement to explicitly state the "broader impact" of any proposed grant. I actually don't mind this requirement: it does not ask to talk about "applications," but rather of all the important research work that is not just establishing technical result. Disseminating results, for example, writing notes, expository work, and surveys and making them available, bringing research-level material to freshmen in a new format, doing outreach, doing something to increase representation of women and minority, and so on.

As reported by Sanjeev Arora in his presentation, however, NSF is now requiring to state how the research in a given proposal is "transformative." (I just got a spelling warning after typing it.) I am not sure this makes any sense. The person sitting next to me commented, "Oh no, the goal of my research is always to maintain the status quo."

The Next Viral Videos

Back in August, Boaz Barak and Moses Charikar organized a two-day course on additive combinatorics for computer scientists in Princeton. Boaz and Avi Wigderson spoke on sum-product theorems and their applications, and I spoke on techniques in the proofs of Szemeredi's theorem and their applications. As an Australian model might say, that's interesting!

Videos of the talks are now online. The quality of the audio and video is quite good, you'll have to decide for yourself on the quality of the lectures. The schedule of the event was grueling, and in my last two lectures (on Gowers uniformity and applications) I am not very lucid. In earlier lectures, however, I am merely sleep deprived -- I can be seen falling asleep in front of the board a few times. Boaz's and Avi's lectures, however, are flawless.

Best Tutorials Ever

FOCS 2007 started yesterday in Providence with a series of tutorials.

Terry Tao gave a talk similar to the one he gave in Madrid, discussing the duality between pseudorandomness and efficiency which is a way to give a unified view of techniques coming from analysis, combinatorics and ergodic theory.

In typical such results, one has a set $F$ of ``simple'' functions (for example linear, or low-degree polynomials, or, in conceivable complexity-theoretic applications, functions of low circuit complexity) and one wants to write an arbitrary function $g$ as

$ g(x) = g_{pr} (x) + g_{str} (x) + g_{err} (x) $

where $g_{pr}$ is pseudorandom with respect to the ``distinguishers'' in $F$, $g_{str}$ is a ``simple combination'' of functions from $\cal F$, and $g_{err}$ accounts for a possible small approximation error. There are a number of ways to instantiate this general template, as can be seen on the accompanying notes, and it is nice to see how even the Szemeredi regularity lemma can be fit into this template. (The ``functions'' are adjacency matrices of graphs, and the ``efficient'' functions are complete bipartite subgraphs.)

Dan Boneh spoke on pairing-based cryptography, an idea that has grown into a whole, rich, area, with specialized conferences and, according to Google Scholar, 1,200+ papers published so far. In this setting one has a group $G$ (for example points on an elliptic curve) such that there is a mapping $e: G X G \rightarrow G_T$ that takes pairs of elements of $G$ into an element of another group $G_T$ satisfying a bilinearity condition. (Such a mapping is a ``pairing,'' hence the name of the area.) Although such mapping can lead to attacks on the discrete log problem in $G$, if the mapping is chosen carefully one may still assume intractability of discrete log in $G$, and the pairing can be very useful in constructing cryptographic protocols and proving their security. In particular, one can get ``identity-based encryption,'' a type of public key cryptography where a user's public key can be her own name (or email address, or any deterministically chosen name), which in turn can be used as a primitive in other applications.

Dan Spielman spoke on spectral graph theory, focusing on results and problems that aren't quite studied enough by theoreticians. He showed some remarkable of example of graph drawings obtained by simply plotting a vertex $i$ to the point $(v(i),w(i))$, where $v$ and $w$ are the second largest and third largest eigenvalues of the laplacian of the adjacency matrix. The sparse cut promised by Cheeger inequality is, in such a drawing, just the cut given by a vertical line across the drawing, and there are nice algebraic explanations for why the drawing looks intuitively ``nice'' for many graphs but not for all. Spectral partitioning has been very successful for image segmentation problems, but it has some drawbacks and it would be nice to find theoretically justified algorithms that would do better.

Typically, I don't go to an Italian restaurant in the US unless I have been there before and liked it, a rule that runs into certain circularity problems. I was happy that yesterday I made an exception to go to Al Forno, which proved to be truly exceptional.