Bypassing UGC from Some Optimal Geometric Inapproximability Results
Agnostic Learning of Monomials by Halfspaces Is Hard
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant
Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
ACM Transactions on Algorithms
2009 50th Annual IEEE Symposium on Foundations of Computer Science
SIAM Journal on Computing
Prasad Raghavendra
Yi Wu
Rajsekar Manokaran
Vitaly Feldman
Moses Charikar
Rishi Saket