Document Open Access Logo

On the Structure of Learnability Beyond P/Poly

Authors Ninad Rajgopal , Rahul Santhanam

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.46.pdf
  • Filesize: 0.83 MB
  • 23 pages

Document Identifiers

Author Details

Ninad Rajgopal
  • University of Warwick, Coventry, UK
Rahul Santhanam
  • University of Oxford, UK

Funding

This work was supported in part by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2014)/ERC Grant Agreement no. 615075.
  • Rajgopal, Ninad: Supported in part by Tom Gur’s UKRI Future Leaders Fellowship MR/S031545/1.

Acknowledgements

Ninad is grateful to Igor Carboni Oliveira for many inspiring discussions, one of which led to the results in Section 2.

Cite AsGet BibTex

Ninad Rajgopal and Rahul Santhanam. On the Structure of Learnability Beyond P/Poly. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 46:1-46:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.46

Abstract

Motivated by the goal of showing stronger structural results about the complexity of learning, we study the learnability of strong concept classes beyond P/poly, such as PSPACE/poly and EXP/poly. We show the following: 1) (Unconditional Lower Bounds for Learning) Building on [Adam R. Klivans et al., 2013], we prove unconditionally that BPE/poly cannot be weakly learned in polynomial time over the uniform distribution, even with membership and equivalence queries. 2) (Robustness of Learning) For the concept classes EXP/poly and PSPACE/poly, we show unconditionally that worst-case and average-case learning are equivalent, that PAC-learnability and learnability over the uniform distribution are equivalent, and that membership queries do not help in either case. 3) (Reducing Succinct Search to Decision for Learning) For the decision problems R_{Kt} and R_{KS} capturing the complexity of learning EXP/poly and PSPACE/poly respectively, we show a succinct search to decision reduction: for each of these problems, the problem is in BPP iff there is a probabilistic polynomial-time algorithm computing circuits encoding proofs for positive instances of the problem. This is shown via a more general result giving succinct search to decision results for PSPACE, EXP and NEXP, which might be of independent interest. 4) (Implausibility of Oblivious Strongly Black-Box Reductions showing NP-hardness of learning NP/poly) We define a natural notion of hardness of learning with respect to oblivious strongly black-box reductions. We show that learning PSPACE/poly is PSPACE-hard with respect to oblivious strongly black-box reductions. On the other hand, if learning NP/poly is NP-hard with respect to oblivious strongly black-box reductions, the Polynomial Hierarchy collapses.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Hardness of Learning
  • Oracle Circuit Classes
  • Succinct Search
  • Black-Box Reductions

Metrics

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

References

  1. Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On basing one-way functions on np-hardness. In Jon M. Kleinberg, editor, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006, pages 701-710. ACM, 2006. URL: https://doi.org/10.1145/1132516.1132614.
  2. Eric Allender. When worlds collide: Derandomization, lower bounds, and kolmogorov complexity. In International Conference on Foundations of Software Technology and Theoretical Computer Science, pages 1-15. Springer, 2001. Google Scholar
  3. Eric Allender, Harry Buhrman, Michal Koucky, Dieter Van Melkebeek, and Detlef Ronneburger. Power from random strings. SIAM Journal on Computing, 35(6):1467-1493, 2006. Google Scholar
  4. Dana Angluin. Queries and concept learning. Machine learning, 2(4):319-342, 1988. Google Scholar
  5. Benny Applebaum, Boaz Barak, and David Xiao. On basing lower-bounds for learning on worst-case assumptions. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 211-220. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/FOCS.2008.35.
  6. László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational complexity, 1(1):3-40, 1991. Google Scholar
  7. 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. URL: https://doi.org/10.1007/BF01275486.
  8. Avrim Blum, Merrick Furst, Michael Kearns, and Richard J Lipton. Cryptographic primitives based on hard learning problems. In Annual International Cryptology Conference, pages 278-291. Springer, 1993. Google Scholar
  9. Andrej Bogdanov and Christina Brzuska. On basing size-verifiable one-way functions on np-hardness. In Yevgeniy Dodis and Jesper Buus Nielsen, editors, Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I, volume 9014 of Lecture Notes in Computer Science, pages 1-6. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-46494-6_1.
  10. Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for np problems. SIAM Journal on Computing, 36(4):1119-1159, 2006. Google Scholar
  11. Harry Buhrman, Lance Fortnow, and Thomas Thierauf. Nonrelativizing separations. In Proceedings. Thirteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference)(Cat. No. 98CB36247), pages 8-12. IEEE, 1998. Google Scholar
  12. Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. Learning algorithms from natural proofs. In Ran Raz, editor, 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, volume 50 of LIPIcs, pages 10:1-10:24. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.CCC.2016.10.
  13. Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, and Rahul Santhanam. Beyond natural proofs: Hardness magnification and locality. 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 70:1-70:48. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ITCS.2020.70.
  14. Joan Feigenbaum and Lance Fortnow. Random-self-reducibility of complete sets. SIAM Journal on Computing, 22(5):994-1005, 1993. Google Scholar
  15. Lance Fortnow and Adam R Klivans. Efficient learning algorithms yield circuit lower bounds. Journal of Computer and System Sciences, 75(1):27-36, 2009. Google Scholar
  16. Lance Fortnow, John Rompel, and Michael Sipser. On the power of multi-prover interactive protocols. Theoretical Computer Science, 134(2):545-557, 1994. Google Scholar
  17. Yoav Freund and Robert E Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-139, 1997. Google Scholar
  18. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct randolli functions. In 25th Annual Symposium on Foundations of Computer Science, 1984., pages 464-479. IEEE, 1984. Google Scholar
  19. Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma. If NP languages are hard on the worst-case, then it is easy to find their hard instances. Comput. Complex., 16(4):412-441, 2007. URL: https://doi.org/10.1007/s00037-007-0235-8.
  20. Dan Gutfreund and Salil P. Vadhan. Limitations of hardness vs. randomness under uniform reductions. In Ashish Goel, Klaus Jansen, José D. P. Rolim, and Ronitt Rubinfeld, editors, Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008. Proceedings, volume 5171 of Lecture Notes in Computer Science, pages 469-482. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-85363-3_37.
  21. 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. URL: https://doi.org/10.1109/FOCS.2018.00032.
  22. Shuichi Hirahara and Osamu Watanabe. On nonadaptive reductions to the set of random strings and its dense subsets. Electronic Colloquium on Computational Complexity (ECCC), 26:25, 2019. URL: https://eccc.weizmann.ac.il/report/2019/025.
  23. 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. IEEE Computer Society, 2011. URL: https://doi.org/10.1109/CCC.2011.34.
  24. 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
  25. Russell Impagliazzo and Levin LA. No better ways to generate hard np instances than picking uniformly at random. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 812-821. IEEE, 1990. Google Scholar
  26. Russell Impagliazzo and Avi Wigderson. Randomness vs time: Derandomization under a uniform assumption. J. Comput. Syst. Sci., 63(4):672-688, 2001. URL: https://doi.org/10.1006/jcss.2001.1780.
  27. Jeffrey C Jackson. An efficient membership-query algorithm for learning dnf with respect to the uniform distribution. Journal of Computer and System Sciences, 55(3):414-440, 1997. Google Scholar
  28. Richard M Karp and Richard J Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 302-309. ACM, 1980. Google Scholar
  29. Michael Kearns and Leslie Valiant. Cryptographic limitations on learning boolean formulae and finite automata. Journal of the ACM (JACM), 41(1):67-95, 1994. Google Scholar
  30. Michael J Kearns, Umesh Virkumar Vazirani, and Umesh Vazirani. An introduction to computational learning theory. MIT press, 1994. Google Scholar
  31. Adam R. Klivans, Pravesh Kothari, and Igor Carboni Oliveira. Constructing hard functions using learning algorithms. In Proceedings of the 28th Conference on Computational Complexity, CCC 2013, K.lo Alto, California, USA, 5-7 June, 2013, pages 86-97. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/CCC.2013.18.
  32. Eyal Kushilevitz and Yishay Mansour. Learning decision trees using the fourier spectrum. SIAM Journal on Computing, 22(6):1331-1348, 1993. Google Scholar
  33. Leonid A Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61(1):15-37, 1984. Google Scholar
  34. Nathan Linial, Yishay Mansour, and Noam Nisan. Constant depth circuits, fourier transform, and learnability. Journal of the ACM (JACM), 40(3):607-620, 1993. Google Scholar
  35. Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 2-10. IEEE, 1990. Google Scholar
  36. Igor Carboni Oliveira and Rahul Santhanam. Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness. In Ryan O'Donnell, editor, 32nd Computational Complexity Conference, CCC 2017, July 6-9, 2017, Riga, Latvia, volume 79 of LIPIcs, pages 18:1-18:49. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.CCC.2017.18.
  37. Robert E Schapire. The strength of weak learnability. Machine learning, 5(2):197-227, 1990. Google Scholar
  38. Luca Trevisan and Salil Vadhan. Pseudorandomness and average-case complexity via uniform reductions. Computational Complexity, 16(4):331-364, 2007. Google Scholar
  39. Chee K Yap. Some consequences of non-uniform conditions on uniform classes. Theoretical computer science, 26(3):287-300, 1983. Google Scholar
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 Imprint Privacy Contact