Polynomial sparsity of boolean functions, certificate trees, and applications
Shachar Lovett (UCSD)
Monday, October 13th 2025, 2-3pm
Abstract:
A classical result of Nisan and Szegedy shows that many complexity measures of boolean functions are equivalent, up to polynomial factors. These include algebraic measures, like the degree of a polynomial computing or approximating the boolean function; and combinatorial measures, like certificate or block sensitivity.
In this work, we develop combinatorial notions, called "certificate trees", tied to the *sparsity* of the polynomial computing a boolean function. We use them to prove that the sparsity of any polynomial approximating a boolean function cannot be much smaller than the sparsity of the polynomial exactly computing it. If time permits, I will also discuss some applications in "lifting theorems", connecting query complexity and communication complexity for some families of functions.
Joined work with Yogesh Dahiya and Arkadev Chattopadhyay