Guest lecture: Regular Languages and Circuit Complexity — 30 years… and counting!
A talk by Michaël Cadilhac (DePaul University in Chicago)
Main content
The talk starts at 13:00, snacks and coffee will be served from 12:45.
Abstract:
Why are regular languages still relevant to complexity theory? With half a century of research in the rearview mirror, it is indeed puzzling that the interplay between regular languages and (small!) complexity classes is not entirely elucidated. In this talk, I will review the successes and failures of the 30-year study of the ties between circuit complexity and regular languages, with formal logic as a bridging formalism.
One main task in this endeavor is the following:
> Characterize the regular languages recognized by Boolean circuits of small, constant depth (e.g., depth-3).
Such characterizations require new lower bounds (what are regular languages *not* expressible with depth-3 circuits?) and can help in automatically providing the shallowest (or "most efficient") circuit for a given regular language. The "Central Conjecture" of Straubing (1994) provides a guiding light for this study: informally, the Conjecture states that circuits for regular languages have very simple wiring. We will see examples and counter-examples of the Conjecture, focusing in particular on a recent result[1] that solves it for depth-3 circuits.
1: Corentin Barloy, Michaël Cadilhac, Charles Paperman, Thomas Zeume.
The Regular Languages of First-Order Logic with One Alternation, LICS 2022.