Rishi Saket

Available identifiers

zbMath Open saket.rishiMaRDI QIDQ619908

List of research outcomes

Publication	Date of Publication	Type
Hardness of learning DNFs using halfspaces	2023-11-14	Paper
Approximation algorithms for stochastic \(k\)-TSP	2020-11-25	Paper
Hardness of rainbow coloring hypergraphs	2020-11-25	Paper
Hardness of finding independent sets in 2-colorable and almost 2-colorable hypergraphs	2019-06-20	Paper
https://portal.mardi4nfdi.de/entity/Q5743431	2019-05-10	Paper
Bypassing UGC from some optimal geometric inapproximability results	2018-10-30	Paper
Hardness of bipartite expansion	2018-03-02	Paper
On the hardness of learning sparse parities	2018-03-02	Paper
Tight hardness of the non-commutative Grothendieck problem	2018-01-10	Paper
On the approximability of digraph ordering	2017-10-10	Paper
Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors	2017-03-10	Paper
Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs	2015-11-27	Paper
On the approximability of digraph ordering	2015-11-19	Paper
Approximating CSPs using LP relaxation	2015-10-27	Paper
Integrality gaps for sparsest cut and minimum linear arrangement problems	2014-11-25	Paper
SDP Integrality Gaps with Local ell_1-Embeddability	2014-07-25	Paper
The Approximability of the Binary Paintshop Problem	2013-10-04	Paper
Stochastic vehicle routing with recourse	2013-08-12	Paper
New and improved bounds for the minimum set cover problem	2012-11-02	Paper
Quasi-random PCP and hardness of 2-catalog segmentation	2012-08-29	Paper
Nearly optimal NP-hardness of vertex cover on \(k\)-uniform \(k\)-partite hypergraphs	2011-08-17	Paper
On the hardness of learning intersections of two halfspaces	2011-01-18	Paper
Hardness of Reconstructing Multivariate Polynomials over Finite Fields	2011-01-17	Paper
Approximate Lasserre integrality gap for unique games	2010-09-10	Paper
On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs	2010-09-07	Paper
Hardness of Embedding Metric Spaces of Equal Size	2009-02-17	Paper
https://portal.mardi4nfdi.de/entity/Q3549718	2009-01-05	Paper

Research outcomes over time

This page was built for person: Rishi Saket