Date:
Mon, 04/04/202211:00-13:00
Location:
Sprinzak 202
HUJI Erdos Lectures 2022
Speaker: Shachar Lovett (UCSD)
When: April 4th, 2022, at 11AM (Israel time)
Where: Sprinzak 202
Live broadcast (and recording) link:
https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=e511cae0-b0ed-4024-8b56-ae670062fb01
Title: (Combinatorial structure) 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, if f has r monomials, then the monomials have a hitting set of size poly-log(r).
Based on joint work with Alexander Knop, Sam McGuire, and Weiqiang Yuan.
Speaker: Shachar Lovett (UCSD)
When: April 4th, 2022, at 11AM (Israel time)
Where: Sprinzak 202
Live broadcast (and recording) link:
https://huji.cloud.panopto.eu/Panopto/Pages/Viewer.aspx?id=e511cae0-b0ed-4024-8b56-ae670062fb01
Title: (Combinatorial structure) 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, if f has r monomials, then the monomials have a hitting set of size poly-log(r).
Based on joint work with Alexander Knop, Sam McGuire, and Weiqiang Yuan.