zbMATH — the first resource for mathematics

Randomness vs time: Derandomization under a uniform assumption. (English) Zbl 1052.68034
Summary: We prove that if BPP \(\neq \) EXP, then every problem in BPP can be solved deterministically in subexponential time on almost every input (on every sampleable ensemble for infinitely many input sizes). This is the first deran-domization result for BPP based on uniform, noncryptographic hardness assumptions. It implies the following gap in the deterministic average-case complexities of problems in BPP: either these complexities are always sub-exponential or they contain arbitrarily large exponential functions. We use a construction of a small “pseudorandom” set of strings from a “hard function” in EXP which is identical to that used in the analogous nonuniform results of L. Babai, L. Fortnow, N. Nisan and A. Wigderson [Comput. Complexity 3, 307–318 (1993; Zbl 0802.68054)] and N. Nisan and A. Wigderson [J. Comput. System Sci. 49, 149–167 (1994; Zbl 0821.68057)]. However, previous proofs of correctness assume the “hard function” is not in P/poly. They give a non constructive argument that a circuit distinguishing the pseudorandom strings from truly random strings implies that a similarly sized circuit exists computing the “hard function.” Our main technical contribution is to show that, if the “hard function” has certain properties, then this argument can be made constructive.

68P25 Data encryption (aspects in computer science)
Full Text: DOI
[1] Andreev, A; Clementi, A; Rolim, J, Hitting sets derandomize BPP, XXIII international colloquium on algorithms, logic and programming (ICALP’96), (1996), p. 357-368 · Zbl 1046.68536
[2] Andreev, A; Clementi, A; Rolim, J, Worst-case hardness suffices for derandomization: A new method for hardness – randomness tradeoffs, Theor. comp. sci., 221, 3-18, (1999) · Zbl 0930.68064
[3] Andreev, A; Clementi, A; Rolim, J, A new general derandomization method, J. assoc. comput. Mach., 45, 179-213, (1998) · Zbl 0903.68089
[4] Andreev, A; Clementi, A; Rolim, J; Trevisan, L, Weak random sources, hitting sets, and BPP simulation, SIAM J. comput., 28, 2103-2116, (1999) · Zbl 0943.68064
[5] Bshouty, N; Cleve, R; Gavalda, R; Kannan, S; Tamon, C, Oracles and queries that are sufficient for exact learning, J. comput. system sci., 52, 421-433, (1996) · Zbl 0858.68075
[6] Babai, L; Fortnow, L; Lund, C, Non-deterministic exponential time has two-prover interactive protocols, Comput. complexity, 1, 3-40, (1991) · Zbl 0774.68041
[7] Babai, L; Fortnow, L; Nisan, N; Wigderson, A, BPP has subexponential time simulations unless EXPTIME has publishable proofs, Comput. complexity, 3, 307-318, (1993) · Zbl 0802.68054
[8] Beaver, D; Feigenbaum, J, Hiding instance in multioracle queries, Proc. 7th symposium on theoretical aspects of computer science, Lecture notes on computer science, 415, (1990), p. 37-48 · Zbl 0733.68005
[9] Blum, M; Luby, M; Rubinfeld, R, Self-testing and self-correcting programs with applications to numerical programs, Comput. complexity, 3, 307-318, (1993)
[10] Blum, M; Micali, S, How to generate cryptographically strong sequences of pseudo-random bits, SIAM J. comput., 13, 850-864, (1984) · Zbl 0547.68046
[11] Cai, J.-Y; Nerurkar, A; Sivakumar, D, Hardness and hierarchy theorems for probabilistic time, 31st symposium on theory of computing, (1999), p. 726-735 · Zbl 1346.68095
[12] Goldreich, O; Krawcyk, H; Luby, M, On the existence of pseudorandom generators, SIAM J. comput., 22, 1163-1175, (1993) · Zbl 0795.94011
[13] Goldreich, O; Levin, L.A, A hard-core predicate for all one-way functions, ACM symp. on theory of computing, (1989), p. 25-32
[14] Goldreich, O; Nisan, N; Wigderson, A, On Yao’s XOR-lemma, Eccc tr 95-050, (1995)
[15] Hastad, J; Impagliazzo, R; Levin, L.A; Luby, M, A pseudorandom generator from any one-way function, SIAM J. comput., 28, 1364-1396, (1999) · Zbl 0940.68048
[16] Impagliazzo, R, Hard-core distributions for somewhat hard problems, 36th foundations of computer science, (1995), p. 538-545 · Zbl 0938.68921
[17] R. Impagliazzo, in preparation.
[18] Impaglizzo, R; Shaltiel, R; Wigderson, A, Near-optimal conversion of hardness into pseudo-randomness, 40th foundations of computer science, (1999), p. 181-190
[19] Impaglizzo, R; Shaltiel, R; Wigderson, A, Extractors and pseudo-random generators with optimal seed lengths, 32nd symposium on theory of computing, (2000), p. 1-10 · Zbl 1296.65007
[20] Impagliazzo, R; Wigderson, A, P=BPP unless E has sub-exponential circuits: derandomizing the XOR lemma, Proc. of the 29th symposium on theory of computing, (1997), p. 220-229 · Zbl 0962.68058
[21] Karp, R.M; Lipton, R.J, Turing machines that take advice, L’ensignment math., 28, 191-209, (1982) · Zbl 0529.68025
[22] Levin, L.A, One-way functions and pseudorandom generators, Combinatorica, 7, 357-363, (1987) · Zbl 0641.68061
[23] Luby, M, Pseudorandomness and cryptographic applications, Princeton computer science notes, (1996), Princeton Univ. Press Princeton
[24] Levin, L.A, Average case complete problems, SIAM J. comput., 15, 285-286, (1986) · Zbl 0589.68032
[25] Lipton, R, New directions in testing, (), 191-202
[26] Nisan, N, Pseudo-random bits for constant depth circuits, Combinatorica, 11, 63-70, (1991) · Zbl 0732.68056
[27] Nisan, N; Wigderson, A, Hardness vs randomness, J. comput. system sci., 49, 149-167, (1994) · Zbl 0821.68057
[28] Razborov, A.A; Rudich, S, Natural proofs, J. comput. system sci., 55, 24-35, (1997) · Zbl 0884.68055
[29] Shamir, A, On the generation of cryptographically strong pseudo-random sequences, 8th ICALP, Lecture notes in computer science, 62, (1981), Springer-Verlag Berlin, p. 544-550
[30] Toda, S, PP is as hard as the polynomial – time hierarchy, SIAM J. comput., 20, 865-877, (1991) · Zbl 0733.68034
[31] A. C. Yao, Theory and application of trapdoor functions, in 23rd Foundation of Computer Science, pp. 80-91, 1982.
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.