Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-091 | 26th April 2018 07:45

Small bias requires large formulas

RSS-Feed




Revision #1
Authors: Andrej Bogdanov
Accepted on: 26th April 2018 07:45
Downloads: 45
Keywords: 


Abstract:

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on (1) the size of general Boolean formulas, (2) the size of De Morgan formulas, and (3) correlation against small De Morgan formulas apply to small-biased functions. As a consequence, any strongly explicit small-biased generator is subject to the best-known explicit formula lower bounds in all these models.

On the other hand, we give a construction of a small-biased function that is tight with respect to lower bound (1) for the relevant range of parameters. We interpret this construction as a natural-type barrier against substantially stronger lower bounds for general formulas.



Changes to previous version:

Corrected a mistake in the quoted high-probability shrinkage lemma; Generalized Proposition 2; fixed some inaccuracies in calculations and references.


Paper:

TR17-091 | 17th May 2017 06:37

Small bias requires large formulas





TR17-091
Authors: Andrej Bogdanov
Publication: 17th May 2017 21:42
Downloads: 501
Keywords: 


Abstract:

A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We demonstrate that known explicit lower bounds on the size of (1) general Boolean formulas, (2) Boolean formulas of fan-in two, (3) de Morgan formulas, as well as (4) correlation lower bounds against small de Morgan formulas apply to small-biased functions. As a consequence, any strongly explicit small-biased generator is subject to the best known explicit formula lower bounds in all these models.

On the other hand, we give a construction of a small-biased function that is tight with respect to lower bounds (1) and (2) for the relevant range of parameters. We interpret this construction as a natural-type barrier against substantially stronger lower bounds for general formulas.



ISSN 1433-8092 | Imprint