Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization

Xiaoyu Li

Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization

T0 review · 1 major / 0 minor · reviewed 2026-06-27 · grok-4.3

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

Pith's one-line read The maximal corruption mass hidden from a degree-2t sum-of-squares certificate equals the Christoffel function of the clean marginal at that point.

desk verdict The paper turns the Christoffel function into an organizing principle for SoS degree barriers in reweighted-hinge robust halfspace learning and supplies an explicit degree-2 barrier instance. read the letter →

arxiv 2606.17215 v1 pith:RFBXY45Y submitted 2026-06-15 cs.LG cs.DSstat.ML

Xiaoyu Li This is my paper · ORCID

classification cs.LGcs.DSstat.ML

keywords robusthalfspacelearningsum-of-squaresChristoffelfunctionmaliciousnoisereweightedhingeoutlierremovalmargin-degreetradeoff

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

The paper shows that any bounded-degree certificate for removing outliers in robust halfspace learning can only see the data through its low-degree moments, so an adversary can hide corruption exactly where the clean distribution already appears typical. This blind spot has a precise size given by the Christoffel function of the clean marginal, which the authors read as the largest mass a degree-2t certificate necessarily misses. The resulting resolution principle directly governs the reweighted-hinge method, producing a margin-degree tradeoff, an explicit degree-2 barrier, and an algorithm family that traces the frontier eta to the power of 1 minus 1 over 2t.

What carries the argument

The Christoffel function λ_{t+1}(c) of the clean marginal, which exactly quantifies the largest corruption mass at c that evades every degree-2t certificate.

What would settle it

An explicit distribution and corruption set where the mass at some center exceeds λ_{t+1}(c) yet a degree-2t certificate still certifies the pancake to error epsilon, or where the mass is strictly less than λ_{t+1}(c) yet no degree-2t certificate succeeds.

Watch

Extended reading notes

Core claim

The governing resource is the Sum-of-Squares degree of the outlier-removal certificate, and the resolution principle states that the maximal corruption mass which can hide at a center c from a degree-2t certificate is exactly the Christoffel function λ_{t+1}(c) of the clean marginal.

Load-bearing premise

The clean marginal admits a well-defined Christoffel function and the weighted-Chebyshev reduction holds with the stated tightness.

Editorial extensions

If this is right

Certifying the dense pancake to error epsilon requires SoS degree Omega(log(1/epsilon)) or margin Omega(sqrt(log(1/epsilon))/sqrt(d)).
Degree-2 certificates remain stuck at breakdown rate eta to the power 1/2 while degree-4 certificates escape.
A degree-2t algorithm achieves recovery rate eta to the power 1 minus 1 over 2t, recovering the t=1 case of prior work.
The degree-2 barrier instance shows the small breakdown rate originates in the degree rather than the analysis.

Reading between the lines

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

The same Christoffel characterization may bound other moment-based outlier filters that operate only on low-degree statistics.
Practical implementations could trade the explicit constant gain against the cost of solving higher-degree SoS programs on pancake-like data.
Extending the reduction to non-Gaussian marginals would test whether the tightness modulo the classical weighted-extremal estimate survives.

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.

Desk Editor's Note

read the letter

The main takeaway is that this work gives a resolution principle: the max corruption mass hiding at a center c from a degree-2t certificate equals the Christoffel function λ_{t+1}(c) of the clean marginal. From there it derives a margin-degree tradeoff, an explicit degree-2 barrier where the method stalls at η^{1/2} while degree 4 escapes, and a general algorithm tracing η^{1-1/2t} (recovering Shen 2025 at t=1).

What is new is the Christoffel characterization itself and the concrete degree-2 instance that pins the small breakdown rate on the degree rather than the analysis. The paper does a clean job connecting the reweighted-hinge method to this quantity, which is already standard in outlier detection, and shows how the pancake density caps the gain. The explicit constructions are useful for anyone trying to understand computational limits of certificate methods.

The soft spot is the tightness claim. The weighted-Chebyshev reduction sets the threshold 2t = Θ((|c|/s)^2) and is called tight only modulo one classical weighted-extremal estimate. If that estimate leaves a gap in the leading constant or is not sharp in the high-margin regime, the claimed exact equality becomes a bound instead. Both the degree-2 barrier and the η^{1-1/2t} frontier inherit this dependence, so the strongest statements rest on that classical piece being sufficiently sharp.

The rest of the argument looks internally consistent and the citations to prior overlapping work are straightforward since the new principle builds directly on them. No load-bearing circularity.

This is for people working on SoS certificates in robust learning who want concrete degree barriers rather than information-theoretic ones. A reader already following Shen 2025 or similar certificate approaches will get the most out of the explicit example and the general rate.

It deserves a serious referee. The explicit barrier and the derived frontier are concrete enough to review even if the exactness of the characterization needs checking against the full derivations.

Referee Report

1 major / 0 minor

Summary. The paper claims that for the reweighted-hinge method in robust γ-margin halfspace learning under malicious noise, the maximal corruption mass hiding at a center c from a degree-2t SoS certificate is exactly the Christoffel function λ_{t+1}(c) of the clean marginal (the resolution principle). This yields three consequences: a margin-degree tradeoff showing that certifying the dense pancake to error ε requires SoS degree Ω(log(1/ε)) or margin Ω(√log(1/ε)/√d), with the threshold 2t=Θ((|c|/s)^2) obtained via weighted-Chebyshev reduction; an explicit degree-2 barrier instance on which degree 2 is limited to η^{1/2} while degree 4 escapes; and a degree-2t algorithm tracing the frontier η^{1-1/2t} (recovering Shen (2025) at t=1), with explicit constants capped by pancake density and shown unimprovable by the degree-2 barrier.

Significance. If the central characterization holds, the work supplies a precise, non-information-theoretic explanation for the degree limitations of certificate-based robust learning by inverting the Christoffel function, which is already used for outlier detection. It gives concrete, falsifiable predictions via the explicit degree-2 instance and the η^{1-1/2t} frontier, recovers prior results at t=1, and isolates the breakdown rate in the degree rather than the analysis. The connection between SoS certificates and Christoffel functions is a notable organizing principle.

major comments (1)

[margin-degree tradeoff and resolution principle] The resolution principle asserts exact equality between maximal hiding mass and λ_{t+1}(c). However, the margin-degree tradeoff section states that the weighted-Chebyshev reduction establishing 2t=Θ((|c|/s)^2) is tight only modulo one classical weighted-extremal estimate. If that estimate leaves a non-vanishing gap in the leading constant (particularly in the high-margin regime), the claimed exact characterization becomes an upper or lower bound, which is load-bearing for both the degree-2 barrier instance and the η^{1-1/2t} frontier.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for isolating this subtlety in the relationship between the resolution principle and the weighted-Chebyshev reduction. We address the concern directly below.

read point-by-point responses

Referee: [margin-degree tradeoff and resolution principle] The resolution principle asserts exact equality between maximal hiding mass and λ_{t+1}(c). However, the margin-degree tradeoff section states that the weighted-Chebyshev reduction establishing 2t=Θ((|c|/s)^2) is tight only modulo one classical weighted-extremal estimate. If that estimate leaves a non-vanishing gap in the leading constant (particularly in the high-margin regime), the claimed exact characterization becomes an upper or lower bound, which is load-bearing for both the degree-2 barrier instance and the η^{1-1/2t} frontier.

Authors: The resolution principle is proved directly from the definition of a degree-2t SoS certificate and the reproducing property of the Christoffel function; the equality between maximal hiding mass and λ_{t+1}(c) holds exactly for any fixed marginal and any center c, without reference to margins or the Chebyshev reduction. The weighted-Chebyshev argument appears only in the subsequent margin-degree tradeoff paragraph, where it is used solely to translate the exact hiding-mass bound into an explicit degree threshold 2t=Θ((|c|/s)^2). We already flag that this translation is tight modulo one classical weighted-extremal estimate. In the regimes relevant to the degree-2 barrier instance and the η^{1-1/2t} frontier (fixed small t, pancake distributions with bounded density), the extremal estimate is known to be asymptotically sharp; any constant-factor gap therefore affects only the implicit constant inside the Θ notation and does not turn the exact hiding-mass equality into a one-sided bound. The explicit degree-2 instance is constructed by direct computation of the Christoffel function, again bypassing the reduction. We will insert a short clarifying sentence in the revision that separates the exact resolution principle from the asymptotic translation used only for the tradeoff. revision: partial

Circularity Check

1 steps flagged · score 4.0 of 10

Recovers Shen (2025) at t=1 by construction via self-cited reweighted-hinge base; general-t characterization has independent content but load-bearing citations lack external verification

self citation load bearing [Abstract]
"a degree-2t algorithm tracing the frontier η^{1-1/2t} (recovering Shen (2025) at t=1), whose gain is an explicit constant, capped by the pancake density and shown unimprovable by the degree-2 barrier."

The general-t frontier and algorithm are presented as consequences of the new Christoffel characterization, yet at t=1 the claimed frontier and recovery are obtained by direct substitution into the reweighted-hinge method of the cited Shen (2025) paper; the load-bearing base case and the invocation of the method itself therefore reduce to self-citation without external verification such as code reproduction or independent proof.

full rationale

The paper's core resolution principle equates maximal hiding mass to the Christoffel function λ_{t+1}(c) for degree-2t certificates and derives the η^{1-1/2t} frontier from it. This recovers the t=1 case of the cited Shen (2025) work by direct substitution into the same reweighted-hinge framework, while the weighted-Chebyshev reduction for the margin-degree tradeoff is stated to hold tightly only modulo a classical estimate. The derivation chain therefore depends on prior results by overlapping authors for its base case and organizing principle without cited machine-checked or externally falsifiable support, producing moderate circularity even though the general-t extension itself is not tautological.

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

Abstract only; no explicit free parameters, axioms, or invented entities can be extracted. The resolution principle itself functions as the organizing assumption.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization." pith.science (2026). https://pith.science/paper/RFBXY45Y

@misc{pith2026260617215,
  author       = {Pith},
  title        = {Pith review of: Sum-of-Squares Degree Barriers for the Reweighted-Hinge Method in Robust Halfspace Learning: A Christoffel-Function Characterization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RFBXY45Y}},
  note         = {Machine review of arXiv:2606.17215}
}

abstract

A certificate that removes outliers sees the data only through its low-degree moments, and an adversary exploits exactly this, hiding corruption where the clean data already looks typical, in the blind spot no bounded-degree test resolves. That blind spot turns out to have an exact size: the Christoffel function of the clean marginal, the very quantity modern data analysis thresholds to detect outliers, here read from the adversary's side as the corruption a bounded-degree certificate cannot remove. We turn this inversion into the organizing principle of the reweighted-hinge approach to robustly learning $\gamma$-margin halfspaces under malicious noise (Shen, 2025; Zeng and Shen, 2025): the governing resource is the Sum-of-Squares degree of the outlier-removal certificate, and the resolution principle states that the maximal corruption mass which can hide at a center $c$ from a degree-$2t$ certificate is exactly the Christoffel function $\lambda_{t+1}(c)$ of the clean marginal. Three consequences follow, all against the certificate method (not information-theoretic). A margin-degree tradeoff: certifying the dense pancake to error $\epsilon$ costs SoS degree $\Omega(\log(1/\epsilon))$ or margin $\Omega(\sqrt{\log(1/\epsilon)}/\sqrt{d})$, explaining why the $\log(1/\epsilon)$ margin Shen (2025) records is forced, with a weighted-Chebyshev reduction making the threshold $2t=\Theta((|c|/s)^2)$ tight modulo one classical weighted-extremal estimate. A degree-$2$ outlier barrier: the resolution principle realized as an explicit instance on which degree $2$ is stuck at $\eta^{1/2}$ while degree $4$ escapes, locating the method's small breakdown rate in the degree, not the analysis. And a degree-$2t$ algorithm tracing the frontier $\eta^{1-1/2t}$ (recovering Shen (2025) at $t=1$), whose gain is an explicit constant, capped by the pancake density and shown unimprovable by the degree-$2$ barrier.

Figures

Figures reproduced from arXiv: 2606.17215 by the authors.

**Figure 1.** The inversion. The same Christoffel curve λt+1 (c) carries two opposite meanings. In moment-based data analysis a large value marks a typical point to keep; here a large value is exactly the corruption mass an adversary can hide at c that no degree-2t certificate can clear. One object, read as a detector on the left and as a barrier on the right. arXiv:2606.17215v1 [cs.LG] 15 Jun 2026 [PITH_FULL_IMAGE:figures/full_… view at source ↗

**Figure 2.** The impossibility mechanism. A degree-2t certificate sees the clean marginal µ only through its first 2t moments, which are reproduced exactly by the (t+1)-node Gauss measure supported on the nodes u1 , . . . , ut+1 ∈ [−Rt+1 ,Rt+1 ] with Rt+1 ≍ s p t. A band B pushed past the node range contains no node, so every measure matching the moments places zero mass there, and a corruption of any rate η planted at c stays i… view at source ↗

**Figure 3.** The resolution threshold. The certificate ceiling λt+1 (c) decays from the bulk, and a corruption of rate η at center c is exposed exactly where the curve drops below the dotted line η. Raising the degree from 2 to 4 pulls the curve down so that at the tail center c = σ/pη the value falls from Θ(η) (still hidden) to Θ(η 2 ) (now resolved): the degree-2/degree-4 gap of Example 3.5. Proof. Apply Proposition 3.3 with t… view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: The moment-cloaked spike behind Theorem 4.7. (a) Two genuine log-concave clusters C± at ±(σ/pη)e1 ; the adversary’s dirty points (filled) are drawn from the same clusters and sit at the clean points’ (hollow) locations, so a label-oblivious variance program sees one in…

**Figure 5.** Figure 5: Map of results: arrows point from each ingredient up to the result that uses it. External facts (bottom, restated in Section C) feed the lemmas, which feed the headline results (top). The §3 framework (Prop 3.3, Prop 3.6) is the Christoffel-function layer that organize…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

The Exact Worst-Case Tail Probability under Bounded Kurtosis
math.PR 2026-07 conditional novelty 8.0 of 10

The worst-case one-sided tail probability under mean 0, variance 1, and fourth moment ≤ κ is a four-regime map with closed forms on three regimes and an algebraic system on the fourth, plus a one-sided/two-sided colla...

Reference graph

Works this paper leans on

63 extracted references · cited by 1 Pith paper

[1]

Proceedings of the 36th International Conference on Algorithmic Learning Theory (

Jie Shen , title =. Proceedings of the 36th International Conference on Algorithmic Learning Theory (. 2025 , note =

2025
[2]

2025 , note =

Shiwei Zeng and Jie Shen , title =. 2025 , note =

2025
[3]

Advances in Neural Information Processing Systems (

Kunal Talwar , title =. Advances in Neural Information Processing Systems (. 2020 , note =

2020
[4]

Long , title =

Pranjal Awasthi and Maria-Florina Balcan and Philip M. Long , title =. Journal of the. 2017 , note =

2017
[5]

2026 , note =

Rita Adhikari and Shiwei Zeng , title =. 2026 , note =

2026
[6]

Hopkins and Jerry Li , title =

Samuel B. Hopkins and Jerry Li , title =. Proceedings of the 50th Annual. 2018 , doi =

2018
[7]

Kothari and Jacob Steinhardt and David Steurer , title =

Pravesh K. Kothari and Jacob Steinhardt and David Steurer , title =. Proceedings of the 50th Annual. 2018 , doi =

2018
[8]

Klivans and Pravesh K

Adam R. Klivans and Pravesh K. Kothari and Raghu Meka , title =. Proceedings of the 31st Conference on Learning Theory (. 2018 , note =

2018

Show all 63 references

[9]

Hopkins and Ankit Pensia and Stefan Tiegel , title =

Ilias Diakonikolas and Samuel B. Hopkins and Ankit Pensia and Stefan Tiegel , title =. 2024 , note =

2024
[10]

Kothari and Goutham Rajendran and Madhur Tulsiani and Aravindan Vijayaraghavan , title =

Ainesh Bakshi and Pravesh K. Kothari and Goutham Rajendran and Madhur Tulsiani and Aravindan Vijayaraghavan , title =. 2024 , note =

2024
[11]

Klivans and Konstantinos Stavropoulos and Kevin Tian and Arsen Vasilyan , title =

Adam R. Klivans and Konstantinos Stavropoulos and Kevin Tian and Arsen Vasilyan , title =. 2025 , note =

2025
[12]

Kane and Alistair Stewart , title =

Ilias Diakonikolas and Daniel M. Kane and Alistair Stewart , title =. Proceedings of the 50th Annual. 2018 , doi =

2018
[13]

Kane and Nikos Zarifis , title =

Ilias Diakonikolas and Daniel M. Kane and Nikos Zarifis , title =. Advances in Neural Information Processing Systems (. 2020 , note =

2020
[14]

Random Structures & Algorithms , volume=

L\'aszl\'o Lov\'asz and Santosh Vempala , title=. Random Structures & Algorithms , volume=
[15]

Lubinsky , title=

Eli Levin and Doron S. Lubinsky , title=
[16]

Orthogonal Polynomials , series=

G\'abor Szeg. Orthogonal Polynomials , series=
[17]

Walter Gautschi , title=
[18]

SIAM Journal on Computing , volume=

Michael Kearns and Ming Li , title=. SIAM Journal on Computing , volume=
[19]

Lieb , title=

Herm Jan Brascamp and Elliott H. Lieb , title=. Journal of Functional Analysis , volume=
[20]

International Mathematics Research Notices , number=

Thomas Kriecherbauer and Kenneth D.\ T.-R.\ McLaughlin , title=. International Mathematics Research Notices , number=
[21]

Lasserre and Edouard Pauwels , title=

Jean B. Lasserre and Edouard Pauwels , title=. Advances in Computational Mathematics , volume=. 2019 , doi=

2019
[22]

Saff and Nikos Stylianopoulos , title=

Bernhard Beckermann and Mihai Putinar and Edward B. Saff and Nikos Stylianopoulos , title=. Foundations of Computational Mathematics , volume=. 2021 , doi=

2021
[23]

Lasserre , title=

Jean B. Lasserre , title=. Optimization Letters , volume=. 2021 , doi=

2021
[24]

Lasserre , title=

Edouard Pauwels and Jean B. Lasserre , title=. Advances in Neural Information Processing Systems (. 2016 , note=

2016
[25]

2022 , isbn=

Jean Bernard Lasserre and Edouard Pauwels and Mihai Putinar , title=. 2022 , isbn=

2022
[26]

Lasserre , title=

Edouard Pauwels and Mihai Putinar and Jean B. Lasserre , title=. Foundations of Computational Mathematics , volume=. 2021 , doi=

2021
[27]

Lasserre , title=

Jean B. Lasserre , title=. Polynomial Optimization, Moments, and Applications , editor=. 2023 , doi=

2023
[28]

Studden , title=

Holger Dette and William J. Studden , title=
[29]

Curto and Lawrence A

Ra\'ul E. Curto and Lawrence A. Fialkow , title=. Houston Journal of Mathematics , volume=
[30]

Annals of Mathematics , volume=

Attila M\'at\'e and Paul Nevai and Vilmos Totik , title=. Annals of Mathematics , volume=
[31]

Journal d'Analyse Math\'ematique , volume=

Vilmos Totik , title=. Journal d'Analyse Math\'ematique , volume=
[32]

Journal of Approximation Theory , volume=

Paul Nevai , title=. Journal of Approximation Theory , volume=
[33]

Percy Deift and Thomas Kriecherbauer and Kenneth D. T.-R. McLaughlin and Stephanos Venakides and Xin Zhou , title=. Communications on Pure and Applied Mathematics , volume=
[34]

Lasserre , title=

Jean B. Lasserre , title=. SIAM Journal on Optimization , volume=
[35]

Parrilo , title=

Pablo A. Parrilo , title=. Mathematical Programming , volume=
[36]

Klivans and Philip M

Adam R. Klivans and Philip M. Long and Rocco A. Servedio , title =. Proceedings of the 36th International Colloquium on Automata, Languages and Programming (. 2009 , note =

2009
[37]

Klivans and Yishay Mansour and Rocco A

Adam Tauman Kalai and Adam R. Klivans and Yishay Mansour and Rocco A. Servedio , title =. 2008 , note =

2008
[38]

Kane and Adam R

Daniel M. Kane and Adam R. Klivans and Raghu Meka , title =. Proceedings of the 26th Conference on Learning Theory (
[39]

Proceedings of the 38th International Conference on Machine Learning (

Jie Shen , title =. Proceedings of the 38th International Conference on Machine Learning (. 2021 , note =

2021
[40]

Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (

Jie Shen , title =. Proceedings of the 26th International Conference on Artificial Intelligence and Statistics (
[41]

Proceedings of the 32nd International Conference on Algorithmic Learning Theory (

Jie Shen and Chicheng Zhang , title =. Proceedings of the 32nd International Conference on Algorithmic Learning Theory (. 2021 , note =

2021
[42]

Advances in Neural Information Processing Systems (

Ilias Diakonikolas and Themis Gouleakis and Christos Tzamos , title =. Advances in Neural Information Processing Systems (. 2019 , note =

2019
[43]

Kane and Vasilis Kontonis and Christos Tzamos and Nikos Zarifis , title =

Ilias Diakonikolas and Daniel M. Kane and Vasilis Kontonis and Christos Tzamos and Nikos Zarifis , title =. Proceedings of the 54th Annual. 2022 , note =

2022
[44]

Kane and Puqian Wang and Nikos Zarifis , title =

Ilias Diakonikolas and Jelena Diakonikolas and Daniel M. Kane and Puqian Wang and Nikos Zarifis , title =. Proceedings of the 36th Conference on Learning Theory (. 2023 , note =

2023
[45]

Kane , title =

Ilias Diakonikolas and Daniel M. Kane , title =. Proceedings of the 35th Conference on Learning Theory (. 2022 , note =

2022
[46]

Kane and Pasin Manurangsi and Lisheng Ren , title =

Ilias Diakonikolas and Daniel M. Kane and Pasin Manurangsi and Lisheng Ren , title =. Advances in Neural Information Processing Systems (. 2022 , note =

2022
[47]

Proceedings of the 28th Conference on Learning Theory (

Pranjal Awasthi and Maria-Florina Balcan and Nika Haghtalab and Ruth Urner , title =. Proceedings of the 28th Conference on Learning Theory (. 2015 , note =

2015
[48]

Proceedings of the 34th Conference on Learning Theory (

Chicheng Zhang and Yinan Li , title =. Proceedings of the 34th Conference on Learning Theory (. 2021 , note =

2021
[49]

Broder and Tong Zhang , title =

Maria-Florina Balcan and Andrei Z. Broder and Tong Zhang , title =. Proceedings of the 20th Annual Conference on Learning Theory (
[50]

Long , title =

Maria-Florina Balcan and Philip M. Long , title =. Proceedings of the 26th Conference on Learning Theory (. 2013 , note =

2013
[51]

Advances in Neural Information Processing Systems (

Songbai Yan and Chicheng Zhang , title =. Advances in Neural Information Processing Systems (. 2017 , note =

2017
[52]

Proceedings of the 29th Conference on Learning Theory (

Pranjal Awasthi and Maria-Florina Balcan and Nika Haghtalab and Hongyang Zhang , title =. Proceedings of the 29th Conference on Learning Theory (
[53]

Advances in Neural Information Processing Systems (

Chicheng Zhang and Jie Shen and Pranjal Awasthi , title =. Advances in Neural Information Processing Systems (. 2020 , note =

2020
[54]

Proceedings of the 31st Conference on Learning Theory (

Chicheng Zhang , title =. Proceedings of the 31st Conference on Learning Theory (. 2018 , note =

2018
[55]

Klivans and Pravesh K

Sushrut Karmalkar and Adam R. Klivans and Pravesh K. Kothari , title =. Advances in Neural Information Processing Systems (. 2019 , note =

2019
[56]

Kane and Pravesh K

Ainesh Bakshi and Ilias Diakonikolas and He Jia and Daniel M. Kane and Pravesh K. Kothari and Santosh S. Vempala , title =. Proceedings of the 54th Annual. 2022 , note =

2022
[57]

Kane and Sushrut Karmalkar and Ankit Pensia and Thanasis Pittas , title =

Ilias Diakonikolas and Daniel M. Kane and Sushrut Karmalkar and Ankit Pensia and Thanasis Pittas , title =. Proceedings of the 35th Conference on Learning Theory (. 2022 , note =

2022
[58]

Advances in Neural Information Processing Systems (

Shiwei Zeng and Jie Shen , title =. Advances in Neural Information Processing Systems (. 2022 , note =

2022
[59]

Proceedings of the 40th International Conference on Machine Learning (

Shiwei Zeng and Jie Shen , title =. Proceedings of the 40th International Conference on Machine Learning (. 2023 , note =

2023
[60]

Kane and Jerry Li and Ankur Moitra and Alistair Stewart , title =

Ilias Diakonikolas and Gautam Kamath and Daniel M. Kane and Jerry Li and Ankur Moitra and Alistair Stewart , title =. 2019 , note =

2019
[61]

Kane and Jerry Li and Jacob Steinhardt and Alistair Stewart , title =

Ilias Diakonikolas and Gautam Kamath and Daniel M. Kane and Jerry Li and Jacob Steinhardt and Alistair Stewart , title =. Proceedings of the 36th International Conference on Machine Learning (. 2019 , note =

2019
[62]

Kane , title =

Ilias Diakonikolas and Daniel M. Kane , title =. arXiv preprint , year =
[63]

Bshouty and Nadav Eiron and Eyal Kushilevitz , title =

Nader H. Bshouty and Nadav Eiron and Eyal Kushilevitz , title =. Theoretical Computer Science , volume =. 2002 , note =

2002

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.

[1] [1]

Proceedings of the 36th International Conference on Algorithmic Learning Theory (

Jie Shen , title =. Proceedings of the 36th International Conference on Algorithmic Learning Theory (. 2025 , note =

2025

[2] [2]

2025 , note =

Shiwei Zeng and Jie Shen , title =. 2025 , note =

2025

[3] [3]

Advances in Neural Information Processing Systems (

Kunal Talwar , title =. Advances in Neural Information Processing Systems (. 2020 , note =

2020

[4] [4]

Long , title =

Pranjal Awasthi and Maria-Florina Balcan and Philip M. Long , title =. Journal of the. 2017 , note =

2017

[5] [5]

2026 , note =

Rita Adhikari and Shiwei Zeng , title =. 2026 , note =

2026

[6] [6]

Hopkins and Jerry Li , title =

Samuel B. Hopkins and Jerry Li , title =. Proceedings of the 50th Annual. 2018 , doi =

2018

[7] [7]

Kothari and Jacob Steinhardt and David Steurer , title =

Pravesh K. Kothari and Jacob Steinhardt and David Steurer , title =. Proceedings of the 50th Annual. 2018 , doi =

2018

[8] [8]

Klivans and Pravesh K

Adam R. Klivans and Pravesh K. Kothari and Raghu Meka , title =. Proceedings of the 31st Conference on Learning Theory (. 2018 , note =

2018