IC Colloquium : Approximability, Analysis and Geometry
Event details
| Date | 25.03.2013 |
| Hour | 16:15 › 17:30 |
| Speaker | Nisheeth Vishnoi, Microsoft Research India |
| Location | |
| Category | Conferences - Seminars |
Abstract
The areas of approximation algorithms and hardness of approximation (together "approximability") are the two facets of the question "How close can polynomial-time algorithms come to finding optimal solutions for NP-hard problems?" Both are not only practically relevant in areas such as optimization, machine learning and cryptography but have also received considerable attention in theoretical computer science for four decades. The last decade, however, has seen an unprecedented progress in this area with deep connections between approximability, Fourier analysis and geometry discovered. A key player here has been the, yet unproven, Unique Games Conjecture (UGC).
In this talk I will present some of my contributions towards this interplay via the UGC. These include exposing limitations of powerful and generic algorithmic approaches involving semi-definite programs, the resolution of a problem in metric geometry, and developing a duality between approximation algorithms and hardness reductions in the linear programming world. Finally, I will discuss some of my work on the validity of the enigmatic UGC and approximability without this conjecture.
Biography
Nisheeth's research interests span several aspects of complexity, algorithms and optimization. He has worked primarily in hardness of approximation, approximation algorithms and fast algorithms for fundamental cut/flow problems. In addition, he is also interested in theoretical problems arising out of biology, machine learning and game theory. Among notable honors, he is the recipient of the Best Paper Award at FOCS 2005, IBM Research Pat Goldberg 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 the PC chair for FSTTCS 2013.
He is currently at Microsoft Research India and is also an adjunct faculty at IIT Kanpur. Prior to this, he has worked 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.
The areas of approximation algorithms and hardness of approximation (together "approximability") are the two facets of the question "How close can polynomial-time algorithms come to finding optimal solutions for NP-hard problems?" Both are not only practically relevant in areas such as optimization, machine learning and cryptography but have also received considerable attention in theoretical computer science for four decades. The last decade, however, has seen an unprecedented progress in this area with deep connections between approximability, Fourier analysis and geometry discovered. A key player here has been the, yet unproven, Unique Games Conjecture (UGC).
In this talk I will present some of my contributions towards this interplay via the UGC. These include exposing limitations of powerful and generic algorithmic approaches involving semi-definite programs, the resolution of a problem in metric geometry, and developing a duality between approximation algorithms and hardness reductions in the linear programming world. Finally, I will discuss some of my work on the validity of the enigmatic UGC and approximability without this conjecture.
Biography
Nisheeth's research interests span several aspects of complexity, algorithms and optimization. He has worked primarily in hardness of approximation, approximation algorithms and fast algorithms for fundamental cut/flow problems. In addition, he is also interested in theoretical problems arising out of biology, machine learning and game theory. Among notable honors, he is the recipient of the Best Paper Award at FOCS 2005, IBM Research Pat Goldberg 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 the PC chair for FSTTCS 2013.
He is currently at Microsoft Research India and is also an adjunct faculty at IIT Kanpur. Prior to this, he has worked 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.
Links
Practical information
- Informed public
- Free
- This event is internal
Contact
- Christine Moscioni