Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity

Authors Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira



PDF
Thumbnail PDF

File

LIPIcs.CCC.2022.16.pdf
  • Filesize: 1.23 MB
  • 60 pages

Document Identifiers

Author Details

Halley Goldberg
  • Simon Fraser University, Burnaby, Canada
Valentine Kabanets
  • Simon Fraser University, Burnaby, Canada
Zhenjian Lu
  • University of Warwick, Coventry, UK
Igor C. Oliveira
  • University of Warwick, Coventry, UK

Acknowledgements

We thank Russell Impagliazzo for a clarification regarding the definition of average-case complexity classes. We are also grateful to the CCC reviewers for their comments and suggestions.

Cite AsGet BibTex

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 16:1-16:60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.CCC.2022.16

Abstract

Understanding the relationship between the worst-case and average-case complexities of NP and of other subclasses of PH is a long-standing problem in complexity theory. Over the last few years, much progress has been achieved in this front through the investigation of meta-complexity: the complexity of problems that refer to the complexity of the input string x (e.g., given a string x, estimate its time-bounded Kolmogorov complexity). In particular, [Shuichi Hirahara, 2021] employed techniques from meta-complexity to show that if DistNP ⊆ AvgP then UP ⊆ DTIME[2^{O(n/log n)}]. While this and related results [Shuichi Hirahara and Mikito Nanashima, 2021; Lijie Chen et al., 2022] offer exciting progress after a long gap, they do not survive in the setting of randomized computations: roughly speaking, "randomness" is the opposite of "structure", and upper bounding the amount of structure (time-bounded Kolmogorov complexity) of different objects is crucial in recent applications of meta-complexity. This limitation is significant, since randomized computations are ubiquitous in algorithm design and give rise to a more robust theory of average-case complexity [Russell Impagliazzo and Leonid A. Levin, 1990]. In this work, we develop a probabilistic theory of meta-complexity, by incorporating randomness into the notion of complexity of a string x. This is achieved through a new probabilistic variant of time-bounded Kolmogorov complexity that we call pK^t complexity. Informally, pK^t(x) measures the complexity of x when shared randomness is available to all parties involved in a computation. By porting key results from meta-complexity to the probabilistic domain of pK^t complexity and its variants, we are able to establish new connections between worst-case and average-case complexity in the important setting of probabilistic computations: - If DistNP ⊆ AvgBPP, then UP ⊆ RTIME[2^O(n/log n)]. - If DistΣ^P_2 ⊆ AvgBPP, then AM ⊆ BPTIME[2^O(n/log n)]. - In the fine-grained setting [Lijie Chen et al., 2022], we get UTIME[2^O(√{nlog n})] ⊆ RTIME[2^O(√{nlog n})] and AMTIME[2^O(√{nlog n})] ⊆ BPTIME[2^O(√{nlog n})] from stronger average-case assumptions. - If DistPH ⊆ AvgBPP, then PH ⊆ BPTIME[2^O(n/log n)]. Specifically, for any 𝓁 ≥ 0, if DistΣ_{𝓁+2}^P ⊆ AvgBPP then Σ_𝓁^{P} ⊆ BPTIME[2^O(n/log n)]. - Strengthening a result from [Shuichi Hirahara and Mikito Nanashima, 2021], we show that if DistNP ⊆ AvgBPP then polynomial size Boolean circuits can be agnostically PAC learned under any unknown 𝖯/poly-samplable distribution in polynomial time. In some cases, our framework allows us to significantly simplify existing proofs, or to extend results to the more challenging probabilistic setting with little to no extra effort.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • average-case complexity
  • Kolmogorov complexity
  • meta-complexity
  • worst-case to average-case reductions
  • learning

Metrics

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

References

  1. 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. URL: https://doi.org/10.1109/CCC.2009.12.
  2. Shai Ben-David, Benny Chor, Oded Goldreich, and Michael Luby. On the theory of average case complexity. J. Comput. Syst. Sci., 44(2):193-219, 1992. URL: https://doi.org/10.1016/0022-0000(92)90019-F.
  3. Andrej Bogdanov and Luca Trevisan. Average-case complexity. Found. Trends Theor. Comput. Sci., 2(1), 2006. URL: https://doi.org/10.1561/0400000004.
  4. Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. SIAM J. Comput., 36(4):1119-1159, 2006. URL: https://doi.org/10.1137/S0097539705446974.
  5. Harry Buhrman, Lance Fortnow, and Aduri Pavan. Some results on derandomization. Theory Comput. Syst., 38(2):211-227, 2005. URL: https://doi.org/10.1007/s00224-004-1194-y.
  6. Lijie Chen, Shuichi Hirahara, and Neekon Vafa. Average-case hardness of NP and PH from worst-case fine-grained assumptions. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 45:1-45:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.45.
  7. Halley Goldberg and Valentine Kabanets. A simpler proof of the worst-case to average-case reduction for polynomial hierarchy via symmetry of information. Electron. Colloquium Comput. Complex., 7:1-14, 2022. URL: https://eccc.weizmann.ac.il/report/2022/007/.
  8. Oded Goldreich. The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, 2001. URL: https://doi.org/10.1017/CBO9780511546891.
  9. Oded Goldreich and Leonid A. Levin. A hard-core predicate for all one-way functions. In Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC '89, pages 25-32, New York, NY, USA, 1989. Association for Computing Machinery. URL: https://doi.org/10.1145/73007.73010.
  10. Shuichi Hirahara. Characterizing average-case complexity of PH by worst-case meta-complexity. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 50-60. IEEE, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00014.
  11. Shuichi Hirahara. Average-case hardness of NP from exponential worst-case hardness assumptions. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 292-302. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451065.
  12. Shuichi Hirahara. Symmetry of information in heuristica. Manuscript, 2021. Google Scholar
  13. Shuichi Hirahara and Mikito Nanashima. On worst-case learning in relativized heuristica. In Symposium on Foundations of Computer Science (FOCS), 2021. Google Scholar
  14. Shuichi Hirahara and Rahul Santhanam. Errorless versus error-prone average-case complexity. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 84:1-84:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.84.
  15. Shuichi Hirahara and Rahul Santhanam. Excluding PH pessiland. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference, ITCS 2022, January 31 - February 3, 2022, Berkeley, CA, USA, volume 215 of LIPIcs, pages 85:1-85:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.85.
  16. Russell Impagliazzo. A personal view of average-case complexity. In Proceedings of the Tenth Annual Structure in Complexity Theory Conference, Minneapolis, Minnesota, USA, June 19-22, 1995, pages 134-147, 1995. URL: https://doi.org/10.1109/SCT.1995.514853.
  17. Russell Impagliazzo. Relativized separations of worst-case and average-case complexities for NP. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, pages 104-114, 2011. URL: https://doi.org/10.1109/CCC.2011.34.
  18. Russell Impagliazzo and Leonid A. Levin. No better ways to generate hard NP instances than picking uniformly at random. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II, pages 812-821. IEEE Computer Society, 1990. URL: https://doi.org/10.1109/FSCS.1990.89604.
  19. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Frank Thomson Leighton and Peter W. Shor, editors, Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, pages 220-229. ACM, 1997. URL: https://doi.org/10.1145/258533.258590.
  20. Michael J. Kearns, Robert E. Schapire, and Linda Sellie. Toward efficient agnostic learning. Mach. Learn., 17(2-3):115-141, 1994. URL: https://doi.org/10.1007/BF00993468.
  21. Pravesh K. Kothari and Roi Livni. Improper learning by refuting. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 55:1-55:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.55.
  22. Clemens Lautemann. BPP and the polynomial hierarchy. Inf. Process. Lett., 17(4):215-217, 1983. URL: https://doi.org/10.1016/0020-0190(83)90044-3.
  23. Troy Lee. Kolmogorov complexity and formula lower bounds. PhD thesis, University of Amsterdam, 2006. Google Scholar
  24. Leonid A. Levin. Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Problemy Peredachi Informatsii, 10(3):30-35, 1974. Google Scholar
  25. Leonid A. Levin. Average case complete problems. SIAM J. Comput., 15(1):285-286, 1986. URL: https://doi.org/10.1137/0215020.
  26. Ming Li and Paul M. B. Vitányi. An introduction to Kolmogorov complexity and its applications. Springer, 2019. Google Scholar
  27. Ming Li and Paul M. B. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications, 4th Edition. Texts in Computer Science. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-11298-1.
  28. Yanyi Liu and Rafael Pass. On one-way functions and kolmogorov complexity. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1243-1254, 2020. URL: https://doi.org/10.1109/FOCS46700.2020.00118.
  29. Yanyi Liu and Rafael Pass. On one-way functions from np-complete problems. Electron. Colloquium Comput. Complex., page 59, 2021. URL: https://eccc.weizmann.ac.il/report/2021/059.
  30. Yanyi Liu and Rafael Pass. On the possibility of basing cryptography on exp̸ = BPP. In Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part I, pages 11-40, 2021. URL: https://doi.org/10.1007/978-3-030-84242-0_2.
  31. Luc Longpré and Osamu Watanabe. On symmetry of information and polynomial time invertibility. Inf. Comput., 121(1):14-22, 1995. URL: https://doi.org/10.1006/inco.1995.1120.
  32. Zhenjian Lu and Igor C. Oliveira. An efficient coding theorem via probabilistic representations and its applications. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 94:1-94:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.94.
  33. Zhenjian Lu, Igor C. Oliveira, and Rahul Santhanam. Pseudodeterministic algorithms and the structure of probabilistic time. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 303-316. ACM, 2021. URL: https://doi.org/10.1145/3406325.3451085.
  34. Zhenjian Lu, Igor C. Oliveira, and Marius Zimand. Optimal coding theorems in time-bounded kolmogorov complexity. In 49th International Colloquium on Automata, Languages and Programming, 2022. Google Scholar
  35. Peter Bro Miltersen, N. V. Vinodchandran, and Osamu Watanabe. Super-polynomial versus half-exponential circuit size in the exponential hierarchy. In Takao Asano, Hiroshi Imai, D. T. Lee, Shin-Ichi Nakano, and Takeshi Tokuyama, editors, Computing and Combinatorics, 5th Annual International Conference, COCOON '99, Tokyo, Japan, July 26-28, 1999, Proceedings, volume 1627 of Lecture Notes in Computer Science, pages 210-220. Springer, 1999. URL: https://doi.org/10.1007/3-540-48686-0_21.
  36. Ashish V. Naik, Kenneth W. Regan, and D. Sivakumar. On quasilinear-time complexity theory. Theor. Comput. Sci., 148(2):325-349, 1995. URL: https://doi.org/10.1016/0304-3975(95)00031-Q.
  37. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80043-1.
  38. Igor C. Oliveira. Randomness and intractability in kolmogorov complexity. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 32:1-32:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.32.
  39. Igor C. Oliveira and Rahul Santhanam. Pseudodeterministic constructions in subexponential time. In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 665-677. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055500.
  40. Hanlin Ren and Rahul Santhanam. Hardness of KT characterizes parallel cryptography. In 36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference), pages 35:1-35:58, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.35.
  41. Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, 2014. URL: http://www.cambridge.org/de/academic/subjects/computer-science/pattern-recognition-and-machine-learning/understanding-machine-learning-theory-algorithms.
  42. Ronen Shaltiel and Christopher Umans. Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM, 52(2):172-216, 2005. URL: https://doi.org/10.1145/1059513.1059516.
  43. Luca Trevisan and Salil P. Vadhan. Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity, 16(4):331-364, 2007. Google Scholar
  44. Salil P. Vadhan. On learning vs. refutation. In Satyen Kale and Ohad Shamir, editors, Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017, volume 65 of Proceedings of Machine Learning Research, pages 1835-1848. PMLR, 2017. URL: http://proceedings.mlr.press/v65/vadhan17a.html.
  45. Emanuele Viola. On constructing parallel pseudorandom generators from one-way functions. In 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA, pages 183-197, 2005. URL: https://doi.org/10.1109/CCC.2005.16.
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