Pith. sign in

REVIEW 4 major objections 6 minor 55 references

Multipass Linear Sketches for Geometric LP-Type Problems

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

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

Pith's one-line read This paper claims that high-accuracy geometric LP-type problems can be solved in poly(d, log(1/eps)) space with d log(1/eps) passes over the data.

desk verdict The multipass upper bound is a genuine advance and likely fixable; the 1-pass lower bound proof has a gap that fails as stated. read the letter →

arxiv 2507.11484 v2 pith:442RJV5G submitted 2025-07-15 cs.DS

N. Efe Çekirge , William Gay , David P. Woodruff This is my paper · ORCID
classification cs.DS
keywords LP-typeproblemslinearsketchesmultipassstreamingminimumenclosingballsupportvectormachineepsilonapproximationturnstilemodeldistributedcomputation
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 studies streaming and distributed algorithms for LP-type problems: minimum enclosing ball, linear SVM, bounded linear programs, and bounded semidefinite programs, in the regime where dimension d is small and accuracy 1/eps is large. Its main claim is that any such problem with O(d) combinatorial and VC dimension can be (1+O(eps))-approximated by a randomized algorithm using O(ds) passes or rounds and O(s ($\sqrt$(d)/eps)^(3d/s)) poly(d, log(1/eps)) words of space, for any trade-off parameter s. Setting s = d log(1/eps) makes the space polynomial in d and polylogarithmic in 1/eps, removing any dependence on the stream length n. The construction works with a linear sketch, so it also handles point deletions and duplicated points, and it applies in the multipass streaming, strict turnstile, coordinator, and parallel computation models. A complementary lower bound says any one-pass (1+eps)-approximation for minimum enclosing ball or linear SVM needs (1/eps)^$\Omega$(d) words, which the paper uses to justify the multipass approach.

What carries the argument

The load-bearing object is the lattice metric eps-net covering the unit d-cube, together with a linear sketch whose rows index the snapped net points; each input point is snapped to the closest net direction and rounded down in norm to the next power of (1+eps), so distinct original points may collide. Collisions are handled by ell0 estimators and ell0 samplers, which are one-pass linear sketches that count and sample distinct snapped points without materializing the net. The weight function is stored implicitly as the number of stored solutions a point violates, and the termination proof combines the upper and lower weight bounds N^(t/(nu s)) <= w_t(Q) <= e^O(t/nu) N, with nu the combinatorial dimension.

What would settle it

Compute the exact MEB radius and the optimal SVM objective for the two Indexing constructions with d = c/eps for a fixed constant c and compare the resulting gap to eps times the larger optimal value; if the gap is ever smaller than eps times that value, the reduction's padding is too weak to force a one-pass algorithm to distinguish the two cases.

Watch

Extended reading notes

Core claim

The central discovery is that discretizing the input into a metric eps-net and compressing the net with a linear sketch turns Clarkson-style weighted sampling into a space-efficient multipass method whose cost is independent of the stream length n. Snapping every point to one of N net directions and rounding its norm down to a power of (1+eps) collapses the input to N distinct snapped points; ell0 estimators and ell0 samplers then sample these points proportionally to a multiplicative weight that is raised by N^(1/s) for each violated stored solution. After O(nu s) iterations the sample contains a basis for the snapped instance, and property 3, that the snapped solution is a (1+O(eps))-approximation of the original, gives the final answer. With s = d log(1/eps) the space becomes poly(d, log(1/eps)), and the same linear-sketch core works in the multipass streaming, strict turnstile, coordinator, and parallel computation models.

Load-bearing premise

The one-pass lower bounds require that the geometric gap between the two Indexing instances be large enough for a (1+eps)-approximation to distinguish them, but the paper computes that gap as only 2 - $\Omega$(eps/d) for MEB and 4 - $\Omega$(eps/d) for SVM, so when d is large the gap can be smaller than the approximation slack and the reduction cannot force a correct answer.

Editorial extensions

If this is right

  • If the main theorem is correct, there is a full space-pass trade-off for high-accuracy low-dimensional LP-type problems: O(ds) passes buy space O(s (sqrt(d)/eps)^(3d/s)) poly(d, log(1/eps)), interpolating from one-pass exponential space to poly-logarithmic space.
  • Setting s = d log(1/eps) yields a poly(d, log(1/eps))-space algorithm with O(d^2 log(1/eps)) passes, removing all dependence on the number of input points n.
  • Because the algorithm is built from linear sketches, it works in the strict turnstile model with insertions and deletions and in distributed models with per-machine load poly(d, N^(1/s)) + O(k) words instead of O(n).
  • The one-pass lower bound of (1/eps)^Omega(d) for MEB and linear SVM in the regime d < (1/eps)^0.999 shows that the extra passes are necessary to achieve subexponential-in-1/eps space.
  • The same framework gives additive eps-approximations for bounded linear programs and bounded semidefinite programs, including linear classification as a bounded LP.

Reading between the lines

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

  • The one-pass lower bounds as written rest on a geometric gap of 2 - Omega(eps/d) for MEB and 4 - Omega(eps/d) for SVM between the two Indexing instances; when d is large relative to 1/eps that gap is smaller than the approximation slack, so the stated lower bound is most safely read for fixed or small d.
  • The snapping-plus-ell0-sampling recipe may extend to other geometric optimization problems that satisfy a Lipschitz property under metric-net snapping, even if they are not LP-type.
  • A concrete testable extension is to run the multipass algorithm with s slightly below d log(1/eps) and check whether the empirical space usage tracks the predicted s (sqrt(d)/eps)^(3d/s) interpolation.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 6 minor

Summary. The paper presents a multipass linear-sketching framework for epsilon-approximate LP-type problems. The main algorithm snaps input points to a metric epsilon-net, represents the snapped multiset through L0 estimators and samplers, and runs the weighted-sampling scheme of Assadi, Karpov, and Zhang over the resulting discrete point set. It claims O(ds)-pass algorithms with space O(s(sqrt(d)/epsilon)^(3d/s)) poly(d, log(1/epsilon)) words, giving polynomial space in d and polylogarithmic space in 1/epsilon when s = d log(1/epsilon). The framework is applied to MEB, linear SVM, bounded LP, and bounded SDP. The paper also claims one-pass lower bounds of (1/epsilon)^Omega(d) words for (1+epsilon)-approximate MEB and linear SVM via reductions from Indexing.

Significance. If the upper-bound results and the lower bounds were fully established, the paper would give a substantial improvement over epsilon-kernel-based streaming algorithms in the low-dimensional high-accuracy regime, and the lower bounds would motivate the multipass model. The upper bound builds on appropriate standard tools: the L0 estimator of Kane-Nelson-Woodruff, the L0 sampler of Jowhari-Saglam-Tardos, and the sampling framework of [8]; these citations are legitimate and the algorithm is not circular. The main caveat is that the lower-bound reduction, as written, does not deliver the stated Omega(d) exponent, and a few application-level complexity claims are not fully supported.

major comments (4)
  1. [§C.1–C.2, Theorems 7–9] The geometric gap between the two Indexing instances is only Theta(epsilon/d), not Theta(epsilon). In the proof of Theorem 7 the paper derives ||p(j)-q||^2 = 16 - 192 epsilon/d and then states a radius gap of 2 - Omega(epsilon/d); the actual radius is 2 - 12 epsilon/d - O(epsilon^2/d^2). For d >= 6, (1+epsilon)(2 - 12 epsilon/d) > 2, so a (1+epsilon)-approximate MEB algorithm may legally return radius 2 on the b_i=0 instance and the reduction cannot force a correct answer. The same Omega(epsilon/d) gap appears in Lemmas 34–35 for SVM and in the margin argument for Theorem 9, so the claimed (1/epsilon)^Omega(d) lower bounds are not established by the given proofs. A construction with mutual angular separation Theta(sqrt(epsilon)) among n = (1/epsilon)^Theta(d) points would yield the needed Theta(epsilon) gap, but no such construction is supplied.
  2. [§D.1, Lemma 20; Algorithm 1] The proof of Lemma 20 relies on the center point p1 being inside the minimum enclosing ball (c,r) of the snapped set Q, stating that 'both q_j and p1 are in (c,r)'. However, Q is defined as the set of snapped points obtained from P, and Algorithm 1 does not add p1 to Q. If p1 is exempted from snapping as the net center, its membership in Q is not established; if p1 is snapped like every other point, it need not map to a lattice point because the origin is not necessarily a point of the constructed lattice. Without p1 in Q, the argument that all original points lie in (c,(1+4epsilon)r) is incomplete, and this affects the correctness proof of the MEB application and Theorem 22.
  3. [§B.1, Theorem 17] The claimed time bound O(nu s (TV n + m + TB)) does not account for the cost of computing the weight of each snapped point in every iteration. Weights are stored implicitly as the number of previous successful solutions violated, so computing w(q_j) for a point q_j requires testing q_j against all previously stored solutions, of which there are O(nu s). This adds a factor of O(nu s) to the per-point work in each pass, so the total time is O(nu^2 s^2 TV n + ...), not O(nu s TV n). The undercount propagates to the time bounds in Theorems 22, 25, 28, and 33.
  4. [§B.8, Theorem 33] The SDP reduction replaces the positive-semidefinite constraint by a finite set of lattice constraints z^T X z >= 0 with z ranging over a net of size O((d sqrt(d)/epsilon)^d). Since the LP-type algorithm must check violators among all constraints of the LP in every iteration, the time per pass should include this exponential number of PSD lattice constraints. The displayed time bound O-tilde(d^2 s (n + m d^2 + d^5)) counts only the n original streamed constraints and omits the lattice constraints, and the comparison with [27] in Table 1 is therefore not supported.
minor comments (6)
  1. [§1, Introduction] The name 'Shahir and Welzl' should be 'Sharir and Welzl'.
  2. [Algorithm 2] The variable p_i used for a sampling probability on line 8 collides with the input point notation p_i; please rename the probability variable.
  3. [§C.1] The sentence 'the distance between p(j) and q is 2 - Omega(epsilon/d)' should refer to the radius of the MEB, since the squared distance was computed as 16 - 192 epsilon/d and the radius is half the diameter.
  4. [§B.4] The first paragraph of the Parallel Computation section says 'In the coordinator model' where it should say 'In the parallel computation model'.
  5. [§A.3, Lemma 16] The recursion in the proof writes w_t(Q) <= w_{t-1}(Q) + ... and then unrolls to w_t(Q) <= ... w_0(Q); the indexing between the update step and the unrolling should be made consistent.
  6. [§A.2, Claim 11] The statement that the TV distance 'converges to 0' is imprecise: for s close to log N, m is only polynomial in d and log(1/epsilon), so the TV bound is O(1/sqrt(m)). The proof should state the explicit constant needed to retain the 3/4 - 1/poly(N) >= 2/3 success probability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the sketching/ℓ0/weighted-sampling derivation is self-contained, and the self-cited Theorem 3 is independent prior work. The Appendix C lower-bound gap is a correctness flaw, not a circular input-prediction.

full rationale

The paper's main algorithm (Section 3, Appendix A) constructs an explicit metric-ε-net, feeds it through a linear sketch, and runs Clarkson/Assadi-style weighted sampling using ℓ0 estimators and samplers. No fitted parameter is later 'predicted'; the target approximation for each application is obtained by proving property (P3) with the lemmas in Appendices B.5–B.8 and D. Claim 10's correctness uses only the LP-type locality/monotonicity axioms and (P3). The cited ℓ0 estimator [32] and sampler [31] are standard theorems whose statements do not assume any result of this paper; [32]'s author overlap is therefore not circular. The only significant defect I find is in the 1-pass lower-bound reductions (§4, Appendix C.1–C.2): the computed radius/margin gap is 2−Ω(ε/d) and 4−Ω(ε/d), respectively, not the 2−Ω(ε) stated in Section 4, so a (1+ε)-approximation is not forced to distinguish the two Indexing cases when d≳6. This invalidates Theorems 7–9 as written, but it is a quantitative reduction error, not a circular derivation; it does not raise the circularity score.

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

The main algorithm assumes the LP-type problem satisfies the three properties P1-P3, uses the standard mu-net sampling lemma and known L0 estimator/sampler results. The lower bound relies on an unproven gap size. The only user-chosen parameter is s.

free parameters (1)
  • s = any s in [1, d log(1/eps)]
    User-chosen trade-off parameter controlling the number of passes versus space usage.
assumptions (4)
  • domain assumption The LP-type problem satisfies properties P1, P2, P3 (locality, monotonicity, and epsilon-net stability).
    Property 3 is asserted to hold for most LP-type problems and proved for MEB, SVM, bounded LP, and bounded SDP in Appendix D.
  • standard math The mu-net sampling bound of Haussler-Welzl (Lemma 6) applies to the violator set system with VC dimension lambda.
    Used to bound the sample size m in Algorithm 2.
  • standard math There exist 1-pass L0 estimators and samplers with polylogarithmic space (Theorems 3 and 4).
    Core tools from prior literature [32] and [31].
  • ad hoc to paper The lower-bound geometric construction creates a gap of Omega(eps) between the two Indexing cases.
    The proof in Section C.1 only shows a gap of Omega(eps/d); without a gap exceeding the approximation slack, the Indexing reduction fails.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Multipass Linear Sketches for Geometric LP-Type Problems." pith.science (2026). https://pith.science/paper/442RJV5G

@misc{pith2026250711484,
  author       = {Pith},
  title        = {Pith review of: Multipass Linear Sketches for Geometric LP-Type Problems},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/442RJV5G}},
  note         = {Machine review of arXiv:2507.11484}
}
abstract

LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinatorial optimization problems, with many important applications in machine learning applications such as classification, bioinformatics, and noisy learning. We study LP-type problems in several streaming and distributed big data models, giving $\varepsilon$-approximation linear sketching algorithms with a focus on the high accuracy regime with low dimensionality $d$, that is, when ${d < (1/\varepsilon)^{0.999}}$. Our main result is an $O(ds)$ pass algorithm with $O(s( \sqrt{d}/\varepsilon)^{3d/s}) \cdot \mathrm{poly}(d, \log (1/\varepsilon))$ space complexity in words, for any parameter $s \in [1, d \log (1/\varepsilon)]$, to solve $\varepsilon$-approximate LP-type problems of $O(d)$ combinatorial and VC dimension. Notably, by taking $s = d \log (1/\varepsilon)$, we achieve space complexity polynomial in $d$ and polylogarithmic in $1/\varepsilon$, presenting exponential improvements in $1/\varepsilon$ over current algorithms. We complement our results by showing lower bounds of $(1/\varepsilon)^{\Omega(d)}$ for any $1$-pass algorithm solving the $(1 + \varepsilon)$-approximation MEB and linear SVM problems, further motivating our multi-pass approach.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

55 extracted references · 36 canonical work pages

  1. [8]

    Distributed and streaming linear programming in low dimensions

    Sepehr Assadi, Nikolai Karpov, and Qin Zhang. Distributed and streaming linear programming in low dimensions. In Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems , PODS '19, page 236–253, New York, NY, USA, 2019. Association for Computing Machinery. https://doi.org/10.1145/3294052.3319697 doi:10.1145/3294052.3319697

    work page arXiv 2019

  2. [27]

    Sublinear time algorithms for approximate semidefinite programming

    Dan Garber and Elad Hazan. Sublinear time algorithms for approximate semidefinite programming. Mathematical Programming , 158(1):329--361, 2016. https://doi.org/10.1007/s10107-015-0932-z doi:10.1007/s10107-015-0932-z

    work page doi:10.1007/s10107-015-0932-z 2016

  3. [1]

    Agarwal, Sariel Har-Peled, and Kasturi R

    Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Approximating extent measures of points. J. ACM , 51(4):606–635, jul 2004. https://doi.org/10.1145/1008731.1008736 doi:10.1145/1008731.1008736

    work page arXiv 2004

  4. [2]

    Agarwal and R

    Pankaj K. Agarwal and R. Sharathkumar. Streaming algorithms for extent problems in high dimensions. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '10, page 1481–1489, USA, 2010. Society for Industrial and Applied Mathematics

    work page 2010

  5. [3]

    Agarwal and Hai Yu

    Pankaj K. Agarwal and Hai Yu. A space-optimal data-stream algorithm for coresets in the plane. In Proceedings of the Twenty-Third Annual Symposium on Computational Geometry , SCG '07, page 1–10, New York, NY, USA, 2007. Association for Computing Machinery. https://doi.org/10.1145/1247069.1247071 doi:10.1145/1247069.1247071

    work page arXiv 2007

  6. [4]

    Linear programming in the semi-streaming model with application to the maximum matching problem

    Kook Jin Ahn and Sudipto Guha. Linear programming in the semi-streaming model with application to the maximum matching problem. Information and Computation , 222:59--79, 2013. 38th International Colloquium on Automata, Languages and Programming (ICALP 2011). URL: https://www.sciencedirect.com/science/article/pii/S0890540112001460, https://doi.org/10.1016/...

    doi:10.1016/j.ic.2012.10.006 2013

  7. [5]

    Woodruff

    Yuqing Ai, Wei Hu, Yi Li, and David P. Woodruff. New characterizations in turnstile streams with applications. In Proceedings of the 31st Conference on Computational Complexity , CCC '16, Dagstuhl, DEU, 2016. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

    work page 2016

  8. [6]

    The space complexity of approximating the frequency moments

    Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences , 58(1):137--147, 1999. URL: https://www.sciencedirect.com/science/article/pii/S0022000097915452, https://doi.org/10.1006/jcss.1997.1545 doi:10.1006/jcss.1997.1545

    arXiv 1999

Show all 55 references
  1. [7]

    da Fonseca, and David M

    Sunil Arya, Guilherme D. da Fonseca, and David M. Mount. Near-Optimal epsilon-Kernel Construction and Related Problems . In Boris Aronov and Matthew J. Katz, editors, 33rd International Symposium on Computational Geometry (SoCG 2017) , volume 77 of Leibniz International Procee...

    2017 doi

  2. [9]

    Clarkson

    Mihai B a doiu and Kenneth L. Clarkson. Smaller core-sets for balls. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '03, page 801–802, USA, 2003. Society for Industrial and Applied Mathematics

    2003

  3. [10]

    Clarkson

    Mihai B a doiu and Kenneth L. Clarkson. Optimal core-sets for balls. Computational Geometry , 40(1):14--22, 2008. URL: https://www.sciencedirect.com/science/article/pii/S0925772107000454, https://doi.org/10.1016/j.comgeo.2007.04.002 doi:10.1016/j.comgeo.2007.04.002

    2008 doi

  4. [11]

    Bagul and Satish K

    Yogesh J. Bagul and Satish K. Panchal. Certain inequalities of K ober and L azarevic type. The Journal of the Indian Mathematical Society , 89(1-2):01–07, Jan. 2022. URL: https://www.informaticsjournals.com/index.php/jims/article/view/20737, https://doi.org/10.18311/jims/2022/...

    2022 doi

  5. [12]

    A. Blum, A. Frieze, R. Kannan, and S. Vempala. A polynomial-time algorithm for learning noisy linear threshold functions. In Proceedings of 37th Conference on Foundations of Computer Science , pages 330--338, 1996. https://doi.org/10.1109/SFCS.1996.548492 doi:10.1109/SFCS.1996.548492

    1996

  6. [13]

    Hand recognition using geometric classifiers

    Yaroslav Bulatov, Sachin Jambawalikar, Piyush Kumar, and Saurabh Sethia. Hand recognition using geometric classifiers. In David Zhang and Anil K. Jain, editors, Biometric Authentication , pages 753--759, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg

    2004

  7. [14]

    Christopher J. C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery , 2(2):121--167, 1998. https://doi.org/10.1023/A:1009715923555 doi:10.1023/A:1009715923555

    1998 doi

  8. [15]

    Learning linear threshold functions in the presence of classification noise

    Tom Bylander. Learning linear threshold functions in the presence of classification noise. In Proceedings of the Seventh Annual Conference on Computational Learning Theory , COLT '94, page 340–347, New York, NY, USA, 1994. Association for Computing Machinery. https://doi.org/1...

    1994

  9. [16]

    Exact matrix completion via convex optimization

    Emmanuel Cand\` e s and Benjamin Recht. Exact matrix completion via convex optimization. Communications of the ACM , 55(6):111–119, June 2012. https://doi.org/10.1145/2184319.2184343 doi:10.1145/2184319.2184343

    2012

  10. [17]

    Candes and Terence Tao

    Emmanuel J. Candes and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory , 56(5):2053--2080, 2010. https://doi.org/10.1109/TIT.2010.2044061 doi:10.1109/TIT.2010.2044061

    2010

  11. [18]

    A comprehensive survey on support vector machine classification: Applications, challenges and trends

    Jair Cervantes, Farid Garcia-Lamont, Lisbeth Rodr \' guez-Mazahua, and Asdrubal Lopez. A comprehensive survey on support vector machine classification: Applications, challenges and trends. Neurocomputing , 408:189--215, 2020. URL: https://www.sciencedirect.com/science/article/...

    2020 doi

  12. [19]

    Timothy M. Chan. Faster core-set constructions and data-stream algorithms in fixed dimensions. Computational Geometry , 35(1):20--35, 2006. Special Issue on the 20th ACM Symposium on Computational Geometry. URL: https://www.sciencedirect.com/science/article/pii/S09257721050009...

    2006 doi

  13. [20]

    o rg-R \

    Timothy M. Chan and Vinayak Pathak. Streaming and dynamic algorithms for minimum enclosing balls in high dimensions. In Frank Dehne, John Iacono, and J \"o rg-R \"u diger Sack, editors, Algorithms and Data Structures , pages 195--206, Berlin, Heidelberg, 2011. Springer Berlin ...

    2011

  14. [21]

    M. T. Chao. A general purpose unequal probability sampling plan. Biometrika , 69(3):653--656, 1982. URL: http://www.jstor.org/stable/2336002

    1982

  15. [22]

    Clarkson

    Kenneth L. Clarkson. Las V egas algorithms for linear and integer programming when the dimension is small. J. ACM , 42(2):488–499, mar 1995. https://doi.org/10.1145/201019.201036 doi:10.1145/201019.201036

    1995

  16. [23]

    Clarkson

    Kenneth L. Clarkson. Coresets, sparse greedy approximation, and the frank-wolfe algorithm. ACM Trans. Algorithms , 6(4), sep 2010. https://doi.org/10.1145/1824777.1824783 doi:10.1145/1824777.1824783

    2010

  17. [24]

    Clarkson, Elad Hazan, and David P

    Kenneth L. Clarkson, Elad Hazan, and David P. Woodruff. Sublinear optimization for machine learning. J. ACM , 59(5), November 2012. https://doi.org/10.1145/2371656.2371658 doi:10.1145/2371656.2371658

    2012

  18. [25]

    Muthukrishnan

    Graham Cormode and S. Muthukrishnan. What's hot and what's not: tracking most frequent items dynamically. In Proceedings of the Twenty-Second ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems , PODS '03, page 296–306, New York, NY, USA, 2003. Association for...

    2003

  19. [26]

    A simple polynomial-time rescaling algorithm for solving linear programs

    John Dunagan and Santosh Vempala. A simple polynomial-time rescaling algorithm for solving linear programs. Mathematical Programming , 114(1):101--114, 2008. https://doi.org/10.1007/s10107-007-0095-7 doi:10.1007/s10107-007-0095-7

    2008 doi

  20. [28]

    Epsilon-nets and simplex range queries

    David Haussler and Emo Welzl. Epsilon-nets and simplex range queries. In Proceedings of the Second Annual Symposium on Computational Geometry , SCG '86, page 61–71, New York, NY, USA, 1986. Association for Computing Machinery. https://doi.org/10.1145/10515.10522 doi:10.1145/10...

    1986

  21. [29]

    Fractional Set Cover in the Streaming Model

    Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, and Anak Yodpinyanee. Fractional Set Cover in the Streaming Model . In Klaus Jansen, Jos\' e D. P. Rolim, David P. Williamson, and Santosh S. Vempala, editors, Approximation, Randomization, and Com...

    2017

  22. [30]

    Woodruff

    Piotr Indyk, Eric Price, and David P. Woodruff. On the power of adaptivity in sparse recovery. In 2011 IEEE 52nd A nnual S ymposium on F oundations of C omputer S cience--- FOCS 2011 , pages 285--294. IEEE Computer Soc., Los Alamitos, CA, 2011. https://doi.org/10.1109/FOCS.201...

    2011 doi

  23. [31]

    Tight bounds for lp samplers, finding duplicates in streams, and related problems

    Hossein Jowhari, Mert Sa g lam, and G\' a bor Tardos. Tight bounds for lp samplers, finding duplicates in streams, and related problems. In Proceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems , PODS '11, page 49–58, New York, NY, U...

    2011

  24. [32]

    Kane, Jelani Nelson, and David P

    Daniel M. Kane, Jelani Nelson, and David P. Woodruff. An optimal algorithm for the distinct elements problem. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems , PODS '10, page 41–52, New York, NY, USA, 2010. Association fo...

    2010

  25. [33]

    Piyush Kumar, Joseph S. B. Mitchell, and E. Alper Yildirim. Approximate minimum enclosing balls in high dimensions using core-sets. ACM J. Exp. Algorithmics , 8:1.1–es, dec 2004. https://doi.org/10.1145/996546.996548 doi:10.1145/996546.996548

    2004

  26. [34]

    Nguyen, and David P

    Yi Li, Huy L. Nguyen, and David P. Woodruff. Turnstile streaming algorithms might as well be linear sketches. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing , STOC '14, page 174–183, New York, NY, USA, 2014. Association for Computing Machinery. h...

    2014

  27. [35]

    Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, and Tianyi Zhou

    S. Cliff Liu, Zhao Song, Hengjie Zhang, Lichen Zhang, and Tianyi Zhou. Space-Efficient Interior Point Method, with Applications to Linear Programming and Maximum Weight Bipartite Matching . In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Collo...

    2023

  28. [36]

    Modelling machine learning algorithms on relational data with datalog

    Nantia Makrynioti, Nikolaos Vasiloglou, Emir Pasalic, and Vasilis Vassalos. Modelling machine learning algorithms on relational data with datalog. In Proceedings of the Second Workshop on Data Management for End-To-End Machine Learning , DEEM'18, New York, NY, USA, 2018. Assoc...

    2018

  29. [37]

    Matou s ek, M

    J. Matou s ek, M. Sharir, and E. Welzl. A subexponential bound for linear programming. Algorithmica , 16(4):498--516, 1996. https://doi.org/10.1007/BF01940877 doi:10.1007/BF01940877

    1996 doi

  30. [38]

    Woodruff, and Hongyang Zhang

    Vasileios Nakos, Xiaofei Shi, David P. Woodruff, and Hongyang Zhang. Improved algorithms for adaptive compressed sensing. In 45th I nternational C olloquium on A utomata, L anguages, and P rogramming , volume 107 of LIPIcs. Leibniz Int. Proc. Inform. , pages Art. No. 90, 14. S...

    2018

  31. [39]

    Approximating smallest enclosing balls

    Frank Nielsen and Richard Nock. Approximating smallest enclosing balls. In Antonio Lagan \'a , Marina L. Gavrilova, Vipin Kumar, Youngsong Mun, C. J. Kenneth Tan, and Osvaldo Gervasi, editors, Computational Science and Its Applications -- ICCSA 2004 , pages 147--157, Berlin, H...

    2004

  32. [40]

    A. B. Novikoff. On convergence proofs on perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata , volume 12, pages 615--622, New York, NY, USA, 1962. Polytechnic Institute of Brooklyn

    1962

  33. [41]

    Woodruff

    Eric Price and David P. Woodruff. Lower bounds for adaptive sparse recovery. In Proceedings of the T wenty- F ourth A nnual ACM - SIAM S ymposium on D iscrete A lgorithms , pages 652--663. SIAM, Philadelphia, PA, 2012

    2012

  34. [42]

    A simpler approach to matrix completion

    Benjamin Recht. A simpler approach to matrix completion. J. Mach. Learn. Res. , 12(null):3413–3430, December 2011

    2011

  35. [43]

    A combinatorial bound for linear programming and related problems

    Micha Sharir and Emo Welzl. A combinatorial bound for linear programming and related problems. In Alain Finkel and Matthias Jantzen, editors, STACS 92 , pages 567--579, Berlin, Heidelberg, 1992. Springer Berlin Heidelberg

    1992

  36. [44]

    Streaming semidefinite programs: O ( n ) passes, small space and fast runtime, 2023

    Zhao Song, Mingquan Ye, and Lichen Zhang. Streaming semidefinite programs: O ( n ) passes, small space and fast runtime, 2023. URL: https://arxiv.org/abs/2309.05135, https://arxiv.org/abs/2309.05135 arXiv:2309.05135

    2023 arXiv

  37. [45]

    Woodruff, Guang Yang, and Jialin Zhang

    Xiaoming Sun, David P. Woodruff, Guang Yang, and Jialin Zhang. Querying a matrix through matrix-vector products. ACM Trans. Algorithms , 17(4), October 2021. https://doi.org/10.1145/3470566 doi:10.1145/3470566

    2021 doi

  38. [46]

    Tsang, James T

    Ivor W. Tsang, James T. Kwok, and Pak-Ming Cheung. Core vector machines: Fast svm training on very large data sets. J. Mach. Learn. Res. , 6:363–392, dec 2005

    2005

  39. [47]

    Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang

    Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and _1 -regression in nearly linear time for dense instances. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , ST...

    2021

  40. [48]

    V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications , 16(2):264--280, 1971. https://arxiv.org/abs/https://doi.org/10.1137/1116025 arXiv:https://doi.org/10.1137/11160...

    1971 doi

  41. [49]

    V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. In Vladimir Vovk, Harris Papadopoulos, and Alexander Gammerman, editors, Measures of Complexity: Festschrift for Alexey Chervonenkis , pages 11--30. Sprin...

    2015 doi

  42. [50]

    Woodruff

    David P. Woodruff. Sketching as a tool for numerical linear algebra. Found. Trends Theor. Comput. Sci. , 10(1–2):1–157, October 2014. https://doi.org/10.1561/0400000060 doi:10.1561/0400000060

    2014 doi

  43. [51]

    Distance metric learning with application to clustering with side-information

    Eric Xing, Michael Jordan, Stuart J Russell, and Andrew Ng. Distance metric learning with application to clustering with side-information. In S. Becker, S. Thrun, and K. Obermayer, editors, Advances in Neural Information Processing Systems , volume 15. MIT Press, 2002. URL: ht...

    2002

  44. [52]

    An extension of K armarkar's projective algorithm for convex quadratic programming

    Yinyu Ye and Edison Tse. An extension of K armarkar's projective algorithm for convex quadratic programming. Mathematical Programming , 44(1):157--179, 1989. https://doi.org/10.1007/BF01587086 doi:10.1007/BF01587086

    1989 doi

  45. [53]

    Alper Yildirim

    E. Alper Yildirim. Two algorithms for the minimum enclosing ball problem. SIAM J. on Optimization , 19(3):1368–1391, nov 2008. https://doi.org/10.1137/070690419 doi:10.1137/070690419

    2008 doi

  46. [54]

    An almost space-optimal streaming algorithm for coresets in fixed dimensions

    Hamid Zarrabi-Zadeh. An almost space-optimal streaming algorithm for coresets in fixed dimensions. Algorithmica , 60(1):46--59, 2011. https://doi.org/10.1007/s00453-010-9392-2 doi:10.1007/s00453-010-9392-2

    2011 doi

  47. [55]

    Hamid Zarrabi - Zadeh and Timothy M. Chan. A simple streaming algorithm for minimum enclosing balls. In Proceedings of the 18th Annual Canadian Conference on Computational Geometry, CCCG 2006, August 14-16, 2006, Queen's University, Ontario, Canada , 2006. URL: http://www.cs.q...

    2006

Pith tools

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