Relations between average case complexity and approximation complexity.

Uriel Feige

Browse the full STOC paper archive.