There are two natural complexity measures associated with DNFs: their size, which is the number of clauses; and their width, which is the maximal number of variables in a clause. It is a folklore result that DNFs of small size can be approximated by DNFs of small width (logarithmic in ... more >>>

The degree-$d$ Chow parameters of a Boolean function $f: \bn \to \R$ are its degree at most $d$ Fourier coefficients.
It is well-known that degree-$d$ Chow parameters uniquely characterize degree-$d$ polynomial threshold functions
(PTFs)
within the space of all bounded functions. In this paper, we prove a robust ... more >>>

We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of $t \geq \omega(\log^2 n)$ on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small ... more >>>