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

Date & Time


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.

  • Materialsplus--large
  • Participantsplus--large

    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
  • Agendaplus--large

    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)

Subscribe to MPS announcements and other foundation updates