<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><b class="">REMINDER: </b><div class=""><b class="">(Updated schedule below)</b><br class=""><br class="">Departments of Computer Science & Mathematics<br class="">Combinatorics & Theoretical Seminar<br class=""><br class="">Alexander Kulikov<br class="">Steklov Institute at St. Petersburg<br class=""><br class="">Tuesday, April 4, 2017<br class="">Ryerson 251 @ 3pm<br class=""><br class="">Title: Lower bounds for general circuits: new results and limitations<br class=""><br class="">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.<br class=""><br class="">Host: Prof. Alexander Razborov<br class=""><br class="">Refreshments will be served prior to the talk at 2:30 in Ry. 255<div class=""><br class=""></div><div class=""></div></div></body></html>