Workshop on Additive Combinatorics and Algebraic Connections

The Monomial Structure of Boolean Functions

Abstract: Let $f:{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.

Date & Time

October 25, 2022 | 2:00pm – 3:00pm

Location

Simonyi 101 and Remote Access

Speakers

Speaker Affiliation

University of California, San Diego

Categories