[1]   N. Alon and M. Capalbo: Smaller explicit superconcentrators. Internet Math., 1(2):151–163, 2004. [InternetMath:1(2):151–163].

[2]   S. Arora and C. Lund: Hardness of approximation. In Dorit S. Hochbaum, editor, Approximation algorithms for NP-hard problems. PWS, Boston, 1996.

[3]   O. Gabber and Z. Galil: Explicit constructions of linear-sized superconcentrators. Journal of Computer and System Sciences, 22(3):407–420, June 1981. [JCSS:10.1016/0022-0000(81)90040-4].

[4]   V. Guruswami, D. Micciancio, and O. Regev: The complexity of the covering radius problem on lattices and codes. Computational Complexity, 14(2):90–121, 2005. Preliminary version in CCC’04. [doi:10.1007/s00037-005-0193-y].

[5]   I. Haviv and O. Regev: Hardness of the covering radius problem on lattices. In Proc. of 21st Ann. Conf. on Computational Complexity (CCC’06), pp. 145–158. IEEE Computer Society Press, 2006. [CCC:10.1109/CCC.2006.23].

[6]   K.-I. Ko and C.-L. Lin: Non-approximability in the polynomial-time hierarchy. Technical Report 94-2, Dept. of Computer Science, SUNY at Stony Brook, 1994.

[7]   K.-I. Ko and C.-L. Lin: On the longest circuit in an alterable digraph. J. Global Optimization, 7(3):279–295, 1995. [Springer:k74448w88p1483ww].

[8]   A. Lubotzky, R. Phillips, and P. Sarnak: Ramanujan graphs. Combinatorica, 8(3):261–277, 1988. [Springer:k285687344657q53].

[9]   G. A. Margulis: Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51–60, 1988.

[10]   C. H. Papadimitriou and M. Yannakakis: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences, 43(3):425–440, 1991. [JCSS:10.1016/0022-0000(91)90023-X].

[11]   M. Schaefer and C. Umans: Completeness in the polynomial-time hierarchy: A compendium. SIGACT News, 33(3):32–49, September 2002. Guest column in Complexity Theory Column. [SIGACT:10.1145/582475.582484].

[12]   M. Schaefer and C. Umans: Completeness in the polynomial-time hierarchy: Part II. SIGACT News, 33(4):22–36, December 2002. Guest column in Complexity Theory Column. [SIGACT:10.1145/601819.601829].

[13]   C.A. Tovey: A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85–89, 1984. [Elsevier:10.1016/0166-218X(84)90081-7].

[14]   V.V. Vazirani: Approximation algorithms. Springer-Verlag, Berlin, 2001.