Document Open Access Logo

Subspace-Invariant AC^0 Formulas

Author Benjamin Rossman

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.93.pdf
  • Filesize: 471 kB
  • 11 pages

Document Identifiers

Author Details

Benjamin Rossman

Cite As Get BibTex

Benjamin Rossman. Subspace-Invariant AC^0 Formulas. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 93:1-93:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.93

Abstract

The n-variable PARITY function is computable (by a well-known recursive construction) by AC^0 formulas of depth d+1 and leaf size n2^{dn^{1/d}}. These formulas are seen to possess a certain symmetry: they are syntactically invariant under the subspace P of even-weight elements in {0,1}^n, which acts (as a group) on formulas by toggling negations on input literals. In this paper, we prove a 2^{d(n^{1/d}-1)} lower bound on the size of syntactically P-invariant depth d+1 formulas for PARITY. Quantitatively, this beats the best 2^{Omega(d(n^{1/d}-1))} lower bound in the non-invariant setting.

Subject Classification

Keywords
  • lower bounds
  • size-depth tradeoff
  • parity
  • symmetry in computation

Metrics

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

References

  1. Miklos Ajtai. Symmetric systems of linear equations modulo p. In TR94-015 of the Electronic Colloquium on Computational Complexity, 1994. Google Scholar
  2. Matthew Anderson and Anuj Dawar. On symmetric circuits and fixed-point logics. Theory of Computing Systems, pages 1-31, 2016. Google Scholar
  3. Andreas Blass, Yuri Gurevich, and Saharon Shelah. Choiceless polynomial time. Ann. Pure &Applied Logic, 100(1-3):141-187, 1999. Google Scholar
  4. Andreas Blass, Yuri Gurevich, and Saharon Shelah. On polynomial time computation over unordered structures. Journal of Symbolic Logic, 67(3):1093-1125, 2002. Google Scholar
  5. Béla Bollobás. The isoperimetric number of random regular graphs. European Journal of combinatorics, 9(3):241-244, 1988. Google Scholar
  6. Anuj Dawar. On symmetric and choiceless computation. In International Conference on Topics in Theoretical Computer Science, pages 23-29. Springer, 2015. Google Scholar
  7. Anuj Dawar, David Richerby, and Benjamin Rossman. Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs. Annals of Pure and Applied Logic, 152:31-50, 2008. Google Scholar
  8. Larry Denenberg, Yuri Gurevich, and Saharon Shelah. Definability by constant-depth polynomial-size circuits. Information and Control, 70(2-3):216-240, 1986. Google Scholar
  9. Erich Grädel and Martin Grohe. Is polynomial time choiceless? In Fields of Logic and Computation II, pages 193-209. Springer, 2015. Google Scholar
  10. Johan Håstad. Almost optimal lower bounds for small depth circuits. In STOC'86: Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 6-20, 1986. Google Scholar
  11. Neil Immerman. Descriptive complexity. Springer, 2012. Google Scholar
  12. V. M. Khrapchenko. Complexity of the realization of a linear function in the class of π-circuits. Mathematical Notes of the Academy of Sciences of the USSR, 9(1):21-23, 1971. Google Scholar
  13. Martin Otto. The logic of explicitly presentation-invariant circuits. In International Workshop on Computer Science Logic, pages 369-384. Springer, 1996. Google Scholar
  14. Søren Riis and Meera Sitharam. Generating hard tautologies using predicate logic and the symmetric group. Logic Journal of IGPL, 8(6):787-795, 2000. Google Scholar
  15. Benjamin Rossman. Choiceless computation and symmetry. In Fields of logic and computation, pages 565-580. Springer, 2010. Google Scholar
  16. Benjamin Rossman. The average sensitivity of bounded-depth formulas. In Proc. 56th Annual IEEE Symposium on Foundations of Computer Science, pages 424-430. IEEE, 2015. 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 About DROPS Imprint Privacy Contact