Pith. sign in

REVIEW 4 major objections 5 minor 15 references

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time

T0 review · 4 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read An $\tilde{O}(n\sqrt{n})$-time algorithm estimates maximum matching size with multiplicative factor $0.5109$, beating the $1/2$ barrier in strongly sublinear time.

desk verdict The paper has a genuinely new approach and a clean derivation of the 0.5109 constant, but the main estimation lemma contains a concrete normalization bug that breaks the proof as written; the fix looks straightforward. read the letter →

arxiv 2506.01669 v1 pith:QECKB3LX submitted 2025-06-02 cs.DS

Sepideh Mahabadi , Mohammad Roghani , Jakub Tarnawski This is my paper · ORCID
classification cs.DS MSC 68W2068W2505C70
keywords maximummatchingsublineartimeapproximationalgorithmrandomgreedymaximalgraphoraclessizeestimationlocalcomputationalgorithmsdynamic
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 claims that the size of a maximum matching in an $n$-vertex graph can be estimated to within a multiplicative factor of $0.5109$ in $\tilde{O}(n\sqrt{n})$ time, using only adjacency-list queries rather than reading the whole graph. If correct, this is the first fixed approximation constant that is clearly above $1/2$ and still runs in strongly sublinear time; earlier alternatives were a $0.5+2^{-280}$ factor in $n^{1+\epsilon}$ time or near-$1$ factors only in time close to $n^2$. The algorithm first spends $\tilde{O}(n\sqrt{n})$ time building an explicit matching by sampling roughly $\sqrt{n}$ neighbors per vertex, which leaves the unmatched induced subgraph with maximum degree about $\sqrt{n}$. It then estimates the effect of two possible augmentations of this matching using nested random-greedy-matching oracles, and takes the better estimate. The $0.5109$ constant comes from a weighted average of the two augmentation bounds, and the analysis shows the max of the two always clears $0.5109$ times the true maximum matching.

What carries the argument

The central object is a random greedy maximal matching (RGMM) oracle: fix a uniformly random permutation of edges and greedily add edges; the oracle reports, for a queried vertex, whether it is matched and with which edge, in time proportional to the graph's average degree. The paper combines this oracle with three structural tools. First, sparsification: explicitly construct a matching $M$ by sampling $\sim\sqrt{n}$ neighbors per vertex, forcing $G[V\setminus V(M)]$ to have maximum degree $\sqrt{n}$. Second, a $b$-matching with capacities $k$ on $V(M)$ and $kb$ on $V\setminus V(M)$, with $b = 1 + \sqrt{2}$: a maximal matching plus such a $b$-matching yields the $(2 - \sqrt{2})$-approximation of the two-pass streaming template. Third, the degree-proportional visit bound for RGMM: when the oracle is started from a random vertex, a vertex $v$ is queried only $\tilde{O}(\deg_G(v)/|V(G)|)$ times in expectation; this converts the naive nested-oracle cost into $\tilde{O}(\sqrt{n} \cdot \bar{d}(G))$ and finally $\tilde{O}(n\sqrt{n})$.

What would settle it

Run the RGMM oracle on a carefully chosen graph family, say a large clique connected by a single edge to a leaf or a dense bipartite gadget attached to a long tail, and record, over many random permutations and random starting vertices, the expected number of times each vertex is queried. The paper's Proposition 4.8 predicts this count is $\tilde{O}(\deg_G(v)/|V(G)|)$ for every vertex. If any family shows a vertex whose query count grows faster than $\deg_G(v)/|V(G)|$ by more than polylog factors, then Lemma 4.10 and the $\tilde{O}(n\sqrt{n})$ theorem collapse; conversely, confirming the bound on adversarial dense graphs would validate the load-bearing premise empirically.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is a sublinear-time algorithm: given adjacency-list access, it estimates $|M_{max}(G)|$ with multiplicative factor $0.5109$ in $\tilde{O}(n\sqrt{n})$ time with high probability. The construction has three load-bearing pieces. Preprocessing builds an explicit matching $M$ by sampling $c=2\sqrt{n}\log n$ neighbors per unmatched vertex, so that with high probability the induced subgraph on vertices still unmatched has maximum degree at most $\sqrt{n}$; queries about $M$ are then free. On top of this, two RGMM oracles are run: one (the inner oracle) produces a maximal matching $M'$ on $G[V\setminus V(M)]$, and one (the outer oracle) estimates a maximal $b$-matching that would augment $M'$ inside the low-degree subgraph; a parallel oracle estimates a $b$-matching augmenting $M$ directly. The approximation proof partitions a fixed maximum matching into five classes according to which of $M$, $M'$, and the remaining vertices contain its endpoints, then shows that the maximum of the two candidate estimates is at least $\gamma\cdot\mu(G)$ for $\gamma = 4(5-2\sqrt{2})/17 - O(\epsilon) > 0.5109$.

Load-bearing premise

All of the $\tilde{O}(n\sqrt{n})$ runtime analysis rests on an externally cited property of the RGMM oracle: a random-start oracle call queries each vertex $v$ only $\tilde{O}(\deg_G(v)/|V(G)|)$ times in expectation. The paper uses this as Proposition 4.8 and points to a separate paper by the same three authors for its proof; if the property were false on some graph family, the nested outer oracle could repeatedly query a costly vertex and the running time would degrade to $O(n^2)$, collapsing the main claim.

Editorial extensions

If this is right

  • Fixed constant above $1/2$: matching size can be estimated with a $0.5109$ multiplicative factor in strongly sublinear $n^{1.5}$ time, not merely $n^{1+\epsilon}$ with a $2^{-280}$ advantage.
  • Matrix oracle model: with adjacency-matrix access, the same algorithm gives a $(0.5109, o(n))$ multiplicative-additive estimate in $\tilde{O}(n\sqrt{n})$ time.
  • Drop-in subroutine: the algorithm can replace a $0.5$-approximation in dynamic matching algorithms that need $\tilde{O}(n\sqrt{n})$-time matching-size estimation, yielding a small but real improvement in their approximation ratio.
  • Average-degree dependent speedups: the inner estimation routines run in $\tilde{O}(\sqrt{n} \cdot \bar{d}(G))$ and $\tilde{O}(\bar{d}(G))$ expected time, so sparse graphs are handled faster than the worst-case $n\sqrt{n}$ bound.
  • High-probability by parallelism: the runtime guarantee is made with high probability by running $O(\log n)$ independent copies and stopping at the first completion.

Reading between the lines

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

  • Editorial inference: the sparsify-to-degree-$\sqrt{n}$ plus degree-proportional-oracle recipe is generic; any problem whose sublinear oracle is a random greedy process with degree-proportional visits could inherit the same speedup, e.g., vertex cover size, b-matching, or hypergraph matching.
  • Editorial inference: replacing the $\sqrt{n}$ sampling threshold with $n^{\alpha}$ would give a time bound of roughly $n^{1+\alpha}$ and a degree bound of $n^{\alpha}$ in the unmatched subgraph, so the same two-case analysis likely yields a continuum of time-versus-approximation trade-offs, with $0.5109$ preserved for the range where the unmatched degree stays small enough.
  • Editorial inference: the weighted-average optimization that yields $\gamma = 4(5-2\sqrt{2})/17$ is not obviously optimal; adding a third augmentation case or a longer augmenting-path b-matching could push the constant toward the streaming template's $2-\sqrt{2} \approx 0.585$ ceiling at the same or slightly larger polynomial time.
  • Editorial inference: because the adjacency-matrix guarantee is $(0.5109, o(n))$ rather than purely multiplicative, and multiplicative constant approximation is impossible in that model, the result is plausibly optimal in kind; a matching lower bound with a similar trade-off would be the natural next step.
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 / 5 minor

Summary. The paper proposes a sublinear-time algorithm for estimating the size of a maximum matching in general graphs. The main theorem claims a multiplicative 0.5109-approximation with adjacency-list access in ~O(n√n) time, together with an adjacency-matrix variant achieving (0.5109, o(n)) and an application to dynamic matching via Beh23. The algorithm explicitly constructs a sparse matching M, uses the random greedy maximal matching (RGMM) oracle to define a maximal matching M' on the unmatched vertices, and then estimates two b-matchings B1 and B2; the final estimate is the maximum of two linear combinations of the estimated sizes. The approximation analysis is modeled on the two-pass streaming algorithm of Konrad and Naidu, and the runtime analysis relies on a per-vertex visit-frequency lemma for RGMM taken from the authors' companion paper [MRTV25].

Significance. If correct, the result would be a significant step beyond the long-standing 1/2 barrier for sublinear-time maximum-matching estimation: it would give a fixed constant 0.5109 at running time n^1.5, whereas prior work offered either only 0.5 + 2^{-280} at n^{1+ε} or near-1 approximation at nearly n^2 time. The approach is conceptually simple and reuses known building blocks in a transparent way. However, the written proof contains several load-bearing gaps in the approximation-ratio analysis and in the justification of the runtime oracle, so the contribution is currently conditional on a successful revision. The paper does not ship machine-checked proofs or code; its value lies in the algorithmic idea and the potential for a repaired analysis.

major comments (4)
  1. [§4.3, Algorithms 4–5, Lemma 4.7] The identities E[Y_i] = 2 E|B1|/n and E[Z_i] = 2 E|B2|/n in the proof of Lemma 4.7 are false for the sampling procedure as stated. The random vertices in G'_1 and G'_2 are chosen from graphs with k|V(M')| + kb|C| and k|V(M)| + kb|V\V(M)| vertices, respectively, and these quantities are not n. For a uniform vertex of G'_2, the matched probability is 2E|B2|/|V(G'_2)|, so the first term of µB2 has expectation E|B2| · n/|V(G'_2)|, which can be smaller than E|B2| by a factor as small as 1/(kb). Since k > 1/(bε^3), this dilutes the b-matching contribution to µ2 by a factor of order k and the 0.5109 lower bound in Lemma 4.7 is not attained. The estimator must use the correct vertex count, or the sampling must be designed so that the n multiplier is valid; note further that |V(G'_1)| depends on the unknown |M'|, so a purely notational fix is not immediate.
  2. [§4.3, Lemma 4.7, Eq. (5)] The step 0.5109 µ(G) ≤ max( |M| + (1−1/b)E|M'| + (1/(kb))E|B1|, (1−1/b)|M| + (1/(kb))E|B2| ) does not follow from Lemma 4.6. Lemma 4.6 bounds the maximum of the realized quantities for each realization, whereas max(E[X], E[Y]) can be strictly smaller than E[max(X,Y)]; Jensen's inequality goes in the opposite direction. To obtain a high-probability lower bound on max(µ1, µ2), the proof should show that each estimate tracks the corresponding realized quantity for a fixed permutation and then apply the deterministic inequalities (3)–(4). As written, the high-probability statement in Lemma 4.7 is not established.
  3. [§4.3, Lemma 4.6, Eq. (2)] Equation (2) asserts |M| = |M*_2| + (1/2)|M*_1| + (1/2)|M'*_2|, which is false in general because a maximum matching M* need not saturate V(M). For example, on the 5-vertex path with M = {(b,c),(d,e)} and M* = {(a,b),(c,d)}, the left side is 2 and the right side is 1.5. The proof only needs the inequality |M| ≥ |M*_2| + (1/2)|M*_1| + (1/2)|M'*_2|, which holds since the right side is half the number of M* endpoints in V(M); the argument can be repaired, but the displayed equality should be corrected to an inequality with an explanation.
  4. [§4.4, Lemmas 4.10/4.12, Propositions 4.8–4.9] The n^1.5 runtime bound rests on Proposition 4.8, quoted from [MRTV25], which asserts that the RGMM oracle visits a vertex v only ~O(deg_G(v)/|V(G)|) times when started from a random vertex. The paper does not prove this lemma, and its application here is delicate: in Algorithm 4 the inner oracle is invoked not on uniformly random vertices but on vertices generated by the outer oracle, so the interaction between the two visit-frequency bounds requires an explicit derivation. The chain of equalities in Lemma 4.10 contains unstated assumptions about the distribution of inner-oracle queries. Since this premise is the entire source of the n^1.5 runtime rather than n^2, the authors should either prove the needed visit-frequency statement in the appendix or supply a precise argument that it applies unchanged in the nested setting.
minor comments (5)
  1. [§4.1, Algorithm 1, line 5] The text says 'for (u,v) ∈ G[V(M), V(M)]'; this should likely be G[V(M), V\V(M)].
  2. [§4.3, Lemma 4.7, Chernoff bound] The displayed Chernoff bound is missing a minus sign in the exponent: it should be 2 exp(−6 E[X] log n / (3 E[X])) rather than 2 exp(6 E[X] log n / (3 E[X])).
  3. [§4.3, Algorithms 4–5] The pseudocode is inconsistent about permutations: Algorithm 4 line 8 says 'fixed permutation π' while Algorithm 5 line 5 says 'random vertices and permutations'. The estimation target (a realized matching/b-matching for a fixed permutation versus an expectation over permutations) needs to be clarified, since the two readings lead to different concentration arguments.
  4. [§6, Multiplicative Approximation] The statement 'if any of |M|, |M'|, |B1|, or |B2| is not a constant fraction of the others, it can be omitted ... without affecting the approximation by more than a function of ε' is not formally justified. Omitting a term from the maximum in Lemma 4.6 can change the constant, so the authors should state the exact error and the regime in which each term can be neglected.
  5. [§4.1, parameter b] The paper says 'we pretend that kb ∈ Z' because k is an integer and b = 1 + √2 is irrational; since b-matching capacities must be integers, the algorithm and analysis should consistently use ⌈kb⌉ and account for the corresponding rounding error in the approximation ratio.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the 0.5109 approximation is a weighted-average combination of external (2−√2) matching lemmas, and the runtime lemma from [MRTV25] is a parameter-free external theorem.

full rationale

The derivation of the approximation factor is self-contained. Lemma 4.6 starts from Lemma 4.5, the known (2−√2−ε) guarantee for maximal matching plus b-matching from [BKSW23]/[ABR24], partitions a fixed maximum matching into five classes, and then lower-bounds the maximum of the two candidate quantities by a weighted average; the constant 0.5109 is the numerical optimum of that weighted average. Lemma 4.7 then only applies Chernoff bounds to the sampling estimates. No step defines the output in terms of the target quantity, and no parameter is fitted to the data being predicted. The runtime analysis relies on Propositions 4.8–4.9, quoted from [MRTV25], a paper sharing all three authors. That is a self-citation, but those propositions are stated as general, parameter-free facts about the random-greedy maximal-matching oracle (visit counts proportional to degree), with assumptions that do not mention the target approximation or the n^{1.5} runtime, and they are cited as a published external theorem rather than re-derived here. Under the reviewing rules, such a citation is real evidence and does not by itself make the derivation circular. A separate correctness concern, not a circularity, is that Lemma 4.7 uses n as the number of vertices in the sampled subgraphs/copy graphs; if the effective vertex sets have sizes |V(G'')| or |V(G'_i)|, the expectation identities E[X_i]=2E|M'|/n and E[Z_i]=2E|B2|/n need appropriate normalization. That would be a bias or estimation error, not a reduction of the output to the input. Therefore no circular step is established, and the score is 0.

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

No new entities are invented; all objects are standard (matchings, b-matchings, RGMM oracles, LCAs). The free parameters are hand-chosen constants that close the probability and approximation calculations, not empirical fits. The axioms mix standard mathematics with published domain results; the least locally checkable are Propositions 4.8 and 4.9 (MRTV25, same authors) and the ABR24 guarantee, which together carry the runtime and the general-graph extension.

free parameters (5)
  • b = 1+sqrt(2) = 1+sqrt(2)
    B-matching capacity ratio inherited from the KN21/BKSW23 two-pass streaming algorithm; chosen to optimize the (2-sqrt(2)) approximation constant in Lemma 4.1, not fitted to data.
  • k = integer larger than 1/(b*epsilon^3)
    Vertex capacity on the matched side of the b-matching (Algorithms 1, 4, 5); a hand-chosen large constant controlling the epsilon slack in Lemmas 4.1 and 4.5.
  • epsilon = small constant
    Slack in the guarantee 0.5109 = 4(5-2*sqrt(2))/17 - O(epsilon); its inverse determines k, coupling approximation ratio and capacity.
  • c = 2*sqrt(n)*log n
    Sparsification sample count in Algorithm 2; set so Lemma 4.3 yields induced degree at most sqrt(n) on unmatched vertices with high probability.
  • r = 6*log^3 n
    Number of oracle samples in Algorithms 4 and 5; set so the Chernoff bounds in Lemma 4.7 give failure probability O(1/n^2).
assumptions (6)
  • domain assumption Proposition 3.1 (Beh21): given adjacency-list access to a graph of average degree d, a random vertex's RGMM oracle query completes in O~(d) expected time.
    Used in Algorithms 4 and 5 for every oracle call; external published result, not re-proven.
  • domain assumption Propositions 4.8 and 4.9 (MRTV25): the RGMM oracle queries vertex v O~(deg(v)/|V|) times, and total expected oracle time for a random vertex is sum_v O~(T(v)*deg(v)/|V|).
    Crux of the n^1.5 runtime analysis in Lemmas 4.10 and 4.12; cited from the authors' own ITCS 2025 paper, not re-proven here.
  • domain assumption Lemma 4.5 second part (ABR24): for general graphs, a random greedy maximal b-matching B satisfies E[mu(M' union B)] >= (2-sqrt(2)-epsilon)*mu(G').
    Basis of the general-graph extension in Lemma 5.1; cited from ABR24, which includes one of the present authors.
  • standard math Integrality of the bipartite matching polytope (Birkhoff-von Neumann theorem).
    Used in Lemma 4.4 to certify that the displayed fractional matchings imply the lower bounds on mu(G).
  • standard math Greedy edge-coloring bound mu(G) >= |E(G)|/(2*Delta(G)) (Claim 6.1).
    Used in Section 6 to convert additive-error estimates into multiplicative ones via Claim 6.1; proven in-text.
  • domain assumption LRY17: (1-epsilon)-approximate local computation algorithm for maximum matching in O~(Delta(G)^{1/epsilon^2}) time.
    Used in Lemma 5.5 to estimate mu(M' union B1) and mu(M union B2) on subgraphs of constant maximum degree.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time." pith.science (2026). https://pith.science/paper/QECKB3LX

@misc{pith2026250601669,
  author       = {Pith},
  title        = {Pith review of: A 0.51-Approximation of Maximum Matching in Sublinear $n^1.5$ Time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QECKB3LX}},
  note         = {Machine review of arXiv:2506.01669}
}
abstract

We study the problem of estimating the size of a maximum matching in sublinear time. The problem has been studied extensively in the literature and various algorithms and lower bounds are known for it. Our result is a $0.5109$-approximation algorithm with a running time of $\tilde{O}(n\sqrt{n})$. All previous algorithms either provide only a marginal improvement (e.g., $2^{-280}$) over the $0.5$-approximation that arises from estimating a \emph{maximal} matching, or have a running time that is nearly $n^2$. Our approach is also arguably much simpler than other algorithms beating $0.5$-approximation.

Figures

Figures reproduced from arXiv: 2506.01669 by the authors.

Figure 1
Figure 1. Our algorithm explicitly constructs a matching [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Illustration for the proof of Lemma 4.6. The thick edges belong to a fixed maximum matching M∗ . Each of them is labeled with its partition (M∗ 2 , M ′∗ 2 , M ′′∗ 2 , M∗ 1 , or M ′∗ 1 ). The two subgraphs for which we invoke Lemma 4.5 are marked (case 1 – highlighted in light blue, case 2 – dashed line). • for general G′ , if B is a random greedy maximal b-matching, we still have E[µ(M′ ∪ B)] ≥ (2 − √ 2 − ε)µ(G′ ). … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Fully dynamic match- ing: (2 − √ 2)-approximation in polylog update time

    [ABR24] Amir Azarmehr, Soheil Behnezhad, and Mohammad Rogh ani. Fully dynamic match- ing: (2 − √ 2)-approximation in polylog update time. In David P. Woodru ff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algori thms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024 , pages 3040–3061. SIAM,

    work page 2024

  2. [6]

    Dynamic matching with better-than-2 approximation in polylogarit hmic update time

    [BKSW23] Sayan Bhattacharya, Peter Kiss, Thatchaphol Sara nurak, and David Wajc. Dynamic matching with better-than-2 approximation in polylogarit hmic update time. In Nikhil 21 Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2023, Florence, Italy, J anuary 22-25, 2023 , pages 100–128. SIAM,

    work page 2023

  3. [7]

    Local computation algorithms for maximum matching: New lower bounds

    [BRR23a] Soheil Behnezhad, Mohammad Roghani, and Aviad Rub instein. Local computation algorithms for maximum matching: New lower bounds. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 2322–2335. IEEE,

    work page 2023

  4. [8]

    Beating greedy matching in sublinear time

    [BRRS23] Soheil Behnezhad, Mohammad Roghani, Aviad Rubins tein, and Amin Saberi. Beating greedy matching in sublinear time. In Nikhil Bansal and Visw anath Nagarajan, edi- tors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algori thms, SODA 2023, Florence, Italy, January 22-25, 2023 , pages 3900–3945. SIAM,

    work page 2023

  5. [9]

    Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation

    [CKK20] Yu Chen, Sampath Kannan, and Sanjeev Khanna. Sublin ear algorithms and lower bounds for metric tsp cost estimation. arXiv preprint arXiv:2006.05490 ,

    work page Pith review arXiv 2006

  6. [11]

    [KN21] Christian Konrad and Kheeran K. Naidu. On two-pass st reaming algorithms for max- imum bipartite matching. In Mary Wootters and Laura Sanita, editors, Approxima- tion, Randomization, and Combinatorial Optimization. Algo rithms and Techniques, APPROX/RANDOM 2021, August 16-18, 2021, University of Wash ington, Seattle, Washington, USA (Virtual Confer...

    work page 2021

  7. [2007]

    Fast local computation algorithms

    [RTVX11] Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning X ie. Fast local computation algorithms. In Innovations in Computer Science - ICS 2011, Tsinghua University, Beijing, China, January 7-9,

    work page 2011

  8. [2011]

    An im proved constant-time ap- proximation algorithm for maximum matchings

    [YYI09] Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. An im proved constant-time ap- proximation algorithm for maximum matchings. In Michael Mi tzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Comput ing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009 , pages 225–234. ACM,

    work page 2009

Show all 15 references
  1. [2012]

    Time-optimal sublinear algorit hms for matching and vertex cover

    [Beh21] Soheil Behnezhad. Time-optimal sublinear algorit hms for matching and vertex cover. In 62nd IEEE Annual Symposium on Foundations of Computer Science , FOCS 2021, Denver, CO, USA, February 7-10, 2022 , pages 873–884. IEEE,

    2021

  2. [2017]

    Sublin- ear Metric Steiner Tree via Improved Bounds for Set Cover

    [MRTV25] Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnaw ski, and Ali Vakilian. Sublin- ear Metric Steiner Tree via Improved Bounds for Set Cover. In Raghu Meka, editor, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), volume 325 of Leibniz Internation...

    2025

  3. [2020]

    Local computation of maximal indepe ndent set

    [Gha22] Mohsen Ghaffari. Local computation of maximal indepe ndent set. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 202 2, Denver, CO, USA, October 31 - November 3, 2022 , pages 438–449,

    2022

  4. [2021]

    Dynamic algorithms for maximum m atching size

    [Beh23] Soheil Behnezhad. Dynamic algorithms for maximum m atching size. In Nikhil Bansal and Viswanath Nagarajan, editors, Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023 , pages 129–162. SIAM,

    2023

  5. [2023]

    Dynamic (1 + ε)- approximate matching size in truly sublinear update time

    [BKS23a] Sayan Bhattacharya, Peter Kiss, and Thatchaphol S aranurak. Dynamic (1 + ε)- approximate matching size in truly sublinear update time. I n 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1563–1588. IEEE,

    2023

  6. [2024]

    Space-Efficient Local Com- putation Algorithms

    [AR VX12] Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning X ie. Space-Efficient Local Com- putation Algorithms. In Proceedings of the Twenty-Third Annual ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2012, Kyoto, Japan, Jan uary 17-19, 2012 , pages 1132–1139,

    2012

  7. [2025]

    [NO08] Huy N Nguyen and Krzysztof Onak

    Schloss Dagstuhl – Leibniz-Zentr um f¨ ur Informatik. [NO08] Huy N Nguyen and Krzysztof Onak. Constant-time appro ximation algorithms via local improvements. In 2008 49th annual IEEE symposium on foundations of computer science, pages 327–336. IEEE,

    2008

Pith tools

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