ACO Distinguished Lecture

Event Details
  • Date/Time:
    • Thursday September 13, 2012
      4:30 pm
  • Location: Weber Space Science and Technology II Room 2, 275 Ferst Drive
  • Phone:
  • URL: http://map.gtalumni.org/index.php
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact

Annette Rohrs, 404-894-9227

Summaries

Summary Sentence: Algorithms, Combinatorics and Optimization (ACO) Distinguished Lecture

Full Summary: No summary paragraph submitted.

Analysis of Boolean Functions, Influence and Noise

Speaker: Professor Gil Kalai, Henry and Manya Noskwith Professor of Mathematics at the Hebrew University of Jerusalem

A few results and two general conjectures regarding analysis of Boolean functions, influence, and threshold phenomena will be presented.

  • Boolean functions are functions of n Boolean variables with values in {0,1}. They are important in combinatorics, theoretical computer science, probability theory and game theory.
  • Influence: Causality is a topic of great interest everywhere, and if causality is not complicated enough, we can ask what is the influence one event has on another one. In a 1985 paper, Ben-Or and Linial, studied influence in the context of collective coin flipping -- a problem in theoretical computer science.
  • Fourier analysis: Over the last two decades, Fourier analysis of Boolean functions and related objects played a growing role in discrete mathematics and theoretical computer science.
  • Threshold phenomena: Threshold phenomena refer to sharp transition in the probability of certain events depending on a parameter p near a critical value. A classic example that goes back to Erdös and Rényi, is the behavior of certain monotone properties of random graphs.

Influence of variables on Boolean functions is connected to their Fourier analysis and threshold behavior as well as to discrete isoperimetry and noise sensitivity.

The first conjecture to be described (with Friedgut) is called the Entropy-Influence Conjecture (it was featured on Tao's blog). It gives a far reaching extension to the KKL theorem, and theorems by Friedgut, Bourgain, and me.

The second conjecture (with Kahn) proposes a far-reaching generalization to results by Friedgut, Bourgain and Hatami.

Related Links

Additional Information

In Campus Calendar
Yes
Groups

School of Mathematics

Invited Audience
No audiences were selected.
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Annette Rohrs
  • Workflow Status: Draft
  • Created On: Sep 7, 2012 - 4:16am
  • Last Updated: Feb 3, 2017 - 12:11pm