Pith. sign in

REVIEW 3 major objections 6 minor 33 references

Boosting with List-Decodable Codes

T0 review · 3 major / 6 minor · reviewed 2026-07-08 · glm-5.2

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

Pith's one-line read Boosting Beats Its Lower Bound via Error-Correcting Codes

desk verdict Clean, novel boosting framework with a real round-complexity improvement; the closure assumption is the main limitation and the paper is honest about it. read the letter →

arxiv 2607.05791 v1 pith:P64YKGDS submitted 2026-07-07 stat.ML cs.CCcs.DScs.LG

Addison Prairie , Li-Yang Tan This is my paper
classification stat.MLcs.CCcs.DScs.LG
keywords boostinggammafraclearnerstrongweakepsilonhypothesis
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

Boosting is a foundational technique in machine learning that converts a weak learner—one that performs only slightly better than random guessing—into a strong learner that achieves arbitrarily high accuracy. Since 1995, a lower bound has held that any boosting algorithm must call the weak learner at least O(log(1/ε)/γ²) times to reach accuracy 1−ε, and this bound was believed to be a fundamental ceiling. This paper circumvents that lower bound for concept classes satisfying a structural closure property: if the class is closed under XOR of O(log(1/γ)) copies of any function in the class, the authors' booster needs only O(log(1/ε)) calls to the weak learner—a quadratic improvement in the dependence on the weak learner's advantage γ. The key insight is a new connection between boosting and list-decodable error-correcting codes. The target function is treated as a message; it is encoded (via the XOR code), the weak learner is run on the encoded version producing a corrupted codeword, and a list decoder recovers a small set of candidate hypotheses from which a strong hypothesis is identified using additional samples. For uniform-distribution learning, a single call to the weak learner suffices.

What carries the argument

List-decodable error-correcting codes (specifically the k-XOR code), distributional codes, local encodability, local list-decoding

What would settle it

Identify a natural concept class that is not closed under O(log(1/γ))-XOR but for which efficient weak learners exist; this would delineate the boundary of the framework's applicability.

Watch

Extended reading notes

Core claim

The central discovery is a reduction from boosting to list-decodable coding. Given a target function f, the booster encodes f as f⊕k (the XOR of k copies of f), runs the weak learner on this encoded function, and treats the resulting weak hypothesis as a corrupted codeword at Hamming distance at most 1/2−γ from the true encoding. A list decoder for the XOR code then produces a short list of candidate functions, one of which approximates f to accuracy 1−ε. This yields a booster with O(log(1/ε)) rounds for XOR-closed classes, breaking the Freund lower bound of Ω(log(1/ε)/γ²) that applies to generic concept classes. The authors also develop a distributional generalization of error-correcting码,的

Load-bearing premise

The concept class being learned must be closed under XOR of O(log(1/γ)) copies of its functions, meaning if f is in the class, then the function that takes k inputs and XORs their f-values must also be in the class. If a concept class lacks this structural property, the framework does not apply.

Editorial extensions

If this is right

  • Concept classes closed under O(log n)-XOR—including small constant-depth circuits like AC0—can be strong-learned with quadratically fewer weak-learner calls than previously known, since γ = n^{-O(1)} only requires closure under O(log n)-XOR.
  • Uniform-distribution boosting can be made distribution-specific: to strong-learn over the uniform distribution, only a uniform-distribution weak learner is needed, and a single call suffices.
  • The code-to-boosting reduction is generic: any locally encodable, locally list-decodable code satisfying the closure property yields a boosting algorithm, opening a design space for future boosters parameterized by code choice.
  • The tradeoff—fewer rounds but each round operates on a polylogarithmically larger input—may be favorable in settings where weak-learner calls are expensive (e.g., distributed or privacy-constrained learning) but sample generation is cheap.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 6 minor

Summary. This paper presents a new boosting algorithm that circumvents Freund's Ω(log(1/ε)/γ²) round-complexity lower bound for concept classes F closed under O(log(1/γ))-XOR. The key idea is a novel connection between boosting and list-decodable codes: the target function is viewed as a message, encoded via the k-XOR code, and the weak learner's output is viewed as a corrupted codeword that is then list-decoded to obtain a strong hypothesis. The paper proves two main theorems: Theorem 1 (distribution-free, O(log(1/ε)) calls to W) and Theorem 2 (uniform-distribution, 1 call to W). The core technical contribution is a distributional list-decoder for the XOR code (Theorem 5/8), which generalizes the decoder of [IJKW10] to arbitrary (including continuous) distributions by replacing sampler-graph arguments with a direct concentration inequality (Claim 6.7).

Significance. The connection between boosting and list-decodable codes is conceptually clean and yields concrete quantitative improvements over prior work. Theorem 2 improves on Boneh-Lipton [BL93] exponentially in the γ-dependence of the closure assumption (O(log(1/γ)/ε)-XOR vs. O(1/(γ²ε))-XOR), making the result applicable to classes like AC⁰ for polynomially-small γ. The distributional decoder (Theorem 8) is a non-trivial generalization of [IJKW10]; the Fubini argument in Claim 6.5 and the KL-divergence-based concentration inequality in Claim 6.7 are verified to be correct and hold for arbitrary distributions. The closure assumption is clearly stated as a condition of the theorem rather than hidden. The framework is modular: Theorem 4 provides a generic code-to-booster template, and the paper is transparent about the input-expansion tradeoff.

major comments (3)
  1. [Theorem 6 / Proof (Section 5)] The proof of Theorem 6 sets k = O(log(1/γ)) and invokes Theorem 5 with ε = 0.01 to obtain a 0.49-weak learner W'. The additional sample complexity is stated as O(k²·log(1/ε)/γ²). However, the weak learner W is called on the (n·k)-th slice F_{n·k}, and if W requires s(n) samples on n-bit inputs, the call on F_{n·k} requires s(n·k) samples. The proof writes the sample bound as S = O(k²/γ²) but does not explicitly track how s(n·k) relates to the stated O(k²·log(1/ε)/γ²) bound. If s is superlinear in the input dimension, the per-call sample cost could exceed what is claimed. The authors should clarify whether s is assumed to be polynomial (in which case s(n·k) = poly(n·k) and the bound holds with the polylog(k) factor absorbed) or state the assumption explicitly.
  2. [Theorem 7 (Section 5)] The proof of Theorem 7 is described as 'a straightforward instantiation of Theorem 4 with Theorem 5,' but no proof is provided beyond this sentence. While the claim is plausible, the additional sample complexity O((log(1/γ) + log(1/ε))/ε) stated in Theorem 7 does not follow immediately from plugging the parameters of Theorem 5 (with k = O(log(1/γ)/ε)) into Theorem 4, which would give O(k²·log(1/ε)/γ²) additional samples. The stated bound appears to exploit additional structure (e.g., the uniform distribution allowing sample generation without labeled examples, or a tighter analysis). A brief derivation would strengthen the paper.
  3. [Section 6, XOR-to-direct-product reduction] The reduction from the XOR code decoder to the direct product decoder (the three-step argument at the beginning of Section 6, citing [IJKW10] and [GL89]) is described as 'the same as that of [IJKW10] and thus we will only describe it for the sake of completeness, without repeating the analysis.' The key claim is that the XOR-to-direct-product reduction from [IJKW10] 'carries over to the distributional setting since it is syntactic and pointwise.' This is load-bearing for Theorem 5, which is in turn load-bearing for both Theorems 1 and 2. While the claim of pointwise/syntactic transfer is plausible, a brief justification of why the distributional setting does not introduce subtleties in steps 1–3 (particularly step 2, which uses the [GL89] Hadamard decoder over D^{2k} × U^{2k}) would be appropriate, given that the paper's own contribution is precisely showing that distributional generaliz
minor comments (6)
  1. [Abstract] The abstract states 'a single batch of Õ(log(1/ε)/γ²) additional samples,' but Theorem 6 gives O(k²·log(1/ε)/γ²) with k = O(log(1/γ)), so the dependence is Õ(log(1/γ)²·log(1/ε)/γ²). The abstract's Õ notation suppresses the log(1/γ)² factor, which is fine, but the reader may initially expect only log(1/ε)/γ². Consider clarifying.
  2. [Section 1, 'Mildness of Our Closure Assumption'] The claim that 'the XOR of O(log n) bits can be computed by a poly(n)-sized DNF/CNF' is correct, but the argument that this makes the closure assumption mild for 'computationally weaker ones such as small, constant-depth circuits' could be more precise. AC⁰ circuits of depth d computing XOR of m bits require size exp(m^{1/(d-1)}), so for m = O(log n) this is exp((log n)^{1/(d-1)}) = n^{o(1)}, which is indeed subpolynomial but not necessarily poly(n) for fixed d. The statement is correct but the reasoning could be sharper.
  3. [Section 4, Proof of Theorem 4] The test set size is stated as '100·log(L)/ε' but the Bernstein bound uses t = 100·log(L)/ε and derives exp(-3tε/8) ≤ 1/(8L). This requires t ≥ (8/(3ε))·8·ln(2L) ≈ (64 ln 2)/(3ε)·log(8L), which is satisfied by t = 100·log(L)/ε for sufficiently large L, but the constant 100 should be verified for small L (e.g., L = O(k/γ²) could be small for moderate parameters).
  4. [Section 6.2.1, Proof of Claim 6.5] In the chain of equalities computing E_x[Φ̂(x)], the step from line 3 to line 4 (exchanging the order of integration) is the key Fubini argument. The footnote on p.17 addresses measure-theoretic subtleties for continuous distributions, which is good. However, the notation dD^{k/2-1}(X) is slightly ambiguous when X is a vector in X^{k/2-1}; consider writing dD^{k/2-1}(X) explicitly as the product measure.
  5. [Section 6.2.2, Proof of Lemma 6.2] In the bound on ξ, the inequality 'ρ·e^{-kρ/2} ≤ α·γ²/16 for ρ ∈ (α/2, 1]' requires k to be sufficiently large relative to α and γ. The condition k ≥ Ω(log(1/γ)/ε) from Theorem 8 (with α = ε/32) gives k ≥ Ω(log(1/γ)/ε), which should suffice, but the explicit verification that this k is large enough for the bound ρ·e^{-kρ/2} ≤ α·γ²/16 to hold at ρ = α/2 would help the reader.
  6. [References] The paper cites [IJKW10] extensively but does not cite [GL89] in the bibliography with full bibliographic details (it appears in the references but the in-text citation format is inconsistent with other references). Minor formatting issue.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback. We address each major comment below. In brief: (1) we will clarify the sample complexity tracking for the weak learner on expanded input domains, explicitly stating the polynomiality assumption; (2) we will add a derivation for Theorem 7's sample bound, which exploits the uniform-distribution structure; and (3) we will expand the justification for why the XOR-to-direct-product reduction carries over to the distributional setting. All three points lead to clarifications or additions to the manuscript rather than changes to the results themselves.

read point-by-point responses

  1. Referee: Theorem 6 / Proof (Section 5): Sample complexity tracking for s(n·k) vs. stated O(k²·log(1/ε)/γ²) bound.

    Authors: The referee is correct that the proof of Theorem 6 does not explicitly track how the sample complexity s(n·k) of the weak learner on the expanded input relates to the stated bound. We will revise the manuscript to clarify this. The key point is that the O(k²·log(1/ε)/γ²) bound refers to the *additional* labeled samples beyond those used by the weak learner calls. The per-call sample cost of W on F_{n·k} is indeed s(n·k), and the total sample complexity includes O(log(1/ε)) · s(n·k) samples for the weak learner calls plus O(k²·log(1/ε)/γ²) additional samples for the decoder and hypothesis testing. We will state explicitly that s is assumed to be polynomial (which is the standard setting for efficient weak learners), so that s(n·k) = poly(n·k) = poly(n, log(1/γ)), and the total sample complexity remains polynomial in all parameters. This assumption was implicit in the paper's claim that the algorithm is efficient (running in poly(n, 1/γ, 1/ε) time), but it should be stated explicitly in the proof of Theorem 6. revision: yes

  2. Referee: Theorem 7 (Section 5): Missing derivation for the O((log(1/γ) + log(1/ε))/ε) sample bound.

    Authors: The referee is correct that the stated bound does not follow from a direct parameter substitution into Theorem 4, and that additional structure from the uniform distribution is being exploited. We will add a brief derivation. The key observation is that in the uniform-distribution setting, the decoder's unlabeled samples from D can be generated using random bits at no labeled-sample cost. Specifically, in Theorem 4, the u unlabeled samples required by the decoder cost zero labeled samples when D is uniform. The only labeled samples needed are the ℓ·s samples for the weak learner call (where ℓ = k for the XOR code, so this is k·s) and the O(log(L)/ε) testing samples. With k = O(log(1/γ)/ε), the list size L = O(k/γ²), and the decoder's sample complexity u = O(k²·log(1/ε)/γ²) being absorbed into unlabeled samples, the labeled sample bound becomes O(log(L)/ε) = O((log(k/γ²))/ε) = O((log(1/γ) + log(1/ε))/ε). We will include this derivation in the revised manuscript. revision: yes

  3. Referee: Section 6, XOR-to-direct-product reduction: Insufficient justification that the reduction carries over to the distributional setting.

    Authors: We agree that the claim of pointwise/syntactic transfer is load-bearing and deserves more justification, particularly given that the distributional generalization is a core contribution of the paper. We will expand the discussion at the beginning of Section 6 to address each of the three steps. For step 1 (XOR to Hadamard), the construction of C' from C is indeed pointwise: each output bit of C' depends only on the corresponding bits of C's output, so the accuracy guarantee transfers from D^k to D^{2k} × U^{2k} by a direct calculation that holds for any distribution D. For step 2 (Hadamard decoding via [GL89]), the Goldreich-Levin decoder operates on the uniform component U^{2k} of the product distribution, and its correctness depends only on the uniform randomness of the bits b_1,...,b_{2k}; the distribution D^{2k} over the x-coordinates enters only through the accuracy of C', which is already established. For step 3 (feeding into Theorem 8), this is a direct application of our distributional direct-product decoder, which is proven for arbitrary D. We will add these justifications to the manuscript, while still not repeating the full analysis from [IJKW10] since the transfer is genuinely syntactic once the distributional correctness of each component is established. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity detected; derivation chain is self-contained

full rationale

The paper's derivation chain is clean and non-circular. Theorem 4 (the generic code-to-boosting connection) is proven directly in Section 4: given a locally encodable, list-decodable code C and a concept class F closed under C, the boosting algorithm runs W on Enc(f), feeds the output to Dec, and tests the resulting list with standard Bernstein/Chernoff bounds. No step reduces to its own input by construction. Theorem 5 (the distributional XOR decoder) is proven via Theorem 8, which is established from scratch through Lemmas 6.1 and 6.2, with the key technical novelty (Claim 6.7's concentration inequality) fully proven in-line. The XOR-to-direct-product reduction cites [IJKW10] and [GL89], but these are external works by different author sets, not self-citations. Theorems 6 and 7 are straightforward instantiations of Theorem 4 with Theorem 5, with no fitted parameters or definitional loops. The closure assumption on F is a clearly stated structural condition, not a definition that smuggles in the conclusion. The weak learner W is an external black-box input, not defined in terms of the boosting output. No step in the chain exhibits any of the enumerated circularity patterns.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

No invented entities. The free parameter k is determined by the theory, not fitted. The axioms are standard learning-theory assumptions or rely on established coding-theory results.

free parameters (1)
  • k (XOR arity) = O(log(1/γ)) for Theorem 1; O(log(1/γ)/ε) for Theorem 2
    Chosen to satisfy the list-decoding radius requirement; not fitted to data but set by the theory.
assumptions (3)
  • domain assumption F is closed under k-XOR
    Required for the encoding to stay within the concept class (Sections 1, 5).
  • domain assumption Existence of a γ-weak learner W
    Standard boosting assumption; W produces hypotheses with accuracy 1/2+γ.
  • standard math List-decoding properties of the XOR code [IJKW10]
    Theorem 5 relies on the list-decodability of the k-XOR code, generalized to the distributional setting.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Boosting with List-Decodable Codes." pith.science (2026). https://pith.science/paper/P64YKGDS

@misc{pith2026260705791,
  author       = {Pith},
  title        = {Pith review of: Boosting with List-Decodable Codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P64YKGDS}},
  note         = {Machine review of arXiv:2607.05791}
}
abstract

Boosting is a fundamental technique for generically improving the accuracy of learning algorithms (Schapire 1989). Existing boosting algorithms construct a strong learner using $O(\log(\frac{1}{\epsilon})/\gamma^2)$ calls to a $\gamma$-advantage weak learner, and this round complexity is known to be optimal for generic boosters that succeed on all concept classes (Freund 1995). We show that this lower bound can be circumvented for concept classes that satisfy a mild closure property. Specifically, we present a new boosting algorithm that, for any class $\mathcal{F}$ closed under $O(\log \frac{1}{\gamma})$-XOR, strong learns $\mathcal{F}$ using $O(\log \frac{1}{\epsilon})$ calls to a $\gamma$-advantage weak learner and a single batch of $\tilde{O}(\log(\frac{1}{\epsilon})/\gamma^2)$ additional samples. Our algorithm arises from a new and simple connection between boosting and list-decodable codes. Viewing the target function as a message, we run the weak learner on its encoding and view the resulting weak hypothesis as a corrupted codeword. Feeding this corrupted codeword to a list decoder, we obtain a small list of candidate hypotheses, at least one of which is a strong hypothesis for the original function. Using additional samples, we identify and output this strong hypothesis.

Figures

Figures reproduced from arXiv: 2607.05791 by the authors.

Figure 1
Figure 1. Existing boosting algorithms repeatedly call the weak learner, using pre￾vious hypotheses to reweight (∽) the distribution of each dataset Si fed to W. The output hout is then constructed by aggregating the weak hypotheses h1, . . . , hT . 3 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Our approach to boosting modifies the function being learned by W, then feeds the resulting weak hypothesis into a decoder to produce a list h1, . . . , hL, one of which is a strong hypothesis for the target function. Using additional samples (S2), we find and output this strong hypothesis with high probability. 2.1 Boosting with List-Decodable Codes To describe how to obtain a boosting algorithm from a list-decodab… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages

  1. [1]

    Communications of the ACM , year=

    Leslie Valiant , title=. Communications of the ACM , year=

    work page

  2. [2]

    On Yao's XOR-Lemma

    Goldreich, Oded and Nisan, Noam and Wigderson, Avi. On Yao's XOR-Lemma. Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation: In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Sal...

    work page doi:10.1007/978-3-642-22670-0_23 2011

  3. [3]

    Pseudorandom Generators without the XOR Lemma , journal =

    Madhu Sudan and Luca Trevisan and Salil Vadhan , keywords =. Pseudorandom Generators without the XOR Lemma , journal =. 2001 , issn =. doi:https://doi.org/10.1006/jcss.2000.1730 , url =

    work page doi:10.1006/jcss.2000.1730 2001

  4. [4]

    Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing , pages =

    Levin, Leonid , title =. Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing , pages =. 1985 , isbn =. doi:10.1145/22145.22185 , abstract =

    work page doi:10.1145/22145.22185 1985

  5. [5]

    39th Computational Complexity Conference (CCC 2024) , pages =

    Blanc, Guy and Koch, Caleb and Strassle, Carmen and Tan, Li-Yang , title =. 39th Computational Complexity Conference (CCC 2024) , pages =. 2024 , volume =. doi:10.4230/LIPIcs.CCC.2024.16 , annote =

    work page doi:10.4230/lipics.ccc.2024.16 2024

  6. [6]

    Goldreich, Oded and Levin, L. A. , title =. Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing , pages =. 1989 , isbn =. doi:10.1145/73007.73010 , abstract =

    work page doi:10.1145/73007.73010 1989

  7. [7]

    SIAM Journal on Computing , volume =

    Impagliazzo, Russell and Jaiswal, Ragesh and Kabanets, Valentine and Wigderson, Avi , title =. SIAM Journal on Computing , volume =. 2010 , doi =. https://doi.org/10.1137/080734030 , abstract =

    work page doi:10.1137/080734030 2010

  8. [8]

    SIAM Journal on Computing , volume =

    Impagliazzo, Russell and Jaiswal, Ragesh and Kabanets, Valentine , title =. SIAM Journal on Computing , volume =. 2009 , doi =. https://doi.org/10.1137/070683994 , abstract =

    work page doi:10.1137/070683994 2009

Show all 33 references
  1. [9]

    Approximation, Randomization, and Combinatorial Optimization

    Blais, Eric and Canonne, Cl\'. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) , pages =. 2015 , volume =. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.512 , annote =

    2015 doi

  2. [10]

    and Burcht, C

    Blum, A. and Burcht, C. and Langford, J. , booktitle=. On learning monotone Boolean functions , year=

  3. [11]

    Goldman and M.J

    S.A. Goldman and M.J. Kearns and R.E. Schapire , abstract =. On the Sample Complexity of Weak Learning , journal =. 1995 , issn =. doi:https://doi.org/10.1006/inco.1995.1045 , url =

    1995 doi

  4. [12]

    , title =

    Boneh, Dan and Lipton, Richard J. , title =. 1993 , isbn =. doi:10.1145/168304.168372 , booktitle =

    1993 doi

  5. [13]

    Schapire , abstract =

    Yoav Freund and Robert E. Schapire , abstract =. A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting , journal =. 1997 , issn =. doi:https://doi.org/10.1006/jcss.1997.1504 , url =

    1997 doi

  6. [14]

    and Freund, Yoav , title =

    Schapire, Robert E. and Freund, Yoav , title =. 2012 , month =. doi:10.7551/mitpress/8291.001.0001 , url =

    2012 doi

  7. [15]

    Boosting a Weak Learning Algorithm by Majority , journal =

    Yoav Freund , abstract =. Boosting a Weak Learning Algorithm by Majority , journal =. 1995 , issn =. doi:https://doi.org/10.1006/inco.1995.1136 , url =

    1995 doi

  8. [16]

    Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages =

    Alon, Noga and Gonen, Alon and Hazan, Elad and Moran, Shay , title =. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages =. 2021 , isbn =. doi:10.1145/3406325.3451030 , abstract =

    2021 doi

  9. [17]

    The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem , year=

    Blanc, Guy and Hayderi, Alexandre and Koch, Caleb and Tan, Li-Yang , booktitle=. The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem , year=

  10. [18]

    2014 , isbn =

    Shalev-Shwartz, Shai and Ben-David, Shai , title =. 2014 , isbn =

    2014

  11. [19]

    Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , pages =

    Shaltiel, Ronen and Viola, Emanuele , title =. Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing , pages =. 2008 , isbn =. doi:10.1145/1374376.1374461 , abstract =

    2008 doi

  12. [20]

    Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs , year=

    Grinberg, Aryeh and Shaltiel, Ronen and Viola, Emanuele , booktitle=. Indistinguishability by Adaptive Procedures with Advice, and Lower Bounds on Hardness Amplification Proofs , year=

  13. [21]

    The Complexity of Local List Decoding

    Gutfreund, Dan and Rothblum, Guy N. The Complexity of Local List Decoding. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. 2008

    2008

  14. [22]

    2009 , eprint=

    Distribution-Specific Agnostic Boosting , author=. 2009 , eprint=

    2009

  15. [23]

    Proceedings of the 23rd International Conference on Neural Information Processing Systems , pages =

    Kalai, Adam Tauman and Kanade, Varun , title =. Proceedings of the 23rd International Conference on Neural Information Processing Systems , pages =. 2009 , isbn =

    2009

  16. [24]

    Long and Rocco A

    Philip M. Long and Rocco A. Servedio , title =. Journal of Machine Learning Research , year =

  17. [25]

    Proceedings of The 35th International Conference on Algorithmic Learning Theory , pages =

    The Impossibility of Parallelizing Boosting , author =. Proceedings of The 35th International Conference on Algorithmic Learning Theory , pages =. 2024 , volume =

    2024

  18. [26]

    Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate , year=

    Mon, Geoffrey and Moshkovitz, Dana and Oh, Justin , booktitle=. Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate , year=

  19. [27]

    A Note on Amplifying the Error-Tolerance of Locally Decodable Codes , volume =

    Ben-Aroya, Avraham and Efremenko, Klim and Ta-Shma, Amnon , year =. A Note on Amplifying the Error-Tolerance of Locally Decodable Codes , volume =

  20. [28]

    SIAM Journal on Computing , volume =

    Dinur, Irit and Harsha, Prahladh and Kaufman, Tali and Navon, Inbal Livni and Ta-Shma, Amnon , title =. SIAM Journal on Computing , volume =. 2021 , doi =. https://doi.org/10.1137/19M1276650 , abstract =

    2021 doi

  21. [29]

    , booktitle=

    Trevisan, L. , booktitle=. List-decoding using the XOR lemma , year=

  22. [30]

    and Bruck, J

    Alon, N. and Bruck, J. and Naor, J. and Naor, M. and Roth, R.M. , journal=. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs , year=

  23. [31]

    List decoding with side information , year=

    Guruswami, Venkatesan , booktitle=. List decoding with side information , year=

  24. [32]

    , booktitle=

    Yao, Andrew C. , booktitle=. Theory and application of trapdoor functions , year=

  25. [33]

    , booktitle=

    Schapire, Robert E. , booktitle=. The strength of weak learnability , year=

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.