0534404 - MÚ 2021 RIV US eng J - Článek v odborném periodiku
Hrubeš, Pavel
On the complexity of computing a random Boolean function over the reals.
Theory of Computing. Roč. 16, October (2020), č. článku 9. ISSN 1557-2862. E-ISSN 1557-2862
Grant CEP: GA ČR(CZ) GA19-05497S
Institucionální podpora: RVO:67985840
Klíčová slova: random Boolean function * quantifier elimination
Obor OECD: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impakt faktor: 1.000, rok: 2020
Způsob publikování: Open access
https://dx.doi.org/10.4086/toc.2020.v016a009

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.
Trvalý link: http://hdl.handle.net/11104/0312602