[Colloquium] Theory Seminars at Computer Science

[Donna Brooms]

~REMINDER~

THEORY SEMINAR

Tuesday, April 16, 2013
3:00 p.m.
Ryerson 251
 
Subhash Khot
University of Chicago
www.cs.uchicago/people/t-9khot
 
Title: “Some open problems in hardness of approximation”
 
Abstract:
 
A widely studied question in theoretical computer science is whether one can compute approximate solutions to NP-hard problems efficiently and if not, whether one can prove that this task is computationally hard (the answer depends in general on specific problem at hand and the quality of approximation sought).
 
I will present some open problems from the hardness side, especially arising from the connections to combinatorics, analysis and geometry.
 
*Refreshments will be served prior to the talk in Ry. 255 at 2:30 p.m.*
 
Host: Prof. Alexander Razborov
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20130416/6ac66853/attachment.htm