FEI conjecture - Motivations, Applications & Special CasesSpeaker: Juspreet
Title: FEI conjecture - Motivations, Applications & Special Cases
Date: 23 Sep 2019 5:30pm-7:00pm
Location: Maxwell-Dworkin 123
Audience background: Probability; Basics of Boolean Function Analysis are nice (but we'll go over them)
Abstract: The FEI conjecture was posited by [Friedgut-Kalai] in ‘96 while investigating monotonic predicates over Random Graphs. Since then, it has been shown to be related to the KKL inequality and is also known to imply a version of Mansour’s conjecture (a long-standing problem in Computational Learning Theory). In the general case, it has proven hard to deal with - However, 2 special cases (for symmetric functions [O’Donnell et al] and functions with extremal influence/entropies [Tal]) have been resolved. We will motivate the conjecture, show its relationship to the KKL inequality & Mansour’s conjecture, state the main results of O’Donnell and Tal, and show brief sketches of the O’Donnell proofs with the main ideas.