Document Open Access Logo

On Randomized Reductions to the Random Strings

Authors Michael Saks, Rahul Santhanam

PDF

File

Thumbnail PDF
PDF
LIPIcs.CCC.2022.29.pdf
  • Filesize: 0.89 MB
  • 30 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Kolmogorov complexity
  • randomized reductions

Metrics

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

Abstract

We study the power of randomized polynomial-time non-adaptive reductions to the problem of approximating Kolmogorov complexity and its polynomial-time bounded variants.
As our first main result, we give a sharp dichotomy for randomized non-adaptive reducibility to approximating Kolmogorov complexity. We show that any computable language L that has a randomized polynomial-time non-adaptive reduction (satisfying a natural honesty condition) to ω(log(n))-approximating the Kolmogorov complexity is in AM ∩ coAM. On the other hand, using results of Hirahara [Shuichi Hirahara, 2020], it follows that every language in NEXP has a randomized polynomial-time non-adaptive reduction (satisfying the same honesty condition as before) to O(log(n))-approximating the Kolmogorov complexity.
As our second main result, we give the first negative evidence against the NP-hardness of polynomial-time bounded Kolmogorov complexity with respect to randomized reductions. We show that for every polynomial t', there is a polynomial t such that if there is a randomized time t' non-adaptive reduction (satisfying a natural honesty condition) from SAT to ω(log(n))-approximating K^t complexity, then either NE = coNE or 𝖤 has sub-exponential size non-deterministic circuits infinitely often.

Cite As Get BibTex

Michael Saks and Rahul Santhanam. On Randomized Reductions to the Random Strings. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 29:1-29:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CCC.2022.29

Author Details

Michael Saks
  • Department of Mathematics, Rutgers, The State University of New Jersey, Piscataway, NJ, USA
Rahul Santhanam
  • Department of Computer Science, University of Oxford, UK

Funding

  • Saks, Michael: Supported in part by the Simons Foundation under Grant 332622.
  • Santhanam, Rahul: Partially funded by EPSRC New Horizons Grant EP/V048201/1.

Acknowledgements

We thank the anonymous reviewers for useful comments. The second author benefited from conversations with Shuichi Hirahara and Rahul Ilango.

References

  1. Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On basing one-way functions on np-hardness. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 701-710, 2006. Google Scholar
  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. Google Scholar
  3. Eric Allender. The new complexity landscape around circuit minimization. In Proceedings of 14th International Conference on Language and Automata Theory and Applications, volume 12038 of Lecture Notes in Computer Science, pages 3-16. Springer, 2020. Google Scholar
  4. Eric Allender, Harry Buhrman, Luke Friedman, and Bruno Loff. Reductions to the set of random strings: The resource-bounded case. Log. Methods Comput. Sci., 10(3), 2014. Google Scholar
  5. Eric Allender, Harry Buhrman, and Michal Koucký. What can be efficiently reduced to the kolmogorov-random strings? Ann. Pure Appl. Log., 138(1-3):2-19, 2006. Google Scholar
  6. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM J. Comput., 35(6):1467-1493, 2006. Google Scholar
  7. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM J. Comput., 35(6):1467-1493, 2006. Google Scholar
  8. Eric Allender and Bireswar Das. Zero knowledge and circuit minimization. In Symposium on Mathematical Foundations of Computer Science (MFCS), pages 25-32, 2014. Google Scholar
  9. Eric Allender, George Davie, Luke Friedman, Samuel Hopkins, and Iddo Tzameret. Kolmogorov complexity, circuits, and the strength of formal theories of arithmetic. Chic. J. Theor. Comput. Sci., 2013, 2013. Google Scholar
  10. Eric Allender, Luke Friedman, and William I. Gasarch. Limits on the computational power of random strings. Inf. Comput., 222:80-92, 2013. Google Scholar
  11. Eric Allender, Joshua A. Grochow, and Cristopher Moore. Graph isomorphism and circuit size. CoRR, abs/1511.08189, 2015. URL: http://arxiv.org/abs/1511.08189.
  12. Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael E. Saks. Minimizing disjunctive normal form formulas and AC0 circuits given a truth table. SIAM J. Comput., 38(1):63-84, 2008. Google Scholar
  13. Eric Allender and Shuichi Hirahara. New insights on the (non-)hardness of circuit minimization and related problems. In International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 54:1-54:14, 2017. Google Scholar
  14. Eric Allender, Dhiraj Holden, and Valentine Kabanets. The minimum oracle circuit size problem. In International Symposium on Theoretical Aspects of Computer Science (STACS), pages 21-33, 2015. Google Scholar
  15. Eric Allender, Michal Koucký, Detlef Ronneburger, and Sambuddha Roy. The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory. J. Comput. Syst. Sci., 77(1):14-40, 2011. Google Scholar
  16. Luis Filipe Coelho Antunes and Lance Fortnow. Worst-case running times for average-case algorithms. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009, pages 298-303. IEEE Computer Society, 2009. Google Scholar
  17. Benny Applebaum, Boaz Barak, and David Xiao. On basing lower-bounds for learning on worst-case assumptions. In Proceedings of 49th Annual IEEE Symposium on Foundations of Computer Science, pages 211-220, 2008. Google Scholar
  18. Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 1st edition, 2009. Google Scholar
  19. Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, and Ronen Shaltiel. Pseudorandomness when the odds are against you. In Proceedings of the 31st Conference on Computational Complexity, volume 50 of LIPIcs, pages 9:1-9:35. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  20. Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. SIAM J. Comput., 36(4):1119-1159, 2006. Google Scholar
  21. Harry Buhrman, Lance Fortnow, Michal Koucký, and Bruno Loff. Derandomizing from random strings. In Proceedings of the 25th Annual Conference on Computational Complexity, CCC '10, 2010. Google Scholar
  22. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Agnostic learning from tolerant natural proofs. In Approximation, Randomization, and Combinatorial Optimization, pages 35:1-35:19, 2017. Google Scholar
  23. Joan Feigenbaum and Lance Fortnow. Random-self-reducibility of complete sets. SIAM J. Comput., 22(5):994-1005, 1993. Google Scholar
  24. Oded Goldreich and Salil P. Vadhan. On the complexity of computational problems regarding distributions. In Oded Goldreich, editor, Studies in Complexity and Cryptography, volume 6650, pages 390-405. Springer, 2011. Google Scholar
  25. Shafi Goldwasser and Michael Sipser. Private coins versus public coins in interactive proof systems. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 59-68. ACM, 1986. Google Scholar
  26. Dan Gutfreund and Salil P. Vadhan. Limitations of hardness vs. randomness under uniform reductions. In Proceedings of 12th International Workshop on Randomness and Computation, volume 5171 of Lecture Notes in Computer Science, pages 469-482. Springer, 2008. Google Scholar
  27. Shuichi Hirahara. Non-black-box worst-case to average-case reductions within NP. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 247-258. IEEE Computer Society, 2018. Google Scholar
  28. Shuichi Hirahara. Unexpected hardness results for kolmogorov complexity under uniform reductions. In Proceedings of 52nd Annual Symposium on Theory of Computing, pages 1038-1051, 2020. Google Scholar
  29. Shuichi Hirahara, Igor Carboni Oliveira, and Rahul Santhanam. Np-hardness of minimum circuit size problem for OR-AND-MOD circuits. In 33rd Computational Complexity Conference, CCC 2018, pages 5:1-5:31, 2018. Google Scholar
  30. Shuichi Hirahara and Osamu Watanabe. Limits of minimum circuit size problem as oracle. In Conference on Computational Complexity (CCC), pages 18:1-18:20, 2016. Google Scholar
  31. Shuichi Hirahara and Osamu Watanabe. On nonadaptive security reductions of hitting set generators. In Proceedings of 24th International Conference on Randomization and Computation, volume 176 of LIPIcs, pages 15:1-15:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  32. John M. Hitchcock. Limitations of efficient reducibility to the kolmogorov random strings. Comput., 1(1):39-43, 2012. Google Scholar
  33. John M. Hitchcock and Aduri Pavan. On the NP-completeness of the minimum circuit size problem. In Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS), pages 236-245, 2015. Google Scholar
  34. Rahul Ilango. Approaching MCSP from above and below: Hardness for a conditional variant and AC^0[p]. In Proceedings of 11th Innovations in Theoretical Computer Science Conference, volume 151 of LIPIcs, pages 34:1-34:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  35. Rahul Ilango. Constant depth formula and partial function versions of MCSP are hard. In Proceedings of 61st IEEE Annual Symposium on Foundations of Computer Science, pages 424-433, 2020. Google Scholar
  36. Rahul Ilango, Bruno Loff, and Igor Carboni Oliveira. Np-hardness of circuit minimization for multi-output functions. In Proceedings of 35th Computational Complexity Conference, volume 169 of LIPIcs, pages 22:1-22:36. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  37. Valentine Kabanets and Jin-yi Cai. Circuit minimization problem. In Symposium on Theory of Computing (STOC), pages 73-79, 2000. Google Scholar
  38. Adam R. Klivans and Dieter van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput., 31(5):1501-1526, 2002. Google Scholar
  39. Ker-I Ko. On the complexity of learning minimum time-bounded turing machines. SIAM Journal on Computing, 20(5):962-986, 1991. Google Scholar
  40. Leonid Levin. Universal search problems. Problems of Information Transmission, 9(3):115-116, 1973. Google Scholar
  41. William J. Masek. Some NP-complete set covering problems. Unpublished Manuscript, 1979. Google Scholar
  42. Cody Murray and Ryan Williams. On the (non) NP-hardness of computing circuit complexity. In Conference on Computational Complexity (CCC), pages 365-380, 2015. Google Scholar
  43. Cody Murray and Ryan Williams. On the (non) np-hardness of computing circuit complexity. Theory Comput., 13(1):1-22, 2017. Google Scholar
  44. Michael Saks and Rahul Santhanam. Circuit lower bounds from np-hardness of MCSP under turing reductions. In Shubhangi Saraf, editor, Proceedings of 35th Computational Complexity Conference, volume 169 of LIPIcs, pages 26:1-26:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  45. Rahul Santhanam. Pseudorandomness and the minimum circuit size problem. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA, volume 151 of LIPIcs, pages 68:1-68:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. Google Scholar
  46. Stathis Zachos. Probabilistic quantifiers and games. J. Comput. Syst. Sci., 36(3):433-451, 1988. URL: https://doi.org/10.1016/0022-0000(88)90037-2.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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