Analysis of Boolean Functions

Date & Time


Location


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 & Slidesplus--large

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

    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

Subscribe to MPS announcements and other foundation updates