Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-036 | 5th March 2019 14:48

On the complexity of computing a random Boolean function over the reals

RSS-Feed




TR19-036
Authors: Pavel Hrubes
Publication: 5th March 2019 16:26
Downloads: 297
Keywords: 


Abstract:

We say that a first-order formula $A(x_1,\dots,x_n)$ over $\mathbb{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. We note that (i) holds over any field of characteristic zero, and (ii) holds for any real closed or algebraically closed field.



ISSN 1433-8092 | Imprint