Derandomized graph products

M. Ajtai, J. Komlós, and E. Szemerédi, Deterministic Simulation in Logspace.Proc. Nineteenth Ann. ACM Symp. Theor. Comput., 1987, 132?140.

N. Alon, Eigenvalues and expanders.Combinatorica 6 (1986), 83?96.

N. Alon andF. R. K. Chung, Explicit construction of linear sized tolerant networks.Discrete Math. 72 (1988), 15?19.

E. Amaldi and V. Kann, The complexity and approximability of finding maximum feasible subsystems of linear relations.Theoret. Comput. Sci., to appear.

S. Arora, L. Babai, J. Stern, and Z. Sweedyk, The Hardness of Approximate Optima in Lattices, Codes and Linear Equations.Proc. 34th Ann. IEEE Symp. Found. Comput. Sci., 1993, 724?733. (Final version submitted toJ. Comput. System Sci.)

S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof Verification and Hardness of Approximation Problems.Proc. 33rd Ann. IEEE Symp. Found. Comput. Sci., 1992, 14?23.

S. Arora and S. Safra, Probabilistic Checking of Proofs; A New Characterization of NP.Proc. 33rd Ann. IEEE Symp. Found. Comput. Sci., 1992, 2?13.

M. Bellare, O. Goldreich, and S. Goldwasser, Randomness in Interactive Proofs.Proc. 31st Ann. IEEE Symp. Found. Comput. Sci., 1990, 563?572.

P. Berman and M. Furer, Approximating maximum independent set in bounded degree graphs.Proc. 5th ACM-SIAM Symp. on Discrete Algorithms, 1994, 365?371.

P. Berman andG. Schnitger, On the Complexity of Approximating the Independent Set Problem.Inform. and Comput. 96 (1992), 77?94.

A. Blum. Ph.D. dissertation, MIT.

A. Cohen and A. Wigderson, Dispersers, deterministic amplification, and weak random sources.Proc. 30th Ann. IEEE Symp. Found. Comput. Sci., 1989, 14?19.

U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy, Approximating Clique is Almost NP-complete.Proc. 32nd Ann. IEEE Symp. Found. Comput. Sci., 1991, 2?12.

O. Gabber andZ. Galil, Explicit Constructions of Linear Sized Superconcentrators.J. Comput. System Sci. 22(3) (1981), 407?420.

M. Garey andD. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979.

M. Halldorsson and J. Radhakrishnan, Greed is good: approximating independent sets in sparse and bounded-degree graphs.Proc. Twenty-sixth Ann. ACM Symp. Theor. Comput., 1994, 439?448.

R. Impagliazzo and D. Zuckerman, How to Recycle Random Bits.Proc. 30th Ann. IEEE Symp. Found. Comput. Sci., 1989, 248?253.

N. Kahale, Better Expansion for Ramanujan Graphs.Proc. 33rd Ann. IEEE Symp. Found. Comput. Sci., 1992, 398?404.

R. M. Karp, Reducibility Among Combinatorial Problems. InComplexity of Computer Computations, ed.R. Miller and J. Thatcher. Plenum Press, 1972, 85?103.

N. Linial and U. Vazirani, Graph Products and Chromatic Numbers.Proc. 30th Ann. IEEE Symp. Found. Comput. Sci., 1989, 124?128.

A. Lubotsky, R. Phillips andP. Sarnak, Ramanujan Graphs.Combinatorica 8(3) (1988), 261?277.

G. A. Margulis, Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and superconcentrators.Problemy Peredachi Informatsii 24 (1988), 51?60 (in Russian). English translation inProblems of Information Transmission 24 (1988), 39?46.

M. Marcus andH. Minc,A Survey of Matrix Theory and Matrix Inequalities. Allyn and Bacon, Inc., Boston, 1964.

C. Papadimitriou andM. Yannakakis, Optimization, Approximation, and Complexity Classes.J. Comput. System Sci. 43 (1991), 425?440.

D. Zuckerman, Simulating BPP Using a General Weak Random Source.Proc. 32nd Ann. IEEE Symp. Found. Comput. Sci. 1991, 79?89.