Derandomization in functional analysis

Thursday evening there is a party at the American Embassy. The invitation, mysteriously, requires "cocktail attire." The clothes that people wear in San Francisco while drinking cocktails in bars do not seem appropriate for an Embassy, so I have to search on google what this means. (Men have to wear jacket and tie.) Ronitt Rubinfeld isn't here yet, Avi Wigderson has a strict no-jacket policy, and so at the party I recognize less than a handful of people. After entering, there is a receiving line. A mathematician from UC San Diego (who, I believe, was one of the organizers of the party) meets the guests first; then he introduces each guest to a jovial fellow whom I assume to be the Ambassador (he is, instead, a government official, something like the science advisor to the Secretary of State). Finally, a woman says "welcome to the United States embassy." It's my turn. Hello, I say to the mathematician, I am Luca Trevisan from U.C. Berkeley. Oh, he says, you are a graduate student. Once we are inside, the three of them give one short speech each. The woman regrets to inform us that the Ambassador had to be somewhere else in Spain and so he could not be with us. He is hiding in the next room, is my comment. He is on vacation, someone else says.

On Friday, Jon Kleinberg gives his plenary talk. He frames his work by considering two ways of viewing computers (and hence, computer science, and hence theoretical computer science). One is that we have inputs, on which we have a computation that gives an output, and we are interested in the efficiency of computation. This would be the design of algorithms and many of the problems studied in computational complexity. In the other view, computers are "mediators" between people, and they are the means of interactions that happen in various forms (emails, electronic markets, blogs,...).

Studying the information exchanges of the second type one is led to study networks, and an important point is that such networks are not artifacts that have been designed; they are phenomena that happen. After giving some concrete examples, he focuses on his results on "small world" networks.

After the break, I go to see Emmanuel Candes's talk on "compressive sampling sensing." Here the idea, not unlike Goldreich-Levin (or Kushilevitz-Mansour) is that we want to reconstruct the Fourier coefficients of a function f:{1,...,N} -> R by looking at only at a small number of values of f, under the promise that only a bounded number of Fourier coefficients of f are non-zero. It turns out that, if k Fourier coefficients are non-zero, it is sufficient to read f at O(klog N) random points and then find the function that, subject to having those values at those points, has the smallest possible l₁ spectral norm. Such minimization can be found in time poly(N) using linear programming. Similar ideas also lead to LP-based algorithms for error-correcting codes. Amusingly, compressive sampling sensing is commonly abbreviated CS, and one slide reads

CS: a new paradigm for analog to digital.

Then, Avi takes me to a lecture by Stanislaw Szarek on geometric functional analysis. The beginning of the lecture, devoted to putting the problems in context is too abstract for me to follow. But then come the concrete problems. Surprisingly (to me) the probabilistic method is used routinely in functional analysis, and, in finite dimensional cases, they are interested in explicit constructions. As partial results, they are interested in constructionts that use few random bits, and one results that is mentioned involves random walks on expander graphs. Some of the derandomization open questions that he discusses have applications in compressive sampling sensing, the area earlier described by Candes.

A one in four chance

Stephen Colbert complains he did not receive the Fields Medal even though he refuted the Poincare conjecture. (via Lance Fortnow.) Ze Frank had done it before but his treatment was judged incomplete.

Pseudorandomness and more pseudorandomness

The first talk of the morning is by Terry Tao. Tim Gowers, in his essay The Two Cultures of Mathematics explains the difference between depth and generality in combinatorics versus other areas of pure math. In combinatorics, one is unlikely to find deep definitions (have you ever tried to understand the statements of the conjectures in the Langlands program?) and very general theorems. In combinatorics, it is more usual to find generality in the form of principles that the practictioners of the subject are aware of and that are exemplified in the proofs of certain theorems. (I hope I have not distorted and oversimplified Gowers's point too much.)

Tao's talk very explicitly points out the principle that emerges from his work on arithmetic progressions. The idea is that one can often define notions of pseudorandomness and structure such that one has a theorem of the following kind:

• Dichotomy: if an object is not pseudorandom, then it has large stuctured component.
  

For example, in the setting of looking for arithmetic progressions of length 3, a subset of {1,...,N} is "structured" if it has a large Fourier coefficient and it is pseudorandom if it has approximately the same number of length-3 progressions of a random subset of {1,...,N} with the same density.

By iterative arguments, one then has theorems of the form

• Decomposition: every object can be written as a "sum" of a pseudorandom part and a structured part
  

This is very important in the proof of the Green-Tao theorem on arithmetic progressions in the primes, but it can be seen, implicitly, in the Szemeredi regularity Lemma and in all proofs of Szemeredi's theorem.

The proof typically goes by: if our object is pseudorandom, we are done; otherwise we find a large structured "piece." We "subtract" it. If what remains is pseudorandom, we are fine, otherwise we subtract another structured part, and so on.

The advantage of this type of decomposition (whether it is done explicitely or it is implicit in the proof) is that one can use techniques from analysis and probability to analyse the pseudorandom part and (depending on the definition of "structure") techniques from analysis and geometry to analyse the structured part. This is how the proof of the Green-Tao theorem ends up using analysis, ergodic theory, combinatorics, and so on.

Often, one can use geometry and algebra only provided that the object is "exactly" structured, while results of the above type may only give "approximate" structure. To bridge this gap one employs results of the type:

• Rigidity: an object that is "approximately structured" is "close" to an object that is structured
  

These are results in the spirit of property testing. (And he mentions property testing in his talk.)

This is all quite abstract, but reading papers in the area (or approaching new problems) with this point of view in mind is very helpful. He also proceeds to summarize the proof of the Green-Tao theorem in terms of the above perspective.

By the way, earlier in the talk, about the general importance of understanding pseudorandomness, Tao talks mentions expander graphs and the P versus BPP question. (As a context, not as specific problems that he is going to work on. For the time being, we are safe.)

Overall, the talk is a model of clarity and insight.

After the break, Avi Wigderson gives his talk on P, NP and Mathematics. Yesterday, Avi told me that, of all the material that he cover in his 50-page proceedings paper, he had decided to talk about pseudorandomness and derandomization, from the perspective that randomness seems to help in computation, but complexity theory suggests that it does not. I despaired, because this is exactly my talk, but luckily Avi's talk has a somewhate complementary emphasis on topics. (So I won't have to spend the next two days remaking my slides and I can go see the Prado tomorrow.)

Avi explains the "hardness versus randomness" principle in terms that could not be clearer, and one can see heads nodding as he goes along (nodding in agreement, not nodding off). He ends up with the following question about the complexity of the permanent: is there a linear transformation L of nXn matrices into kXk matrices such that, (i) for every matrix M, the determinant of L(M) equals the permanent of M and (ii) k is only polynomial in n? (The answer is supposed to be NO.) From known results one can derive that k need not be more than exp(O(n)) and a Omega(n²) lower bound is also known.

This is to say that one can work on complexity theory without having to learn about such things as algorithms, Turing machines and so on, and that purely algebraic questions are completely open and very related to complexity questions.

Laudationes

After a lunch-time "reception" (the less said, the better), the first afternoon session is dedicated to the laudationes. An expert in the area speaks on the work of each Field Medalist and of Jon Kleinberg.

First, a mathematician from ETH Zurich (who is, however, Italian) speaks on the work of Andrei Okounkov. He studies "partitions," which, in the simplest case, are ways of writing an integer as the sum of a non-decreasing sequence of integers. Partitions are related to the representation theory of the symmetric group, and apply in a variety of problems that were too technical for me to follow.

John Lott spoke on Perelman's work. Lott is part of one of the three teams that have been working out complete expositions of Perelman's work. His talk is extremely clear. The Poincare conjecture states that

every 3-dimensional manifold that is simply connected and compact is diffeomorphic to the boundary of a sphere ball in R⁴.

Where "simply connected" means that a simple loop can always be shrunk to a point via a continous transformation. "Diffeomorphic" means, probably, "equivalent under the appropriate type of nice continuous transformations." The lower dimensional analog is that any surface with "no holes" can be "stretched" into the surface of a sphere ball. Even though this is a purely topological problem (the assumption is a topological property and the conclusion is a topological property), the big idea was to use methods from analysis. Specifically, Hamilton suggested in the 80s to consider a physics-inspired continuous transformation (the "Ricci flow") on the manifold until it "rounds up" and becomes a sphere. (The continous transformation maps the starting manifold into a "diffeomorphic" one.) Unfortunately, the process produces singularities, and Hamilton had found ways to remove them in certain nicely-behaved special case. Perlman's work shows how to always remove such singularities. This was a major tour de force. Before Perelman's work, apparently, the experts in the area considered the known obstacles to eliminating singularities in all cases to be almost insurmountable, and did not consider Hamilton's program to be too promising. Hamilton said that he was "as surprised as anybody else" by the fact that Perelman made the Ricci flow approach work.

Next, Fefferman delivers the laudatio for Tao. It is a daunting task given the variety of areas that Tao has worked on. Fefferman choses to talk about the Kakeya problem, about non-linear Schrodinger equations and about arithmetic progressions in the primes. By the way, both his work on the Kakeya problem and the work about arithmetic progressions (though not the work on the primes in particular) have applications in theoretical computer science.

The laudatio for Werner is a complete disaster. The speaker reads from a prepared speech, and the big screen (that, for the previous speakers, had shown slides of the presentation) shows the text of the speech. This doesn't do justice to Werner's work on proving rigorous results in statistical physics which were previously derived via non-rigorous methods. His work includes problems of the type that computer scientists work on. In his interview, Werner says that he feels he shares the medal with Oded Schramm and Greg Lawler. Oded Schramm, in particular, was a leading figure in this line of work, but he was already over the age limit in 2002, and this work was done after 1998, so he could never be considered for the award.

John Hopcroft delivers the laudatio for Jon Kleinberg. He emphasizes five results: the hubs-authority idea for web search ranking, his work on small-world models and algorithms, the work on ``bursts'' in data, the work on nearest neighbor data structures and the work on collaborative filtering. Like Fefferman, Hopcroft runs out of time.

In the late afternoon (this is a LONG day), Hamilton gives a plenary talk on his work on the Poincare conjecture. Despit Lott's nice earlier introduction, I get rapidly lost in what seems a series of unrelated technical statements. Avi seems to follow. "No, no, they are not unrelated, he is building up an exposition of the proof by explaining all the problems and how they are overcome." He starts late because of projector problems, and he runs enormously out of time. At one point the session chair timidly stands up, not quite sure what to do, then walks towards the podium, then walks back, apparently with Hamilton not noticing. Where is Johan Hastad when you need him?

Congratulations, Jon!

There is a long line to enter the conference center this morning. Only at the end, I realize that invited speakers (but of course!) can skip the line and stride in. The line is because of security checks. Everybody passes through a metal detector, and bags are checked. So much security for a math conference? (Later we understand why.)

We start with a string trio (guitar, violin and cello) playing live. The sound of the violin is butchered by the sound system. Then the VIPs come on stage. Chairing the award cerimony is His Majesty Juan Carlos I, King of Spain. This is not going to be like a STOC business meeting. The King is accompanied by a person in a white military uniform with lots of stripes on his shoulders. The King sits in the middle of a table on stage, flanked by congress organizers and Spanish politicians. (The minister of Research and the mayor of Madrid.) The guy with the white uniform takes a seat behind the King. Then, one by one, everybody gets up and gives a speech.

John Ball starts his speech by explaining how mathematicians talk about their work freely, without fear that their work will be stolen, and how work is appreciated solely based on its merits, not on the way it is promoted. This is how the vast majority of mathematicians work, he continues, and exceptions are rare, and noted. It might be a reference to some of the recent events around the proof of the Poincare conjecture.

The mayor of Madrid starts what seems like a canned speech that he always gives at scientific/ technological events. Towards the end, however, he talks quite eloquently about the virtues of mathematics, its ability to make sense of a complex world, its commitment to truth, its trascendence of religion, race, and so on. Finally, he says, it is not just mathematicians that have to make an effort to come closer to the everyman and to explain the practical applications of mathematics. It is everybody's civic duty to learn more about math and science. (He said it better.)

Griffiths starts by saying "One of the main activities of the IMU [the International Mathematical Union] in the last few years has been the selection of a new logo." Hilarity ensues in the audience. (He seemingly did not mean it as a joke.) A documentary on the new logo is played.

More and more people talk, and at long last we come to the award of the Fields Medals. As expected, Terry Tao and Grisha Perelman receive the award, plus two other mathematicians that work in areas that I am not familiar with.

Perelman, is announced, has declined the Fields Medal. Someone from the back claps.

The Nevanlinna prize goes to Jon Kleinberg. This is definitely the computer science award with the most distinguished record, and I want to congratulate the committee for, once more, making an excellent choice. Congratulations to Jon too, of course.

Hey, you look like a mathematician!

ICM is held in a fairly remote conference center near the airport. The organizers had the good sense of not recommending the hotels next to the conference center but rather a number of hotels midway between there and the city center, so one can get to the conference with a short subway ride and also not be in the middle of nowhere. The recommended hotels, however, were still quite out of the way, and, by the information I found online, they sounded big and anonymous. So I got a reservation in a nice smaller hotel that is not far from Plaza Real and other touristic attractions, and it is also in what seems one of the cool neighborhoods, with a lot of bars and restaurants, including many gay bars. It takes, unfortunately, a good 45 minutes by subway to reach the conference center.

So this afternoon, as I was checking in at the hotel, being very proud of my choice, wearing an A&F shirt, faded jeans and Kenneth Cole shoes, and feeling as non-nerdy as I can get, the person behind me in line waves hello and asks: "Are you here for ICM too?"

Madrid is full of mathematicians

I have just arrived in Madrid for the International Congress of Mathematicians. Held every four years for more than a century, it features a number of plenary talks (Avi Wigderson will talk about P versus NP and computational complexity) and a number of talks in parallel sections devoted to specific topics (one of the parallel sections is on computer science).

Being used to the small scale, and the biannual frequency, of STOC and FOCS, it's hard to adjust to the size and the self-importance here. Tomorrow, for example, we start with an opening cerimony. Four years ago, in Beijing, the opening cerimony was held in the Great Hall of the People, and President Jiang Zemin attended. That's like having the conference in Washington D.C. and holding the opening cerimony in the Capitol, with George Bush coming to give a speech and congratulate the new Field Medalists. One can almost imagine the speech, ``I want to congratulate these good people, because God made them do good work, and we appreciate their good work. September 11 changed everything, so we must stay the course, just like they stayed their course when doing their good work.''

If I understand the program correctly, the Field Medals and the Nevanlinna Price will be announced during the opening cerimony. As part of taking itself very seriously, it is a tradition of the conference that the identities of the recipients are kept secret until then. When I registered, for example, I received a big bag with two huge and heavy books, which are the proceedings. (There are a lot of talks, and for each talk there is a paper of up to 25 pages.) It turns out that those two books, however (each heavier than a FOCS/STOC proceedings), are just Volume II and Volume III of the proceedings. Volume I is distributed later, because it contains articles about the prize winners (plus all the articles of the plenary speakers; Volume II and III contain the articles of the parallel sections).

Since the conference is held only once every four years, and Mathematics is a really vast subject, with thousands of researchers, there is a big fuss made over who gives the invited talks.

At the registration desk, invited speakers have a separate line. At the opening cerimony, the best seats are for press, IMU functionaries and ''authorities'' (that's what it says in the program), then there are very good seats for the speakers who give plenary talks, then seats in the back for the speakers who talk in the parallel sessions, and then, well behind, are all the others. And in uncharacteristic (for the US government) official show of support for the sciences, the American Embassy in Spain is holding a party for the American invited speakers.

Given what is at stake (I mean, who wouldn't want to stand in shorter lines, to see the opening cerimony up close, and to meet a US Ambassador?), the program committee that makes the invitations is kept secret, to protect the committee members from too much external pressure. I wonder how this ``double blind'' system would work at STOC and FOCS: the program committee invites speakers without knowing what paper they will present, and nobody knows who is on the program committee.

The big story of this conference will probably be the official announcement that Perelman's proof of the Poincare conjecture has been verified. The story has a fascinating human element, from the excentricity of Perelman to the rush of various teams to complete the verification, and it has already been the subject, last week, of a beautiful New York Times article by Dennis Overbye. In this week's New Yorker there is another article by Sylvia Nasar, of Beautiful Mind fame. More tomorrow on Perelman, on whether, as expected, he will be awarded the Fields Medal, and whether, as expected, he will fail to show up.