Analysis of Boolean Functions

April 3-9, 2016

 
Organizers:
Krzysztof Oleskiewicz, University of Warsaw
Elchanan Mossel, University of Pennsylvania
Ryan O’Donnell, Carnegie Mellon University

Related Links:

This third symposium for Analysis of Boolean Functions focused on “New Analytic tools in Discrete Fourier Analysis”, in particular on the methods coming from fields as diverse as probability theory, functional analysis and statistical physics, and their applications in the discrete cube setting.

Key topics:
  • Functional inequalities, concentration of measure
  • Discrete random matrices
  • Phase transitions, percolation, random graphs, Ising models, sharp thresholds and cutoffs
  • The Fourier analytic structure of circuits
  • Noise sensitivity

Click here for a PDF of the schedule and participant list, or see the Agenda and Participants sections below.

Agenda & Slides

Sunday
8:00 -10:00 PM Dinner
Monday
7:30 – 10:30 AM Breakfast
10:30 – 10:55 AM A. Bonami: Quantitative Central limit theorems and cumulants in Wiener chaos (Slides PDF)
10:55 – 11:20 AM A. Wigderson: New algorithms and Fourier tail bounds for sensitive Boolean functions
11:20 – 11:45 AM A. Naor: Metric X_p Inequalities
11:45 – 12:15 PM Break
12:15 – 12:40 PM A. De: Noisy population recovery in polynomial time
12:40 – 1:05 PM U. Feige: Learning and optimization for approximately nice set functions
1:05 – 1:30 PM G. Kalai: Influence, correlation, and Chvatal’s conjecture
1:30 – 2:30 PM Lunch
3:00 – 4:30 PM Discussion & Recreation
4:30 – 5:00 PM Tea
5:00 – 5:25 PM R. Servedio: Addition is Exponentially Harder than Counting for Shallow Monotone Circuits (Slides PDF)
5:30 – 6:30 PM Long Talk 1
6:30 – 7:00 PM Open Problems 1
8:00 – 9:30 PM Dinner at the Wintergarden
Tuesday
7:30 – 10:00 AM Breakfast
10:30 – 2:00 PM Guided Hike to Partnach Gorge
2:00 – 3:00 PM Lunch
3:00 – 5:00 PM Recreation & Discussion
5:00 – 5:25 PM Tea
5:30 – 6:30 PM KKL Retrospective
5:00 – 5:30 PM Tea
8:00 – 9:30 PM Dinner
Wednesday
7:30 – 10:30 AM Breakfast
10:30 – 10:55 AM B. Green: Fourier uniformity of Boolean functions on subspaces
10:55 – 11:20 AM J. Kahn: A conjecture implying Chvatal’s Conjecture
11:20 – 11:45 AM N. Sun: The free energy of random regular k-NAE-SAT (Slides PDF)
11:45 – 12:15 PM Break
12:15 – 12:40 PM Y. Zhao: Quasirandom Cayley graphs (Slides PDF)
12:40 – 1:05 PM R. Eldan: Curvature, concentration and an entropic interpolation scheme for Markov chains
1:05 – 1:30 PM D. Moshkovitz: Candidate Hard Unique Game (Slides PDF)
1:30 – 2:30 PM Lunch
3:00 – 4:30 PM Discussion & Recreation
4:30 – 5:00 PM Tea
5:00 – 6:00 PM Long Talk 2
6:00 – 7:00 PM Long Talk 3
8:00 – 9:30 PM Dinner
Thursday
7:30 – 10:30 AM Breakfast
10:30 – 10:55 AM G. Schechtman: Embedding Pythagorean powers of hypercubes in hypercubes
10:55 – 11:20 AM M. Rudelson: Delocalization of eigenvectors of general random matrices
11:20 – 11:45 AM P. Raghavendra: On sum-of-square SDP relaxations for norms of random tensors
11:45 – 12:15 PM Break
12:15 – 12:40 PM J. Lee: Entropy and sparsity in the Fourier spectrum
12:40 – 1:05 PM V. Guruswami: Analysis of polymorphisms and promise constraint satisfaction (Slides PDF)
1:05 – 1:30 PM N. Linial: Discrepancy in higher dimensions
1:30 – 2:30 PM Lunch
3:00 – 4:30 PM Discussion & Recreation
4:30 – 5:00 PM Tea
5:00 – 6:00 PM Long Talk 4
6:00 – 7:00 PM Long Talk 5
8:00 – 9:30 PM Dinner
Friday
7:30 – 10:30 AM Breakfast
10:30 – 11:30 AM Long Talk 6
11:45 – 12:15 PM Break
12:15 – 1:05 PM Long Talk 7
1:30 – 2:30 PM Lunch
3:00 – 4:30 PM Discussion & Recreation
4:30 – 5:00 PM Tea
5:00 – 6:00 PM Open Problems 2
6:00 – 7:00 PM Wrapup
8:00 – 9:30 PM Dinner at Kaminstüberl

Participants

Aline Bonami Université d’Orléans
Anindya De Northwestern University
Ronen Eldan Weizmann Institute of Science
Uriel Feige Weizmann Institute of Science
Ben Green Oxford University
Venkatesan Guruswami Carnegie Mellon University
Jeff Kahn Rutgers University
Gil Kalai Hebrew University of Jerusalem
James Lee University of Washington
Nathan Linial Hebrew University of Jerusalem
Dana Moshkovitz MIT
Elchanan Mossel UC Berkeley
Assaf Naor Princeton University
Ryan O’Donnell Carnegie Mellon University
Krzysztof Oleszkiewicz University of Warsaw
Prasad Raghavendra UC Berkeley
Mark Rudelson University of Michigan
Gideon Schechtman Weizmann Institute
Rocco Servedio Columbia University
Jeff Steif Chamlers University of Technology
Nike Sun MIT
Avi Wigderson Institute for Advanced Study
Yufei Zhao Oxford University

 
« Back to Simons Symposia