Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR12-062 | 16th October 2012 15:29

#### Average-Case Lower Bounds for Formula Size

Revision #2
Authors: Ilan Komargodski, Ran Raz
Accepted on: 16th October 2012 15:29
Keywords:

Abstract:

We give an explicit function $h:\{0,1\}^n\to\{0,1\}$ such that any deMorgan formula of size $O(n^{2.499})$ agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$). We also show, using the same technique, that any boolean formula of size $O(n^{1.999})$ over the complete basis, agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$).

Our construction is based on Andreev's $\Omega(n^{2.5-o(1)})$ formula size lower bound that was proved for the case of exact computation \cite{And87}.

Revision #1 to TR12-062 | 18th May 2012 13:00

#### Average-Case Lower Bounds for Formula Size

Revision #1
Authors: Ilan Komargodski, Ran Raz
Accepted on: 18th May 2012 13:00
Keywords:

Abstract:

We give an explicit function $h:\{0,1\}^n\to\{0,1\}$ such that any deMorgan formula of size $O(n^{2.499})$ agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$). The same technique also shows that any boolean formula of size $O(n^{1.999})$ over the complete basis, agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$). Previously, such lower bounds were only obtained for exact computation.

Our construction is based on Andreev's $\Omega(n^{2.5-o(1)})$ formula size lower bound that was proved for the case of exact computation \cite{And87}.

Changes to previous version:

Added reference to Santhanam's work (FOCS 2010).

### Paper:

TR12-062 | 17th May 2012 16:06

#### Average-Case Lower Bounds for Formula Size

TR12-062
Authors: Ilan Komargodski, Ran Raz
Publication: 17th May 2012 16:17
Keywords:

Abstract:

We give an explicit function $h:\{0,1\}^n\to\{0,1\}$ such that any deMorgan formula of size $O(n^{2.499})$ agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$). Previous lower bounds for formula size were obtained for exact computation.

The same technique also shows that any boolean formula of size $O(n^{1.999})$ over the complete basis, agrees with $h$ on at most $\frac{1}{2} + \epsilon$ fraction of the inputs, where $\epsilon$ is exponentially small (i.e. $\epsilon = 2^{-n^{\Omega(1)}}$).

Our construction is based on Andreev's $\Omega(n^{2.5-o(1)})$ formula size lower bound that was proved for the case of exact computation \cite{And87}.

ISSN 1433-8092 | Imprint
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9945372939109802, "perplexity": 893.5025325552228}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2017-17/segments/1492917119782.43/warc/CC-MAIN-20170423031159-00554-ip-10-145-167-34.ec2.internal.warc.gz"}