[Colloquium] FW: Guest Speaker announcement

[Ponda Barnes]

Reminder!!
 
 
Guest Speaker
 
Presented by: Toyota Technological Institute at Chicago
 
Speaker: Andrej Bogdanov
Speaker's home page: http://dimacs.rutgers.edu/~adib/
 
Date: Friday, May 4, 2007
Time: 10:00
Location: TTI-C Conference room
 
 
Title: Average-case hardness for NP
 
 
Abstract:
 
The gold standard of difficulty for a computational problem is NP hardness.
However, NP hard instances of problems are quite atypical.  In practice, and
in many theoretical settings as well,
one sometimes adopts the view that NP hard instances are so rare that they
present no serious obstacle to the design of efficient algorithms Yet
experience tells us that some NP problems are intractable even on typical
instances.  This assumption is a fundamental axiom of modern cryptography.
So far computer science has been unable to explain why this happens.  In
this talk, I will focus on two basic questions:
 
* What is a typical instance?  * Can the extensive theory of NP hardness be
used to explain why for certain problems typical instances are also hard?
 
These two questions will give a glimpse of the central role that
average-case complexity plays in the theory of computation.
 
If you have any questions or would like to meet the speaker, please contact
Ponda Barnes at pondabarnes at tti-c.org
For future TTI-C talks and events please got to
http://ttic.uchicago.edu/cal/month.php
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20070504/e01b92df/attachment-0001.html