Theory of Computing
-------------------
Title     : On the Complexity of Computing a Random Boolean Function Over the Reals
Authors   : Pavel Hrubes
Volume    : 16
Number    : 9
Pages     : 1-12
URL       : https://theoryofcomputing.org/articles/v016a009

Abstract
--------

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, Gal, 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
Briet 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.