Boolean functions
The goal is to study Boolean functions and their applications. Along the way, we will post questions that puzzle us, if you know the answer, please email us. 🙂
- Time: Every Wedn 14:30~16:00 (KST), April 27-
- Zoom: 890 901 6918, PW: 202204
Announcement
- No reading on June 29.
- Reading on July 6 is moved to 16:00 (KST).
- Reading on July 13 is moved to July 15 at 14:30 (KST).
- July 27 reading is replaced by Lifshitz’s talk: https://dimag.ibs.re.kr/event/2022-07-27/
- No reading on August 3, due to summer school.
- 4/27: Basics on discrete Fourier analysis; exact (approximate): (almost) linear functions are (almost) monomials.
- 5/4: Condorcet’s paradox in 3-candidate election, Kalai’s proof of Arrow’s thm, correlated pair, noise stability.
- 5/11: Polymorphism, noise operator, probability of having a Condorcet winner.
- 5/18: Proof of Friedgut-Kalai-Noar by induction.
- 5/25: Proof of FKN via Bonami’s inequality, noise operator and hypercontractivity.
- 6/1: Proof of hypercontractivity, influence.
- 6/8: Proof of Friedgut’s Junta thm: high level Fourier coeff. easy to bound via influence, low level ones via hypercontractivity.
- 6/15: Proof of Kahn-Kalai-Linial on influencial coordinate, tight example: tribes.
- 6/21: Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality by Kelman, Khot, Kindler, Minzer and Safra.
- 7/6: Bourgain’s Junta thm.
- 7/15: Bourgain’s Junta thm.
- 7/27: Product-free sets in the alternating group: https://dimag.ibs.re.kr/event/2022-07-27/
Thoughts
- polymorphism considers commutativity, what about associativity?
