Shachar Lovett


The monomial structure of boolean functions

Combinatorics Seminar

15th February 2022, 5:00 pm – 6:00 pm
Virtual (online) Zoom seminar; a link will be sent to the Bristol Combinatorics Seminar mailing list, the week before the seminar.

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, if f has r monomials, then they have a hitting set of size poly-log(r).

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

Organisers: David Ellis, Tom Johnston

Comments are closed.