[Colloquium] Theory Seminars at Computer Science
Donna Brooms via Colloquium
colloquium at mailman.cs.uchicago.edu
Wed Mar 29 10:08:59 CDT 2017
Departments of Computer Science & Mathematics
Combinatorics & Theoretical Seminar
Alexander Kulikov
Steklov Institute at St. Petersburg
Tuesday, April 4, 2017
Ryerson 251 @ 3pm
Title: Lower bounds for general circuits: new results and limitations
Abstract: Currently, we know highly non-trivial proofs of lower bounds for restricted circuit classes (e.g., constant depth circuits, formulas, monotone circuits). At the same time, for general circuits we know only modest linear lower bounds and essentially just one simple inductive argument for proving such bounds, the gate elimination method. In the talk we will discuss generalizations of this method and its limitations. We will conclude with several open problems.
Host: Prof. Alexander Razborov
Refreshments will be served prior to the talk at 2:30 in Ry. 255
More information about the Colloquium
mailing list