Circuit Complexity as a Mathematician's Playground: Logic, Algebra, Combinatorics

Abstract: A (Boolean) circuit is a directed acyclic graph with AND, OR, and NOT nodes, some input nodes, and an output node; they naturally compute Boolean functions. Circuit complexity is the study of how intricate or large a circuit needs to be in order to implement a given Boolean function. If this description naturally hints to the use of combinatorial tools, circuit complexity also relies on finite model theory and deep algebraic concepts — specifically, (profinite) semigroup theory. In this talk, I will focus on a specific class of circuits, depth-3 circuits, and will explore a class of "simple" Boolean functions they express. In doing so, I will go on a guided tour of the logical, algebraic, and combinatorial tools used in circuit complexity.

Based on joint work with Corentin Barloy & Charles Paperman (U. Lille, France) and Thomas Zeume (Bochum U., Germany).

computational complexitycombinatoricslogic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic