Pith. sign in

REVIEW 2 major objections 6 minor 39 references

Computational-Statistical Tradeoffs from NP-hardness

T0 review · 2 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves NP-hardness-based computational-statistical tradeoffs in PAC learning: for every polynomial p, a VC-1 concept class requires Θ(p(n)) samples for time-efficient learning, and O(log n)-sample learners must be slow unless NP…

desk verdict First NP-hardness-based computational-statistical tradeoffs in PAC learning; the central reduction is sound, and the paper deserves serious peer review. read the letter →

arxiv 2507.13222 v1 pith:PNLI6LAO submitted 2025-07-17 cs.CC cs.DScs.LG

Guy Blanc , Caleb Koch , Carmen Strassle , Li-Yang Tan This is my paper · ORCID
classification cs.CCcs.DScs.LG MSC 68Q3268Q15
keywords PAClearningcomputational-statisticaltradeoffsNP-hardnesssamplecomplexityVCdimensionimproperRPvsNPnondeterminism
topics P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes the first computational-statistical tradeoffs in PAC learning that rest on NP-hardness rather than average-case or cryptographic assumptions. For every polynomial p(n), it constructs a concept class whose VC dimension is 1, so one sample determines the concept information-theoretically, yet time-efficient learning requires Θ(p(n)) samples, and with O(log n) samples any learner must be slow unless NP has fast randomized algorithms. The same construction yields an equivalence: RP = NP if and only if every NP-enumerable class is learnable in polynomial time with O(VCdim(C)) samples. All lower bounds hold against improper learners, sidestepping a known barrier to NP-hardness results for this setting.

What carries the argument

The load-bearing object is the concept class C_{L,V}: for each input z, the concept Cert_z is the constant-zero function if z ∉ L, and otherwise encodes the lexicographically first certificate w* for z through a constant-rate error-correcting code, outputting one encoded bit on each useful input (z,i) and 0 elsewhere. Learning Cert_z with few samples is shown to be at least as hard as deciding L with the same number of nondeterministic bits: a learner using m samples yields an Arthur-Merlin protocol for L with m proof bits and perfect soundness, and hence a randomized algorithm running in time $2^{{O(m)}}$ times the learner's runtime. This transfers time-versus-nondeterminism curves for NP languages into time-versus-sample curves for learning, and because the concepts are p(n)-sparse, a simple empirical risk minimizer learns them quickly once O(p(n)) samples are available.

What would settle it

For the concept class constructed from SAT with p(n) = n, the proof predicts that any learner using δn samples and running in $2^{{δn}}$ time would imply a randomized $2^{{O(δn)}}$-time algorithm for SAT; exhibiting such a learner, or any randomized polynomial-time O(log n)-sample learner for the class, would directly refute the conditional lower bound under randomized ETH or RP ≠ NP.

Watch

Extended reading notes

Core claim

For every time-constructible growth function p(n) ≥ n, there is an n-variate concept class C with VCdim(C) = 1 that is learnable to error ε using O(1/ε) samples in $2^{{O(p(n))}}$ time and using O(p(n)/ε) samples in O(p(n)/ε) time. Crucially, any algorithm that learns C with m(n) samples in time t(n) would imply NTIME(p(n)) ⊆ RTIME($2^{{O(m(n))}}$ t(n) log t(n) poly(p(n))). Consequently, a class that is information-theoretically learnable from one sample can require Θ(p(n)) samples for time-efficient learning, and under RP ≠ NP, O(log n) samples force superpolynomial time. Each concept is a decision tree of size O(p(n)), and the lower bound applies even to improper learners.

Load-bearing premise

The sharp Θ(p(n)) tradeoff assumes that every problem solvable by a nondeterministic machine in p(n) steps can be reduced to one fixed universal problem without changing the input length by more than a constant factor, and that the runtime bound p(n) can itself be computed efficiently.

Editorial extensions

If this is right

  • Under RP ≠ NP, there exists a VC-1 concept class that is learnable in polynomial time with O(n) samples, while any learner using O(log n) samples requires superpolynomial time.
  • Under randomized ETH, the same class is learnable from O(n) samples in O(n) time, but any learner using at most δn samples requires 2^{Ω(n)} time.
  • RP = NP if and only if every NP-enumerable class is learnable in polynomial time with O(VCdim(C)) samples, combining the forward observation of [PV88] with the new converse.
  • The tradeoffs extend to uniform-distribution PAC learning at the cost of VC dimension at most n, and to online learning where Littlestone dimension is 1 and mistake bounds replace sample complexity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Our inference: because the reduction is tailored to learners with a bounded sample count, an interesting test is whether increasing the sample budget slightly beyond the threshold breaks the argument in a way that could be quantified; this would map exactly where the [ABX08] barrier resumes force.
  • Our inference: the error-correcting code's rate and distance set the constants in the tradeoff, so choosing a code with rate close to 1 might sharpen the gap between the O(1)-sample slow learner and the Θ(p(n))-sample fast learner.
  • Our inference: a uniform-distribution analogue that kept VC dimension 1 would exactly match the distribution-free tradeoff; the present paper only achieves VC dimension at most n in that setting, leaving the gap as a natural open extension.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper introduces, for any language L in NTIME(t(n),p(n)) with verifier V, a concept class C_{L,V} whose concepts encode the lexicographically first certificate of each input through an error-correcting code on a sparse set of 'useful' examples. The main theorem (Theorem 2) shows that for every time-constructible growth function p(n) this class has VC dimension 1, is NTIME-enumerable, is learnable with O(1/ε) samples in exponential time, and is learnable with O(p(n)/ε) samples in polynomial time; conversely, any m(n)-sample, time-t(n) learner for C_{L,V} yields an AM protocol for L with m(n) proof bits and, by the perfect-soundness simulation, places NTIME(p(n)) in RTIME(2^{O(m(n))} t(n) log t(n) poly(p(n))). From this the paper derives sharp computational-statistical tradeoffs under randomized-ETH-type assumptions, an RP-versus-NP characterization, and extensions to uniform-distribution and online learning.

Significance. If the result stands, it is the first computational-statistical tradeoff in PAC learning based on worst-case NP-hardness rather than on cryptographic or average-case assumptions, and it provides a converse to the Pitt-Valiant observation that RP=NP makes all NP-enumerable classes learnable with O(VCdim) samples. The core reduction in Lemma 7.2 is carefully constructed: Merlin's labels form a valid sample, the code's error-correction radius matches the learner's error guarantee, and the perfect soundness is automatic because negative instances have no certificates. The decision-tree representation and the enumerability argument via Lex(V) are also clean and reproducible. The paper additionally gives a plausible explanation of why the ABX08 barrier is avoided, namely that the reduction is tied to a bounded sample count, and it extends the tradeoffs to uniform-distribution and online settings, which broadens the significance of the work.

major comments (2)
  1. [Section 8, proof of Theorem 2] The reduction x ↦ ⟨V,x⟩ from an arbitrary L ∈ NTIME(p(n)) to the universal language L⋆ increases the input length by a constant depending on V, so the contrapositive of Corollary 7.3 formally yields NTIME(p(n)) ⊆ RTIME(f(n+O(1))) rather than RTIME(f(n)) as stated in Theorem 2(ii). For polynomial p and for the exponential thresholds used in Corollaries 8.1–8.3 the constant shift is absorbed into the O(·) and poly(·) notation, but Theorem 2 as written quantifies over every time-constructible growth function, for which p(n+O(1)) need not be O(p(n)). Please either restrict Theorem 2 to polynomial p (matching the abstract) or add an explicit closure condition such as p(n+O(1)) = Θ(p(n)), and state explicitly that the constant shift is absorbed.
  2. [Section 9.1, Claim 9.2] The proof of Claim 9.2 first relies on the learner to succeed with probability 0.99 and then applies Markov's inequality to a fresh random x to conclude that the conditional error is at most ε⋆ with probability at least 0.99. If the learner is only guaranteed the 2/3 success probability of Definition 5.1, the product of these two probabilities is below the 2/3 completeness required by Definition 5.7. This is fixable by boosting the learner to high confidence at the cost of a constant factor in the sample count (absorbed in O(m(n))) and then adjusting constants, but the proof as written should state this amplification step explicitly.
minor comments (6)
  1. [Section 7.2, Corollary 7.3] Corollary 7.3 states 'There is a constant ε > 0' but never defines ε, and its proof invokes Lemma 7.2, which requires the code constant ε⋆; Corollary 8.1's proof has the same issue when it refers to 'the constant from Theorem 2'. Replace ε by ε⋆ throughout these statements.
  2. [Section 6.3.2, Claim 6.7] The runtime O(p(n)/ε) ignores the fact that reading each example of length n costs Ω(n) bit operations; the stated runtime should include an n factor (or the cost model should be stated explicitly). This does not affect the polynomial-time corollaries, since p(n) ≥ n, but it makes the formal runtime claim inaccurate.
  3. [Section 6.3.1, Claim 6.2] The proof that VCdim(C_{L,V}) = 1 assumes the existence of a concept labeling a chosen point by 1; if L is empty, or if the lexicographically first certificate for every accepting input encodes to an all-zero codeword, the VC dimension can be 0. Add a nondegeneracy condition or choose the code so that Enc(0) has a 1-coordinate.
  4. [Section 9.1, Claim 9.2, step 3] The sample is written as {(x(1), w1), …, (x(m), wm)}, but the examples drawn in step 1 are y(j) = (i(j), x(j)); the learner must receive the full pair (i(j), x(j)) together with the label wj.
  5. [Section 3.3] The informal description that the reduction 'produces G_i's for which none of the corresponding f_i's belong to C' appears to conflict with Lemma 7.2, where the distribution used for a positive instance is labeled by Cert_z ∈ C. Please clarify the intended relationship to the ABX08 framework, since the formal proof does not depend on this discussion.
  6. [Section 9.2, proof of Theorem 4] The proof contains the typo 'there there is', and the per-round runtime expression in Corollary 9.6 has unbalanced parentheses; also the references entry [CR VW02] contains a formatting artifact.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all lower bounds are conditional on external worst-case assumptions and the reductions are self-contained.

full rationale

The paper's derivation is self-contained with respect to its own claims. The central reduction Lemma 7.2 takes an m-sample, time-T learner A for CL,V and builds an AM protocol for L with m bits of nondeterminism: Merlin supplies the m labels, A outputs a hypothesis, decoding recovers a certificate, and V verifies it. Completeness uses the code's error-correction guarantee and the learner's error bound; soundness is perfect because for z not in L no certificate verifies. This is a genuine reduction, not an equivalence built into the definitions: the concept class merely encodes certificates, and the lower bound is conditional on the external assumption NTIME(p(n)) not subset of RTIME(t(n)). The upper bounds (VCdim = 1, O(1/epsilon)-sample exponential-time learner, and O(p(n)/epsilon)-sample fast ERM) are standard VC/ERM arguments. The only transfer step, Section 8's use of L* = {<M,x> : M accepts x in p(|x|) steps} as NTIME(p(n))-hard, is a standard universal simulation and padding argument, and the constant input-length increase is absorbed by the O(.) and poly(.) bounds; it does not smuggle in the target conclusion. No fitted parameters are renamed as predictions, and no load-bearing self-citation appears: the cited [PV88] direction is used only for the forward implication, while all code, enumerability, and reduction lemmas on which the main theorem depends are proved in the paper. The barrier-circumvention claim is a novelty claim, not a circularity. Hence score 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No new physical or mathematical entities are postulated; the concept class CL,V is a finite set of Boolean functions constructed from a verifier and an error-correcting code, not an unexplained primitive. All assumptions are standard complexity hypotheses or known results.

assumptions (6)
  • domain assumption The relevant worst-case assumptions: NTIME(p(n)) is not contained in RTIME(t(n)); in corollaries, RP≠NP or randomized ETH.
    Theorem 2 and its corollaries are conditional on these hypotheses. They are standard complexity assumptions, not derived in the paper.
  • standard math Efficient binary error-correcting codes with constant rate and constant relative distance exist (Definition 5.8).
    Used to encode certificates so that a hypothesis with error below the decoding radius yields the true certificate. The authors cite expander codes [SS96, CRVW02].
  • standard math L* = {⟨M,x⟩ : M accepts x in p(|x|) steps} is NTIME(p(n))-hard, and time-p(n) nondeterministic machines can be simulated in O(p(n) log p(n)) time.
    Invoked in Section 8 to transfer hardness from arbitrary NTIME(p(n)) languages to the constructed concept class. Depends on standard universal simulation and padding.
  • standard math VC dimension and empirical risk minimization facts: VCdim(C) ≤ log|C| and ERM learns finite classes with O(log|C|/ε) samples.
    Used for the upper bounds (O(1/ε) and O(p(n)/ε) sample learners) and for the VCdim bound in the uniform-distribution extension.
  • domain assumption PAC learners are distribution-free and must output efficiently evaluable hypotheses.
    The lower-bound reduction (Lemma 7.2) evaluates the learner's hypothesis on all useful inputs and relies on the learner succeeding on the uniform distribution over useful examples. This is the standard PAC definition used in the paper.
  • standard math Fact 2.1 (Pitt and Valiant): if RP=NP, every NP-enumerable class is learnable in polynomial time with O(VCdim(C)) samples.
    Forward direction of Corollary 2.2, cited from prior work; the paper proves only the converse.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Computational-Statistical Tradeoffs from NP-hardness." pith.science (2026). https://pith.science/paper/PNLI6LAO

@misc{pith2026250713222,
  author       = {Pith},
  title        = {Pith review of: Computational-Statistical Tradeoffs from NP-hardness},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PNLI6LAO}},
  note         = {Machine review of arXiv:2507.13222}
}
abstract

A central question in computer science and statistics is whether efficient algorithms can achieve the information-theoretic limits of statistical problems. Many computational-statistical tradeoffs have been shown under average-case assumptions, but since statistical problems are average-case in nature, it has been a challenge to base them on standard worst-case assumptions. In PAC learning where such tradeoffs were first studied, the question is whether computational efficiency can come at the cost of using more samples than information-theoretically necessary. We base such tradeoffs on $\mathsf{NP}$-hardness and obtain: $\circ$ Sharp computational-statistical tradeoffs assuming $\mathsf{NP}$ requires exponential time: For every polynomial $p(n)$, there is an $n$-variate class $C$ with VC dimension $1$ such that the sample complexity of time-efficiently learning $C$ is $\Theta(p(n))$. $\circ$ A characterization of $\mathsf{RP}$ vs. $\mathsf{NP}$ in terms of learning: $\mathsf{RP} = \mathsf{NP}$ iff every $\mathsf{NP}$-enumerable class is learnable with $O(\mathrm{VCdim}(C))$ samples in polynomial time. The forward implication has been known since (Pitt and Valiant, 1988); we prove the reverse implication. Notably, all our lower bounds hold against improper learners. These are the first $\mathsf{NP}$-hardness results for improperly learning a subclass of polynomial-size circuits, circumventing formal barriers of Applebaum, Barak, and Xiao (2008).

Figures

Figures reproduced from arXiv: 2507.13222 by the authors.

Figure 1
Figure 1. An illustration of a computational-statistical tradeoff [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. An illustration of a computationally intractable learning problem [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Computational-statistical tradeoffs under randomized ETH. Time-efficient learning [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: An illustration of Lemma 3.1 3.3 Details of the [ABX08] barrier and why we evade it [ABX08] considered nonadaptive Turing reductions from an NP-hard language L to the learning of a concept class C. These are reductions that map an instance z to multiple, say k, learnin…
Figure 5
Figure 5. Figure 5: Illustration of a decision tree for Certz where z = 1n . Proof. If z ̸∈ L, then Certz is a decision tree of size 1. Otherwise, assume z ∈ L and w ⋆ is the lexicographically first certificate for z. We will describe the decision tree Tz. See [PITH_FULL_IMAGE:figures/fu…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 36 canonical work pages

  1. [1]

    Computational Complexity: A Modern Approach

    Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach . Cambridge University Press, 2009

    2009

  2. [2]

    On basing lower-bounds for learning on worst-case assumptions

    Benny Applebaum, Boaz Barak, and David Xiao. On basing lower-bounds for learning on worst-case assumptions. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS) , pages 211--220, 2008

    work page 2008

  3. [3]

    On basing one-way functions on NP -hardness

    Adi Akavia, Oded Goldreich, Shafi Goldwasser, and Dana Moshkovitz. On basing one-way functions on NP -hardness. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC) , pages 701--710, 2006

    work page 2006

  4. [4]

    The design and analysis of computer algorithms

    Alfred Aho, John Hopcroft, and Jeffrey Ullman. The design and analysis of computer algorithms . Addison--Wesley, 1974

    work page 1974

  5. [5]

    Trading group theory for randomness

    L \'a szl \'o Babai. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC) , pages 421--429, 1985

    work page 1985

  6. [6]

    Reducibility and statistical-computational gaps from secret leakage

    Matthew Brennan and Guy Bresler. Reducibility and statistical-computational gaps from secret leakage. In Proceedings of the 33rd Annual Conference on Learning Theory (COLT) , pages 648--847, 2020

    work page 2020

  7. [7]

    Learnability and the Vapnik-Chervonenkis dimension

    Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred Warmuth. Learnability and the Vapnik-Chervonenkis dimension . Journal of the ACM (JACM) , 36(4):929--965, 1989

    work page 1989

  8. [8]

    Cryptographic primitives based on hard learning problems

    Avrim Blum, Merrick Furst, Michael Kearns, and Richard J Lipton. Cryptographic primitives based on hard learning problems. In Annual International Cryptology Conference (CRYPTO) , pages 278--291, 1993

    work page 1993

Show all 39 references
  1. [9]

    Learning boolean functions in an infinite attribute space

    Avrim Blum. Learning boolean functions in an infinite attribute space. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC) , pages 64--72, 1990

    1990

  2. [10]

    On worst-case to average-case reductions for NP problems

    Andrej Bogdanov and Luca Trevisan. On worst-case to average-case reductions for NP problems. SIAM Journal on Computing , 36(4):1119--1159, 2006

    2006

  3. [11]

    The complexity of unique k - SAT : An isolation lemma for k - CNFs

    Chris Calabro, Russell Impagliazzo, Valentine Kabanets, and Ramamohan Paturi. The complexity of unique k - SAT : An isolation lemma for k - CNFs . Journal of Computer and System Sciences , 74(3):386--393, 2008

    2008

  4. [12]

    Randomness conductors and constant-degree lossless expanders

    Michael Capalbo, Omer Reingold, Salil Vadhan, and Avi Wigderson. Randomness conductors and constant-degree lossless expanders. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC) , page 659–668, 2002

    2002

  5. [13]

    Computational sample complexity

    Scott Decatur, Oded Goldreich, and Dana Ron. Computational sample complexity. SIAM Journal on Computing , 29(3):854--879, 2000

    2000

  6. [14]

    Exponential time complexity of the Permanent and the Tutte polynomial

    Holger Dell, Thore Husfeldt, D\' a niel Marx, Nina Taslaman, and Martin Wahl\' e n. Exponential time complexity of the Permanent and the Tutte polynomial. ACM Trans. Algorithms , 10(4), 2014

    2014

  7. [15]

    More data speeds up training time in learning halfspaces over sparse vectors

    Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. More data speeds up training time in learning halfspaces over sparse vectors. Advances in Neural Information Processing Systems (NeurIPS) , 26, 2013

    2013

  8. [16]

    From average case complexity to improper learning complexity

    Amit Daniely, Nati Linial, and Shai Shalev-Shwartz. From average case complexity to improper learning complexity. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC) , pages 441--448, 2014

    2014

  9. [17]

    Hardness of proper learning

    Vitaly Feldman. Hardness of proper learning. In Encyclopedia of Algorithms , 2016

    2016

  10. [18]

    Random-self-reducibility of complete sets

    Joan Feigenbaum and Lance Fortnow. Random-self-reducibility of complete sets. SIAM Journal on Computing , 22(5):994--1005, 1993

    1993

  11. [19]

    How to construct random functions

    Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM (JACM) , 33(4):792--807, 1986

    1986

  12. [20]

    Limited nondeterminism

    Judy Goldsmith, Matthew Levy, and Martin Mundhenk. Limited nondeterminism. ACM SIGACT News , 27(2):20--29, 1996

    1996

  13. [21]

    No better ways to generate hard NP instances than picking uniformly at random

    Russell Impagliazzo and Levin Leonid. No better ways to generate hard NP instances than picking uniformly at random. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS) , pages 812--821, 1990

    1990

  14. [22]

    A personal view of average-case complexity

    Russell Impagliazzo. A personal view of average-case complexity. In Proceedings of 10th Annual Structure in Complexity Theory Conference , pages 134--147, 1995

    1995

  15. [23]

    Machine learning: Trends, perspectives, and prospects

    Michael Jordan and Tom Mitchell. Machine learning: Trends, perspectives, and prospects. Science , 349(6245):255--260, 2015

    2015

  16. [24]

    Computations with a restricted number of nondeterministic steps

    Chandra Kintala and Patrick Fischer. Computations with a restricted number of nondeterministic steps. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing (STOC) , pages 178--185, 1977

    1977

  17. [25]

    Cryptographic limitations on learning B oolean formulae and finite automata

    Michael Kearns and Leslie Valiant. Cryptographic limitations on learning B oolean formulae and finite automata. Journal of the ACM , 41(1):67--95, 1994

    1994

  18. [26]

    Kearns and Umesh Vazirani

    Michael J. Kearns and Umesh Vazirani. An Introduction to Computational Learning Theory . The MIT Press, 08 1994

    1994

  19. [27]

    Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm

    Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning , 2:285--318, 1988

    1988

  20. [28]

    From on-line to batch learning

    Nick Littlestone. From on-line to batch learning. In Proceedings of the 2nd Annual Conference on Learning Theory (COLT) , pages 269--284, 1989

    1989

  21. [29]

    Some results on relativized deterministic and nondeterministic time hierarchies

    Shlomo Moran. Some results on relativized deterministic and nondeterministic time hierarchies. Journal of Computer and System Sciences , 22(1):1--8, 1981

    1981

  22. [30]

    Computational limitations on learning from examples

    Leonard Pitt and Leslie G Valiant. Computational limitations on learning from examples. Journal of the ACM (JACM) , 35(4):965--984, 1988

    1988

  23. [31]

    The strength of weak learnability

    Robert Schapire. The strength of weak learnability. Machine learning , 5:197--227, 1990

    1990

  24. [32]

    Computational sample complexity and attribute-efficient learning

    Rocco Servedio. Computational sample complexity and attribute-efficient learning. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC) , pages 701--710, 1999

    1999

  25. [33]

    https://simons.berkeley.edu/programs/computational-complexity-statistical-inference , 2021

    Simons Institute Program on Computational Complexity of Statistical Inference. https://simons.berkeley.edu/programs/computational-complexity-statistical-inference , 2021

    2021

  26. [34]

    Expander codes

    Michael Sipser and Daniel Spielman. Expander codes. IEEE Transactions on Information Theory , 42(6):1710--1722, 1996

    1996

  27. [35]

    Understanding Machine Learning: From Theory to Algorithms

    Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms . Cambridge University Press, 2014

    2014

  28. [36]

    Using more data to speed-up training time

    Shai Shalev-Shwartz, Ohad Shamir, and Eran Tromer. Using more data to speed-up training time. In Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics (AISTATS) , volume 22, pages 1019--1027, 2012

    2012

  29. [37]

    A theory of the learnable

    Leslie Valiant. A theory of the learnable. Communications of the ACM , 27(11):1134--1142, 1984

    1984

  30. [38]

    On the uniform convergence of relative frequencies of events to their probabilities

    Vladimir Vapnik and Alexey Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications , 16(2):264--280, 1971

    1971

  31. [39]

    New perspectives on the complexity of computational learning, and other problems in theoretical computer science

    David Xiao. New perspectives on the complexity of computational learning, and other problems in theoretical computer science . Ph.D. Thesis, Princeton University, 2009

    2009

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.