Analysis of Boolean Functions: New Directions and Applications: February 5-February 11, 2012

Play this video
Play list

The 2012 Analysis of Boolean Functions workshop focused mainly on application areas in theoretical computer science, including:

  • Hardness of approximation
  • Property testing
  • Pseudorandomness
  • Concrete complexity
  • Computational learning theory

The symposium included some traditional talks on recent results, but its aim was also to encourage research through a variety of talk/discussion formats: group exploration of new ideas, survey and area-introduction talks, and discussion of partial progress towards open problems.

Follow-up workshops are planned for 2014 and 2016, expanding the theme of discrete analysis to other areas of mathematics.



Per Austrin University of Toronto
Irit Dinur The Weizmann Institute of Science
David Ellis University of London
Parikshit Gopalan Microsoft Research
Johan Hastad KTH Royal Institute of Technology
Hamed Hatami McGill University
Gil Kalai Institute of Mathematics Hebrew University
Daniel Kane Harvard University
Tali Kaufman Massachusetts Institute of Technology
Guy Kindler The Hebrew University of Jerusalem
Shachar Lovett Institute for Advanced Study
Elchanan Mossel UC Berkeley
Jelani Nelson Massachusetts Institute of Technology
Ryan O’Donnell Carnegie Mellon University
Krzysztof Oleszkiewicz University of Warsaw
Oded Regev École Normale Supérieure
Alexander Samorodnitsky The Hebrew University of Jerusalem
Shubhangi Saraf Institute for Advanced Study
Rocco Servedio Columbia University
Madhu Sudan Massachusetts Institute of Technology
Luca Trevisan Stanford University
Avi Wigderson Institute for Advanced Study


Monday, February 6

  • Opening Remarks
  • Open problems session (organizer: Ryan O’Donnell)
  • Madhu Sudan
    Invariance in Property Testing
  • Avi Wigderson
    Matrix Scaling
  • Rocco Servedio
    Recent Results on Chow Parameters
  • Breakout Sessions / Research in Small Groups
  • Alex Samorodnitsky
    A Conjectural Isoperimetric-type Inequality for Functions on the Hamming Cube
  • Informal Discussions

Tuesday, February 7

  • Daniel Kane
    New Structure Theorems for Low-degree Polynomials of Rademachers
  • Per Austrin
    Adversarial Biasing of Boolean Functions
  • Luca Trevisan
    Higher-order Cheeger Inequalities
  • Krzysztof Oleszkiewicz
    Extensions of the FKN Theorem
  • Oded Regev
    Noncommutative Grothendieck Inequalities
  • Breakout Sessions / Research in Small Groups
  • Irit Dinur
    Coloring and Covering PCPs
  • Informal Discussions

Wednesday, February 8

  • Hamed Hatami
    A structure Theorem for Boolean Functions with Small Total Influences
  • Elchanan Mossel
    Geometric Influences
  • Shachar Lovett
    Probabilistic Existence of Rigid Combinatorial Objects
  • Informal Discussions

Thursday, February 9

  • Tali Kaufmann
    Locally Testable Codes and Expanders
  • Parikshit Gopalan
    The Short Code
  • Open Problem Session II
  • Guy Kindler
    Gaussian Noise Sensitivity
  • Breakout Sessions / Research in Small Groups
  • David Ellis
    Triangle Intersecting Families of Graphs
  • Informal Discussions

Friday, February 10

  • Jelani Nelson
    Applications of FT-mollification
  • Johan Håstad
    Ideas for Improved NP-hardness of 2CSPs
  • Shubhangi Saraf
    Lower Bounds for 2-query Locally Correctable Codes
  • Gil Kalai
    Near Equality Cases for Harper’s Inequality
  • Breakout Sessions / Research in Small Groups
  • Informal Discussions

Download full agenda (PDF)