Rishi Saket  Rishi Saket photo       

contact information

Researcher
India Research Laboratory, Bangalore, India
  +91dash72dash59207768

links



2016

Hardness of Bipartite Expansion
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
European Symposium on Algorithms (ESA), 2016


2015

Tight Hardness of the Non-commutative Grothendieck Problem
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
European Symposium on Algorithms (ESA), 2015

Approximating CSPs using LP Relaxation
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
Symposium on Foundations of Computer Science (FOCS), 2014




2013


The Approximability of the Binary Paintshop Problem
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
IEEE Conference on Computational Complexity (CCC), 2013


2012

Hardness of Bipartite Expansion with Blocks
Subhash Khot, Rishi Saket
Manuscript, 2012

Hardness of Finding Independent Sets in Almost q-Colorable Graphs
Subhash Khot, Rishi Saket
Symposium on Foundations of Computer Science (FOCS), 2012


Stochastic Vehicle Routing with Recourse
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
Symposium on Discrete Algorithms (SODA), 2012


2011



2010

Quasi-Random PCP and Hardness of 2-Catalog Segmentation
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
APPROX-RANDOM, 2010

On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
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
Symposium on Foundations of Computer Science (FOCS), 2009


2008

Hardness of Minimizing and Learning DNF Expressions
Subhash Khot, Rishi Saket
Symposium on Foundations of Compputer Science (FOCS), 2008

On Hardness of Learning Intersection of Two Halfspaces
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
Symposium on Foundations of Computer Science (FOCS), 2007



2006

Frame Packing Algorithms for Automotive Applications
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
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
Symposium on Theory of Computing (STOC), 2006


2004

Algorithms for Computational Biology: Sequence Analysis
Varun Gupta, Rishi Saket
B.Tech Final Project Report, IIT Delhi, 2004