Analysis of Boolean Functions: New Directions and Applications (2012)
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.
- Materials
-
Participants
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 -
Agenda
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