[Colloquium] 2 Talks by Avi Wigderson on Campus

[caseyk]

UNIVERSITY OF CHICAGO

DEPARTMENT OF COMPUTER SCIENCE

Avi Wigderson (IAS) will give two talks on campus this week.
The first is a TTI-C Distinguished Lecture (Thursday), the
second a technical talk at the U.Chicago CS Dept. (Friday).

Dates, places, titles:
---------------------
TTI-C lecture:
Thursday, March 6, 3:30pm
Biological Sciences Learning Center (room 115- 1st floor)
924 East 57th St.
"Randomness: a computational complexity view"

U.C. Dept CS Complexity Theory Seminar:
Friday, March 7, 10:30 am
Ryerson 276 (1100 E 58th St)
"Algebrization: A New Barrier in Complexity Theory"

The two abstracts are appended.
-----------------------------------------------------------
TTI-C Distinguished Lecture

"Randomness: a computational complexity view"

Abstract.

Man has grappled with the meaning and utility of randomness for  
centuries.
Research in the Theory of Computation in the last thirty years has  
enriched
this study considerably. I'll describe two main aspects of this  
research on
randomness, demonstrating its power and weakness respectively.

-Randomness is paramount to computational efficiency:

The use of randomness can dramatically enhance computation (and do other
wonders) for a variety of problems and settings. In particular, examples
will be given of probabilistic algorithms (with tiny error) for natural
tasks in different areas of mathematics, which are exponentially  
faster than
their (best known) deterministic counterparts.

-Computational efficiency is paramount to understanding randomness:

I will explain the computationally-motivated definition of  
"pseudorandom"
distributions, namely ones which cannot be distinguished from the  
uniform
distribution by efficient procedure from a given class. We then show how
such pseudorandomness may be generated deterministically, from  
(appropriate)
computationally difficult problems. Consequently, randomness is  
probably not
as powerful as it seems above.

I'll conclude with the power of randomness in other computational  
settings,
primarily probabilistic proof systems. We discuss the remarkable  
properties
of Zero-Knowledge proofs and of Probabilistically Checkable proofs.

-----------------------------------------------------------
Any questions, please contact Chrissy Novak  cnovak at tti-c.org or
(773)834-2216
-----------------------------------------------------------
UChicago Dept CS Complexity Seminar

"Algebrization: A New Barrier in Complexity Theory"

Abstract.

Any proof of P != NP will have to overcome two barriers: relativization
and natural proofs. Yet over the last decade, we have seen circuit lower
bounds (for example, that PP does not have linear-size circuits) that
overcome both barriers simultaneously. So the question arises of whether
there is a third barrier to progress on the central questions in
complexity theory. In this paper we present such a barrier, which we
call algebraic relativization or algebrization. The idea is that, when
we relativize some complexity class inclusion, we should give the
simulating machine access not only to an oracle A, but also to a
low-degree extension of A over a finite field or ring.

We systematically go through basic results and open problems in
complexity theory to delineate the power of the new algebrization
barrier. First, we show that all known non-relativizing results based
on arithmetization, both inclusions such as IP = PSPACE and MIP = NEXP,
and separations such as MA_EXP is not contained P/poly, indeed  
algebrize.
Second, we show that almost all of the major open problems, including
P versus NP, P versus RP, and NEXP versus P/poly, will require
non-algebrizing techniques. In some cases algebrization seems to explain
exactly why progress stopped where it did: for example, why we have
superlinear circuit lower bounds for PromiseMA but not for NP.

Joint work with Scott Aaronson

--------------------------------------------
This will be a technical talk.

Host: Laci Babai
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080304/9cd716a9/attachment.html