On Symmetric Circuits and Fixed-Point Logics

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...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2017-04, Vol.60 (3), p.521-551
Main Authors: Anderson, Matthew, Dawar, Anuj
Format: Article
Language:English
Subjects:
Analysis
Automorphisms
Boolean
Boolean algebra
Circuits
Computer programming
Computer Science
Graph theory
Graphs
Invariants
Logic
Permutations
Polynomials
Queries
Studies
Symmetry
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1432-4350
1433-0490
DOI:10.1007/s00224-016-9692-2