ICM 2014

I’m currently in Seoul for the 2014 ICM, where I’ll be giving a talk on — what else? — analysis of Boolean functions. I’ve written an accompanying article for the proceedings, Social choice, computational complexity, Gaussian geometry, and Boolean functions, the abstract of which follows:

We describe a web of connections between the following topics: the mathematical theory of voting and social choice; the computational complexity of the Maximum Cut problem; the Gaussian Isoperimetric Inequality and Borell’s generalization thereof; the Hypercontractive Inequality of Bonami; and, the analysis of Boolean functions. A major theme is the technique of reducing inequalities about Gaussian functions to inequalities about Boolean functions $f : \{-1,1\}^n \to \{-1,1\}$, and then using induction on $n$ to further reduce to inequalities about functions $f : \{-1,1\} \to \{-1,1\}$. We especially highlight De, Mossel, and Neeman’s recent use of this technique to prove the Majority Is Stablest Theorem and Borell’s Isoperimetric Inequality simultaneously.

The article actually includes a few ideas that don’t explicitly appear in the book, so please take a look if you’re interested. I hope the article will make a nice fit for the congress; it has a few connections (some major, some minor) with work being discussed by several other speakers here, including Boaz Barak, Andrei Bulatov, Sourav Chatterjee, Julia Chuzhoy, Alessio Figalli, Monique Laurent, Michel Ledoux, and (last but certainly not least) our newest Nevanlinna Prize winner, Subhash Khot. (Congratulations Subhash!) Indeed, my talk on Saturday will mostly center around a very famous conjecture made by Subhash — I refer, of course, to the Majority Is Stablest Conjecture. :)

PS: In case you happen to actually be at the congress, you can buy a “special ICM edition” of the book for $30 (or, even cheaper, ₩30,000) at the Cambridge University Press booth.

4 comments to ICM 2014

  • vzn

    congratulations on attending & the talk & your new book published! have already seen it cited elsewhere eg other blog(s). re ICM 2014, see also Fields medal/Nevanlinna prize 2014 with many more links on the awards incl many on unique games conjecture… curious, do you have any blogs on UGC? does it have any connections to boolean fns analysis?

    • Thanks! Unique Games is discussed somewhat in Chapter 7 of the book (see especially the exercises towards the end). There are many connections between UGC and analysis of Boolean functions, it seems; here are just a couple out of many choices:

      http://arxiv.org/pdf/1305.4581v1.pdf in which Khot and Vishnoi disprove the “Goemans–Linial Conjecture” on embeddability of metric spaces; they do it by constructing a kind of SDP integrality gap for Unique Games (relying heavily on AOBF), and then using another AOBF-based reduction. As one of Subhash’s most amazing (co-)works, I’m not sure why this paper didn’t get more press at ICM…

      http://arxiv.org/pdf/1405.1374v1.pdf A very recent paper by Agarwal–Kindler–Kolla–Trevisan in which they observe that the discrete hypercube appears to be the hardest known underlying graph for the Unique Games problem, give some limited evidence for hardness in this case, but also conjecture an easiness result.

  • Ben Green

    I got my special ICM edition and enjoyed browsing it on the flight home.

Leave a Reply

  

  

  

You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>