In this paper we give polynomial-size hitting sets for multilinear any-order read-once oblivious algebraic branching programs and for depth-$3$ set-multilinear circuits where each variable set has constant size. Our results also extend to the border of both classes and hold over fields of any characteristic.

The proof combines the ... more >>>

We prove unconditionally that either NE contains a language requiring Boolean circuits of size at least $2^n/(2n)$, or $VP^0_{\mathbb{Z}}\ne VNP^0_{\mathbb{Z}}$, a constant-free version of Valiant's conjecture over the integers. The Boolean alternative implies that $NP\not\subseteq SIZE[n^k]$ for every constant $k\ge1$. Our proof gives a fine-grained variant of the connection between ... more >>>

We initiate the study of the space complexity of property testing. We focus on five properties of Boolean functions that have been intensively studied in the property testing literature: monotonicity, symmetry, linearity, being a junta, and being a linear threshold function.

On the upper bounds side, we show --- ... more >>>