Algebraic and Logical Approaches to Circuit Complexity

One of the outstanding open questions in computational complexity concerns the power of circuits that include modular counting gates along with the usual AND and OR gates. More precisely, the class ACC consists of languages recognized by constant-­‐depth polynomial-­‐size families of circuits with unbounded fan-­‐in AND, OR and MOD-q gates for a fixed modulus q; the question is whether ACC is strictly contained in NC1. At present this is known only for prime power moduli, a result proved in the mid 1980’s.

There are some very striking connections between this question and problems and techniques originating in both finite model theory and the algebraic theory of finite automata. This talk is an overview of these connections along with the efforts, some by now quite old, some much more recent, to exploit them in addressing the status ofACC.