Talk information

Date: Sunday, April 30, 2023
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Shachar Lovett (UCSD)
Title: The monomial structure of Boolean functions

Abstract:

Let $f \colon \{0,1\}^n \to \{0,1\}$ be a Boolean function. It can be uniquely represented as a multilinear polynomial. What is the structure of its monomials? This question turns out to be connected to some well-studied problems, such as the log-rank conjecture in communication complexity and the union-closed conjecture in combinatorics. I will describe these connections, and a new structural result, showing that set systems of monomials of boolean functions have small hitting sets, concretely of poly-logarithmic size. The proof uses a combination of algebraic, probabilistic and combinatorial techniques.

Based on joint work with Alexander Knop, Sam McGuire, and Weiqiang Yuan.