Document Open Access Logo

Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity

Authors Yanyi Liu, Rafael Pass

PDF
Thumbnail PDF

File

LIPIcs.CCC.2022.35.pdf
  • Filesize: 0.74 MB
  • 17 pages

Document Identifiers

Author Details

Yanyi Liu
  • Cornell Tech, New York, NY, USA
Rafael Pass
  • Cornell Tech, New York, NY, USA
  • Tel-Aviv University, Israel

Funding

  • Pass, Rafael: Worked done while being on a sabbatical at Tel-Aviv University. Supported in part by NSF Award SATC-1704788, NSF Award RI-1703846, AFOSR Award FA9550-18-1-0267, and a JP Morgan Faculty Award. This material is based upon work supported by DARPA under Agreement No. HR00110C0086. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government or DARPA.

Acknowledgements

We thank the anonymous reviewers for many helpful comments, and most notably for making us aware of [Hirahara, 2020].

Cite As Get BibTex

Yanyi Liu and Rafael Pass. Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CCC.2022.35

Abstract

A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. We consider this problem in the context of promise problems (i.e,. the prBPP v.s. prP problem) and show that for all sufficiently large constants c, the following are equivalent:  
- prBPP = prP. 
- For every BPTIME(n^c) algorithm M, and every sufficiently long z ∈ {0,1}ⁿ, there exists some x ∈ {0,1}ⁿ such that M fails to decide whether Kt(x∣z) is "very large" (≥ n-1) or "very small" (≤ O(log n)).  where Kt(x∣z) denotes the Levin-Kolmogorov complexity of x conditioned on z. As far as we are aware, this yields the first full characterization of when prBPP = prP through the hardness of some class of problems. Previous hardness assumptions used for derandomization only provide a one-sided implication.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Derandomization
  • Kolmogorov Complexity
  • Hitting Set Generators

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alexander E Andreev, Andrea EF Clementi, and Jose DP Rolim. A new general derandomization method. Journal of the ACM (JACM), 45(1):179-213, 1998. Google Scholar
  2. Alexander E Andreev, Andrea EF Clementi, José DP Rolim, and Luca Trevisan. Weak random sources, hitting sets, and bpp simulations. SIAM Journal on Computing, 28(6):2103-2116, 1999. Google Scholar
  3. Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  4. László Babai, Lance Fortnow, Noam Nisan, and Avi Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307-318, 1993. Google Scholar
  5. Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13(4):850-864, 1984. Google Scholar
  6. Harry Buhrman and Lance Fortnow. One-sided versus two-sided error in probabilistic computation. In Annual Symposium on Theoretical Aspects of Computer Science, pages 100-109. Springer, 1999. Google Scholar
  7. Gregory J. Chaitin. On the simplicity and speed of programs for computing infinite sets of natural numbers. J. ACM, 16(3):407-422, 1969. Google Scholar
  8. Lijie Chen, Ron D Rothblum, Roei Tell, and Eylon Yogev. On exponential-time hypotheses, derandomization, and circuit lower bounds. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 13-23. IEEE, 2020. Google Scholar
  9. Lijie Chen and Roei Tell. Hardness vs randomness, revised: Uniform, non-black-box, and instance-wise. Electronic Colloquium on Computational Complexity, 2021. URL: https://eccc.weizmann.ac.il/report/2021/080/l.
  10. Oded Goldreich. In a world of p= bpp. In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 191-232. Springer, 2011. Google Scholar
  11. Shuichi Hirahara. Non-disjoint promise problems from meta-computational view of pseudorandom generator constructions. In 35th Computational Complexity Conference (CCC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  12. Rahul Ilango, Bruno Loff, and Igor Carboni Oliveira. NP-hardness of circuit minimization for multi-output functions. In 35th Computational Complexity Conference, CCC 2020, pages 22:1-22:36, 2020. Google Scholar
  13. Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson. In search of an easy witness: Exponential time vs. probabilistic polynomial time. Journal of Computer and System Sciences, 65(4):672-694, 2002. Google Scholar
  14. Russell Impagliazzo and Avi Wigderson. P = BPP if e requires exponential circuits: Derandomizing the xor lemma. In STOC '97, pages 220-229, 1997. Google Scholar
  15. Ker-I Ko. On the notion of infinite pseudorandom sequences. Theor. Comput. Sci., 48(3):9-33, 1986. URL: https://doi.org/10.1016/0304-3975(86)90081-2.
  16. A. N. Kolmogorov. Three approaches to the quantitative definition of information. International Journal of Computer Mathematics, 2(1-4):157-168, 1968. Google Scholar
  17. Clemens Lautemann. BPP and the polynomial hierarchy. Inf. Process. Lett., 17(4):215-217, 1983. Google Scholar
  18. Leonid A. Levin. Universal search problems (russian), translated into English by BA Trakhtenbrot in [Trakhtenbrot, 1984]. Problems of Information Transmission, 9(3):265-266, 1973. Google Scholar
  19. Luc Longpré and Sarah Mocas. Symmetry of information and one-way functions. In Wen-Lian Hsu and Richard C. T. Lee, editors, ISA '91 Algorithms, 2nd International Symposium on Algorithms, Taipei, Republic of China, December 16-18, 1991, Proceedings, volume 557 of Lecture Notes in Computer Science, pages 308-315. Springer, 1991. URL: https://doi.org/10.1007/3-540-54945-5_75.
  20. Cody Murray and Ryan Williams. Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for np and nqp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 890-901, 2018. Google Scholar
  21. Noam Nisan. Pseudorandom bits for constant depth circuits. Combinatorica, 11(1):63-70, 1991. Google Scholar
  22. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  23. Michael Sipser. A complexity theoretic approach to randomness. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 330-335. ACM, 1983. Google Scholar
  24. R.J. Solomonoff. A formal theory of inductive inference. part i. Information and Control, 7(1):1-22, 1964. URL: https://doi.org/10.1016/S0019-9958(64)90223-2.
  25. Madhu Sudan, Luca Trevisan, and Salil Vadhan. Pseudorandom generators without the xor lemma. Journal of Computer and System Sciences, 62(2):236-266, 2001. Google Scholar
  26. Roei Tell. Proving that prbpp= prp is as hard as proving that “almost np” is not contained in p/poly. Information Processing Letters, 152:105841, 2019. Google Scholar
  27. Boris A Trakhtenbrot. A survey of Russian approaches to perebor (brute-force searches) algorithms. Annals of the History of Computing, 6(4):384-400, 1984. Google Scholar
  28. Salil P Vadhan. Pseudorandomness. Foundations and Trendsregistered in Theoretical Computer Science, 7(1-3):1-336, 2012. Google Scholar
  29. Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982, pages 80-91, 1982. Google Scholar
  30. A. K. Zvonkin and L. A. Levin. the Complexity of Finite Objects and the Development of the Concepts of Information and Randomness by Means of the Theory of Algorithms. Russian Mathematical Surveys, 25(6):83-124, December 1970. URL: https://doi.org/10.1070/RM1970v025n06ABEH001269.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact