11 citations · 27 across the 17 of their papers we have counts for
Showing 2010 · cs.CCShow all
2 papers · 2 filters
cs.CC2010
A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem
Per Austrin, Subhash Khot
We present a simple deterministic gap-preserving reduction from SAT to the Minimum Distance of Code Problem over $\F_2$. We also show how to extend the reduction to work over any f…
cs.CC2010★ 2 cited
Improved Inapproximability For Submodular Maximization
Per Austrin
We show that it is Unique Games-hard to approximate the maximum of a submodular function to within a factor 0.695, and that it is Unique Games-hard to approximate the maximum of a…