A Geometric Approach to Problems in Optimization and Data Science

Naren Sarayu Manoj

REVIEW 3 major objections 4 minor 15 references

A Geometric Approach to Problems in Optimization and Data Science

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read The thesis's central claim is that a single-pass, low-memory algorithm can round an asymmetric convex polytope to distortion $O(\min\{R/r_0, d\log(R/r_0)\})$, nearly matching John's theorem.

desk verdict A competently written thesis that repackages the author's own conference papers; the streaming proof is solid, but the abstract overstates near-optimality once the warm-start and monotone-algorithm restrictions are factored in. read the letter →

arxiv 2504.16270 v1 pith:A3ACUWWK submitted 2025-04-22 math.OC cs.LGstat.ML

Naren Sarayu Manoj This is my paper · ORCID

classification math.OCcs.LGstat.ML MSC 90C2552A2768W2752A20

keywords streamingalgorithmsellipsoidalapproximationconvexpolytopesJohn'stheoremhullcoresetsmonotonehigh-dimensionalgeometry

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 thesis claims that high-dimensional geometry and probability can be turned into algorithmic and statistical tools across five problem areas, and its centerpiece is a streaming ellipsoidal-rounding theorem. The theorem states that there is a one-pass algorithm that, given a ball of radius $r_0$ inside an asymmetric convex polytope $Z$, maintains an enclosing ellipsoid at every timestep and ends with a rounding whose distortion is $O(\min\{R(Z)/r_0,\, d\log(R(Z)/r_0)\})$, where $R(Z)$ is the circumradius; the algorithm stores $O(d^2)$ numbers and runs in $\tilde O(n d^2)$ time. Since John's theorem guarantees that no ellipsoid can approximate a general convex body better than factor $d$, this nearly matches the offline optimum and is the first streaming guarantee of this kind for asymmetric polytopes. The same monotone-update machinery yields streaming convex-hull coresets, and the thesis also contributes new sparsification and regression algorithms based on block Lewis weights, a dueling-optimization algorithm with a monotone adversary, a statistical model of backdoor data-poisoning attacks, and stability guarantees for spectral clustering under helpful misspecification.

What carries the argument

The load-bearing object is a parameterized monotone update rule. After an affine reduction that maps the current outer ellipsoid to the unit ball and the new point to the first coordinate axis, the rule chooses the next ellipsoid from the family with horizontal semiaxis $a = e^\gamma$, vertical semiaxis $b = 1 + (\alpha-\alpha')/2$, center $c = -\alpha + \alpha' a$, and scaling $1/\alpha' = 1/\alpha + 2\gamma$, where $\gamma$ is set so that the outer ellipsoid first covers the new point. The rule is monotone in the sense that the new outer ellipsoid contains the old outer ellipsoid and the new point, while the new inner ellipsoid is contained in the convex hull of the old inner ellipsoid and the new point. These two invariants alone imply that any such sequence is a valid rounding, and an evolution condition bounding the increase of $1/\alpha$ by a constant times the log-volume increase of the outer ellipsoid telescopes into the final distortion bound. Irregular updates, which increase the dimension of the affine span by one, are handled separately and add at most one to the distortion each time.

What would settle it

Run Algorithm 2 on the lower-bound adversary's stream from Section 2.7, namely the vertices of a regular simplex followed by points placed just outside the current ellipsoid, and measure the final $1/\alpha_n$. The theorem predicts $O(\min\{R/r_0, d\log(R/r_0)\})$; a single stream where the measured distortion exceeds that bound by more than a constant factor would overturn the central claim.

Watch

Extended reading notes

Core claim

The central discovery, stated as Theorem 1, is that monotone update rules can solve streaming ellipsoidal rounding for asymmetric polytopes nearly as well as the best offline rounding. Algorithm 2 starts from the supplied inner ball $\boldsymbol c_0 + r_0 B_2^d$, grows a ball around it until the aspect ratio is large enough, and then applies a one-parameter family of ellipsoidal updates; at every step the convex hull of the points seen so far lies in the current outer ellipsoid, and at the end the inner ellipsoid $\boldsymbol c_n + \alpha_n \mathcal E_n$ lies inside $Z$ while $Z$ lies in $\boldsymbol c_n + \mathcal E_n$, with $1/\alpha_n = O(\min\{R(Z)/r_0,\, d\log(R(Z)/r_0)\})$. The algorithm stores $O(d^2)$ floating-point numbers and processes each point in $O(d^2 \log d)$ time using rank-one SVD updates. A companion lower bound shows that within the natural class of monotone streaming algorithms this approximation factor is essentially best possible.

Load-bearing premise

The main algorithm's near-John guarantee is only as good as the user-supplied inner ball $\boldsymbol c_0 + r_0 B_2^d$; if $r_0$ is far below the polytope's true inradius, the approximation factor can be arbitrarily worse than the existential factor $d$.

Editorial extensions

If this is right

If the central theorem is correct, streaming systems can maintain a near-John ellipsoidal summary of an asymmetric point stream using only $O(d^2)$ memory, which was previously achievable only for centrally symmetric polytopes.
The same framework immediately gives the first single-pass streaming coresets for the convex hull of asymmetric point sets, with $O(d \log(R/r_0))$ selected points and the same order of distortion as the ellipsoidal rounding.
For origin-symmetric streams the approximation improves to $O(\min\{R/r_0, \sqrt{d\log(R/r_0)}\})$, matching the symmetric lower bound up to log factors.
When the input points have integer coordinates in $[-N,N]$, the distortion becomes $O(d \log(dN))$, independent of the stream length and aspect ratio.
No one-pass monotone algorithm can approximate the minimum-volume outer ellipsoid better than $\sqrt{d}$ in the symmetric case, and no monotone algorithm beats $\Omega(d \log \kappa / \log d)$ in the asymmetric case, so the algorithm's dependence on the aspect ratio is not an artifact of the analysis.

Reading between the lines

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

One consequence left implicit is that the same warm-start plus monotone-update recipe could be adapted to streaming membership or separation-oracle models, since the update rule only needs the previous ellipsoid and the newly revealed point or violated constraint.
A practical reading of the theorem is that the user-supplied inner ball, not the ambient dimension, controls the final distortion; investing a small offline preprocessing pass to find a large inner ball could make the streaming guarantee approach John's factor $d$ on real datasets.
The lower bound is proved only for monotone algorithms, so whether a non-monotone streaming algorithm can break the $d \log(R/r_0)$ barrier for asymmetric polytopes remains open; the paper's symmetrization argument suggests the barrier is genuine, but it does not settle the unrestricted case.
The block Lewis weights developed in the later chapters are a separate geometric primitive; if their covering-number estimates transfer to overlapping group structures, the sparsification results could extend beyond the partition setting considered here.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Colleague,

Quick take: this is a PhD thesis that consolidates the author's own conference papers, not a new-results paper. Chapter 2 is the real meat: a careful, self-contained proof of the streaming asymmetric ellipsoidal rounding algorithm, including the monotone update rule, the evolution inequality, the volume argument, and a simplified analysis of the symmetric case. That material is worth having in one place. Chapters 3 and 4 likewise give detailed proofs for block Lewis weights and distributionally robust regression, including near-optimal sparsity rates and iteration complexities. The remaining chapters are readable restatements of prior work on dueling optimization, backdoor PAC attacks, and semirandom stochastic block models. Bibliographic notes are honest and every chapter points to the original papers.

The soft spots are exactly where the abstract oversells. The "nearly worst-case optimal" claim should be read with two caveats. First, Theorem 1's O(min{R/r0, d log(R/r0)}) guarantee needs a warm-start ball of radius r0 inside the final polytope; if r0 is a poor choice, the bound can be arbitrarily bad relative to John's existential d. Second, the warm-start-free guarantee in Theorem 3 depends on max_{t' <= t} R_t / r_{t'} over all prefixes, which can be much larger than the final aspect ratio. The stress-test example is correct: an early skinny triangle dominates the bound even when the final body is well-rounded. The lower bound (Theorem 7) applies only to monotone algorithms, so the abstract's "nearly worst-case optimal" is stronger than what is established. These are not fatal flaws in the proofs; they are claims that need to be stated honestly. The paper also includes experiments without code or data, so the numeric sections are illustrative rather than reproducible. I did not check every later proof line by line, but the chapters I read are technically coherent and I saw no circularity.

Who is this for? Someone who wants the full streaming proof in one document. It is not a source of new theorems. I would cite the original conference papers rather than the thesis. If a journal editor sent this to referees with instructions to check the streaming chapter and ask for a scaled-back abstract, that would be reasonable; it is not desk-reject-quality work.

Referee Report

3 major / 4 minor

Summary. This manuscript is a PhD thesis collecting results in optimization and data science. The first part develops streaming algorithms for approximating convex polytopes by ellipsoids and coresets, introduces block Lewis weights for sparsification and robust regression, and studies dueling optimization with a monotone adversary. The second part analyzes PAC learning under backdoor data poisoning and spectral clustering under a semirandom stochastic block model. The central, most fully developed contribution is Chapter 2, which gives a one-pass, O(d^2)-memory streaming ellipsoidal rounding algorithm for asymmetric polytopes, together with a monotone-update framework, a volume-based evolution-condition analysis, and lower bounds for the restricted class of monotone algorithms. The later chapters are presented as summaries of previously published works and were not fully assessable from the provided text.

Significance. If the claims in Chapter 2 hold as stated, the paper makes a genuine contribution: it provides the first efficient single-pass streaming ellipsoidal rounding for asymmetric polytopes with O(d^2) memory, and it does so through a self-contained and unusually explicit geometric analysis. The update rule is given in closed form, the monotonicity invariants are verified in detail, and the volume-evolution argument is transparent enough to be checked directly. The lower-bound constructions against monotone algorithms are also a useful step. However, the significance is substantially tempered by the gap between the advertised near-optimality with respect to John's theorem and what is actually proved: the O(min{R/r0, d log(R/r0)}) guarantee depends on a warm-start ball that the algorithm does not construct, the fully online version replaces the final aspect ratio with a worst-case prefix ratio, and the lower bounds apply only to a restricted algorithmic class. These caveats are disclosed in parts of the text, but the introduction and chapter summaries state the results in stronger terms.

major comments (3)

[Section 1.1, Section 1.2.1, Theorem 1 (Section 2.4)] The claim that these streaming algorithms 'nearly agree with John's theorem' is stronger than what is proved. John's theorem gives an O(d) bound independent of the geometry, while Theorem 1's guarantee is O(min{R(Z)/r0, d log(R(Z)/r0)}), where r0 is the radius of a user-supplied initial ball. If the supplied r0 is much smaller than the true inradius (e.g., r0 = r(Z)/T for large T), both terms in the min can be arbitrarily larger than d. Since Theorem 1 does not provide or estimate r0, the comparison to John's existential bound in the introduction is an overstatement; the correct statement is a guarantee relative to the quality of the warm start.
[Section 2.4.5, Theorem 3] The warm-start-free Algorithm 4 does not recover the same guarantee. Theorem 3 replaces R(Z)/r0 with the prefix quantity max_{t' ≤ t} R_t / r_{t'}, and the paper itself concedes immediately after Theorem 3 that this prefix ratio can be much larger than the final aspect ratio. A concrete 2D example is the stream (-1,0), (1,0), (0,ε), (0,1): the t=3 polytope is an O(ε)-thin triangle with aspect ratio about 1/ε, while the final polytope has constant aspect ratio. Thus Theorem 3's bound is controlled by an ephemeral thin prefix and can be arbitrarily worse than John's O(d) bound for the final body. The fully online algorithm is therefore not 'nearly optimal' in the sense advertised.
[Section 2.7, Theorem 7; Definition 4] The lower-bound claim supporting 'nearly worst-case optimal' is proved only for the restricted class of monotone algorithms defined in Definition 4, and Theorem 6 is further restricted to deterministic symmetric monotone algorithms. This leaves open the possibility that a non-monotone streaming algorithm achieves a substantially better approximation factor on the constructed instances. Consequently, the abstract and introduction's wording that the algorithms are 'nearly worst-case optimal' or 'nearly agree with John's theorem' is not supported by the established lower bounds; the upper and lower bounds together characterize only the monotone subclass.

minor comments (4)

[Theorem 3 statement] The phrase 'let r_t and R_t be the largest and smallest parameters, respectively' should be clarified: r_t is the largest inradius parameter and R_t is the smallest circumradius parameter.
[Definition 4 and Section 2.2.1] Definition 4 lists invariant (2.2.1) as 𝒄_t+ℰ_t ⊇ conv((𝒄_{t-1}+ℰ_{t-1})∪{𝒛_t}), but the subsequent discussion states a weaker condition (2.2.1a). The logical relationship between the displayed invariants and the prose should be made explicit.
[Algorithm 4, Line 10] The formula defining M contains garbled notation involving '1D v'_dt, zE'; this should be rewritten in standard mathematical notation.
[Section 2.4.5, Algorithm 4 header] The algorithm's output line says 'Output: Ellipsoid ℰ, center 𝒄, and scale α' but the pseudocode omits the final ellipsoid at Line 17; this inconsistency should be fixed.

Circularity Check

0 steps flagged · score 0.0 of 10

No construction-level circularity: the streaming, sparsification, and statistical results are derived from explicit lemmas and external benchmarks; advertised near-optimality is qualified by warm-start and monotone restrictions.

full rationale

The thesis gives full proofs of its main theorems. In Chapter 2, the monotone update rule is derived from geometric lemmas in Section 2.4.2, the evolution condition (2.2.3) is proved from the update parameters, and Theorem 1 follows by telescoping; Theorem 3 supplies an explicit irregular update (Lemma 2.4.19) and Theorem 4 uses a determinant argument. None of these statements take the claimed approximation factor as an assumption. The self-citations to MMO22 and MMO24 are bibliographic rather than load-bearing, since the proofs are reproduced in the text; for instance, Section 2.5 explicitly says the algorithm is the same as in MMO22 but then proves the analysis within the thesis. The lower bounds prove their restriction to monotone algorithms rather than importing an unverified uniqueness result. In Chapters 3 and 4, block Lewis weight existence is imported from external work [JLLS23], and the new content is the sparsification and optimization analysis; the optimality lower bound is taken from external work [LWW21]. The abstract's 'nearly worst-case optimal' claim is stronger than the formal statements when no warm start is available: Theorem 3's prefix aspect-ratio term can exceed the final R/r, as the paper itself notes, and the lower bound applies only to the monotone class defined in Definition 4. Those are scope limitations and advertising overclaims, not circular reductions. No equation in the paper reduces a predicted quantity to a fitted input by construction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 2 invented entities

The central claims rest on standard mathematical results and on the thesis's own modeling assumptions. The main free parameter in the streaming results is the warm-start radius r0. The thesis introduces two new mathematical objects (block Lewis weights, memorization capacity) without independent empirical evidence.

free parameters (2)

initial ball radius r0 = user-specified
Algorithm 2 requires a valid warm start; the final approximation factor depends on R(Z)/r0.
phase-transition threshold d log d = d log d
Algorithm 2 switches from the local ball update to the full ellipsoid update at this threshold; changing it trades the two regimes but is not fitted to data.

assumptions (5)

standard math John's theorem (Theorem 1.1.1)
Used as the offline existential benchmark for all ellipsoidal approximation results.
standard math Concentration of measure for random Gaussian vectors (Properties 1-3 in Section 1.1)
Basis for dueling optimization and backdoor attack algorithms.
domain assumption Existence of block Lewis weights from a determinant maximization problem [JLLS23, Section 4]
The sparsification theorems assume the optimal weights exist and inherit the optimality conditions; the thesis does not re-derive their existence.
domain assumption Monotone adversary models (monotone feedback in dueling optimization; only-intra-cluster edge additions in spectral clustering)
These are modeling choices that define the threat/helpful models; results are conditional on these assumptions.
standard math Entrywise eigenvector perturbation bounds (e.g., [AFWZ20])
Chapter 7 relies on these tools to prove sign consistency of eigenvectors.

invented entities (2)

Block Lewis weights
purpose: Assign importance scores to groups of matrix rows for sparsification and ellipsoidal approximation of block norms.
New mathematical construction; no falsifiable empirical handle outside the paper's own theorems.
Memorization capacity
purpose: Measures when a learning problem is vulnerable to backdoor attacks.
A new statistical definition; its value is its theoretical use, not an external observable.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Geometric Approach to Problems in Optimization and Data Science." pith.science (2026). https://pith.science/paper/A3ACUWWK

@misc{pith2026250416270,
  author       = {Pith},
  title        = {Pith review of: A Geometric Approach to Problems in Optimization and Data Science},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/A3ACUWWK}},
  note         = {Machine review of arXiv:2504.16270}
}

read the original abstract

We give new results for problems in computational and statistical machine learning using tools from high-dimensional geometry and probability. We break up our treatment into two parts. In Part I, we focus on computational considerations in optimization. Specifically, we give new algorithms for approximating convex polytopes in a stream, sparsification and robust least squares regression, and dueling optimization. In Part II, we give new statistical guarantees for data science problems. In particular, we formulate a new model in which we analyze statistical properties of backdoor data poisoning attacks, and we study the robustness of graph clustering algorithms to ``helpful'' misspecification.

Figures

Figures reproduced from arXiv: 2504.16270 by the authors.

**Figure 2.1.** A monotone update step. For brevity, we refer to ℰ and 𝛼 · ℰ as the previous ellipsoids ℰ𝑡−1, 𝛼ℰ𝑡−1, and ℰ ′ and 𝛼 ′ · ℰ′ as the next ellipsoids ℰ𝑡 , 𝛼𝑡 · ℰ𝑡 . ℰ and 𝛼ℰ are, respectively, the larger and smaller black circles. 𝑐 + ℰ′ and 𝑐 + 𝛼 ′ℰ ′ are the larger and smaller blue ellipses. The dotted lines show 𝜕(conv (𝛼ℰ ∪ {𝒛})) \ 𝜕(𝛼ℰ), i.e. the the boundary of conv (𝛼 · ℰ ∪ {𝒛}) minus the boundary of 𝛼ℰ. 2.2.2. St… view at source ↗

**Figure 2.2.** Irregular update step. ℰ𝑡−1 and 𝛼 · ℰ𝑡−1 are, respectively, the light blue strip on the 𝑥-axis and the dark blue strip on the 𝑥-axis. 𝒛𝑡 = (0, √ 1 + 2𝛼) is the newly received point. It turns out that it is sufficient to consider only this special case. To see this, note that we can choose an affine transformation that maps any new point 𝒛𝑡 and previous ellipsoid ℰ𝑡−1 to the setting shown in [PITH_FULL_IMAGE:figures… view at source ↗

**Figure 2.3.** Outer ellipses of the update step. As before, ℰ is the black circle and 𝑐 + ℰ′ is the blue ellipse. 𝑐𝑟 + ℰ′ is the magenta ellipse, with its center at 𝑐𝑟 and the dotted magenta line showing the position of 𝑐𝑟 along the 𝑥-axis. 𝑐𝑟 is defined so 𝑐𝑟 + ℰ′ and ℰ are tangent at two points. 𝑄 is one of these two tangent points. First, note points on the boundary of 𝑐𝑟 + ℰ′ are described by the equation (𝑥 − 𝑐𝑟) 2 𝑎 2 + 𝑦 2… view at source ↗

Figures from the paper (9 more)

**Figure 2.4.** Figure 2.4: Inner ellipses of the update step. As before, 𝛼ℰ is the black circle and 𝑐 + 𝛼 ′ℰ is the blue ellipse. 𝑃0 is the shared leftmost point of 𝛼ℰ and 𝑐 + 𝛼 ′ℰ ′ . There are two lines through 𝒗 that are tangent to 𝛼ℰ, one of which we call 𝐿 and pictured in orange. We call …

**Figure 2.5.** Figure 2.5: Inner ellipses of the update step. As before, 𝛼ℰ is the black circle, 𝑐 + 𝛼 ′ℰ is the blue ellipse, 𝐿 is the orange line through 𝒛 and tangent to 𝛼ℰ, 𝑃1 and 𝑃2 are the tangent points on the lines through 𝒛 tangent to 𝛼ℰ, and 𝑃1𝒛, 𝑃2𝒛 are the dotted black lines. 𝑐+ +𝛼…

**Figure 2.6.** Figure 2.6: The inner ellipses in the two-dimensional lower bound. 𝒪 is the origin. The black solid circle is the previous inner ellipse 𝛼ℰ, and the blue solid circle is the next inner ellipse 𝑐 +𝛼 ′ℰ ′ . The vertical dotted blue line 𝑥 = 𝑐 through the center 𝑐 marks the locatio…

**Figure 2.7.** Figure 2.7: Tree of cases in the lower bound ≥ 𝑏 · 𝐴 − 𝐴 2(𝑑 − 1)log 𝑏 = 𝑏 − 1 2 log 𝑏 𝐴 𝑑 − 1 ≥ 1 2 𝐴 𝑑 where the last line uses that 𝑥−1 2 log(𝑥) > 1 2 when 𝑥 > 1. □ In light of Lemma 2.7.11, we can then assume in the sequel Term II is larger, meaning that Δ𝑃 ≤ 2 log 𝑎 (2.7.8)…

**Figure 7.1.** Figure 7.1: Top left, bottom left: Agreement with the planted bisection of the bipartition obtained from several matrices associated with an input graph generated from a distribution in NSSBM(𝑛, 𝑝, 𝑝, 𝑞) for fixed values of 𝑛, 𝑝, 𝑞 and varying values of 𝑝. In the top left plot, …

**Figure 7.2.** Figure 7.2: Agreement with the planted bisection of the bipartition obtained from unnormalized spectral bisection, for graphs generated from a distribution in NSSBM(𝑛, 𝑝, 𝑝, 𝑞) for fixed values of 𝑛, 𝑝 and varying values of 𝑝 > 𝑞. The left plot uses 𝑝 = 1/2, the right plot uses…

**Figure 7.3.** Figure 7.3: Agreement with the planted bisection of the bipartition obtained from several matrices associated with an input graph generated from a distribution 𝒟 𝐺1,𝐺2 𝑞 ∈ DCM(𝑛, 𝑑in, 𝑞) for fixed values of 𝑛, 𝑞 and varying the size of the planted clique 𝑆. In the left plot, the…

**Figure 7.4.** Figure 7.4: The minimum in-cluster degree 𝑑in and the spectral gap𝜆3(bL)−𝜆2(bL) of distributions 𝒟 𝐺1,𝐺2 𝑞 ∈ DCM(𝑛, 𝑑in, 𝑞) with fixed values of 𝑛, 𝑞 and varying the size of the planted clique 𝑆. The red horizontal line on the left corresponds to the value 𝑛𝑞 + √ 𝑛, the red hori…

**Figure 7.5.** Figure 7.5: Embedding of the vertices given by the second eigenvector 𝒖2 of several matrices associated with a graph sampled from a distribution 𝒟 𝐺1,𝐺2 𝑞 ∈ DCM(𝑛, 𝑑in, 𝑞), with the size of the planted clique set to |𝑆| = 2/5 · 𝑛. Horizontal dashed lines, from top to bottom, cor…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 10 canonical work pages

[9]

Limit theorems for mixed-norm sequence spaces with applications to volume distribution

arXiv:2209.08937 [math.PR] (cited on page 92). [KKTY22] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida. Spectral hypergraph sparsifiers of nearly linear size. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1159–

work page Pith review arXiv
[11]

Concentration and regularization of random graphs

arXiv:1506.00669 [math.PR] (cited on page 267). [LC10] Yann LeCun and Corinna Cortes. MNIST handwritten digit database, 2010. url: http://yann.lecun.com/exdb/mnist/(cited on pages 221, 241). 304 [Lee23] JamesRLee.Spectralhypergraphsparsificationviachaining.In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 207–218,

work page Pith review arXiv 2010
[12]

Spectral hypergraph sparsification via chaining

arXiv:2209.04539 [math.PR] (cited on pages 82, 87, 93, 116). [LS19] Yin Tat Lee and Aaron Sidford. Solving linear programs with sqrt(rank) linear system solves, 2019. arXiv:1910.08033 [cs.DS] (cited on pages 85, 92, 137, 138, 140–143). [LS18] Renato Paes Leme and Jon Schneider. Contextual search via intrinsic vol- umes, 2018.doi: 10.48550/ARXIV.1804.03195...

work page Pith review arXiv 2019
[13]

Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes

arXiv: 2206.07250 [cs.DS] (cited on pages 12, 23, 24, 26, 28, 29, 51, 58). [MMO24] Yury Makarychev, Naren Sarayu Manoj, and Max Ovsiankin. Near-optimal streaming ellipsoidal rounding for general convex polytopes. InProceedings of Fifty Sixth Annual ACM Symposium on Theory of Computing (STOC), June

work page Pith review arXiv
[204]

[JS00] William Johnson and Gideon Schechtman

Interscience Publishers, Inc, 1948 (cited on pages 9, 24, 143). [JS00] William Johnson and Gideon Schechtman. Finite dimensional subspaces of 𝐿𝑝. Handbook of the Geometry of Banach Spaces, 1, September 2000 (cited on page 91). [JKP22] Michael Juhos, Zakhar Kabluchko, and Joscha Prochno. Limit theorems for mixed-norm sequence spaces with applications to vo...

work page 1948
[1170]

Spectral Hypergraph Sparsifiers of Nearly Linear Size

IEEE, 2022. arXiv:2106.02353 [cs.DS] (cited on page 82). [KSJ18] Sai Praneeth Karimireddy, Sebastian U. Stich, and Martin Jaggi. Global lin- ear convergence of newton’s method without strong-convexity or lipschitz gradients,2018.arXiv: 1806.00413 [cs.LG]. url: https://arxiv.org/abs/ 1806.00413(cited on page 145). [KA21] Maximilian Kasy and Rediet Abebe. F...

work page Pith review arXiv 2022
[2003]

[Dat14] Big Data

doi: https://doi.org/10.1002/rsa.10073(cited on page 199). [Dat14] Big Data. Seizing opportunities, preserving values. The White House Report Washington, 2014 (cited on page 136). [DPVW14] MarkADavenport,YanivPlan,EwoutVanDenBerg,andMaryWootters.1- bitmatrixcompletion. InformationandInference:AJournaloftheIMA ,3(3):189– 223, 2014 (cited on page 198). [DLS...

arXiv 2014
[2017]

[GLDG19] Tianyu Gu, Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg

arXiv:1708.06733 [cs.CR] (cited on page 223). [GLDG19] Tianyu Gu, Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg. Bad- Nets:evaluatingbackdooringattacksondeepneuralnetworks. IEEEAccess, 7:47230–47244, 2019 (cited on page 223). 301 [GV16] Olivier Guédon and Roman Vershynin. Community detection in sparse networks via grothendieck’s inequality.Probabilit...

arXiv 2019

Show all 15 references

[2018]

[GC23] XingGaoandYuCheng.Robustmatrixsensinginthesemi-randommodel

doi: 10.1109/ALLERTON.2018.8635938(cited on page 261). [GC23] XingGaoandYuCheng.Robustmatrixsensinginthesemi-randommodel. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. url: https://openreview.net/forum?id=nSr2epejn2(cited on page 263). [GNW24] Ju...

2018
[2021]

[CKP09] ToonCalders,FaisalKamiran,andMykolaPechenizkiy.Buildingclassifiers with independency constraints

arXiv:2110.02954 [math.OC] (cited on page 140). [CKP09] ToonCalders,FaisalKamiran,andMykolaPechenizkiy.Buildingclassifiers with independency constraints. In2009 IEEE international conference on data mining workshops, pages 13–18. IEEE, 2009 (cited on page 140). [CHJJS22] Yair ...

arXiv
[2022]

[JLS23] ArunJambulapati,YangPLiu,andAaronSidford.Chaining,groupleverage score overestimates, and fast spectral hypergraph sparsification

arXiv:2111.01848 [cs.DS] (cited on pages 92, 97, 125, 128, 138–140, 142, 143, 145, 146, 163, 185). [JLS23] ArunJambulapati,YangPLiu,andAaronSidford.Chaining,groupleverage score overestimates, and fast spectral hypergraph sparsification. InProceed- ings of the 55th Annual ACM S...

2023 arXiv
[2023]

arXiv:2212.05619 [cs.DS] (cited on pages 252, 263)

isbn: 9781450399135. arXiv:2212.05619 [cs.DS] (cited on pages 252, 263). [BPSSW21] Brian Bullins, Kshitĳ Patel, Ohad Shamir, Nathan Srebro, and Blake E Woodworth. A stochastic newton algorithm for distributed convex opti- mization.AdvancesinNeuralInformationProcessingSystems ,...

arXiv
[2024]

[MB21] Naren Sarayu Manoj and Avrim Blum

arXiv:2311.09460 [cs.DS] (cited on pages 12, 23). [MB21] Naren Sarayu Manoj and Avrim Blum. Excess capacity and backdoor poi- soning.AdvancesinNeuralInformationProcessingSystems(NeurIPS) ,34,2021. arXiv: 2109.00685 [cs.LG] (cited on pages 19, 213). [MO25] NarenSarayuManojandMa...

2021 arXiv
[4625]

why should I trust you?

PMLR, 2019. arXiv:1902.00146 [cs.LG] (cited on page 140). [Moi21a] Ankur Moitra. Semirandom stochastic block models. InBeyond the Worst-Case Analysis of Algorithms. Tim Roughgarden, editor. Cambridge University Press, 2021, pages 212–233.doi: 10 . 1017 / 9781108637435 . 014(ci...

2019 arXiv
[6774]

org / 10

doi: https : / / doi . org / 10 . 1006 / jagm . 1995 . 1034. url: https : //www.sciencedirect.com/science/article/pii/S0196677485710346 (cited on page 263). [BS95b] Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable graphs. Journal of Algorithms, 19(2):20...

1995 arXiv

Pith tools

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

[1] [9]

Limit theorems for mixed-norm sequence spaces with applications to volume distribution

arXiv:2209.08937 [math.PR] (cited on page 92). [KKTY22] Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida. Spectral hypergraph sparsifiers of nearly linear size. In2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 1159–

work page Pith review arXiv

[2] [11]

Concentration and regularization of random graphs

arXiv:1506.00669 [math.PR] (cited on page 267). [LC10] Yann LeCun and Corinna Cortes. MNIST handwritten digit database, 2010. url: http://yann.lecun.com/exdb/mnist/(cited on pages 221, 241). 304 [Lee23] JamesRLee.Spectralhypergraphsparsificationviachaining.In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 207–218,

work page Pith review arXiv 2010

[3] [12]

Spectral hypergraph sparsification via chaining

arXiv:2209.04539 [math.PR] (cited on pages 82, 87, 93, 116). [LS19] Yin Tat Lee and Aaron Sidford. Solving linear programs with sqrt(rank) linear system solves, 2019. arXiv:1910.08033 [cs.DS] (cited on pages 85, 92, 137, 138, 140–143). [LS18] Renato Paes Leme and Jon Schneider. Contextual search via intrinsic vol- umes, 2018.doi: 10.48550/ARXIV.1804.03195...

work page Pith review arXiv 2019

[4] [13]

Streaming Algorithms for Ellipsoidal Approximation of Convex Polytopes

arXiv: 2206.07250 [cs.DS] (cited on pages 12, 23, 24, 26, 28, 29, 51, 58). [MMO24] Yury Makarychev, Naren Sarayu Manoj, and Max Ovsiankin. Near-optimal streaming ellipsoidal rounding for general convex polytopes. InProceedings of Fifty Sixth Annual ACM Symposium on Theory of Computing (STOC), June

work page Pith review arXiv

[5] [204]

[JS00] William Johnson and Gideon Schechtman

Interscience Publishers, Inc, 1948 (cited on pages 9, 24, 143). [JS00] William Johnson and Gideon Schechtman. Finite dimensional subspaces of 𝐿𝑝. Handbook of the Geometry of Banach Spaces, 1, September 2000 (cited on page 91). [JKP22] Michael Juhos, Zakhar Kabluchko, and Joscha Prochno. Limit theorems for mixed-norm sequence spaces with applications to vo...

work page 1948

[6] [1170]

Spectral Hypergraph Sparsifiers of Nearly Linear Size

IEEE, 2022. arXiv:2106.02353 [cs.DS] (cited on page 82). [KSJ18] Sai Praneeth Karimireddy, Sebastian U. Stich, and Martin Jaggi. Global lin- ear convergence of newton’s method without strong-convexity or lipschitz gradients,2018.arXiv: 1806.00413 [cs.LG]. url: https://arxiv.org/abs/ 1806.00413(cited on page 145). [KA21] Maximilian Kasy and Rediet Abebe. F...

work page Pith review arXiv 2022

[7] [2003]

[Dat14] Big Data

doi: https://doi.org/10.1002/rsa.10073(cited on page 199). [Dat14] Big Data. Seizing opportunities, preserving values. The White House Report Washington, 2014 (cited on page 136). [DPVW14] MarkADavenport,YanivPlan,EwoutVanDenBerg,andMaryWootters.1- bitmatrixcompletion. InformationandInference:AJournaloftheIMA ,3(3):189– 223, 2014 (cited on page 198). [DLS...

arXiv 2014

[8] [2017]

[GLDG19] Tianyu Gu, Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg

arXiv:1708.06733 [cs.CR] (cited on page 223). [GLDG19] Tianyu Gu, Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg. Bad- Nets:evaluatingbackdooringattacksondeepneuralnetworks. IEEEAccess, 7:47230–47244, 2019 (cited on page 223). 301 [GV16] Olivier Guédon and Roman Vershynin. Community detection in sparse networks via grothendieck’s inequality.Probabilit...

arXiv 2019