Goldreich O. Computational Complexity. A Conceptual Perspective

Подождите немного. Документ загружается.

CUUS063 main CUUS063 Goldreich 978 0 521 88473 0 March 31, 2008 18:49

BIBLIOGRAPHY

[130] R. Impagliazzo and M. Yung. Direct Zero-Knowledge Computations. In Crypto87, Springer-

Verlag Lecture Notes in Computer Science (Vol. 293), pages 40–51, 1987.

[131] M. Jerrum, A. Sinclair, and E. Vigoda. A Polynomial-Time Approximation Algorithm for

the Permanent of a Matrix with Non-Negative Entries. Journal of the ACM,Vol.51(4),pages

671–697, 2004.

[132] M. Jerrum, L. Valiant, and V. V. Vazirani. Random Generation of Combinatorial Str uc-

tures from a Uniform Distribution. Theoretical Computer Science, Vol. 43, pages 169–188,

1986.

[133] B. Juba and M. Sudan. Towards Universal Semantic Communication. ECCC, TR07-084,

2007.

[134] V. Kabanets and R. Impagliazzo. Derandomizing Polynomial Identity Tests Means Proving

Circuit Lower Bounds. Computational Complexity, Vol. 13, pages 1-46, 2004. Preliminary

version in 35th STOC, 2003.

[135] N. Kahale. Eigenvalues and Expansion of Regular Graphs. Journal of the ACM,Vol.42(5),

pages 1091–1106, 1995.

[136] R. Kannan, H. Venkateswaran, V. Vinay, and A. C. Yao. A Circuit-Based Proof of Toda’s

Theorem. Information and Computation, Vol. 104 (2), pages 271–276, 1993.

[137] M. Karchmer and A. Wigderson. Monotone Circuits for Connectivity Require Super-

logarithmic Depth. SIAM J. Discrete Math., Vol. 3 (2), pages 255–265, 1990. Preliminary

version in 20th STOC, 1988.

[138] R. M. Karp. Reducibility Among Combinatorial Problems. In Complexity of Computer

Computations, R. E. Miller and J. W. Thatcher (eds.), Plenum Press, pages 85–103,

1972.

[139] R. M. Karp and R. J. Lipton. Some Connections Between Nonuniform and Uniform Com-

plexity Classes. In 12th ACM Symposium on the Theory of Computing, pages 302–309,

1980.

[140] R. M. Karp and M. Luby. Monte-Carlo Algorithms for Enumeration and Reliability Problems.

In 24th IEEE Symposium on Foundations of Computer Science, pages 56-64, 1983.

[141] R. M. Karp and V. Ramachandran. Parallel Algorithms for S hared-Memory Machines. In

Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity,J.van

Leeuwen (ed.), MIT Press/Elsevier, pages 869–942, 1990.

[142] M. J. Kearns and U. V. Vazirani. An Introduction to Computational Learning Theory.MIT

Press, 1994.

[143] S. Khot and O. Regev. Vertex Cover Might Be Hard to Approximate to Within 2 − ε.In18th

IEEE Conference on Computational Complexity, pages 379–386, 2003.

[144] V. M. Khrapchenko. A Method of Determining Lower Bounds for the Complexity of Pi-

Schemes. In Matematicheskie Zametki, Vol. 10 (1), pages 83–92, 1971 (in Russian). English

translation in Mathematical Notes of the Academy of Sciences of the USSR, Vol. 10 (1), pages

474–479, 1971.

[145] J. Kilian. A Note on E fﬁcient Zero-Knowledge Proofs and Arguments. In 24th ACM Sympo-

sium on the Theory of Computing, pages 723–732, 1992.

[146] D. E. Knuth. The Art of Computer Programming,Vol.2(Seminumerical Algorithms).

Addison-Wesley, 1969 (ﬁrst edition) and 1981 (second edition).

[147] A. Kolmogorov. Three Approaches to the Concept of “The Amount of Information.” Probl.

of Inform. Transm., Vol. 1 (1), 1965.

[148] E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1996.

[149] R. E. Ladner. On the Str ucture of Polynomial Time Reducibility. Journal of the ACM, Vol. 22,

1975, pages 155–171.

[150] C. Lautemann. BPP and the Polynomial Hierarchy. Information Processing Letters, Vol. 17,

pages 215–217, 1983.

[151] F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hyper-

cubes. Morgan Kaufmann Publishers, San Mateo, CA, 1992.

595

CUUS063 main CUUS063 Goldreich 978 0 521 88473 0 March 31, 2008 18:49

BIBLIOGRAPHY

[152] L. A. Levin. Universal Search Problems. Problemy Peredaci Informacii 9, pages 115–116,

1973 (in Russian). English translation in Problems of Information Transmission 9, pages

265–266. A better English translation appears in [221].

[153] L. A. Levin. Randomness Conservation Inequalities: Information and Independence in Math-

ematical Theories. Information and Control, Vol. 61, pages 15–37, 1984.

[154] L. A. Levin. Average Case Complete Problems. SIAM Journal on Computing, Vol. 15, pages

285–286, 1986.

[155] L. A. Levin. Fundamentals of Computing. SIGACT News, Education Forum, special 100th

issue, Vol. 27 (3), pages 89–110, 1996.

[156] M. Li and P. Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications.

Springer Verlag, August 1993.

[157] R. J. Lipton. New Directions in Testing. Distributed Computing and Cryptography, J. Feigen-

baum and M. Merritt (eds.), DIMACS Series in Discrete Mathematics and Theoretical Com-

puter Science, American Mathematics Society, Vol. 2, pages 191–202, 1991.

[158] N. Livne. All Natural NPC Problems Have Average-Case Complete Versions. ECCC, TR06-

122, 2006.

[159] C.-J. Lu, O. Reingold, S. Vadhan, and A. Wigderson. Extractors: Optimal up to Constant

Factors. In 35th ACM Symposium on the Theory of Computing, pages 602–611, 2003.

[160] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan Graphs. Combinatorica,Vol.8,pages

261–277, 1988.

[161] M. Luby and A. Wigderson. Pairwise Independence and Derandomization. Foundations and

Trends in Theoretical Computer Science, Vol. (4), 2005. Preliminary version: TR-95-035,

ICSI, Berkeley, 1995.

[162] C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic Methods for Interactive Proof

Systems. Journal of the ACM, Vol. 39 (4), pages 859–868, 1992. Preliminary version in 31st

FOCS, 1990.

[163] F. MacWilliams and N. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1981.

[164] G. A. Margulis. Explicit Construction of Concentrators. Prob. Per. Infor., Vol. 9 (4), pages

71–80, 1973 (in Russian). English translation in Problems of Infor. Trans., pages 325–332,

1975.

[165] S. Micali. Computationally Sound Proofs. SIAM Journal on Computing,Vol.30(4),pages

1253–1298, 2000. Preliminary version in 35th FOCS, 1994.

[166] G. L. Miller. Riemann’s Hypothesis and Tests for Primality. Journal of Computer and System

Science, Vol. 13, pages 300–317, 1976.

[167] P. B. Miltersen and N. V. Vinodchandran. Derandomizing Arthur-Merlin Games Using Hitting

Sets. Computational Complexity, Vol. 14 (3), pages 256–279, 2005. Preliminar y version in

40th FOCS, 1999.

[168] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

[169] M. Naor. Bit Commitment Using Pseudorandom Generators. Journal of Cryptology,Vol.4,

pages 151–158, 1991.

[170] J. Naor and M. Naor. Small-Bias Probability Spaces: Efﬁcient Constructions and Applica-

tions. SIAM Journal on Computing, Vol. 22, pages 838–856, 1993. Preliminary version in

22nd STOC, 1990.

[171] M. Naor and M. Yung. Universal One-Way Hash Functions and Their Cryptographic Appli-

cation. In 21st ACM Symposium on the Theory of Computing, pages 33–43, 1989.

[172] M. Nguyen, S. J. Ong, and S. Vadhan. Statistical Zero-Knowledge Arguments for NP from

Any One-Way Function. In 47th IEEE Symposium on Foundations of Computer Science,

pages 3-14, 2006.

[173] N. Nisan. Pseudorandom Bits for Constant Depth Circuits. Combinatorica, Vol. 11 (1), pages

63–70, 1991.

[174] N. Nisan. Pseudorandom Generators for Space Bounded Computation. Combinatorica,

Vol. 12 (4), pages 449–461, 1992. Preliminary version in 22nd STOC, 1990.

596

CUUS063 main CUUS063 Goldreich 978 0 521 88473 0 March 31, 2008 18:49

BIBLIOGRAPHY

[175] N. Nisan. RL ⊆ SC. Computational Complexity, Vol. 4, pages 1-11, 1994. Preliminary

version in 24th STOC, 1992.

[176] N. Nisan and A. Wigderson. Hardness vs Randomness. Journal of Computer and System

Science, Vol. 49 (2), pages 149–167, 1994. Preliminary version in 29th FOCS, 1988.

[177] N. Nisan and D. Zuckerman. Randomness Is Linear in Space. Journal of Computer and

System Science, Vol. 52 (1), pages 43–52, 1996. Preliminary version in 25th STOC, 1993.

[178] C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1994.

[179] C. H. Papadimitriou and M. Yannakakis. Optimization, Approximation, and Complexity

Classes. In 20th ACM Symposium on the Theory of Computing, pages 229–234, 1988.

[180] N. Pippenger and M. J. Fischer. Relations Among Complexity Measures. Journal of the

ACM, Vol. 26 (2), pages 361–381, 1979.

[181] E. Post. A Variant of a Recursively Unsolvable Problem. Bull. AMS, Vol. 52, pages 264–268,

1946.

[182] M. O. Rabin. Digitalized Signatures. In Foundations of Secure Computation (R. A. DeMillo

et al. eds.), Academic Press, 1977.

[183] M. O. Rabin. Digitalized Signatures and Public Key Functions as Intractable as Factoring.

MIT/LCS/TR-212, 1979.

[184] M. O. Rabin. Probabilistic Algorithm for Testing Primality. Journal of Number Theory,

Vol. 12, pages 128–138, 1980.

[185] R. Raz. A Parallel Repetition Theorem. SIAM Journal on Computing, Vol. 27 (3), pages

763–803, 1998. Extended abstract in 27th STOC, 1995.

[186] R. Raz and A. Wigderson. Monotone Circuits for Matching Require Linear Depth. Journal

of the ACM, Vol. 39 (3), pages 736–744, 1992. Preliminary version in 22nd STOC, 1990.

[187] A. Razborov. Lower Bounds for the Monotone Complexity of some Boolean Functions. In

Doklady Akademii Nauk SSSR, Vol. 281 (4), pages 798–801, 1985 (in Russian). English

translation in Soviet Math. Doklady, Vol. 31, pages 354–357, 1985.

[188] A. Razborov. Lower Bounds on the Size of Bounded-Depth Networks over a Complete Basis

with Logical Addition. In Matematicheskie Zametki, Vol. 41 (4), pages 598–607, 1987 (in

Russian). English translation in Mathematical Notes of the Academy of Sci. of the USSR,

Vol. 41 (4), pages 333–338, 1987.

[189] A. R. Razborov and S. Rudich. Natural Proofs. Journal of Computer and System Science,

Vol. 55 (1), pages 24–35, 1997. Preliminary version in 26th STOC, 1994.

[190] O. Reingold. Undirected ST-Connectivity in Log-Space. In 37th ACM Symposium on the

Theory of Computing, pages 376–385, 2005.

[191] O. Reingold, S. Vadhan, and A. Wigderson. Entropy Waves, the Zig-Zag Graph Product,

and New Constant-Degree Expanders and Extractors. Annals of Mathematics, Vol. 155 (1),

pages 157–187, 2001. Preliminary version in 41st FOCS, pages 3–13, 2000.

[192] H. G. Rice. Classes of Recursively Enumerable Sets and Their Decision Problems. Trans.

AMS, Vol. 89, pages 25–59, 1953.

[193] R. L. Rivest, A. Shamir, and L. M. Adleman. A Method for Obtaining Digital Signatures and

Public Key Cryptosystems. CACM, Vol. 21 (Feb.), pages 120–126, 1978.

[194] D. Ron. Property Testing. In Handbook on Randomization, Volume 2, S. Rajasekaran,

P. M. Pardalos, J. H. Reif, and J. D. P. Rolim (eds.), pages 597–649, 2001.

[195] R. Rubinfeld and M. Sudan. Robust Characterization of Polynomials with Applications to

Program Testing. SIAM Journal on Computing, Vol. 25 (2), pages 252–271, 1996.

[196] M. Saks and S. Zhou. BP

SPACE(S) ⊆ DSPACE(S

3/2

). Journal of Computer and System

Science, Vol. 58 (2), pages 376–403, 1999. Preliminary version in 36th FOCS, 1995.

[197] W. J. Savitch. Relationships Between Nondeterministic and Deterministic Tape Complexities.

Journal of Computer and System Science, Vol. 4 (2), pages 177–192, 1970.

[198] A. Selman. On the Structure of NP. Notices Amer. Math. Soc., Vol. 21 (6), page 310, 1974.

[199] J. T. Schwartz. Fast Probabilistic Algorithms for Veriﬁcation of Polynomial Identities. Journal

of the ACM, Vol. 27 (4), pages 701–717, October 1980.

597

CUUS063 main CUUS063 Goldreich 978 0 521 88473 0 March 31, 2008 18:49

BIBLIOGRAPHY

[200] R. Shaltiel. Recent Developments in Explicit Constructions of Extractors. In Current Trends

in Theoretical Computer Science: The Challenge of the New Century,Vol.1:Algorithms

and Complexity, G. Paun, G. Rozenberg, and A. Salomaa (eds.), World Scientiﬁc, 2004.

Preliminary version in Bulletin of the EATCS 77, pages 67–95, 2002.

[201] R. Shaltiel and C. Umans. Simple Extractors for All Min-Entropies and a New Pseudo-

Random Generator. In 42nd IEEE Symposium on Foundations of Computer Science, pages

648–657, 2001.

[202] A. Shamir. IP = PSPACE. Journal of the ACM, Vol. 39 (4), pages 869–877, 1992. Preliminary

version in 31st FOCS, 1990.

[203] C. E. Shannon. A Symbolic Analysis of Relay and Switching Circuits. Trans. American

Institute of Electrical Engineers, Vol. 57, pages 713–723, 1938.

[204] C. E. Shannon. A Mathematical Theory of Communication. Bell Sys. Tech. Jour., Vol. 27,

pages 623–656, 1948.

[205] C. E. Shannon. Communication Theory of Secrecy Systems. Bell Sys. Tech. Jour., Vol. 28,

pages 656–715, 1949.

[206] A. Shpilka. Lower Bounds for Matrix Product. SIAM Journal on Computing, pages 1185-

1200, 2003.

[207] M. Sipser. A Complexity Theoretic Approach to Randomness. In 15th ACM Symposium on

the Theory of Computing, pages 330–335, 1983.

[208] M. Sipser. Introduction to the Theory of Computation. PWS Publishing, 1997.

[209] R. Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit

Complexity. In 19th ACM Symposium on the Theory of Computing, pages 77–82, 1987.

[210] R. J. Solomonoff. A Formal Theory of Inductive Inference. Information and Control,Vol.7

(1), pages 1–22, 1964.

[211] R. Solovay and V. Strassen. A Fast Monte-Carlo Test for Primality. SIAM Journal on Com-

puting, Vol. 6, pages 84–85, 1977. Addendum in SIAM Journal on Computing,Vol.7,page

118, 1978.

[212] D. A. Spielman. Advanced Complexity Theory, Lectures 10 and 11. Notes (by D. Lewin

and S. Vadhan), March 1997. Available from

http://www.cs.yale.edu/homes/

spielman/AdvComplexity/1998/

as lect10.ps and lect11.ps.

[213] L. J. Stockmeyer. The Polynomial-Time Hierarchy. Theoretical Computer Science,Vol.3,

pages 1–22, 1977.

[214] L. Stockmeyer. The Complexity of Approximate Counting. In 15th ACM Symposium on the

Theory of Computing, pages 118–126, 1983.

[215] V. Strassen. Algebraic Complexity Theor y. In Handbook of Theoretical Computer Science:

Vo lume A: Algorithms and Complexity, J. van Leeuwen (ed.), MIT Press/Elsevier, pages

633–672, 1990.

[216] M. Sudan. Decoding of Reed Solomon Codes Beyond the Error-Correction Bound. Journal

of Complexity, Vol. 13 (1), pages 180–193, 1997.

[217] M. Sudan. Algorithmic Introduction to Coding Theory. Lecture notes, available from

http://theory.csail.mit.edu/ ˜ madhu/FT01/, 2001.

[218] M. Sudan, L. Trevisan, and S. Vadhan. Pseudorandom Generators Without the XOR Lemma.

Journal of Computer and System Science, Vol. 62 (2), pages 236–266, 2001.

[219] R. Szelepcsenyi. A Method of Forced Enumeration for Nondeterministic Automata. Acta

Informatica, Vol. 26, pages 279–284, 1988.

[220] S. Toda. PP Is as Hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing,

Vol. 20 (5), pages 865–877, 1991.

[221] B. A. Trakhtenbrot. A Survey of Russian Approaches to Perebor (Brute Force Search)

Algorithms. Annals of the History of Computing, Vol. 6 (4), pages 384–398, 1984.

[222] L. Trevisan. Extractors and Pseudorandom Generators. Journal of the ACM, Vol. 48 (4),

pages 860–879, 2001. Preliminary version in 31st STOC, 1999.

598

CUUS063 main CUUS063 Goldreich 978 0 521 88473 0 March 31, 2008 18:49

BIBLIOGRAPHY

[223] L. Trevisan. On Uniform Ampliﬁcation of Hardness in NP. In 37th ACM Symposium on the

Theory of Computing, pages 31–38, 2005.

[224] V. Trifonov. An O(log n log log n) Space Algorithm for Undirected st-Connectivity. In 37th

ACM Symposium on the Theory of Computing, pages 623–633, 2005.

[225] A. M. Turing. On Computable Numbers, with an Application to the Entscheidungsproblem.

Proc. Londom Mathematical Soceity, Ser. 2, Vol. 42, pages 230–265, 1936. A Correction,

ibid., Vol. 43, pages 544–546.

[226] C. Umans. Pseudo-Random Generators for All Hardness. Journal of Computer and System

Science, Vol. 67 (2), pages 419–440, 2003.

[227] S. Vadhan. A Study of Statistical Zero-Knowledge Proofs. Ph.D. thesis, MIT, 1999.

Available from

http://www.eecs.harvard.edu/∼salil/papers/phdthesis-

abs.html

[228] S. Vadhan. An Unconditional Study of Computational Zero Knowledge. SIAM Journal on

Computing, Vol. 36 (4), pages 1160–1214, 2006. Extended abstract in 45th FOCS, 2004.

[229] S. Vadhan. Lecture Notes for CS 225: Pseudorandomness, Spring 2007. Available from

http://www.eecs.harvard.edu/∼salil.

[230] L. G. Valiant. The Complexity of Computing the Permanent. Theoretical Computer Science,

Vol. 8, pages 189–201, 1979.

[231] L. G. Valiant. Completeness Classes in Algebra. In 11th ACM Symposium on the Theory of

Computing, pages 249–261, 1979.

[232] L. G. Valiant. A Theory of the Learnable. CACM, Vol. 27 (11), pages 1134–1142, 1984.

[233] L. G. Valiant and V. V. Vazirani. NP Is as Easy as Detecting Unique Solutions. Theoretical

Computer Science, Vol. 47 (1), pages 85–93, 1986.

[234] J. von Neumann. First Draft of a Report on the EDVAC, 1945. Contract No. W-670-ORD-

492, Moore School of Electrical Engineering, Univ. of Pennsylvania. Reprinted (in part) in

Origins of Digital Computers: Selected Papers, Springer-Verlag, pages 383–392, 1982.

[235] J. von Neumann, Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100, pages

295–320, 1928.

[236] I. Wegener. The Complexity of Boolean Functions. Wiley-Teubner, 1987.

[237] I. Wegener. Branching Programs and Binary Decision Diagrams – Theory and Applications.

SIAM Monographs on Discrete Mathematics and Applications, 2000.

[238] A. Wigderson. The Amazing Power of Pairwise Independence. In 26th ACM Symposium on

the Theory of Computing, pages 645–647, 1994.

[239] A. C. Yao. Theory and Application of Trapdoor Functions. In 23rd IEEE Symposium on

Foundations of Computer Science, pages 80–91, 1982.

[240] A. C. Yao. Separating the Polynomial-Time Hierarchy by Oracles. In 26th IEEE Symposium

on Foundations of Computer Science, pages 1-10, 1985.

[241] A. C. Yao. How to Generate and Exchange Secrets. In 27th IEEE Symposium on Foundations

of Computer Science, pages 162–167, 1986.

[242] S. Yekhanin. Towards 3-Query Locally Decodable Codes of Subexponential Length. In 39th

ACM Symposium on the Theory of Computing, pages 266–274, 2007.

[243] R. E. Zippel. Probabilistic Algorithms for Sparse Polynomials. In the Proceedings of

EUROSAM ’79: International Symposium on Symbolic and Algebraic Manipulation,E.

Ng (ed.). Lecture Notes in Computer Science (Vol. 72), pages 216–226, Springer, 1979.

[244] D. Zuckerman. Linear-Degree Extractors and the Inapproximability of Max-Clique and

Chromatic Number. In 38th ACM Symposium on the Theory of Computing, pages 681–690,

2006.

599

CUUS063 main CUUS063 Goldreich 978 0 521 88473 0 March 31, 2008 18:49

600

CUUS063 main CUUS063 Goldreich 978 0 521 88473 0 March 31, 2008 18:49

Index

Author Index

Adleman, L. M., 227, 501

Agrawal, M., 227

Ajtai, M., 337

Aleliunas, R., 228

Arora, S., 406

Babai, L., 405, 406, 578

Barak, B., 498

Ben-Or, M., 405

Blum, M., 140, 227, 277, 278, 335

Borodin, A., 140, 175

Brassard, G., 407

Chaitin, G. J., 285, 307

Chaum, D., 407

Church, A., 43

Cobham, A., 43

Cook, S. A., 97, 98, 229

epeau, C., 407

Difﬁe, W., 277, 501

Dinur, I., 407

Edmonds, J., 43

Even, S., 99

Feige, U., 406, 453

Fortnow , L., 405, 406

Furst, M. L., 474

Goldreich, O., 277, 336, 405, 453, 492, 517

Goldwasser, S., 335, 336, 405, 406, 453, 492,

502, 503 , 505, 572

Hartmanis, J., 140

astad, J., 336, 453, 474

Hellman, M. E., 277, 501

Huang, M., 227

Immerman, N., 175

Impagliazzo, R., 278, 336

Jerrum, M., 229

Karchmer, M., 475

Karloff, H., 405

Karp,R.M.,97, 98, 121, 122,

228

Kayal, N., 227

Kilian, J., 405, 407

Kolmogorov, A., 285, 307

Komlos, J., 337

Ladner, R. E., 98

Lautemann, C., 228

Levin, L. A., 97, 98, 277, 336, 406, 454

Lipton, R. J., 122, 228, 278

Lov

asz, L., 228, 406, 453

Luby, M., 278, 336

Lund, C., 405, 406

Micali, S., 277, 335, 336, 405, 407, 492, 502,

503, 505, 517

Miller, G. L., 227

Moran, S., 578

Motwani, R., 406

Naor, J., 337

Naor, M., 337

Nisan, N., 277, 336, 337, 405

Papadimitriou, C. H., 455

Rabin, M. O., 227

Rackoff, C., 228, 277, 405

Raz, R., 475

Razborov, A. R., 473

Reingold, O., 175, 561

601

CUUS063 main CUUS063 Goldreich 978 0 521 88473 0 March 31, 2008 18:49

INDEX

Rivest, R. L., 501

Ron, D., 453

Rubinfeld, R., 278, 453

Safra, S., 406, 453

Savitch, W. J., 175

Saxe, J. B., 474

Saxena, N., 227

Selman, A. L., 99

Shamir, A., 405, 501

Shannon, C. E., 43, 285, 472, 500

Sipser, M., 228, 229, 474, 572

Solomonoff, R. J., 285

Solovay, R., 227

Stearns, R. E., 140

Stockmeyer, L. J., 121, 229

Strassen, V., 227

Sudan, M., 278, 406, 453

Szegedy, M., 406

Szelepcsenyi, R., 175

Szemer

edi, E., 337

Toda, S., 229, 566

Trevisan, L., 278, 542

Turing, A. M., 43, 354

Vadhan, S., 278, 561

Valiant, L. G., 229

Vazirani, V. V., 229

Wigderson, A., 278, 336, 405, 475, 517,

561

Yacobi, Y., 99

Yannakakis, M., 455

Ya o , A . C . , 277, 335, 336, 474, 517

Zuckerman, D., 337

Subject Index

algorithms, see computability theory

approximate counting, 211–216, 221–224

satisfying assignments to a DNF, 212–214

approximation, 418–429

counting, see approximate counting

hardness, see hardness of approximation

arithmetic circuits, 475–478

average-case complexity, 429–452

Blum-Micali Generator, see pseudorandom

generators

Boolean circuits, 37–42, 72–77, 109–113, 129,

304, 471 –475

bounded fan-in, 39

constant-depth, 42, 314, 473–474

depth, 42

Monotone, 42, 472–473

natural proofs, 306

size, 39–40, 109–110

unbounded fan-in, 39, 41, 42

uniform, 40, 110–111, 155

Boolean formulae, 37, 41–42, 474–475, 585–586

clauses, 41

CNF, 41, 72–77, 585–586

DNF, 42, 585–586

literals, 41

Monotone, 475

Quantiﬁed, 586

Byzantine Agreement, 520

Chebyshev’s Inequality, 525–526, 530

Chernoff Bound, 526–527

Chinese R eminder Theorem, 409

Church-Turing Thesis, 25, 33

circuits, see Boolean circuits

CNF, see Boolean for mulae

Cobham-Edmonds Thesis, 33, 46, 75, 128, 130

coding theory, 546 –554

concatenated codes, 550–551

connection to hardness ampliﬁcation, 257,

266–270

good codes, 551

Hadamard code, 254, 255, 282, 386–387, 549

list decoding, 254, 255, 266–270, 543, 547,

553

locally decodable, 552–553

locally testable, 552–553

Long-Code, 549

Reed-Muller code, 267, 549–550

Reed-Solomon code, 549

unique decoding, 547

commitment schemes, see cryptography

communication complexity, 474–475

complexity classes

⊕P, 566–571

P, 202 –216, 465, 566–571

AC0, 117, 314, 468

AM, 365

BPL, 200–201, 319, 323–325, 467

BPP, 189–193, 195–199, 304–305, 308–312,

319, 465

coNL, 143 , 168–171

coNP, 82, 94–97, 116, 143, 167, 469, 478

coRP, 193–198, 199

distNP, 434–442, 446–452

distPC, 444

SPACE, 139, 144, 166

TIME, 130

602

CUUS063 main CUUS063 Goldreich 978 0 521 88473 0 March 31, 2008 18:49

INDEX

complexity classes (cont.)

ISP, 153

E, 466

EXP, 55, 466, 467

IP, see interactive proof systems, 352, 355, 359,

365, 377 , 466

L, 154–156 , 467

MA, 199 , 365

NC, 155, 167, 468

NEXP, 466

NL, 143 , 164–171, 200, 323, 467

NP, 44–97, 113–116 , 119–121, 143, 164, 167,

315, 356 , 359, 365, 377, 383–404,

465–467, 469, 477, 478

as proof system, 51–53

as search problem, 48–50

optimal search, 92–94

traditional deﬁnition, 55–57, 117–119, 163,

186

NPC, see NP-completeness

NPI, 82

SPACE, 166

two models, 162–164

TIME, 134

P, 44–97, 111, 112, 114, 116, 153–155, 164,

465, 469 , 471, 473

as search problem, 48–50

P/poly, 108–113, 119–121, 468

PC, 48–50, 54–55, 57, 60–70, 72, 75, 88, 89,

92–95, 202 –227, 419, 444

PCP, see probabilistic checkable proof systems

PF, 48–50, 54–55, 444

PH, 113–121, 191, 203, 466, 566–571

PSPACE, 172–175, 359, 467

quasi-P, 314, 466

RL, 200–202, 323, 467

RP, 193–199, 199, 465

sampNP, 446–452

SC, 152, 323

SZK, 378

TC0, 468

tpcBPP, 443

tpcP, 433, 435–436

tpcPF, 444

ZK, see zero-knowledge proof systems, 368,

371, 377

ZPP, 199, 465

computability theory, 17–36

computational indistinguishability, 289, 291, 292,

295–299, 335, 490–491

multiple samples, 296–299

non-triviality, 296

the hybrid technique, 297–299, 303, 312, 322,

335

vs statistical closeness, 296

computational learning theory, 306

computational problems

3SAT, 77, 586

3XC, 78

bipartiteness, 427, 428, 584

Bounded Halting, 70

Bounded Non-halting, 70–71

CEVL, 154

Clique, 80, 420–422, 427, 585

CSAT, 72–77

CSP, 395–399

Determinant, 205, 477–478, 587

Directed Connectivity, 164–171, 201

Exact Set Cover, 79

extracting modular square roots, 588

factoring integers, 97, 99, 102, 484, 488, 505,

588

Graph 2-Colorability, 584

Graph 3-Colorability, 80, 375, 428, 585

Graph Isomorphism, 358, 372, 585

Graph k-Colorability, 427

Graph Non-Isomorphism, 358

Halting Problem, 27–28, 70, 71, 354

Hamiltonian path, 585

Independent Set, 80, 585

kQBF, 123, 586

Perfect Matching, 205–211, 221, 585

Permanent, 205–211, 236, 477–478, 587

primality testing, 99, 192–193, 588

QBF, 172–175, 362, 408, 586

SAT, 64–65, 72–77, 94, 423, 586

Set Cover, 78

st-CONN, 164–171

testing Polynomial Identity, 194–195

TSP, 421

UCONN, 155–162

Undirected Connectivity, 155–162, 165,

201–202, 584

Verte x C ov er, 80, 420, 422, 585

computational tasks and models, 17

computationally sound proof systems

arguments, 407

constant-depth circuits, see Boolean circuits

constraint satisfaction problems, see CSP

Cook-reductions, see Reduction

counting problems, 202–227

approximation, see approximate counting

perfect matching, 205–211

satisfying assignments to a DNF, 204

cryptography, 482–522

coin tossing, 521–522

commitment schemes, 376, 495–496,

520–522

603

CUUS063 main CUUS063 Goldreich 978 0 521 88473 0 March 31, 2008 18:49

INDEX

cryptography (cont.)

computational indistinguishability, see

computational indistinguishability

encryption schemes, 500–507

general protocols, 511–522

hard-core predicates, see one-way functions

hashing, see hashing

message authentication schemes, 507–511

modern vs classical, 483, 500

Oblivious Transfer, 519–520

one-way functions, see one-way functions

pseudorandom functions, see pseudorandom

functions

pseudorandom generators, see pseudorandom

generators

secret sharing, 518–519, 521

signature schemes, 507–511

trapdoor permutations, 488–489, 505–506,

509, 517 , 519–520

Veriﬁable Secret Sharing, 521

zero-knowledge, see zero-knowledge proof

systems

CSP, see computational problems

decision problems, 19, 20, 50–55, 444–446

unique solutions, see unique solutions

diagonalization, 133

direct product theorems, 261–266, 277

dispersers, 540

error-correcting codes, see coding theory

error reduction, 188, 190, 212, 214, 220,

230–232, 351, 355, 356, 368, 383, 403,

407, 572

randomness-efﬁcient, 539–540

expander graphs, 332, 333, 554–565

ampliﬁcation, 556

constructions, 560–565

eigenvalue gap, 555–556

expansion, 555–556

explicitness, 556–557

mixing, 557–559

random walk, 333–334, 559–560

extractors, see randomness extractors

ﬁnite automata, 36

ﬁnite ﬁelds, 586

formulae, see Boolean formulae

fourier coefﬁcients, 329

game theory

Min-Max Principle, 272–273

gap problems, see promise problems

gap theorems, see time gaps

GF(2), 586

GF(2

), 587

odel’s Incompleteness Theorem, 354

graph properties, 426

graph theory, 583–585

Hadamard code, see coding theory

Halting Problem, see computational problems

hard regions, see inapproximable predicates

hardness of approximation

Max3SAT, 401

MaxClique, 403

the PCP connection, 399–403, 421–424

hashing, 527–533

as a random sieve, 215–216, 218–220,

224–227

collision-free, 511

collision-resistant, 511

extraction property, 538

highly independent, 529, 532–533

Leftover Hash Lemma, 529–533

mixing property, 319, 530

pairwise independent, 529–532

universal, 304, 529

Universal One-Way, 511

hierarchy theorems, see time hierarchies

hitters, 535–536

Hoefding Inequality, 527

inapproximable predicates, 255–277

hard regions, 271–274

Information Theory, 249–250, 285, 483

interactive proof systems, 352–368, 405

algebraic methods, 359

Arthur-Merlin, 364, 365, 571–582

computational soundness, 367–368, 497

constant-round, 314, 336, 365

for Graph Non-Isomorphism, 358

for PSPACE, 359–363

hierarchy, 364–365, 571–582

linear speedup, 365

power of the prover, 366–367

public-coin, 314, 364, 365, 571–582

two-sided error, 364, 365

Karp-reductions, see reduction

knowledge complexity, 371

Kolmogorov Complexity, 31–32, 39, 286, 307

Levin-reductions, see reduction

Linear Feedback Shift Registers, 330

list decoding, see coding theory

low-degree tests, see property testing

lower bounds, 469–481

604