research-article

Bootstrapping results for threshold circuits “just beyond” known lower bounds

Authors:

Lijie Chen,

Roei TellAuthors Info & Claims

STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

Pages 34 - 41

https://doi.org/10.1145/3313276.3316333

Published: 23 June 2019 Publication History

Get Access

Abstract

The best known lower bounds for the circuit class TC⁰ are only slightly super-linear. Similarly, the best known algorithm for derandomization of this class is an algorithm for quantified derandomization (i.e., a weak type of derandomization) of circuits of slightly super-linear size. In this paper we show that even very mild quantitative improvements of either of the two foregoing results would already imply super-polynomial lower bounds for TC⁰. Specifically:

(1) If for every c>1 and sufficiently large d∈ℕ it holds that n-bit TC⁰ circuits of depth d require n^{1+c^−d} wires to compute certain NC¹-complete functions, then TC⁰≠NC¹. In fact, even lower bounds for TC⁰ circuits of size n^{1+c^−d} against these functions when c>1 is fixed and sufficiently small would yield lower bounds for polynomial-sized circuits. Lower bounds of the form n^{1+c^−d} against these functions are already known, but for a fixed c≈2.41 that is too large to yield new lower bounds via our results.

(2) If there exists a deterministic algorithm that gets as input an n-bit TC⁰ circuit of depth d and n^{1+(1.61)^−d} wires, runs in time 2^{n^o(1)}, and distinguishes circuits that accept at most B(n)=2^{n^{1−(1.61)^−d}} inputs from circuits that reject at most B(n) inputs, then NEXP⊈TC⁰. An algorithm for this “quantified derandomization” task is already known, but it works only when the number of wires is n^{1+c^−d}, for c>30, and with a smaller B(n)≈2^{n^{1−(30/c)^d}}.

Intuitively, the “takeaway” message from our work is that the gap between currently-known results and results that would suffice to get super-polynomial lower bounds for TC⁰ boils down to the precise constant c>1 in the bound n^{1+c^−d} on the number of wires. Our results improve previous results of Allender and Koucký (2010) and of the second author (2018), respectively, whose hypotheses referred to circuits with n^1+c/d wires (rather than n^{1+c^−d} wires). We also prove results similar to two results above for other circuit classes (i.e., ACC⁰ and CC⁰).

References

[1]

Scott Aaronson. P ? = N P, 2017. Accessed at http://www.scottaaronson.com/ papers/pnp.pdf, June 20, 2017.

Abstract

References

Cited By

Index Terms

Recommendations

The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity

Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits

Uniform derandomization from pathetic lower bounds

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Conference

Acceptance Rates

Upcoming Conference

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations