Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR20-150 | 7th October 2020 10:35

#### Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

TR20-150
Authors: Lijie Chen, Xin Lyu, Ryan Williams
Publication: 8th October 2020 16:53
Keywords:

Abstract:

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether $\mathrm{NEXP} \subset \mathrm{i.o.-}\mathrm{NP}$; that is, it is open whether nondeterministic exponential time computations can be simulated on infinitely many input lengths by $\mathrm{NP}$ algorithms. This difficulty also applies to Williams' algorithmic method for circuit lower bounds [Williams, J. ACM 2014]. In particular, although [Murray and Williams, STOC 2018] proved $\mathrm{NTIME}[2^{\mathrm{polylog}(n)}] \not\subset \mathrm{ACC}^0$, it has remained an open problem to show that $\mathrm{E}^{\mathrm{NP}}$ ($2^{O(n)}$ time with an $\mathrm{NP}$ oracle) is not contained in $\mathrm{i.o.-}\mathrm{ACC}^0$.

In this paper, we show how many infinitely-often circuit lower bounds proved by the algorithmic method can be adapted to establish almost-everywhere lower bounds.

- We show there is a function $f \in \mathrm{E}^{\mathrm{NP}}$ such that for all sufficiently large input lengths $n$ and $\varepsilon \leq o(1)$, $f$ cannot be $(1/2+2^{-n^{\varepsilon}})$-approximated by $2^{n^\varepsilon}$-size $\mathrm{ACC}^0$ circuits on inputs of length $n$, improving lower bounds in [Chen and Ren, STOC 2020] and [Viola, ECCC 2020].

- We construct rigid matrices in $\mathrm{P}^{\mathrm{NP}}$ for all but finitely many inputs, rather than infinitely often as in [Alman and Chen, FOCS 2019] and [Bhangale et al., FOCS 2020].

- We show there are functions in $\mathrm{E}^{\mathrm{NP}}$ requiring constant-error probabilistic degree at least $\Omega(n/\log^2 n)$ for all large enough $n$, improving an infinitely-often separation of [Viola, ECCC 2020].

Our key to proving almost-everywhere worst-case lower bounds is a new constructive'' proof of an NTIME hierarchy theorem proved by [Fortnow and Santhanam, CCC 2016], where we show for every weak'' nondeterminstic algorithm (with smaller running-time and short witness), a refuter algorithm'' exists that can construct bad'' inputs for the hard language. We use this refuter algorithm to construct an almost-everywhere hard function. To extend our lower bounds to the average case, we prove a new XOR Lemma based on approximate linear sums, and combine it with the PCP-of-proximity applications developed in [Chen and Williams, CCC 2019] and [Chen and Ren, STOC 2020]. As a byproduct of our new XOR Lemma, we obtain a nondeterministic pseudorandom generator for poly-size $\mathrm{ACC}^0$ circuits with seed length $\mathrm{polylog}(n)$, which resolves an open question in [Chen and Ren, STOC 2020].

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": 1, "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.9535329937934875, "perplexity": 1585.1469657656196}, "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-2020-45/segments/1603107889651.52/warc/CC-MAIN-20201025183844-20201025213844-00054.warc.gz"}