Document Open Access Logo

Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits

Author Benedikt Pago

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2023.73.pdf
  • Filesize: 0.82 MB
  • 15 pages

Document Identifiers

Author Details

Benedikt Pago
  • Mathematical Foundations of Computer Science, RWTH Aachen University, Germany

Acknowledgements

I thank Daniel Wiebking for his group-theoretic help.

Cite As Get BibTex

Benedikt Pago. Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.MFCS.2023.73

Abstract

Choiceless Polynomial Time (CPT) is one of the few remaining candidate logics for capturing Ptime. In this paper, we make progress towards separating CPT from polynomial time by firstly establishing a connection between the expressive power of CPT and the existence of certain symmetric circuit families, and secondly, proving lower bounds against these circuits. We focus on the isomorphism problem of unordered Cai-Fürer-Immerman-graphs (the CFI-query) as a potential candidate for separating CPT from Ptime. Results by Dawar, Richerby and Rossman, and subsequently by Pakusa, Schalthöfer and Selman show that the CFI-query is CPT-definable on linearly ordered and preordered base graphs with small colour classes. We define a class of CPT-algorithms, that we call "CFI-symmetric algorithms", which generalises all the known ones, and show that such algorithms can only define the CFI-query on a given class of base graphs if there exists a family of symmetric XOR-circuits with certain properties. These properties include that the circuits have the same symmetries as the base graphs, are of polynomial size, and satisfy certain fan-in restrictions. Then we prove that such circuits with slightly strengthened requirements (i.e. stronger symmetry and fan-in and fan-out restrictions) do not exist for the n-dimensional hypercubes as base graphs. This almost separates the CFI-symmetric algorithms from Ptime - up to the gap that remains between the circuits whose existence we can currently disprove and the circuits whose existence is necessary for the definability of the CFI-query by a CFI-symmetric algorithm.

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
Keywords
  • logic in computer science
  • finite model theory
  • descriptive complexity
  • symmetric computation
  • symmetric circuits
  • graph isomorphism

Metrics

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

Related Versions

References

  1. Matthew Anderson and Anuj Dawar. On symmetric circuits and fixed-point logics. Theory of Computing Systems, 60(3):521-551, 2017. Google Scholar
  2. Albert Atserias, Andrei Bulatov, and Anuj Dawar. Affine systems of equations and counting infinitary logic. Theoretical Computer Science, 410(18):1666-1683, 2009. Google Scholar
  3. Andreas Blass, Yuri Gurevich, and Saharon Shelah. Choiceless polynomial time. Annals of Pure and Applied Logic, 100(1-3):141-187, 1999. Google Scholar
  4. J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12:389-410, 1992. Google Scholar
  5. Ashok Chandra and David Harel. Structure and complexity of relational queries. In 21st Annual Symposium on Foundations of Computer Science (sfcs 1980), pages 333-347. IEEE, 1980. URL: https://doi.org/10.1109/SFCS.1980.41.
  6. Anuj Dawar. The nature and power of fixed-point logic with counting. ACM SIGLOG News, 2(1):8-21, 2015. Google Scholar
  7. Anuj Dawar, Erich Grädel, and Wied Pakusa. Approximations of Isomorphism and Logics with Linear-Algebraic Operators. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 112:1-112:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.112.
  8. Anuj Dawar, Erich Grädel, and Moritz Lichter. Limitations of the invertible-map equivalences. Journal of Logic and Computation, September 2022. URL: https://doi.org/10.1093/logcom/exac058.
  9. 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(1-3):31-50, 2008. Google Scholar
  10. Anuj Dawar and Gregory Wilsenach. Symmetric Arithmetic Circuits. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 36:1-36:18, 2020. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.36.
  11. Anuj Dawar and Gregory Wilsenach. Symmetric circuits for rank logic. ACM Transactions on Computational Logic (TOCL), 23(1):1-35, 2021. Google Scholar
  12. Anuj Dawar and Gregory Wilsenach. Lower Bounds for Symmetric Circuits for the Determinant. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), pages 52:1-52:22, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.52.
  13. John Dixon and Brian Mortimer. Permutation Groups. Springer, New York, 1996. Google Scholar
  14. Ronald Fagin. Generalized first-order spectra and polynomial-time recognizable sets. Complexity of computation, 7:43-73, 1974. Google Scholar
  15. F. Gire and H.K. Hoang. An extension of fixpoint logic with a symmetry-based choice construct. Information and Computation, 144(1):40-65, 1998. URL: https://doi.org/10.1006/inco.1998.2712.
  16. E. Grädel, W. Pakusa, S. Schalthöfer, and L. Kaiser. Characterising Choiceless Polynomial Time with First-Order Interpretations. In Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 677-688, 2015. Google Scholar
  17. Erich Grädel and Martin Grohe. Is Polynomial Time Choiceless? In Fields of Logic and Computation II, pages 193-209. Springer, 2015. Google Scholar
  18. Martin Grohe. The quest for a logic capturing PTIME. In 2008 23rd Annual IEEE Symposium on Logic in Computer Science, pages 267-271. IEEE, 2008. URL: https://doi.org/10.1109/LICS.2008.11.
  19. Martin Grohe, Pascal Schweitzer, and Daniel Wiebking. Deep Weisfeiler Leman, 2020. URL: https://arxiv.org/abs/2003.10935.
  20. Yuri Gurevich. Logic and the Challenge of Computer Science. In Current Trends in Theoretical Computer Science. Computer Science Press, 1988. Google Scholar
  21. William He and Benjamin Rossman. Symmetric formulas for products of permutations, 2022. URL: https://arxiv.org/abs/2211.15520.
  22. Moritz Lichter. Separating Rank Logic from Polynomial Time. J. ACM, November 2022. URL: https://doi.org/10.1145/3572918.
  23. Moritz Lichter. Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting, 2022. URL: https://arxiv.org/abs/2210.07869.
  24. Moritz Lichter and Pascal Schweitzer. Choiceless Polynomial Time with Witnessed Symmetric Choice. In LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022, LICS '22. Association for Computing Machinery, 2022. URL: https://doi.org/10.1145/3531130.3533348.
  25. Daniel Neuen and Pascal Schweitzer. An exponential lower bound for individualization-refinement algorithms for graph isomorphism. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 138-150, New York, NY, USA, 2018. Association for Computing Machinery. URL: https://doi.org/10.1145/3188745.3188900.
  26. Benedikt Pago. Choiceless Computation and Symmetry: Limitations of Definability. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021), volume 183 of Leibniz International Proceedings in Informatics (LIPIcs), pages 33:1-33:21, 2021. URL: https://doi.org/10.4230/LIPIcs.CSL.2021.33.
  27. Benedikt Pago. Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits, 2023. URL: https://arxiv.org/abs/2302.05426.
  28. Wied Pakusa. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. PhD thesis, RWTH Aachen, 2015. Google Scholar
  29. Wied Pakusa, Svenja Schalthöfer, and Erkal Selman. Definability of Cai-Fürer-Immerman problems in Choiceless Polynomial Time. ACM Transactions on Computational Logic (TOCL), 19(2):1-27, 2018. URL: https://doi.org/10.1145/3154456.
  30. Benjamin Rossman. Choiceless Computation and Symmetry. In Fields of Logic and Computation, pages 565-580. Springer, 2010. Google Scholar
  31. Benjamin Rossman. Subspace-Invariant AC⁰ Formulas. Logical Methods in Computer Science, 15, 2019. Google Scholar
  32. Svenja Schalthöfer. Choiceless Computation and Logic. PhD thesis, RWTH Aachen, 2020. 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