3 papers
cs.CC2021
Lower Bounds for Symmetric Circuits for the Determinant
Anuj Dawar, Gregory Wilsenach
Dawar and Wilsenach (ICALP 2020) introduce the model of symmetric arithmetic circuits and show an exponential separation between the sizes of symmetric circuits for computing the d…
cs.CC2020
Symmetric Arithmetic Circuits
Anuj Dawar, Gregory Wilsenach
We introduce symmetric arithmetic circuits, i.e. arithmetic circuits with a natural symmetry restriction. In the context of circuits computing polynomials defined on a matrix of va…
cs.CC2018
Symmetric Circuits for Rank Logic
Anuj Dawar, Gregory Wilsenach
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 pow…