# Rishi Saket

## contact information

Researcher

India Research Laboratory, Bangalore, India

+917259207768

India Research Laboratory, Bangalore, India

+917259207768

## links

**2018**

Hardness of learning noisy halfspaces using polynomial thresholds

Arnab Bhattacharyya, Suprovat Ghoshal and Rishi Saket

Arnab Bhattacharyya, Suprovat Ghoshal and Rishi Saket

*Conference on Learning Theory (COLT)*, 2018**2017**

Approximation Algorithms for Stochastic k-TSP

Alina Ene, Viswanath Nagarajan, and Rishi Saket

Alina Ene, Viswanath Nagarajan, and Rishi Saket

*Foundations of Software Technology and Theoretical Computer Science (FSTTCS)*, 2017
Hardness of Rainbow Coloring Hypergraphs

Venkatesan Guruswami and Rishi Saket

Venkatesan Guruswami and Rishi Saket

*Foundations of Software Technology and Theoretical Computer Science (FSTTCS)*, 2017**2016**

Hardness of Bipartite Expansion

Subhash Khot and Rishi Saket

Subhash Khot and Rishi Saket

*European Symposium on Algorithms (ESA), 2016*
On the Hardness of Learning Sparse Parities

Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, and Rishi Saket

Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, and Rishi Saket

*European Symposium on Algorithms (ESA), 2016***2015**

Tight Hardness of the Non-commutative Grothendieck Problem

Jop Briet, Oded Regev, Rishi Saket

Jop Briet, Oded Regev, Rishi Saket

*Symposium on Foundations of Computer Science (FOCS)*, 2015
On the Approximability of Digraph Ordering

Sreyash Kenkre, Vinayaka Pandit, Manish Purohit, Rishi Saket

Sreyash Kenkre, Vinayaka Pandit, Manish Purohit, Rishi Saket

*European Symposium on Algorithms (ESA)*, 2015
Approximating CSPs using LP Relaxation

Subhash Khot, Rishi Saket

Subhash Khot, Rishi Saket

*International Colloquium on Automata, Languages and Programming (ICALP)*, 2015**2014**

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2^{(log n)^{Omega(1)}} Colors

Subhash Khot, Rishi Saket

Subhash Khot, Rishi Saket

*Symposium on Foundations of Computer Science (FOCS)*, 2014
Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs

Rishi Saket

Rishi Saket

*IEEE Conference on Computational Complexity (CCC)*, 2014
Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs

Subhash Khot, Rishi Saket

Subhash Khot, Rishi Saket

*Symposium on Discrete Algorithms (SODA)*, 2014**2013**

A PTAS for the Classical Ising Spin Glass Problem on the Chimera Graph Structure

Rishi Saket

Rishi Saket

*Manuscript*, 2013
The Approximability of the Binary Paintshop Problem

Anupam Gupta, Satyen Kale, Viswanath Nagarajan, Rishi Saket, Baruch Schieber

Anupam Gupta, Satyen Kale, Viswanath Nagarajan, Rishi Saket, Baruch Schieber

*APPROX-RANDOM*, 2013
Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover

Sushant Sachdeva, Rishi Saket

Sushant Sachdeva, Rishi Saket

*IEEE Conference on Computational Complexity (CCC)*, 2013**2012**

Hardness of Finding Independent Sets in Almost q-Colorable Graphs

Subhash Khot, Rishi Saket

Subhash Khot, Rishi Saket

*Symposium on Foundations of Computer Science (FOCS)*, 2012
New and Improved Bounds for the Minimum Set Cover Problem

Rishi Saket, Maxim Sviridenko

Rishi Saket, Maxim Sviridenko

*APPROX-RANDOM*, 2012
Stochastic Vehicle Routing with Recourse

Inge Li Goertz, Viswanath Nagarajan, Rishi Saket

Inge Li Goertz, Viswanath Nagarajan, Rishi Saket

*International Colloquium on Automata, Languages and Programming (ICALP)*, 2012
Bypassing UGC from some optimal geometric inapproximability results

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

*Symposium on Discrete Algorithms (SODA)*, 2012**2011**

Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs

Sushant Sachdeva, Rishi Saket

Sushant Sachdeva, Rishi Saket

*APPROX-RANDOM*, 2011**2010**

Quasi-Random PCP and Hardness of 2-Catalog Segmentation

Rishi Saket

Rishi Saket

*Foundations of Software Technology and Theoretical Computer Science (FSTTCS)*, 2010
Approximate Lasserre Integrality Gap for Unique Games

Subhash Khot, Preyas Popat, Rishi Saket

Subhash Khot, Preyas Popat, Rishi Saket

*APPROX-RANDOM*, 2010
On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs

Venkatesan Guruswami, Rishi Saket

Venkatesan Guruswami, Rishi Saket

*International Colloquium on Automata, Languages and Programming (ICALP)*, 2010**2009**

SDP Integrality Gaps with Local l1-Embeddability

Subhash Khot, Rishi Saket

Subhash Khot, Rishi Saket

*Symposium on Foundations of Computer Science (FOCS)*, 2009**2008**

Hardness of Minimizing and Learning DNF Expressions

Subhash Khot, Rishi Saket

Subhash Khot, Rishi Saket

*Symposium on Foundations of Compputer Science (FOCS)*, 2008
On Hardness of Learning Intersection of Two Halfspaces

Subhash Khot, Rishi Saket

Subhash Khot, Rishi Saket

*Symposium on Theory of Computing (STOC)*, 2008**2007**

Hardness of Reconstructing Multivariate Polynomials over Finite Fields

Parikshit Gopalan, Subhash Khot, Rishi Saket

Parikshit Gopalan, Subhash Khot, Rishi Saket

*Symposium on Foundations of Computer Science (FOCS)*, 2007**2006**

Frame Packing Algorithms for Automotive Applications

Nicolas Navet, Rishi Saket

Nicolas Navet, Rishi Saket

*Journal of Embedded Computing**2*(*1*), 93-102, 2006
A 3-Query Non-Adaptive PCP with Perfect Completeness

Subhash Khot, Rishi Saket

Subhash Khot, Rishi Saket

*IEEE Conference on Computational Complexity (CCC), 2006*
Integrality Gaps for Sparsest Cut and Minimum Linear Arrangement Problems

Nikhil Devanur, Subhash Khot, Rishi Saket, Nisheeth Vishnoi

Nikhil Devanur, Subhash Khot, Rishi Saket, Nisheeth Vishnoi

*Symposium on Theory of Computing (STOC)*, 2006**2004**

Algorithms for Computational Biology: Sequence Analysis

Varun Gupta, Rishi Saket

Varun Gupta, Rishi Saket

*B.Tech Final Project Report, IIT Delhi*, 2004