Revised: July 10, 2020
Published: October 21, 2020
Abstract: [Plain Text Version]
We say that a first-order formula $A(x_1,\dots,x_n)$ over $\R$ defines a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, if for every $x_1,\dots,x_n\in\{0,1\}$, $A(x_1,\dots,x_n)$ is true iff $f(x_1,\dots,x_n)=1$. We show that:
(i) every $f$ can be defined by a formula of size $O(n)$,
(ii) if $A$ is required to have at most $k\geq 1$ quantifier alternations, there exists an $f$ which requires a formula of size $2^{\Omega(n/k)}$.
The latter result implies several previously known as well as some new lower bounds in computational complexity: a non-constructive version of the lower bound on span programs of Babai, Gál, and Wigderson (Combinatorica 1999); Rothvoß's result (CoRR 2011) that there exist $0/1$ polytopes that require exponential-size linear extended formulations; a similar lower bound by Briët et al. (Math. Program. 2015) on semidefinite extended formulations; and a new result stating that a random Boolean function has exponential linear separation complexity. We note that (i) holds over any field of characteristic zero, and (ii) holds over any real closed or algebraically closed field.
Licensed under a Creative Commons Attribution License (CC-BY)