Reading Spring 2022

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


  • 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:
  • No reading on August 3, due to summer school.
  1. 4/27: Basics on discrete Fourier analysis; exact (approximate): (almost) linear functions are (almost) monomials.
  2. 5/4: Condorcet’s paradox in 3-candidate election, Kalai’s proof of Arrow’s thm, correlated pair, noise stability.
  3. 5/11: Polymorphism, noise operator, probability of having a Condorcet winner.
  4. 5/18: Proof of Friedgut-Kalai-Noar by induction.
  5. 5/25: Proof of FKN via Bonami’s inequality, noise operator and hypercontractivity.
  6. 6/1: Proof of hypercontractivity, influence.
  7. 6/8: Proof of Friedgut’s Junta thm: high level Fourier coeff. easy to bound via influence, low level ones via hypercontractivity.
  8. 6/15: Proof of Kahn-Kalai-Linial on influencial coordinate, tight example: tribes.
  9. 6/21: Theorems of KKL, Friedgut, and Talagrand via Random Restrictions and Log-Sobolev Inequality by Kelman, Khot, Kindler, Minzer and Safra.
  10. 7/6: Bourgain’s Junta thm.
  11. 7/15: Bourgain’s Junta thm.
  12. 7/27: Product-free sets in the alternating group:


  • polymorphism considers commutativity, what about associativity?

IBS Extremal Combinatorics and Probability Group
기초과학연구원 수리및계산과학연구단 극단 조합 및 확률 그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Extremal Combinatorics and Probability Group (ECOPRO)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail:, Fax: +82-42-878-9209
Copyright © IBS 2021. All rights reserved.