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 >>>

Feedforward neural networks with sigmoid activations are of fundamental importance in neural computation. However, our understanding of the circuit complexity of such networks for implementing Boolean functions remains limited. The analog output of the sigmoid, along with its transcendental nature, leads to unique mathematical challenges for proving lower bounds.

... more >>>