On the Structure of Learnability beyond P/poly
Ninad Rajgopal, Rahul Santhanam · Computational Complexity · 2025
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 E/poly . We show the following: (Unconditional Lower Bounds for Learning) Building on 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. (Robustness of Learning) For the concept classes EXP/poly and PSPACE/poly , we unconditionally show 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. (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. (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 blackbox 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.