On the Structure of Learnability beyond P/poly

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

On the Structure of Learnability beyond P/poly

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

On the Structure of Learnability beyond P/poly

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

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

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

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

Název periodika

Computational Complexity

ISSN

1016-3328

e-ISSN

1420-8954

Svazek periodika

34

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

49

Strana od-do

1

Kód UT WoS článku

001390549400001

EID výsledku v databázi Scopus

2-s2.0-85214214404