<div dir="ltr"><div><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif">When:     <span class="gmail-m_7692690357644826767gmail-m_-7299232485244876288gmail-m_-8835445654570712268gmail-m_-2510718269459749973gmail-m_-2700415185665105741gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-il">Friday</span>, February 3rd at noon </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif">Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526</font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;line-height:normal"><font face="arial, helvetica, sans-serif" style="font-size:12.8px">Who:       </font><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">Li-Yang Tan, TTIC </span></font></p><br><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><br></p></div><div><div style="font-size:12.8px">Title: Computational complexity through the lens of circuits, proofs, and randomness </div><div style="font-size:12.8px"><br></div><span style="font-size:12.8px">Abstract: Computational complexity theory is rooted in many of computer science's most fascinating questions.  Three examples of such questions are: Are there functions that are simple to describe, and yet require large circuits to compute?  Are there short mathematical theorems that require lengthy proofs?  Does every efficient randomized algorithm have an efficient deterministic counterpart?  </span><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">In this talk I will describe results motivated by and contributing to our understanding of these questions, focusing on three results: </div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">(1) An average-case depth hierarchy theorem for boolean circuits, which resolves a thirty-year-old conjecture in circuit complexity; </div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">(2) Exponentially-improved lower bounds for the Frege proof system, the canonical proof system for propositional logic; </div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">(3) The fastest deterministic algorithm for finding satisfying assignments of CNF formulas that have many such assignments, a basic unresolved problem in derandomization.  </div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">These results illuminate rich connections among the respective subfields of complexity theory --- circuit complexity, proof complexity, and pseudorandomness --- and also have implications to areas outside of complexity theory, such as parallel computing and SAT solving.  I will also touch on how the techniques we have developed point to avenues for progress on a few flagship challenges of complexity theory.</div></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">********************************************************************************************************************</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><div class="gmail_default" style="font-size:12.8px"><b><font face="arial, helvetica, sans-serif">Research at TTIC Seminar Series</font></b></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">TTIC is hosting a weekly seminar series presenting the research currently underway at the Institute. Every week a different TTIC faculty member will present their research.  The lectures are intended both for students seeking research topics and adviser, and for the general TTIC and University of Chicago communities interested in hearing what their colleagues are up to.   </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">To receive announcements about the seminar series, please subscribe to the mailing list: <a href="https://groups.google.com/a/ttic.edu/group/talks/subscribe" target="_blank">https://groups.google.co<wbr>m/a/ttic.edu/group/<span class="gmail-m_7692690357644826767gmail-m_-7299232485244876288gmail-m_-6544832015911959341gmail-m_-2510718269459749973gmail-m_-2700415185665105741gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-m_-8247393949946928606gmail-m_-8480526344443392316gmail-m_-1056553444316568634gmail-m_593248408351034154gmail-m_8873931552348078312gmail-m_-3900280345830708483gmail-m_2412953322955092339gmail-m_-3568727914368024249gmail-m_-7538648194147727859gmail-il"><span class="gmail-m_7692690357644826767gmail-m_-7299232485244876288gmail-m_-6544832015911959341gmail-m_-2510718269459749973gmail-m_-2700415185665105741gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-m_-8247393949946928606gmail-m_-8480526344443392316gmail-m_-1056553444316568634gmail-m_593248408351034154gmail-m_8873931552348078312gmail-m_-3900280345830708483gmail-m_2412953322955092339gmail-m_-3568727914368024249gmail-il"><span class="gmail-m_7692690357644826767gmail-m_-7299232485244876288gmail-m_-6544832015911959341gmail-m_-2510718269459749973gmail-m_-2700415185665105741gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-il">talks</span></span></span>/subsc<wbr>ribe</a></font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">Speaker details can be found at: <a href="http://www.ttic.edu/tticseminar.php" target="_blank">http://www.ttic.edu/tticse<wbr>minar.php</a>.</font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif">For additional questions, please contact Nathan Srebro at <a href="mailto:mcallester@ttic.edu" target="_blank">nati@ttic.edu</a></font></div><div class="gmail_default" style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div></div><div style="font-size:12.8px"><br></div><br clear="all"><div><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 504</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div>
</div>