BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium : Approximability\, Analysis and Geometry
DTSTART:20130325T161500
DTEND:20130325T173000
DTSTAMP:20260407T194918Z
UID:f1cee1795514ffb3acf5febf2cf5b27db275f8dafe1951181fd81149
CATEGORIES:Conferences - Seminars
DESCRIPTION:Nisheeth Vishnoi\, Microsoft Research India\nAbstract\nThe are
 as of approximation algorithms and hardness of approximation (together "ap
 proximability") are the two facets of the question "How close can polynomi
 al-time algorithms come to finding optimal solutions for NP-hard problems?
 " Both are not only practically relevant in areas such as optimization\, m
 achine learning and cryptography but have also received considerable atten
 tion in theoretical computer science for four decades. The last decade\, h
 owever\, has seen an unprecedented progress in this area with deep connect
 ions between approximability\, Fourier analysis and geometry discovered. A
  key player here has been the\, yet unproven\, Unique Games Conjecture (UG
 C).\nIn this talk I will present some of my contributions towards this int
 erplay via the UGC. These include exposing limitations of powerful and gen
 eric algorithmic approaches involving semi-definite programs\, the resolut
 ion of a problem in metric geometry\, and developing a duality between app
 roximation algorithms and hardness reductions in the linear programming wo
 rld. Finally\, I will discuss some of my work on the validity of the enigm
 atic UGC and approximability without this conjecture.Biography\nNisheeth's
  research interests span several aspects of complexity\, algorithms and op
 timization. He has worked primarily in hardness of approximation\, approxi
 mation algorithms and fast algorithms for fundamental cut/flow problems. I
 n addition\, he is also interested in theoretical problems arising out of 
 biology\, machine learning and game theory. Among notable honors\, he is t
 he recipient of the Best Paper Award at FOCS 2005\, IBM Research Pat Goldb
 erg Memorial Award for 2006 and the Indian National Science Academy Young 
 Scientist Award for 2011. He has also authored a monograph "Lx=b" and is t
 he PC chair for FSTTCS 2013.\nHe is currently at Microsoft Research India 
 and is also an adjunct faculty at IIT Kanpur. Prior to this\, he has worke
 d at CNRS\, UC Berkeley\, and IBM India Research Lab.  He received his Ph
 .D. in the ACO program at Georgia Tech in 2004 and completed his Bachelor 
 of Technology in Computer Science and Engg. from IIT Bombay.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR