[1]   Leonard Berman and Juris Hartmanis: On isomorphisms and density of NP and other complete sets. SIAM J. Comput., 6(2):305–322, 1977. Preliminary version in STOC’76. [doi:10.1137/0206023]

[2]   Uriel Feige, Michael Langberg, and Kobbi Nissim: On the hardness of approximating NP witnesses. In Proc. 3rd Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’00), pp. 120–131. Springer, 2000. [doi:10.1007/3-540-44436-X_13]

[3]   Anna Gál, Shai Halevi, Richard J. Lipton, and Erez Petrank: Computing from partial solutions. In Proc. 14th IEEE Conf. on Computational Complexity (CCC’99), pp. 34–45. IEEE Comp. Soc. Press, 1999. [doi:10.1109/CCC.1999.766260]

[4]   Venkatesan Guruswami: List Decoding of Error-Correcting Codes (Winning Thesis of the 2002 ACM Doctoral Dissertation Competition). Volume 3282 of Lecture Notes in Computer Science. Springer, 2005. [doi:10.1007/b104335]

[5]   Venkatesan Guruswami and Atri Rudra: Soft decoding, dual BCH codes, and better list-decodable ϵ-biased codes. IEEE Trans. Inform. Theory, 57(2):705–717, 2011. Preliminary version in CCC’08. See also at ECCC. [doi:10.1109/TIT.2010.2095193]

[6]   Venkatesan Guruswami and Madhu Sudan: List decoding algorithms for certain concatenated codes. In Proc. 32nd STOC, pp. 181–190. ACM Press, 2000. [doi:10.1145/335305.335327]

[7]   Samir Khuller: Algorithms Column: the Vertex Cover problem. SIGACT News, 33(2):31–33, 2002. [doi:10.1145/564585.564598]

[8]   Ravi Kumar and D. Sivakumar: Proofs, codes, and polynomial-time reducibilities. In Proc. 14th IEEE Conf. on Computational Complexity (CCC’99), pp. 46–53. IEEE Comp. Soc. Press, 1999. [doi:10.1109/CCC.1999.766261]

[9]   George L. Nemhauser and Leslie E. Trotter, Jr.: Vertex packings: Structural properties and algorithms. Mathematical Programming, 8(1):232–248, 1975. [doi:10.1007/BF01580444]

[10]   Daniel Sheldon and Neal E. Young: Hamming approximation of NP witnesses. Unpublished manuscript, 2003.

[11]   Michael Sipser: Introduction to the Theory of Computation. Thomson Course Technology, 2006.