The connection between circuit complexity and first-order logic

Pranshu Gaba
Varun Ramanathan
Friday, 17 May 2024, 11:30 to 12:30
A-201 (STCS Seminar Room)

Descriptive complexity is a branch of computational complexity where complexity classes are described using forms of logic, giving machine-independent characterizations of the complexity classes. In this talk, we look at an important result in descriptive complexity:

[BIS88, Theorem 8.1] A class of structures is in DLOGTIME-uniform AC0 if and only if the class is definable in first-order logic with numerical predicates.

Here, DLOGTIME is the class of languages accepted by a deterministic random-access Turing machine in logarithmic time.
A language is said to be in DLOGTIME-uniform AC0 if it can be recognized by a family of constant-depth, polynomial-size circuits with AND and OR gates, where the circuits can be constructed by a DLOGTIME machine. The proof involves showing that if a language is in DLOGTIME, then it is definable in first-order logic with numerical predicates.

[BIS88] David A. Mix-Barrington, Neil Immerman, and Howard Straubing. 1990. On uniformity within NC1. J. Comput. Syst. Sci. 41, 3 (Dec. 1990), 274–306.