SIGACT news complexity theory column 51

ABSTRACT

Warmest thanks to guest columnist Oded Goldreich for this issue's article. Also, I'd like to commend to all readers the web directory, www.wisdom.weizmann.ac.il/~oded/cc-texts.html, that appears as reference [15] of Oded's column. This directory is a real treasure trove.

REFERENCES

• 1: R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th IEEE Symposium on Foundations of Computer Science, pages 218--223, 1979.
• 2: N Alon, Eigen values and expanders, Combinatorica, v.6 n.2, p.83-96, 1986 [doi>10.1007/BF02579166]
• 3: N. Alon and V. D. Milman. λ1, Isoperimetric Inequalities for Graphs and Superconcentrators, J. Combinatorial Theory, Ser. B, Vol. 38, pages 73--88, 1985.
• 4: Roy Armoni , Amnon Ta-Shma , Avi Wigderson , Shiyu Zhou, SL ⊆L^4/3, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.230-239, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258593]
• 5: Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
• 6: Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
• 7: László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
• 8: Mihir Bellare , Oded Goldreich , Madhu Sudan, Free Bits, PCPs, and Nonapproximability---Towards Tight Results, SIAM Journal on Computing, v.27 n.3, p.804-915, June 1998 [doi>10.1137/S0097539796302531]
• 9: Eli Ben-Sasson , Oded Goldreich , Prahladh Harsha , Madhu Sudan , Salil Vadhan, Robust pcps of proximity, shorter pcps and applications to coding, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007361]
• 10: E. Ben-Sasson and M. Sudan. Simple PCPs with Poly-log Rate and Query Complexity. ECCC, TR04-060, 2004.
• 11: A Z Broder, How hard is it to marry at random? (On the approximation of the permanent), Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.50-58, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12136]
• 12: I. Dinur. The PCP Theorem by Gap Amplification. ECCC, TR05-046, 2005.
• 13: Irit Dinur , Omer Reingold, Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.155-164, October 17-19, 2004 [doi>10.1109/FOCS.2004.16]
• 14: U. Feige , S. Goldwasser , L. Lovász , S. Safra , M. Szegedy, Approximating clique is almost NP-complete (preliminary version), Proceedings of the 32nd annual symposium on Foundations of computer science, p.2-12, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185341]
• 15: O. Goldreich. Proving that Undirected Connectivity is in L (with a long appendix on expander graphs). Dec. 2005. Available from http://www.wisdom.weizmann.ac.il/~oded/cc-texts.html
• 16: O. Gaber and Z. Galil. Explicit Constructions of Linear Size Superconcentrators. Journal of Computer and System Science, Vol. 22, pages 407--420, 1981.
• 17: M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
• 18: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM (JACM), v.51 n.4, p.671-697, July 2004 [doi>10.1145/1008731.1008738]
• 19: N. Linial, A. Samorodnitsky, and A. Wigderson. A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Combinatorica, Vol. 20 (4), pages 545--568, 2000.
• 20: A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan Graphs. Combinatorica, Vol. 8, pages 261--277, 1988.
• 21: G.A. Margulis. Explicit Construction of Concentrators. (In Russian.) Prob. Per. Infor. 9 (4) (1973), 71--80. English translation in Problems of Infor. Trans., pages 325--332, 1975.
• 22: N. Nisan. Pseudorandom Generators for Space Bounded Computation. Combinatorica, Vol. 12 (4), pages 449--461, 1992.
• 23: Noam Nisan, RL⊆SC , Computational Complexity, v.4 n.1, p.1-11, Jan. 1994 [doi>10.1007/BF01205052]
• 24: Noam Nisan , David Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences, v.52 n.1, p.43-52, Feb. 1996 [doi>10.1006/jcss.1996.0004 ]
• 25: Omer Reingold, Undirected ST-connectivity in log-space, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060647]
• 26: O. Reingold , S. Vadhan , A. Wigderson, Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.3, November 12-14, 2000
• 27: E. Rozenman and S. Vadhan. Derandomized Squaring of Graphs. In Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM'05), LNCS Vol. 3624, Springer, pages 436--447, 2005.
• 28: L. G. Valiant. The Complexity of Computing the Permanent. Theoretical Computer Science, Vol. 8, pages 189--201, 1979.
• 29: L. Wittgenstein. Tractatus Logico-Philosophicus, 1922.

INDEX TERMS

Primary Classification:
  A. General Literature
  A.m MISCELLANEOUS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes