[Colloquium] Theory Seminars at Computer Science

[Donna Brooms via Colloquium]

REMINDER: 
(Updated schedule below)

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



 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170404/1989c2bb/attachment-0002.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: A. Kulikov.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 78967 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170404/1989c2bb/attachment-0001.docx>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170404/1989c2bb/attachment-0003.html>