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

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F20%3A00534404" target="_blank" >RIV/67985840:_____/20:00534404 - isvavai.cz</a>
Result on the web
<a href="https://dx.doi.org/10.4086/toc.2020.v016a009" target="_blank" >https://dx.doi.org/10.4086/toc.2020.v016a009</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4086/toc.2020.v016a009" target="_blank" >10.4086/toc.2020.v016a009</a>

Result language
angličtina
Original language name
On the complexity of computing a random Boolean function over the reals
Original language description
We say that a first-order formula A(x1,…,xn) over R defines a Boolean function f:{0,1}n→{0,1}, if for every x1,…,xn∈{0,1}, A(x1,…,xn) is true iff f(x1,…,xn)=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≥1 quantifier alternations, there exists an f which requires a formula of size 2Ω(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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA19-05497S" target="_blank" >GA19-05497S: Complexity of mathematical proofs and structures</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)