Document Open Access Logo

Unexpected Power of Random Strings

Author Shuichi Hirahara

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.41.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Shuichi Hirahara
  • National Institute of Informatics, Tokyo, Japan

Funding

  • Hirahara, Shuichi: ACT-I, JST and JSPS KAKENHI Grant Number 18H04090.

Acknowledgements

I thank Eric Allender, Michal Koucký, and Osamu Watanabe for helpful discussions, and thank anonymous reviewers for helpful comments. I got the ideas of this work during the joint work with Osamu Watanabe.

Cite As Get BibTex

Shuichi Hirahara. Unexpected Power of Random Strings. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.41

Abstract

There has been a line of work trying to characterize BPP (the class of languages that are solvable by efficient randomized algorithms) by efficient nonadaptive reductions to the set of Kolmogorov-random strings: Buhrman, Fortnow, Koucký, and Loff (CCC 2010 [Buhrman et al., 2010]) showed that every language in BPP is reducible to the set of random strings via a polynomial-time nonadaptive reduction (irrespective of the choice of a universal Turing machine used to define Kolmogorov-random strings). It was conjectured by Allender (CiE 2012 [Allender, 2012]) and others that their lower bound is tight when a reduction works for every universal Turing machine; i.e., "the only way to make use of random strings by a nonadaptive polynomial-time algorithm is to derandomize BPP."
In this paper, we refute this conjecture under the plausible assumption that the exponential-time hierarchy does not collapse, by showing that the exponential-time hierarchy EXPH can be solved in exponential time by nonadaptively asking the oracle whether a string is Kolmogorov-random or not. In addition, we provide an exact characterization of S_2^{exp} in terms of exponential-time-computable nonadaptive reductions to arbitrary dense subsets of random strings.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Kolmogorov-Randomness
  • Nonadaptive Reduction
  • BPP
  • Symmetric Alternation

Metrics

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

Related Versions

References

  1. Eric Allender. Curiouser and Curiouser: The Link between Incompressibility and Complexity. In Proceedings of the 8th Conference on Computability in Europe (CiE), pages 11-16, 2012. URL: https://doi.org/10.1007/978-3-642-30870-3_2.
  2. Eric Allender. The Complexity of Complexity. In Computability and Complexity - Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, pages 79-94, 2017. URL: https://doi.org/10.1007/978-3-319-50062-1_6.
  3. Eric Allender, Harry Buhrman, Luke Friedman, and Bruno Loff. Reductions to the set of random strings: The resource-bounded case. Logical Methods in Computer Science, 10(3), 2014. URL: https://doi.org/10.2168/LMCS-10(3:5)2014.
  4. Eric Allender, Harry Buhrman, and Michal Koucký. What can be efficiently reduced to the Kolmogorov-random strings? Ann. Pure Appl. Logic, 138(1-3):2-19, 2006. URL: https://doi.org/10.1016/j.apal.2005.06.003.
  5. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from Random Strings. SIAM J. Comput., 35(6):1467-1493, 2006. URL: https://doi.org/10.1137/050628994.
  6. Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, and Iddo Tzameret. Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic. Chicago J. Theor. Comput. Sci., 2013, 2013. URL: http://cjtcs.cs.uchicago.edu/articles/2013/5/contents.html.
  7. Eric Allender, Luke Friedman, and William I. Gasarch. Limits on the computational power of random strings. Inf. Comput., 222:80-92, 2013. URL: https://doi.org/10.1016/j.ic.2011.09.008.
  8. Eric Allender and Shuichi Hirahara. New Insights on the (Non-)Hardness of Circuit Minimization and Related Problems. TOCT, 11(4):27:1-27:27, 2019. URL: https://doi.org/10.1145/3349616.
  9. Eric Allender, Dhiraj Holden, and Valentine Kabanets. The Minimum Oracle Circuit Size Problem. Computational Complexity, 26(2):469-496, 2017. URL: https://doi.org/10.1007/s00037-016-0124-0.
  10. Harry Buhrman, Lance Fortnow, Michal Koucký, and Bruno Loff. Derandomizing from Random Strings. In Proceedings of the Conference on Computational Complexity (CCC), pages 58-63, 2010. URL: https://doi.org/10.1109/CCC.2010.15.
  11. Jin-yi Cai. 𝖲₂^p ⊆ ZPP^NP. J. Comput. Syst. Sci., 73(1):25-35, 2007. URL: https://doi.org/10.1016/j.jcss.2003.07.015.
  12. Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, and Mitsunori Ogihara. Competing provers yield improved Karp-Lipton collapse results. Inf. Comput., 198(1):1-23, 2005. URL: https://doi.org/10.1016/j.ic.2005.01.002.
  13. Mingzhong Cai, Rodney G. Downey, Rachel Epstein, Steffen Lempp, and Joseph S. Miller. Random strings and tt-degrees of Turing complete C.E. sets. Logical Methods in Computer Science, 10(3), 2014. URL: https://doi.org/10.2168/LMCS-10(3:15)2014.
  14. Ran Canetti. More on BPP and the Polynomial-Time Hierarchy. Inf. Process. Lett., 57(5):237-241, 1996. URL: https://doi.org/10.1016/0020-0190(96)00016-6.
  15. Shuichi Hirahara. Identifying an Honest EXP^NP Oracle Among Many. In Proceedings of the Conference on Computational Complexity (CCC), pages 244-263, 2015. URL: https://doi.org/10.4230/LIPIcs.CCC.2015.244.
  16. Shuichi Hirahara and Akitoshi Kawamura. On characterizations of randomized computation using plain Kolmogorov complexity. Computability, 7(1):45-56, 2018. URL: https://doi.org/10.3233/COM-170075.
  17. Shuichi Hirahara and Osamu Watanabe. Limits of Minimum Circuit Size Problem as Oracle. In Proceedings of the Conference on Computational Complexity (CCC), pages 18:1-18:20, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.18.
  18. John M. Hitchcock and Aduri Pavan. On the NP-Completeness of the Minimum Circuit Size Problem. In Proceedings of the Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), pages 236-245, 2015. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2015.236.
  19. Russell Impagliazzo and Avi Wigderson. P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma. In Proceedings of the Symposium on the Theory of Computing (STOC), pages 220-229, 1997. URL: https://doi.org/10.1145/258533.258590.
  20. Valentine Kabanets and Jin-yi Cai. Circuit minimization problem. In Proceedings of the Symposium on Theory of Computing (STOC), pages 73-79, 2000. URL: https://doi.org/10.1145/335305.335314.
  21. Marcos A. Kiwi, Carsten Lund, Daniel A. Spielman, Alexander Russell, and Ravi Sundaram. Alternation in interaction. Computational Complexity, 9(3-4):202-246, 2000. URL: https://doi.org/10.1007/PL00001607.
  22. Cody D. Murray and R. Ryan Williams. On the (Non) NP-Hardness of Computing Circuit Complexity. Theory of Computing, 13(1):1-22, 2017. URL: https://doi.org/10.4086/toc.2017.v013a004.
  23. Alexander Russell and Ravi Sundaram. Symmetric Alternation Captures BPP. Computational Complexity, 7(2):152-162, 1998. URL: https://doi.org/10.1007/s000370050007.
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