18 citations · 35 across the 3 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2006
Pseudorandomness and Combinatorial Constructions
Luca Trevisan
In combinatorics, the probabilistic method is a very powerful tool to prove the existence of combinatorial objects with interesting and useful properties. Explicit constructions of…
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.