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(n2) 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.

10 thoughts on “Pseudorandomness and more pseudorandomness

  1. Do you know the reference for that quadratic lower bound on permanent-computing determinants? (It should be a recent thing.)

  2. Avi is the king of selling complexity to mathematicians.

    Besides permanent vs. determinant, he could’ve picked many other examples of “purely mathematical questions” that have enormous complexity implications:

    Show that more than polylog(n) additions, subtractions, and multiplications of previous numbers are needed to reach n! starting from 1.

    Find an explicit n-by-n invertible matrix over a finite field, for which more than c*n row operations are needed to convert it to the identity.

  3. Anonymous: I don’t know if the conference organizers are making slides available on the web. (The conference web site is a bit messy.)
    It is likely that Tao will post slides of his talk on his homepage after returning. Avi used mostly the slides from his talk “The power and weakness of randomness” which is available at

    Mahdi: Avi said that the result is due to an algebraic geometer but that the proof is very simple (and uses only elementary calculus) once you know what you are doing. I understand that the result is unpublished. (Possibly, unwritten.)

  4. Hello Luca Trevisan. I am at the ICM as well and am interested in meeting you here.

    Also I agree with everything said on this blog, but I can’t think much to add at the moment. Well, I might have mentioned Smirnov as well as Schramm and Lawler, but it is not my place to speak for Wendelin Werner.

  5. Hi Luca

    Interesting that Avi mentions permanent vs. determinant in his
    talk. Manindra seems to be intending
    to talk exactly on this problem in his talk … seemingly this links also to the Mulmuley-Sohoni work (geometric
    approach to distinguishing P from NP over the reals).

    Also, the link to the n^2 lower bound (that avi sent me some time back) is

    Enjoy Madrid. Will miss you at Banff.

    – Madhu

  6. But is the n^2 lower bound a “natural proof” in the sense of Razborov and Rudich?

  7. Dan Faith Roofing also offers Weather – Proofing Underlayment, EPDM Flat Roofing
    Membrane, and a Modified Ruberoid Torch Membrane. The waterproofing underlayment is an extra barrier against water leakage.
    New houses that need a nice roofing style or a basic renovation
    to provide your house a new roof that will perfectly suit with the entire structure of your
    apartment needs the services of a roofing contractor.

  8. Marketing is not about tricking people to want things as may have been in the past,
    the modern consumer, Internet-savvy companies actually invited into their lives to talk to them if
    they offer something relevant and useful to them, through the following on Twitter or “taste” of your Facebook page.
    There are numerous different types of internet marketing that you can take advantage of to get their
    name out there. Put an easy-to-area hyperlink to your privacy policy on every site in a apparent
    location above the best right corner of every page.

  9. However, when the person at the front of the line is swinging a bat, a different set of rules should apply.
    China manufacturers are open to the demands of multinational culture and they can regulate
    the manner in which they process orders and control management in accordance with global demand.
    The resulting innovations can have massive spillovers for a

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s