Volume 16 (2020) Article 9 pp. 1-12

On the Complexity of Computing a Random Boolean Function Over the Reals

by Pavel Hrubeš

Received: January 26, 2019
Revised: July 10, 2020
Published: October 21, 2020

$\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.

DOI: 10.4086/toc.2020.v016a009

© 2020 Pavel Hrubeš
Licensed under a Creative Commons Attribution License (CC-BY)