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

Contacts

Registration and Travel Assistance

Susan Gatewood
susan.gatewood(replace this with the @ sign)protravelinc.com
(646) 747-9317

Meeting Questions and Assistance

Meghan Fazzi
Senior Executive Assistant, Simons Foundation
mfazzi(replace this with the @ sign)simonsfoundation.org
(212) 524-6080

Reimbursement and Travel Policy

Download the Simons Symposia Travel and Expense Reimbursement Policy (PDF)

Reimbursement

Any expenses not directly paid for by the Simons Foundation are subject to reimbursement based on the travel policy. Please review the policy and complete the provided reimbursement form when submitting your expenses. All expenses with original receipts and completed expense reimbursement form are due within THIRTY DAYS (30) after the conclusion of the symposium. Should you have any questions, please contact Meghan Fazzi.

Guest Policy

It is the foundation’s policy to discourage spouses, families or others from joining participants during the meeting. Participants who choose to invite guests to come before or stay on after the meeting do so at their own expense. The Simons Foundation will not cover expenses associated with such extensions.

Additional Nights

Should you decide to extend your stay, Schloss Elmau will honor the conference rate of 337.50/night for up to two nights. Any nights beyond those associated with the conference will not be reimbursed by the foundation. Please note on your registration form if you wish to extend your stay.