List Decoding in Average-Case Complexity and Pseudorandomness
Venkatesan Guruswami · 2006
This is a brief survey into the applications of list decoding in complexity theory, specifically in relating the worst-case and average-case complexity of computational problems, and in construction of pseudorandom generators. Since we do not have space for full proofs, the aim is to give a flavor of the utility of list decoding in these settings together with pointers to where further details can be found.