Document Open Access Logo

Symmetric Circuits for Rank Logic

Authors Anuj Dawar , Gregory Wilsenach

PDF
Thumbnail PDF

File

LIPIcs.CSL.2018.20.pdf
  • Filesize: 0.53 MB
  • 16 pages

Document Identifiers

Author Details

Anuj Dawar
  • Department of Computer Science and Technology, University of Cambridge, UK
Gregory Wilsenach
  • Department of Computer Science and Technology, University of Cambridge, UK

Funding

  • Wilsenach, Gregory: Funding provided by the Gates Cambridge Scholarship.

Cite AsGet BibTex

Anuj Dawar and Gregory Wilsenach. Symmetric Circuits for Rank Logic. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.CSL.2018.20

Abstract

Fixed-point logic with rank (FPR) is an extension of fixed-point logic with counting (FPC) with operators for computing the rank of a matrix over a finite field. The expressive power of FPR properly extends that of FPC and is contained in P, but it is not known if that containment is proper. We give a circuit characterization for FPR in terms of families of symmetric circuits with rank gates, along the lines of that for FPC given by [Anderson and Dawar 2017]. This requires the development of a broad framework of circuits in which the individual gates compute functions that are not symmetric (i.e., invariant under all permutations of their inputs). This framework also necessitates the development of novel techniques to prove the equivalence of circuits and logic. Both the framework and the techniques are of greater generality than the main result.

Subject Classification

ACM Subject Classification
  • Theory of computation → Circuit complexity
  • Theory of computation → Finite Model Theory
  • Theory of computation → Complexity theory and logic
Keywords
  • fixed-point logic with rank
  • circuits
  • symmetric circuits
  • uniform families of circuits
  • circuit characterization
  • circuit framework
  • finite model theory
  • descriptive complexity

Metrics

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

Related Versions

References

  1. M. Anderson and A. Dawar. On symmetric circuits and fixed-point logics. Theory of Computing Systems, 60(3):521-551, 2017. Google Scholar
  2. A. Dawar. The nature and power of fixed-point logic with counting. ACM SIGLOG News, 2(1):8-21, 2015. Google Scholar
  3. A. Dawar. On symmetric and choiceless computation. In Mohammad Taghi Hajiaghayi and Mohammad Reza Mousavi, editors, Topics in Theoretical Computer Science, pages 23-29, Cham, 2016. Springer International Publishing. Google Scholar
  4. 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, 9(4), 2013. Google Scholar
  5. A. Dawar, M. Grohe, B. Holm, and B. Laubner. Logics with rank operators. In 2009 24th Annual IEEE Symposium on Logic In Computer Science (LICS), pages 113-122, 2009. Google Scholar
  6. A. Dawar and B. Holm. Pebble games with algebraic rules. In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming, pages 251-262, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  7. A. Dawar and G. Wilsenach. Symmetric circuits for rank logic. arXiv, 2018. URL: http://arxiv.org/abs/1804.02939.
  8. L. Denenberg, Y. Gurevich, and S. Shelah. Definability by constant-depth polynomial-size circuits. Information and Control, 70(2):216-240, 1986. Google Scholar
  9. E. Grädel and W. Pakusa. Rank logic is dead, long live rank logic! In 2015 24th Annual Conference on Computer Science Logic, (CSL), pages 390-404, 2015. Google Scholar
  10. M. Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. Lecture Notes in Logic. Cambridge University Press, 2017. URL: https://books.google.co.uk/books?id=RLYrDwAAQBAJ.
  11. L. Hella. Logical hierarchies in ptime. Information and Computation, 129(1):1-19, 1996. Google Scholar
  12. N. Immerman. Relational queries computable in polynomial time. Information and Control, 68(1-3):86-104, 1986. Google Scholar
  13. N. Immerman. Descriptive Complexity. Graduate texts in computer science. Springer New York, 1999. Google Scholar
  14. L. Libkin. Elements of Finite Model Theory. Texts in Theoretical Computer Science. An EATCS Series. Springer Berlin Heidelberg, 2004. Google Scholar
  15. M. Otto. The logic of explicitly presentation-invariant circuits. In 1996 10th International Workshop, Annual Conference on Computer Science Logic (CSL), pages 369-384. Springer, Berlin, Heidelberg, 1997. Google Scholar
  16. M. Vardi. The complexity of relational query languages (extended abstract). In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, pages 137-146, New York, NY, USA, 1982. ACM. 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