Repository logo
 

Symmetric Circuits for Rank Logic

Accepted version
Peer-reviewed

Type

Article

Change log

Abstract

jats:pFixed-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 finit 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 in 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.</jats:p>

Description

Keywords

Finitemodel theory, descriptive complexity, fixed-point logics, fixed-point logic with rank, circuit complexity, symmetric circuits, uniform families of circuits, circuit characterization, circuit frameworks

Journal Title

ACM Transactions on Computational Logic

Conference Name

Journal ISSN

1529-3785
1557-945X

Volume Title

Publisher

Association for Computing Machinery (ACM)

Rights

All rights reserved
Sponsorship
Engineering and Physical Sciences Research Council (EP/S03238X/1)
EPSRC grant EP/S03238X/