Document Open Access Logo

More on AC^0[oplus] and Variants of the Majority Function

Authors Nutan Limaye, Srikanth Srinivasan, Utkarsh Tripathi

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.22.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Nutan Limaye
  • Department of Computer Science and Engineering, IIT Bombay, India
Srikanth Srinivasan
  • Department of Mathematics, IIT Bombay, India
Utkarsh Tripathi
  • Department of Mathematics, IIT Bombay, India

Cite AsGet BibTex

Nutan Limaye, Srikanth Srinivasan, and Utkarsh Tripathi. More on AC^0[oplus] and Variants of the Majority Function. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.22

Abstract

In this paper we prove two results about AC^0[oplus] circuits. (1) We show that for d(N) = o(sqrt(log N/log log N)) and N <= s(N) <= 2^(dN^(1/4d^2)) there is an explicit family of functions {f_N:{0,1}^N - > {0,1}} such that - f_N has uniform AC^0 formulas of depth d and size at most s; - f_N does not have AC^0[oplus] formulas of depth d and size s^epsilon, where epsilon is a fixed absolute constant. This gives a quantitative improvement on the recent result of Limaye, Srinivasan, Sreenivasaiah, Tripathi, and Venkitesh, (STOC, 2019), which proved a similar Fixed-Depth Size-Hierarchy theorem but for d << log log N and s << exp(N^(1/2^Omega(d))). As in the previous result, we use the Coin Problem to prove our hierarchy theorem. Our main technical result is the construction of uniform size-optimal formulas for solving the coin problem with improved sample complexity (1/delta)^O(d) (down from (1/delta)^(2^O(d)) in the previous result). (2) In our second result, we show that randomness buys depth in the AC^0[oplus] setting. Formally, we show that for any fixed constant d >= 2, there is a family of Boolean functions that has polynomial-sized randomized uniform AC^0 circuits of depth d but no polynomial-sized (deterministic) AC^0[oplus] circuits of depth d. Previously Viola (Computational Complexity, 2014) showed that an increase in depth (by at least 2) is essential to avoid superpolynomial blow-up while derandomizing randomized AC^0 circuits. We show that an increase in depth (by at least 1) is essential even for AC^0[oplus]. As in Viola’s result, the separating examples are promise variants of the Majority function on N inputs that accept inputs of weight at least N/2 + N/(log N)^(d-1) and reject inputs of weight at most N/2 - N/(log N)^(d-1).

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • AC^0[oplus]
  • Coin Problem
  • Promise Majority

Metrics

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

Related Versions

References

  1. Leonard M. Adleman. Two Theorems on Random Polynomial Time. In 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16-18 October 1978, pages 75-83, 1978. Google Scholar
  2. Miklós Ajtai. ∑^1_1-formulae on finite structures. Ann. Pure Appl. Logic, 24(1):1-48, 1983. URL: https://doi.org/10.1016/0168-0072(83)90038-6.
  3. Miklós Ajtai and Michael Ben-Or. A Theorem on Probabilistic Constant Depth Computations. In STOC, pages 471-474. ACM, 1984. Google Scholar
  4. Kazuyuki Amano. Bounds on the Size of Small Depth Circuits for Approximating Majority. In ICALP (1), Lecture Notes in Computer Science, pages 59-70. Springer, 2009. Google Scholar
  5. Sanjeev Arora and Boaz Barak. Computational complexity : a modern approach. Cambridge University Press, 2009. Google Scholar
  6. Roger C. Baker, Glyn Harman, and János Pintz. The difference between consecutive primes, II. Proceedings of the London Mathematical Society, 83:532–562, 2001. Google Scholar
  7. Joshua Brody and Elad Verbin. The Coin Problem and Pseudorandomness for Branching Programs. In FOCS, pages 30-39. IEEE Computer Society, 2010. Google Scholar
  8. Gil Cohen, Anat Ganor, and Ran Raz. Two Sides of the Coin Problem. In APPROX-RANDOM, volume 28 of LIPIcs, pages 618-629. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2014. Google Scholar
  9. Merrick L. Furst, James B. Saxe, and Michael Sipser. Parity, Circuits, and the Polynomial-Time Hierarchy. Mathematical Systems Theory, 17(1):13-27, 1984. URL: https://doi.org/10.1007/BF01744431.
  10. Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. AC^0[p] Lower Bounds Against MCSP via the Coin Problem. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece., pages 66:1-66:15, 2019. Google Scholar
  11. John Hastad. Almost Optimal Lower Bounds for Small Depth Circuits. Advances in Computing Research, 5:143-170, 1989. Google Scholar
  12. Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, and Amir Yehudayoff. Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece., pages 72:1-72:14, 2019. Google Scholar
  13. Svante Janson. Poisson Approximation for Large Deviations. Random Struct. Algorithms, 1(2):221-230, 1990. Google Scholar
  14. Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. A fixed-depth size-hierarchy theorem for AC^0[⊕] via the coin problem. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019., pages 442-453, 2019. Google Scholar
  15. Ryan O'Donnell and Karl Wimmer. Approximation by DNF: Examples and Counterexamples. In ICALP, volume 4596 of Lecture Notes in Computer Science, pages 195-206. Springer, 2007. Google Scholar
  16. Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan. Parity Helps to Compute Majority. In 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA., pages 23:1-23:17, 2019. Google Scholar
  17. Alexander A. Razborov. On the Method of Approximations. In STOC, pages 167-176. ACM, 1989. Google Scholar
  18. Benjamin Rossman. On the constant-depth complexity of k-clique. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 721-730, 2008. URL: https://doi.org/10.1145/1374376.1374480.
  19. Benjamin Rossman and Srikanth Srinivasan. Separation of AC⁰[⊕] Formulas and Circuits. In ICALP, volume 80 of LIPIcs, pages 50:1-50:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  20. Ronen Shaltiel and Emanuele Viola. Hardness Amplification Proofs Require Majority. SIAM J. Comput., 39(7):3122-3154, 2010. URL: https://doi.org/10.1137/080735096.
  21. Roman Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In STOC, pages 77-82. ACM, 1987. Google Scholar
  22. Roman Smolensky. On Representations by Low-Degree Polynomials. In FOCS, pages 130-138. IEEE Computer Society, 1993. Google Scholar
  23. Emanuele Viola. Randomness Buys Depth for Approximate Counting. Computational Complexity, 23(3):479-508, 2014. URL: https://doi.org/10.1007/s00037-013-0076-6.
  24. Andrew Chi-Chih Yao. Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version). In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985, pages 1-10, 1985. 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