| Publication | Date of Publication | Type |
|---|
Hardness of learning DNFs using halfspaces
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Approximation algorithms for stochastic \(k\)-TSP
(available as arXiv preprint) | 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
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
| scientific article; zbMATH DE number 7053310 (Why is no real title available?) | 2019-05-10 | Paper |
Bypassing UGC from some optimal geometric inapproximability results
ACM Transactions on Algorithms | 2018-10-30 | Paper |
| Hardness of bipartite expansion | 2018-03-02 | Paper |
On the hardness of learning sparse parities
(available as arXiv preprint) | 2018-03-02 | Paper |
Tight hardness of the non-commutative Grothendieck problem
Theory of Computing | 2018-01-10 | Paper |
On the approximability of digraph ordering
Algorithmica | 2017-10-10 | Paper |
Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
SIAM Journal on Computing | 2017-03-10 | Paper |
Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs
SIAM Journal on Discrete Mathematics | 2015-11-27 | Paper |
On the approximability of digraph ordering
Lecture Notes in Computer Science | 2015-11-19 | Paper |
Approximating CSPs using LP relaxation
Automata, Languages, and Programming | 2015-10-27 | Paper |
Integrality gaps for sparsest cut and minimum linear arrangement problems
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
SDP Integrality Gaps with Local ell_1-Embeddability
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
The Approximability of the Binary Paintshop Problem
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Stochastic vehicle routing with recourse
Automata, Languages, and Programming | 2013-08-12 | Paper |
New and improved bounds for the minimum set cover problem
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 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
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
On the hardness of learning intersections of two halfspaces
Journal of Computer and System Sciences | 2011-01-18 | Paper |
Hardness of Reconstructing Multivariate Polynomials over Finite Fields
SIAM Journal on Computing | 2011-01-17 | Paper |
Approximate Lasserre integrality gap for unique games
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
Automata, Languages and Programming | 2010-09-07 | Paper |
Hardness of Embedding Metric Spaces of Equal Size
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
| scientific article; zbMATH DE number 5485546 (Why is no real title available?) | 2009-01-05 | Paper |
