Hardness of Approximation
Hardness of Approximation studies the phenomenon that for several fundamental NP-hard problems, even computing approximate solutions to them remains an NP-hard problem. The talk will give an overview of this study along with its connections to algorithms, analysis, and geometry.
Subhash Khot teaches at the Courant Institute of Mathematical Sciences, New York University. He completed his PhD from Princeton CS Department in 2003. His past affiliations include Georgia Tech and U. Chicago. His research interests are broadly in Theoretical Computer Science, and specifically in hardness of approximation and probabilistically checkable proofs, with connections to algorithms, analysis, and geometry.