Speaker: Michaël Cadilhac
DePaul University
Will give a Logic Seminar entitled:
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). Bio: Assistant Prof. of Computer Science at DePaul U., Chicago, since 2019, interested in circuit complexity, automata theory, and finite model theory. PhD 2013 from Université de Montréal; Post-docs in Tübingen, Germany (2014-2017) and Oxford, UK (2017-2019).
Date: 04-26-2024
Time: 3:40 pm
Location: 231 Hayes-Healy Bldg