License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.41
URN: urn:nbn:de:0030-drops-44455
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4445/
Go to the corresponding LIPIcs Volume Portal

Anderson, Matthew ; Dawar, Anuj

On Symmetric Circuits and Fixed-Point Logics

pdf-format:
3.pdf (0.6 MB)

Abstract

We study properties of relational structures such as graphs that are decided by families of Boolean circuits. Circuits that decide such properties are necessarily invariant to permutations of the elements of the input structures. We focus on families of circuits that are symmetric, i.e., circuits whose invariance is witnessed by automorphisms of the circuit induced by the permutation of the input structure. We show that the expressive power of such families is closely tied to definability in logic. In particular, we show that the queries defined on structures by uniform families of symmetric Boolean circuits with majority gates are exactly those definable in fixed-point logic with counting. This shows that inexpressibility results in the latter logic lead to lower bounds against polynomial-size families of symmetric circuits.

BibTeX - Entry

@InProceedings{anderson_et_al:LIPIcs:2014:4445,
  author =	{Matthew Anderson and Anuj Dawar},
  title =	{{On Symmetric Circuits and Fixed-Point Logics}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{41--52},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4445},
  URN =		{urn:nbn:de:0030-drops-44455},
  doi =		{10.4230/LIPIcs.STACS.2014.41},
  annote =	{Keywords: symmetric circuit, fixed-point logic, majority, counting, uniformity}
}

Keywords: symmetric circuit, fixed-point logic, majority, counting, uniformity
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI