<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">UNIVERSITY OF CHICAGO<br><br>DEPARTMENT OF COMPUTER SCIENCE<br><br>Avi Wigderson (IAS) will give two talks on campus this week.<br>The first is a TTI-C Distinguished Lecture (Thursday), the<br>second a technical talk at the U.Chicago CS Dept. (Friday).<br><br>Dates, places, titles:<br>---------------------<br>TTI-C lecture:<br>Thursday, March 6, 3:30pm<br>Biological Sciences Learning Center (room 115- 1st floor)<br>924 East 57th St.<br>"Randomness: a computational complexity view"<br><br>U.C. Dept CS Complexity Theory Seminar:<br>Friday, March 7, 10:30 am<br>Ryerson 276 (1100 E 58th St)<br>"Algebrization: A New Barrier in Complexity Theory"<br><br>The two abstracts are appended.<br>-----------------------------------------------------------<br>TTI-C Distinguished Lecture<br><br>"Randomness: a computational complexity view"<br><br>Abstract.<br><br>Man has grappled with the meaning and utility of randomness for centuries.<br>Research in the Theory of Computation in the last thirty years has enriched<br>this study considerably. I'll describe two main aspects of this research on<br>randomness, demonstrating its power and weakness respectively.<br><br>-Randomness is paramount to computational efficiency:<br><br>The use of randomness can dramatically enhance computation (and do other<br>wonders) for a variety of problems and settings. In particular, examples<br>will be given of probabilistic algorithms (with tiny error) for natural<br>tasks in different areas of mathematics, which are exponentially faster than<br>their (best known) deterministic counterparts.<br><br>-Computational efficiency is paramount to understanding randomness:<br><br>I will explain the computationally-motivated definition of "pseudorandom"<br>distributions, namely ones which cannot be distinguished from the uniform<br>distribution by efficient procedure from a given class. We then show how<br>such pseudorandomness may be generated deterministically, from (appropriate)<br>computationally difficult problems. Consequently, randomness is probably not<br>as powerful as it seems above.<br><br>I'll conclude with the power of randomness in other computational settings,<br>primarily probabilistic proof systems. We discuss the remarkable properties<br>of Zero-Knowledge proofs and of Probabilistically Checkable proofs.<br><br>-----------------------------------------------------------<br>Any questions, please contact Chrissy Novak <a href="mailto:cnovak@tti-c.org">cnovak@tti-c.org</a> or <br>(773)834-2216<br>-----------------------------------------------------------<br>UChicago Dept CS Complexity Seminar<br><br>"Algebrization: A New Barrier in Complexity Theory"<br><br>Abstract.<br><br>Any proof of P != NP will have to overcome two barriers: relativization <br>and natural proofs. Yet over the last decade, we have seen circuit lower <br>bounds (for example, that PP does not have linear-size circuits) that <br>overcome both barriers simultaneously. So the question arises of whether <br>there is a third barrier to progress on the central questions in <br>complexity theory. In this paper we present such a barrier, which we <br>call algebraic relativization or algebrization. The idea is that, when <br>we relativize some complexity class inclusion, we should give the <br>simulating machine access not only to an oracle A, but also to a <br>low-degree extension of A over a finite field or ring.<br><br>We systematically go through basic results and open problems in <br>complexity theory to delineate the power of the new algebrization <br>barrier. First, we show that all known non-relativizing results based <br>on arithmetization, both inclusions such as IP = PSPACE and MIP = NEXP, <br>and separations such as MA_EXP is not contained P/poly, indeed algebrize.<br>Second, we show that almost all of the major open problems, including <br>P versus NP, P versus RP, and NEXP versus P/poly, will require <br>non-algebrizing techniques. In some cases algebrization seems to explain<br>exactly why progress stopped where it did: for example, why we have <br>superlinear circuit lower bounds for PromiseMA but not for NP.<br><br>Joint work with Scott Aaronson<br><br>--------------------------------------------<br>This will be a technical talk.<br><br>Host: Laci Babai</body></html>