18 citations · 64 across the 9 of their papers we have counts for
Showing 2004Show all
2 papers · 1 filter
cs.CC2004
Some Applications of Coding Theory in Computational Complexity
Luca Trevisan
Error-correcting codes and related combinatorial constructs play an important role in several recent (and old) results in computational complexity theory. In this paper we survey r…
cs.CC2004★ 18 cited
Inapproximability of Combinatorial Optimization Problems
Luca Trevisan
We survey results on the hardness of approximating combinatorial optimization problems.