Rishi Saket
I am a fourth year PhD student in the Theory Group of the College of Computing at Georgia Tech. I received my bachelor's degree from the Computer Science and Engineering Department at IIT Delhi in August 2004.
I am interested in problems related to hardness of approximation, PCPs, metric embeddings, lower bounds etc.
My CV pdf.
Publications :
Hardness of Minimizing and Learning DNF Expressions.
with Subhash Khot. To appear in FOCS 2008.
On Hardness of Learning Intersection of Two Halfspaces.
with Subhash Khot. In Proc. STOC 2008.
Hardness of Reconstructing Multivariate Polynomials over Finite Fields.
with Parikshit Gopalan and Subhash Khot. In Proc. FOCS 2007.
Hardness of Embedding Metric Spaces of Equal
Size.
with Subhash Khot. In Proc. Approx 2007.
A 3-Query Non-Adaptive PCP with Perfect Completeness.
with Subhash A. Khot. In Proc. Complexity 2006.
Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement Problems
with Nikhil Devanur, Subhash Khot and Nisheeth Vishnoi. In Proc. STOC 2006.
One of my friends has a new startup Flipkart.com.