zbMATH — the first resource for mathematics

Bravely, moderately: a common theme in four recent works. (English) Zbl 1343.68113
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 373-389 (2011).
Summary: We highlight a common theme in four relatively recent works that establish remarkable results by an iterative approach. Starting from a trivial construct, each of these works applies an ingeniously designed sequence of iterations that yields the desired result, which is highly non-trivial. Furthermore, in each iteration, the construct is modified in a relatively moderate manner. The four works we refer to are
the polynomial-time approximation of the permanent of non-negative matrices by M. Jerrum et al. [J. ACM 51, No. 4, 671–697 (2004; Zbl 1204.65044)];
the iterative (Zig-Zag) construction of expander graphs by O. Reingold et al. [Ann. Math. (2) 155, No. 1, 157–187 (2002; Zbl 1008.05101)];
the log-space algorithm for undirected connectivity by O. Reingold [“Undirected ST-connectivity in log-space”, in: Proceedings of the 37th annual ACM symposium on theory of computing, STOC 2005. New York, NY: ACM. 376–385 (2005; doi:10.1145/1060590.1060647)];
and, the alternative proof of the PCP Theorem by I. Dinur [in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. New York, NY: ACM Press. 241–250 (2006; Zbl 1301.68133)].

For the entire collection see [Zbl 1220.68005].

68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68W25 Approximation algorithms
PDF BibTeX Cite
Full Text: DOI
[1] Aleliunas, R., Karp, R.M., Lipton, R.J., Lovász, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: 20th FOCS, pp. 218–223 (1979)
[2] Alon, N.: Eigenvalues and expanders. Combinatorica 6, 83–96 (1986) · Zbl 0661.05053
[3] Alon, N., Milman, V.D.: {\(\lambda\)} 1, Isoperimetric Inequalities for Graphs and Superconcentrators. J. Combinatorial Theory, Ser. B 38, 73–88 (1985) · Zbl 0549.05051
[4] Armoni, R., Ta-Shma, A., Wigderson, A., Zhou, S.: SL L 4/3. In: 29th STOC, pp. 230–239 (1997) · Zbl 0968.68118
[5] Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof Verification and Intractability of Approximation Problems. JACM 45, 501–555 (1998); Preliminary version in 33rd FOCS (1992) · Zbl 1065.68570
[6] Arora, S., Safra, S.: Probabilistic Checkable Proofs: A New Characterization of NP. JACM 45, 70–122 (1998); Preliminary version in 33rd FOCS (1992) · Zbl 0903.68076
[7] Babai, L., Fortnow, L., Levin, L., Szegedy, M.: Checking Computations in Polylogarithmic Time. In: 23rd STOC, pp. 21–31 (1991)
[8] Bellare, M., Goldreich, O., Sudan, M.: Free Bits, PCPs and Non-Approximability – Towards Tight Results. SICOMP 27(3), 804–915 (1998); Extended abstract in 36th FOCS (1995) · Zbl 0912.68041
[9] Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Robust PCPs of proximity, Shorter PCPs and Applications to Coding. In: 36th STOC, pp. 1–10 (2004); Full version in ECCC, TR04-021 (2004) · Zbl 1118.68071
[10] Ben-Sasson, E., Sudan, M.: Simple PCPs with Poly-log Rate and Query Complexity. In: ECCC, TR04-060 (2004) · Zbl 1192.68287
[11] Broder, A.: How hard is it to marry at random (On the approximation of the Permanent). In: 18th STOC, pp. 50–58 (1986)
[12] Dinur, I.: The PCP Theorem by Gap Amplification. In: 38th STOC, pp. 241–250 (2006) · Zbl 1301.68133
[13] Dinur, I., Reingold, O.: Assignment-testers: Towards a combinatorial proof of the PCP-Theorem. In: 45th FOCS, pp. 155–164 (2004) · Zbl 1127.68031
[14] Feige, U., Goldwasser, S., Lovász, L., Safra, S., Szegedy, M.: Approximating Clique is almost NP-complete. JACM 43, 268–292 (1996); Preliminary version in 32nd FOCS (1991) · Zbl 0882.68129
[15] Goldreich, O.: Computational Complexity: A Conceptual Perspective. Cambridge University Press, Cambridge (2008) · Zbl 1154.68056
[16] Gaber, O., Galil, Z.: Explicit Constructions of Linear Size Superconcentrators. JCSS 22, 407–420 (1981) · Zbl 0487.05045
[17] Jerrum, M., Sinclair, A.: Approximating the Permanent. SICOMP 18, 1149–1178 (1989) · Zbl 0723.05107
[18] Jerrum, M., Sinclair, A., Vigoda, E.: A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Non-Negative Entries. JACM 51(4), 671–697 (2004); Preliminary version in 33rd STOC pp. 712–721 (2001) · Zbl 1204.65044
[19] Linial, N., Samorodnitsky, A., Wigderson, A.: A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. Combinatorica 20(4), 545–568 (2000) · Zbl 0973.15004
[20] Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan Graphs. Combinatorica 8, 261–277 (1988) · Zbl 0661.05035
[21] Margulis, G.A.: Explicit Construction of Concentrators. Prob. Per. Infor. 9(4), 71–80 (1973) (in Russian); English translation in Problems of Infor. Trans., pp. 325–332 (1975) · Zbl 0312.22011
[22] Nisan, N.: Pseudorandom Generators for Space Bounded Computation. Combinatorica 12(4), 449–461 (1992) · Zbl 0759.68024
[23] Nisan, N.: \({\mathcal RL}\subseteq{\mathcal SC}\) . Journal of Computational Complexity 4, 1–11 (1994) · Zbl 0806.68043
[24] Nisan, N., Zuckerman, D.: Randomness is Linear in Space. JCSS 52(1), 43–52 (1996) · Zbl 0846.68041
[25] Reingold, O.: Undirected ST-Connectivity in Log-Space. In: 37th STOC (2005) · Zbl 1192.68374
[26] Reingold, O., Vadhan, S., Wigderson, A.: Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. Annals of Mathematics 155(1), 157–187 (2001); Preliminary version in 41st FOCS, pp. 3–13 (2000) · Zbl 1008.05101
[27] Rozenman, E., Vadhan, S.: Derandomized Squaring of Graphs. In: Chekuri, C., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) APPROX 2005 and RANDOM 2005. LNCS, vol. 3624, pp. 436–447. Springer, Heidelberg (2005) · Zbl 1142.05331
[28] Valiant, L.G.: The Complexity of Computing the Permanent. Theoretical Computer Science 8, 189–201 (1979) · Zbl 0415.68008
[29] Wittgenstein, L.: Tractatus Logico-Philosophicus (1922)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.