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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA19-05497S" target="_blank" >GA19-05497S: Složitost matematických důkazů a struktur</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2020

Kód důvěrnosti údajů

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

Název periodika

Theory of Computing

ISSN

1557-2862

e-ISSN

—

Svazek periodika

16

Číslo periodika v rámci svazku

October

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

12

Strana od-do

9

Kód UT WoS článku

000585121500001

EID výsledku v databázi Scopus

2-s2.0-85100104829