Department of Informatics
Guest lecture

Guest lecture: Regular Languages and Circuit Complexity — 30 years… and counting!

A talk by Michaël Cadilhac (DePaul University in Chicago)

Michaël Cadilhac
Michaël Cadilhac (DePaul University in Chicago)

Main content

The talk starts at 13:00, snacks and coffee will be served from 12:45.


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.