Document Open Access Logo

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹

Authors Lijie Chen, Zhenjian Lu, Xin Lyu, Igor C. Oliveira

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.51.pdf
  • Filesize: 0.82 MB
  • 20 pages

Document Identifiers

Author Details

Lijie Chen
  • MIT, Cambridge, MA, USA
Zhenjian Lu
  • University of Warwick, Coventry, UK
Xin Lyu
  • Tsinghua University, Beijing, China
Igor C. Oliveira
  • University of Warwick, Coventry, UK

Funding

Lijie Chen is supported by an IBM fellowship. This work received support from the Royal Society University Research Fellowship URF⧵R1⧵191059.

Acknowledgements

We would like to thank William Hoza for asking whether PRGs for 𝒞 imply average-case lower bounds against 𝒞 under the uniform distribution. We are also grateful to Roei Tell for the observation that part of our equivalence theorem extends to the constant-error case as well.

Cite AsGet BibTex

Lijie Chen, Zhenjian Lu, Xin Lyu, and Igor C. Oliveira. Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 51:1-51:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.51

Abstract

We develop a general framework that characterizes strong average-case lower bounds against circuit classes 𝒞 contained in NC¹, such as AC⁰[⊕] and ACC⁰. We apply this framework to show: - Generic seed reduction: Pseudorandom generators (PRGs) against 𝒞 of seed length ≤ n -1 and error ε(n) = n^{-ω(1)} can be converted into PRGs of sub-polynomial seed length. - Hardness under natural distributions: If 𝖤 (deterministic exponential time) is average-case hard against 𝒞 under some distribution, then 𝖤 is average-case hard against 𝒞 under the uniform distribution. - Equivalence between worst-case and average-case hardness: Worst-case lower bounds against MAJ∘𝒞 for problems in 𝖤 are equivalent to strong average-case lower bounds against 𝒞. This can be seen as a certain converse to the Discriminator Lemma [Hajnal et al., JCSS'93]. These results were not known to hold for circuit classes that do not compute majority. Additionally, we prove that classical and recent approaches to worst-case lower bounds against ACC⁰ via communication lower bounds for NOF multi-party protocols [Håstad and Goldmann, CC'91; Razborov and Wigderson, IPL'93] and Torus polynomials degree lower bounds [Bhrushundi et al., ITCS'19] also imply strong average-case hardness against ACC⁰ under the uniform distribution. Crucial to these results is the use of non-black-box hardness amplification techniques and the interplay between Majority (MAJ) and Approximate Linear Sum (SUM̃) gates. Roughly speaking, while a MAJ gate outputs 1 when the sum of the m input bits is at least m/2, a SUM̃ gate computes a real-valued bounded weighted sum of the input bits and outputs 1 (resp. 0) if the sum is close to 1 (resp. close to 0), with the promise that one of the two cases always holds. As part of our framework, we explore ideas introduced in [Chen and Ren, STOC'20] to show that, for the purpose of proving lower bounds, a top layer MAJ gate is equivalent to a (weaker) SUM̃ gate. Motivated by this result, we extend the algorithmic method and establish stronger lower bounds against bounded-depth circuits with layers of MAJ and SUM̃ gates. Among them, we prove that: - Lower bound: NQP does not admit fixed quasi-polynomial size MAJ∘SUM̃∘ACC⁰∘THR circuits. This is the first explicit lower bound against circuits with distinct layers of MAJ, SUM̃, and THR gates. Consequently, if the aforementioned equivalence between MAJ and SUM̃ as a top gate can be extended to intermediate layers, long sought-after lower bounds against the class THR∘THR of depth-2 polynomial-size threshold circuits would follow.

Subject Classification

ACM Subject Classification
  • Theory of computation
Keywords
  • circuit complexity
  • average-case hardness
  • complexity lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Eric Allender, Vikraman Arvind, and Fengming Wang. Uniform derandomization from pathetic lower bounds. In RANDOM-APPROX, pages 380-393. Springer, 2010. Google Scholar
  2. Josh Alman, Timothy M. Chan, and R. Ryan Williams. Polynomial representations of threshold functions and algorithmic applications. In FOCS, pages 467-476, 2016. Google Scholar
  3. Benny Applebaum. Garbled circuits as randomized encodings of functions: a primer. In Tutorials on the Foundations of Cryptography, pages 1-44. Springer International Publishing, 2017. Google Scholar
  4. Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC⁰. SIAM J. Comput., 36(4):845-888, 2006. Google Scholar
  5. Sergei Artemenko and Ronen Shaltiel. Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification. Comput. Complex., 23(1):43-83, 2014. Google Scholar
  6. Richard Beigel and Jun Tarui. On ACC. Comput. Complex., 4:350-366, 1994. Google Scholar
  7. Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, and Sankeerth Rao. Torus polynomials: An algebraic approach to ACC lower bounds. In ITCS, pages 13:1-13:16, 2019. Google Scholar
  8. Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multi-party protocols. In STOC, pages 94-99, 1983. Google Scholar
  9. Arkadev Chattopadhyay and Nikhil S. Mande. A short list of equalities induces large sign rank. In FOCS, pages 47-58, 2018. Google Scholar
  10. Lijie Chen. Non-deterministic quasi-polynomial time is average-case hard for ACC circuits. In FOCS, pages 1281-1304, 2019. Google Scholar
  11. Lijie Chen, Zhenjian Lu, Xin Lyu, and Igor Carboni Oliveira. Majority vs. approximate linear sum and average-case complexity below NC1. Electron. Colloquium Comput. Complex., 28:40, 2021. Google Scholar
  12. Lijie Chen and Xin Lyu. Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma. In STOC, 2021. Google Scholar
  13. Lijie Chen, Xin Lyu, and Ryan Williams. Almost-everywhere circuit lower bounds from non-trivial derandomization. In FOCS, pages 1-12, 2020. Google Scholar
  14. Lijie Chen and Hanlin Ren. Strong average-case lower bounds from non-trivial derandomization. In STOC, pages 1327-1334, 2020. Google Scholar
  15. Lijie Chen and Ryan Williams. Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity. In CCC, pages 19:1-19:43, 2019. Google Scholar
  16. Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola. On beating the hybrid argument. Theory Comput., 9:809-843, 2013. Google Scholar
  17. Jürgen Forster. A linear lower bound on the unbounded error probabilistic communication complexity. In CCC, pages 100-106, 2001. Google Scholar
  18. Mikael Goldmann, Johan Håstad, and Alexander A. Razborov. Majority gates vs. general weighted threshold gates. Comput. Complex., 2:277-300, 1992. Google Scholar
  19. Oded Goldreich, Noam Nisan, and Avi Wigderson. On Yao’s XOR-lemma. In Studies in Complexity and Cryptography, pages 273-301. Springer, 2011. Google Scholar
  20. Shafi Goldwasser, Dan Gutfreund, Alexander Healy, Tali Kaufman, and Guy N. Rothblum. Verifying and decoding in constant depth. In STOC, pages 440-449, 2007. Google Scholar
  21. Frederic Green, Johannes Köbler, and Jacobo Torán. The power of the middle bit. In CCC, pages 111-117, 1992. Google Scholar
  22. Aryeh Grinberg, Ronen Shaltiel, and Emanuele Viola. Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs. In FOCS, pages 956-966, 2018. Google Scholar
  23. Dan Gutfreund and Guy N. Rothblum. The complexity of local list decoding. In RANDOM-APPROX, pages 455-468, 2008. Google Scholar
  24. András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, and György Turán. Threshold circuits of bounded depth. J. Comput. Syst. Sci., 46(2):129-154, 1993. Google Scholar
  25. Johan Håstad. On the size of weights for threshold gates. SIAM J. Discret. Math., 7(3):484-492, 1994. Google Scholar
  26. Johan Håstad and Mikael Goldmann. On the power of small-depth threshold circuits. Comput. Complex., 1:113-129, 1991. Google Scholar
  27. Xuangui Huang and Emanuele Viola. Average-case rigidity lower bounds. In CSR, 2021. Google Scholar
  28. Russell Impagliazzo. Hard-core distributions for somewhat hard problems. In FOCS, pages 538-545, 1995. Google Scholar
  29. Russell Impagliazzo and Sam McGuire. Comparing computational entropies below majority (or: When is the dense model theorem false?). In ITCS, pages 2:1-2:20, 2021. Google Scholar
  30. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In STOC, pages 220-229, 1997. Google Scholar
  31. Yuval Ishai and Eyal Kushilevitz. Perfect constant-round secure computation via perfect randomizing polynomials. In ICALP, pages 244-256, 2002. Google Scholar
  32. Daniel M. Kane and Ryan Williams. Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits. In STOC, pages 633-643, 2016. Google Scholar
  33. Adam R. Klivans. On the derandomization of constant depth circuits. In RANDOM-APPROX, pages 249-260, 2001. Google Scholar
  34. Vaibhav Krishan. Upper bound for torus polynomials. In CSR, 2021. Google Scholar
  35. Leonid A. Levin. One-way functions and pseudorandom generators. Comb., 7(4):357-363, 1987. Google Scholar
  36. Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu. Complexity of hard-core set proofs. Comput. Complex., 20(1):145-171, 2011. Google Scholar
  37. Cody D. Murray and R. Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma. SIAM J. Comput., 49(5), 2020. Google Scholar
  38. Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Comput. Complex., 4:301-313, 1994. Google Scholar
  39. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  40. Alexander A. Razborov. Lower bounds on the size of constant-depth networks over a complete basis with logical addition. Mathematicheskie Zametki, 41(4):598-607, 1987. Google Scholar
  41. Alexander A. Razborov and Avi Wigderson. n^Ω(log n) lower bounds on the size of depth-3 threshold circuits with AND gates at the bottom. Inf. Process. Lett., 45(6):303-307, 1993. Google Scholar
  42. Ronen Shaltiel and Emanuele Viola. Hardness amplification proofs require majority. SIAM J. Comput., 39(7):3122-3154, 2010. Google Scholar
  43. Madhu Sudan, Luca Trevisan, and Salil P. Vadhan. Pseudorandom generators without the XOR lemma. J. Comput. Syst. Sci., 62(2):236-266, 2001. Google Scholar
  44. Suguru Tamaki. A satisfiability algorithm for depth two circuits with a sub-quadratic number of symmetric and threshold gates. Electron. Colloquium Comput. Complex., 23:100, 2016. Google Scholar
  45. Emanuele Viola. The complexity of constructing pseudorandom generators from hard functions. Comput. Complex., 13(3-4):147-188, 2005. Google Scholar
  46. Emanuele Viola. Guest column: correlation bounds for polynomials over 0,1. SIGACT News, 40(1):27-44, 2009. Google Scholar
  47. Emanuele Viola. Constant-error pseudorandomness proofs from hardness require majority. ACM Trans. Comput. Theory, 11(4):19:1-19:11, 2019. Google Scholar
  48. Emanuele Viola. New lower bounds for probabilistic degree and AC⁰ with parity gates. Electron. Colloquium Comput. Complex., 27:15, 2020. Google Scholar
  49. Ryan Williams. Improving exhaustive search implies superpolynomial lower bounds. SIAM J. Comput., 42(3):1218-1244, 2013. Google Scholar
  50. Ryan Williams. Limits on representing boolean functions by linear combinations of simple functions: Thresholds, ReLUs, and low-degree polynomials. In CCC, pages 6:1-6:24, 2018. Google Scholar
  51. Ryan Williams. New algorithms and lower bounds for circuits with linear threshold gates. Theory of Computing, 14(1):1-25, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact