Rishi Saket
Beginning Fall 2009 I am a post doc at the School of Computer Science at Carnegie Mellon University. My host is Prof. Venkatesan Guruswami.
I completed my PhD under the guidance of Prof. Subhash Khot as part of 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, learning theory, metric embeddings and integrality gaps.
Publications :
SDP Integrality Gaps with Local l1-Embeddability.
with Subhash Khot. To Appear, FOCS 2009.
Hardness of Minimizing and Learning DNF Expressions.
with Subhash Khot. In Proc. 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.
Invited to
SICOMP special issue for 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.