On the Structure of Learnability beyond P/poly

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10515160" target="_blank" >RIV/00216208:11320/25:10515160 - isvavai.cz</a>

Result on the web

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=cFad2TY9eu" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=cFad2TY9eu</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00037-024-00260-5" target="_blank" >10.1007/s00037-024-00260-5</a>

Result language

angličtina

Original language name

On the Structure of Learnability beyond P/poly

Original language description

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 RKt and RKS 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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2025

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Computational Complexity

ISSN

1016-3328

e-ISSN

1420-8954

Volume of the periodical

34

Issue of the periodical within the volume

1

Country of publishing house

CH - SWITZERLAND

Number of pages

49

Pages from-to

1

UT code for WoS article

001390549400001

EID of the result in the Scopus database

2-s2.0-85214214404