E. Allender
ABSTRACT
If secure pseudorandom generators exist, then probabilistic computation does not uniformly speed up deterministic computation. If sets in P must contain infinitely many noncomplex strings, then nondeterministic computation does not uniformly speed up deterministic computation. Connections are drawn between pseudorandom generation, generalized Kolmogorov complexity, and immunity properties of complexity classes.
- Ad-79.L. Adleman, Time,space, and randornnessTechnical Report MIT/LCS/TM-~3~Google Scholar
- AH-86.L. Adleman and M.-D. Huang, these proceedings.Google Scholar
- AW-85.M. Ajtai and A. Wigderson., Determirdetie simulation of probabilistic constant depth circuits, Proc. 26th IEEE Symposium on Foundations of Computer Science, pp. 11-19. Google ScholarDigital Library
- AR-86.E. W. Allender and It. Rubinstein, P-printable sets, submitted for publication. Preliminary versions of this work may be found in {AI-86, Ru-86}.Google Scholar
- Al-86.E.W. Allender, The complexity of sparse sets in P, Structure in Complexity Theory Conference, Lecture Notes in Computer Science 223, pp. 1-11. Google ScholarDigital Library
- BB-86.J.L. Balcazar and R. V. Book, Sets with small generalized Kolmogorov eomplezity, to appear in Acts Infbrmatica.A preliminary version appeared as On generalized Kolmogorov complezity,Proc. 3rd Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 210, pp. 334-340. Google ScholarDigital Library
- BM-84.M. Blum and S. Micali, How to oer terate ~ryptooraphieally strong sequences of pseudo-random bits, SIAM J. Comput. 13, 850-864. Google ScholarDigital Library
- BH-86.R. Boppana and ItHirscMeld, Paeudorandom generators and eomp, lezity classes, manuscript, M.I.T.Google Scholar
- Br-81.G. Brassard, A time.luck tradeoff in relativized cryptography, J. Computer' and System Sciences 22, 280-311.Google ScholarCross Ref
- Ch-66.G. Chaitin, On the length of programs for computing finite binary sequenees, J. ACM 13, 547-569. Google ScholarDigital Library
- ELY-82.S. Even, T. Long, and Y. Yacobi, A note on deterministic and nondeterministie time complexity, Information and Control 55, 117-124.Google Scholar
- GHS-86.J. Geske, D. Huynh, and A. Selm~m, A hierarchy theorem for almost everywhere complex sets with application to polynomial complexity degrees, Proc. 4th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Not.._.!E.,s in Com._..~ purer Science. Google ScholarDigital Library
- GK-86.S. Goldwazser and J. Killian, Almost all primes can be quickly certified, Pros. 18th Annual ACM Symposium on Theory of Computing, pp. 316-329. Google ScholarDigital Library
- GM-84.S. Goldwasser and S. Micali, Probabilistic en,,ryption, J. Computer and System Sciences 28, 270-299.Google ScholarCross Ref
- Ha-83.J. Hartmanis, Generalized Kolmogorov complexity and the structure of feasible computations, Proc. 24th IEEE Symposium on Foundations of Computer Science, pp. 439-445. Google ScholarDigital Library
- He-86.L. Hemachandra, Can P and NP manufacture randomnessf, manuscript.Google Scholar
- HU-79.J. E. Hopcroft and J. D. Ullman, Introduction to Automata The.__~9__~a Lang:~_ages, and Computation, Addison- Wesley, Reading, Mass. Google ScholarDigital Library
- Hu-86.D. T. Huynh, Resource-bounded Kolmogorov complexity of hard languatles, Structure in Complexity Theory Confor once, Lecture Notesin Computer Science 223, pp. 184-195. Google ScholarDigital Library
- Ko-86.K.-I. Ks, On the notion of infinite pzeu. dorandom sequences, to appear in Theoretical Computer Science,Google Scholar
- KOSW-86.K.-I. Ks, P. Orponen, U. SchSning, and O. Watanabe, What is a hard instance of a computational problem? Structure in Complexity Theory Conference, Lecture Notes in Comvuter Science 223, pp. 197-217. Google ScholarDigital Library
- Ko-65.A. Kolmogorov, Three approaches to the quantitative definition of randomness, Prob. info. Transmission 1, 1-7.Google Scholar
- Le-73.L. Levin, Universal sequential search problems, Problems Inform. Transmission 9~ 265-266.Google Scholar
- Le-84.L. Levin, Randomness conservation inequalities; injormation and independence in mathematical theories, Information and Control 61, 15-37. Google ScholarDigital Library
- Le-85.L. Levin, One-way /unctions and pseudorandom generators, Proc. 17th Annual A CM Symposium on Theory of Computing, pp. 363-365. Google ScholarDigital Library
- Lo-86.Luc Longpre, Resource bounded Kolms/orgy complexity, a link between computational complexity and information theory, Doctoral Dissertation, Cornell University. Google ScholarDigital Library
- Pe-80.G. Peterson, Succinct representations, random strings and complexity classes, Proc. 21st IEEE Symposium on Foundations of Computer Science, pp. 86-95. Google ScholarDigital Library
- RT-84.J. Reif and j. Tygar, Efficient parallel pseudo-random number generation, Tech. Report TR-07-84, Harvard University.Google Scholar
- Ru-86.R. Rubinstein, A note on sets with small generalized Kolmogorov complexity, Technical Report TR #86-4, Iowa State University.Google Scholar
- Sc-85.U. SchSning, Complexity and Structure, Lecture Notes in Computer Science 211. Google ScholarDigital Library
- Sh-81.A. Sh~mir, On the generation of erl/ptographlcalllt strong pseudorandom sequences, A CM Transactions on Computer Systems 1, 38-44. Google ScholarDigital Library
- Si-83.M. Sipser, A complexity theoretic approach to randomness, Proc. 15th Annual ACM Symposium on Theory of Computing, pp. 330-335. Google ScholarDigital Library
- Si-87.M. Sipser, Personal Communication.Google Scholar
- Wa-86.O. Watanabe, Generalized Kolmogorov complezitli of computations, manuscript.Google Scholar
- Wi-83.R. Wilber, Randomness and the densitlt of hard problems, Proc. 24th IEEE Symposium on Foundations of Computer Science, pp. 335-342. Google ScholarDigital Library
- Ya-82.A. Yao, Theory and applications of trapdoor functions, Proc. 23rd IEEE Symposium on Foundations of Computer Science, pp. 80-91. Google ScholarCross Ref
Index Terms
- Some consequences of the existence of pseudorandom generators
Recommendations
Paradigms for Unconditional Pseudorandom Generators
This is a survey of unconditional pseudorandom generators (PRGs). A PRG uses a short, truly random seed to generate a long, "pseudorandom" sequence of bits. To be more specific, for each restricted model of computation (e.g., bounded-depth circuits or ...
Extractors and pseudorandom generators
We introduce a new approach to constructing extractors. Extractors are algorithms that transform a “weakly random” distribution into an almost uniform distribution. Explicit constructions of extractors have a variety of important applications, and tend ...
Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of ComputingAssume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. We prove under a precise version of this ...
Comments