BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Michaël Cadilhac (DePaul University)
DTSTART:20230914T180000Z
DTEND:20230914T190000Z
DTSTAMP:20260423T021215Z
UID:OLS/126
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/OLS/126/">Ci
 rcuit Complexity as a Mathematician's Playground: Logic\, Algebra\, Combin
 atorics</a>\nby Michaël Cadilhac (DePaul University) as part of Online lo
 gic seminar\n\n\nAbstract\nA (Boolean) circuit is a directed acyclic graph
  with AND\, OR\, and NOT nodes\, some input nodes\, and an output node\; t
 hey naturally compute Boolean functions.  Circuit complexity is the study 
 of how intricate or large a circuit needs to be in order to implement a gi
 ven Boolean function.  If this description naturally hints to the use of c
 ombinatorial tools\, circuit complexity also relies on finite model theory
  and deep algebraic concepts — specifically\, (profinite) semigroup theo
 ry.  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 ex
 press.  In doing so\, I will go on a guided tour of the logical\, algebrai
 c\, and combinatorial tools used in circuit complexity.\n\nBased on joint 
 work with Corentin Barloy & Charles Paperman (U. Lille\, France) and Thoma
 s Zeume (Bochum U.\, Germany).\n
LOCATION:https://researchseminars.org/talk/OLS/126/
END:VEVENT
END:VCALENDAR