Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SMALL-BIASED SETS:
Reports tagged with small-biased sets:
TR17-091 | 17th May 2017
Andrej Bogdanov

Small bias requires large formulas

Revisions: 1

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




ISSN 1433-8092 | Imprint