# Rishi Saket

According to our database

Collaborative distances:

^{1}, Rishi Saket authored at least 35 papers between 2006 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2019

Hardness of Learning DNFs using Halfspaces.

Electronic Colloquium on Computational Complexity (ECCC), 2019

2017

Tight Hardness of the Non-Commutative Grothendieck Problem.

Theory of Computing, 2017

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2

^{(log n)Ømega(1)}Colors.
SIAM J. Comput., 2017

Hardness of Rainbow Coloring Hypergraphs.

Electronic Colloquium on Computational Complexity (ECCC), 2017

Hardness of learning noisy halfspaces using polynomial thresholds.

Electronic Colloquium on Computational Complexity (ECCC), 2017

On the Approximability of Digraph Ordering.

Algorithmica, 2017

Approximation Algorithms for Stochastic k-TSP.

Proceedings of the 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2017

2016

Bypassing UGC from Some Optimal Geometric Inapproximability Results.

ACM Trans. Algorithms, 2016

Approximating CSPs using LP Relaxation.

Electronic Colloquium on Computational Complexity (ECCC), 2016

Hardness of Bipartite Expansion.

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs.

SIAM J. Discrete Math., 2015

On the hardness of learning sparse parities.

Electronic Colloquium on Computational Complexity (ECCC), 2015

2014

Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2

^{log nΩ(1)}Colors.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Hardness of Finding Independent Sets in 2-Colorable and Almost 2-Colorable Hypergraphs.

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

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

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Hardness of Finding Independent Sets in 2-Colorable Hypergraphs and of Satisfiable CSPs.

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

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

CoRR, 2013

Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover.

Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, 2013

The Approximability of the Binary Paintshop Problem.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Stochastic Vehicle Routing with Recourse.

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Hardness of Finding Independent Sets in Almost q-Colorable Graphs.

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

New and Improved Bounds for the Minimum Set Cover Problem.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

On the hardness of learning intersections of two halfspaces.

J. Comput. Syst. Sci., 2011

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

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

Quasi-Random PCP and Hardness of 2-Catalog Segmentation.

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

Approximate Lasserre Integrality Gap for Unique Games.

Proceedings of the Approximation, 2010

2009

SDP Integrality Gaps with Local ell_1-Embeddability.

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

On hardness of learning intersection of two halfspaces.

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Hardness of Minimizing and Learning DNF Expressions.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

Electronic Colloquium on Computational Complexity (ECCC), 2007

Hardness of Embedding Metric Spaces of Equal Size.

Proceedings of the Approximation, 2007

2006

Frame packing algorithms for automotive applications.

J. Embedded Computing, 2006

Integrality gaps for sparsest cut and minimum linear arrangement problems.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

A 3-Query Non-Adaptive PCP with Perfect Completeness.

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006