Volume 16 (2020) Article 9 pp. 1-12
On the Complexity of Computing a Random Boolean Function Over the Reals
Revised: July 10, 2020
Published: October 21, 2020
[PDF (230K)]    [PS (966K)]    [PS.GZ (260K)]
[Source ZIP]
Keywords: random Boolean function, quantifier elimination
ACM Classification: F.1.3, F.2.3
AMS Classification: 68Q17, 03C10

Abstract: [Plain Text Version]

$\newcommand{\R}{{\mathbb R}}$

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.