Approximations of Isomorphism and Logics with Linear-Algebraic Operators (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Anuj Dawar, Erich Grädel, Wied Pakusa



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.112.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Anuj Dawar
  • University of Cambridge, UK
Erich Grädel
  • RWTH Aachen University, Germany
Wied Pakusa
  • RWTH Aachen University, Germany

Cite AsGet BibTex

Anuj Dawar, Erich Grädel, and Wied Pakusa. Approximations of Isomorphism and Logics with Linear-Algebraic Operators (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 112:1-112:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.112

Abstract

Invertible map equivalences are approximations of graph isomorphism that refine the well-known Weisfeiler-Leman method. They are parameterized by a number k and a set Q of primes. The intuition is that two equivalent graphs G equiv^IM_{k, Q} H cannot be distinguished by means of partitioning the set of k-tuples in both graphs with respect to any linear-algebraic operator acting on vector spaces over fields of characteristic p, for any p in Q. These equivalences have first appeared in the study of rank logic, but in fact they can be used to delimit the expressive power of any extension of fixed-point logic with linear-algebraic operators. We define {LA^{k}}(Q), an infinitary logic with k variables and all linear-algebraic operators over finite vector spaces of characteristic p in Q and show that equiv^IM_{k, Q} is the natural notion of elementary equivalence for this logic. The logic LA^{omega}(Q) = Cup_{k in omega} LA^{k}(Q) is then a natural upper bound on the expressive power of any extension of fixed-point logics by means of Q-linear-algebraic operators. By means of a new and much deeper algebraic analysis of a generalized variant, for any prime p, of the CFI-structures due to Cai, Fürer, and Immerman, we prove that, as long as Q is not the set of all primes, there is no k such that equiv^IM_{k, Q} is the same as isomorphism. It follows that there are polynomial-time properties of graphs which are not definable in LA^{omega}(Q), which implies that no extension of fixed-point logic with linear-algebraic operators can capture PTIME, unless it includes such operators for all prime characteristics. Our analysis requires substantial algebraic machinery, including a homogeneity property of CFI-structures and Maschke’s Theorem, an important result from the representation theory of finite groups.

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
Keywords
  • Finite Model Theory
  • Graph Isomorphism
  • Descriptive Complexity
  • Algebra

Metrics

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

References

  1. A. Atserias, A. Bulatov, and A. Dawar. Affine Systems of Equations and Counting Infinitary Logic. Theoretical Computer Science, 410:1666-1683, 2009. Google Scholar
  2. A. Atserias and E. N. Maneva. Sherali-Adams relaxations and indistinguishability in counting logics. SIAM J. Comput., 42:112-137, 2013. Google Scholar
  3. L. Babai. Graph Isomorphism in Quasipolynomial Time [extended abstract]. In Proc. 48th Annual ACM SIGACT Symp. Theory of Computing, STOC, pages 684-697, 2016. Google Scholar
  4. A. Barghi and I Ponomarenko. Non-Isomorphic Graphs with Cospectral Symmetric Powers. Electr. J. Comb., 16(1), 2009. Google Scholar
  5. A. Blass, Y. Gurevich, and S. Shelah. On Polynomial Time Computation Over Unordered Structures. Journal of Symbolic Logic, 67(3):1093-1125, 2002. Google Scholar
  6. J. Cai, M. Fürer, and N. Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, 1992. Google Scholar
  7. P.J. Cameron. Permutation Groups. London Mathematical Society Student Texts. Cambridge University Press, 1999. Google Scholar
  8. A. Chistov, G. Ivanyos, and M. Karpinski. Polynomial Time Algorithms for Modules over Finite Dimensional Algebras. In Proceedings of ISSAC '97, pages 68-74. ACM, 1997. Google Scholar
  9. A. Dawar. The nature and power of fixed-point logic with counting. ACM SIGLOG News, 2(1):8-21, 2015. Google Scholar
  10. A. Dawar, E. Grädel, B. Holm, E. Kopczynski, and W. Pakusa. Definability of linear equation systems over groups and rings. Logical Methods in Computer Science, Special Issue dedicated to CSL 2012, 2013. URL: http://www.lmcs-online.org/ojs/viewarticle.php?id=1325.
  11. A. Dawar, E. Grädel, and W. Pakusa. Approximations of Isomorphism and Logics with Linear-Algebraic Operators. arXiv abs/1902.06648. URL: http://arxiv.org/abs/1902.06648.
  12. A. Dawar, M. Grohe, B. Holm, and B. Laubner. Logics with Rank Operators. In Proceedings of LICS 2009, pages 113-122, 2009. Google Scholar
  13. A. Dawar and B. Holm. Tractable Approximations of Graph Isomorphism. forthcoming. Google Scholar
  14. A. Dawar and B. Holm. Pebble Games with Algebraic Rules. Fundam. Inform., 150(3-4):281-316, 2017. Google Scholar
  15. A. Dawar and D. Vagnozzi. Generalizations of k-Weisfeiler-Leman Partitions and Related Graph Invariants. forthcoming. Google Scholar
  16. H. Derksen. The Graph Isomorphism Problem and approximate categories. J. Symb. Comput., 59:81-112, 2013. URL: http://dx.doi.org/10.1016/j.jsc.2013.06.002.
  17. E. Grädel, M. Grohe, B. Pago, and W. Pakusa. A Finite-Model-Theoretic View on Propositional Proof Complexity. Logical Methods in Computer Science, 15:1:4:1-4:53, 2019. Google Scholar
  18. E. Grädel and W. Pakusa. Rank logic is dead, long live rank logic! Journal of Symbolic Logic, 2019. Google Scholar
  19. M. Grohe. The quest for a logic capturing PTIME. In Proceedings of the 23rd IEEE Symposium on Logic in Computer Science (LICS'08), pages 267-271, 2008. Google Scholar
  20. M. Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Cambridge University Press, 2017. Google Scholar
  21. M. Grohe and M.Otto. Pebble Games and linear equations. J. Symb. Log., 80:797-844, 2015. Google Scholar
  22. B. Holm. Descriptive Complexity of Linear Algebra. PhD thesis, University of Cambridge, 2010. Google Scholar
  23. S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. Google Scholar
  24. M. Otto. Bounded Variable Logics and Counting. Springer, 1997. Google Scholar
  25. W. Pakusa. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. PhD thesis, RWTH Aachen University, 2016. Google Scholar
  26. R.S. Pierce. Associative Algebras. Graduate Texts in Mathematics. Springer, 1982. 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