[Colloquium] Talk by Alexander Razborov on Monday, November 26, 2007

[Nita Yack]

COMPUTER SCIENCE



The University of Chicago







Monday, November 26, 2007

2:30 p.m.

Ryerson 251


Alexander Razborov

Steklov Mathematical Institute, Russian Academy of Sciences

http://www.mi.ras.ru/~razborov/



Title: Grand Challenges in Complexity Theory


Abstract: Modern complexity theory is a vast, loosely defined area.  
Its methods and methodology can be successfully applied whenever one  
has a set of tasks, a class of admissible solutions, and numerical  
characteristics to measure the ``quality'' of a solution. This talk  
will focus on two specific scenarios: classical computational  
complexity and proof complexity. The story we will tell, however, is  
highly representative of the methods that have been tried in the  
field at large, with its mixed bag of successes, setbacks, and  
promising directions.



I will try to reveal some of the tight, beautiful and unexpected  
connections existing between different branches of complexity theory.  
I will discuss the ``grand challenges'' of the field, including "P vs  
NP" and questions about the power of classical proof systems.








Host:  Laci Babai

*The talk will be followed by refreshments in Ryerson 255*

Persons who need assistance should call 773-702-6614


Nita

**************************
Nita Yack
Departmental Administrator
Computer Science Department
1100 E. 58th Street - Room 151
Chicago, IL 60637
(773) 702-6019
(773) 702-8487 FAX

"Hard work spotlights the character of people: some turn up their  
sleeves, some turn up their noses, and some don't turn up at all."


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20071120/ae23be66/attachment-0001.html