betaFeedback

WorksComputer Science

Optimal LCA and Sublinear Estimation for Bipartite Matching in ΔO(1/ε)Δ^{O(1/\varepsilon)} Queries

Abstract

A local computation algorithm (LCA) for matching answers ``who is the mate of vv?'' by inspecting only a small part of the graph, with all answers consistent with one matching. For nn-vertex graphs of maximum degree Δ≥2Δ\ge2, Levi et al. [Algorithmica'17] give a (1−ε)(1-\varepsilon)-approximate matching LCA using (Δ/ε)O(1/ε2)polylog⁡(n)(Δ/\varepsilon)^{O(1/\varepsilon^2)} \operatorname{polylog}(n) queries per invocation, while Yoshida et al. [SIAM J. Comput.'12] estimate the maximum matching size within additive error εn\varepsilon n using ΔO(1/ε2)Δ^{O(1/\varepsilon^2)} queries. Behnezhad, Roghani, and Rubinstein [FOCS'23] proved a ΔΩ(1/ε)Δ^{Ω(1/\varepsilon)} lower bound for both tasks, even on bipartite graphs and even when the LCA's matching guarantee is relaxed to additive εn\varepsilon n error. This leaves a gap between linear and quadratic dependence on 1/ε1/\varepsilon in the exponent. We close this gap on bipartite graphs. We give an LCA that answers each mate query with ΔO(1/ε)Δ^{O(1/\varepsilon)} queries for a (1−ε)(1-\varepsilon)-approximate matching, and an estimator for the maximum matching size within εn\varepsilon n using ΔO(1/ε)Δ^{O(1/\varepsilon)} queries. On general graphs, the same algorithm gives a half-integral fractional matching and estimates the maximum fractional matching size. Our approach runs O(ε−1log⁡Δ)O(\varepsilon^{-1}\logΔ) rounds of a deterministic local optimization method in which vertices propose to neighbors and update prices according to incoming loads. We design its updates to admit exact recursive sampling with constant expected branching, obtaining the improved randomized bound without exploring full dependency neighborhoods. To our knowledge, this is the first LCA construction based on exact recursive sampling of the iterates of a deterministic continuous optimization method. We expect this approach to have applications beyond matching.

Introduction

A matching in a graph G=(V,E)G=(V,E) is a set of edges no two of which share an endpoint, and ν(G)\nu(G) denotes its maximum size. Maximum matching is a central problem in combinatorial optimization, with applications ranging from assignment problems to sparse matrix computation [21, 37]. Its algorithmic study spans more than six decades, with Edmonds’s polynomial-time algorithm for general graphs as a foundational milestone [23].

We study graphs with nn vertices and maximum degree at most Δ\Delta, where nn may be much larger than Δ\Delta. For such graphs, even reading the entire input may be too costly. Our goal is to answer local queries about an almost maximum matching, or to estimate its size, while inspecting only a small part of the graph. The first task is the subject of local computation algorithms (LCAs), introduced by Rubinfeld, Tamir, Vardi, and Xie [52] and Alon, Rubinfeld, Vardi, and Xie [3]. The second is sublinear-time estimation, studied since the work of Parnas and Ron [50] and Nguyen and Onak [46]. Matching has received extensive attention in both settings [6, 8, 9, 11, 12, 13, 38, 40, 46, 50, 54, 56], and we review the known bounds below. We also consider the distributed LOCAL and CONGEST models, where vertices communicate with their neighbors in synchronous rounds and complexity is measured by the number of communication rounds.

We study both matchings and their classical fractional relaxation. A fractional matching assigns nonnegative weights fef_e to edges such that ∑e∋vfe≤1\sum_{e\ni v} f_e \le1 at every vertex. Its value is ∑efe\sum_e f_e, and νf(G)\nu_f(G) denotes the maximum possible value. It is half-integral if every weight belongs to {0,12,1}\{0,\frac{1}{2},1\}. On bipartite graphs, νf(G)=ν(G)\nu_f(G)=\nu(G).

The local computation model. The vertices are labeled by [n][n], and nn and a degree bound Δ≥2\Delta\ge2 are known. A degree query at vv returns deg⁡(v)\deg(v). A neighbor query at (v,i)(v,i) returns the ii-th neighbor of vv, with neighbors listed in a fixed but arbitrary order. An LCA [3, 52] provides query access to a solution without constructing the entire output. For matching, a mate query at a vertex returns its partner or reports that it is unmatched. For fractional matching, an edge query returns the weight assigned to an edge.

Our LCAs do not use preprocessing and do not retain state between invocations. A randomized LCA has access to a random tape shared by all invocations, allowing repeated evaluations to reproduce the same random choices. All answers must be globally consistent: they must agree with one feasible solution, in every query order, including adaptively chosen queries.

We measure an LCA’s query complexity by the worst-case number of graph queries used to answer one solution query. A size estimator returns a numerical estimate of ν(G)\nu(G) or νf(G)\nu_f(G), and its query complexity is the total number of graph queries it makes.

Computation is free when measuring graph-query complexity. We separately bound computational work in the finite-arithmetic model of § 2.1.

The distributed LOCAL and CONGEST models. In both models [51], each vertex is a processor that communicates with its neighbors in synchronous rounds. The LOCAL model measures information radius and allows messages of unrestricted size; the CONGEST additionally restricts communication bandwidth to O(log⁡n)O(\log n) bits per edge in each direction per round. After rr rounds, a vertex’s output can depend only on information within its radius-rr neighborhood. Thus distributed round complexity measures how far information must travel, whereas LCA query complexity measures how much of the input is inspected. An LCA can simulate an rr-round distributed algorithm by exploring the radius-rr neighborhood of the queried vertex, using (2Δ)O(r)(2\Delta)^{O(r)} graph queries [50]. In addition to query and round complexity, we separately bound the computational work per local query and the message size per edge per round in our distributed implementation.

Approximation guarantees. The optimal matching can depend on information arbitrarily far from the queried vertex, even on paths. We therefore focus on approximation when seeking bounds independent of nn.

For the matching itself, we seek a multiplicative guarantee: a (1−ε)(1-\varepsilon)-approximate matching has size at least (1−ε)ν(G)(1-\varepsilon)\nu(G), and analogously at least (1−ε)νf(G)(1-\varepsilon)\nu_f(G) for fractional matching. To describe earlier results, we also use additive approximation notation: a matching MM is (1,εn)(1,\varepsilon n)-approximate if ∣M∣≥ν(G)−εn|M|\ge\nu(G)-\varepsilon n, and more generally (α,εn)(\alpha,\varepsilon n)-approximate if ∣M∣≥αν(G)−εn|M|\ge\alpha\nu(G)-\varepsilon n. Note that since ν(G),νf(G)≤n/2\nu(G),\nu_f(G)\le n/2, a multiplicative (1−ε)(1-\varepsilon)-approximate guarantee implies an additive (1,εn/2)(1,\varepsilon n/2) guarantee and hence is stronger.

For size estimation, a multiplicative guarantee with a fixed ε\varepsilon requires distinguishing the empty graph from a graph with a single edge, which requires Ω(n)\Omega(n) queries. For query bounds independent of nn, we therefore seek additive accuracy.

Known algorithms. Sublinear algorithms for estimating matching size in bounded-degree graphs go back to Parnas and Ron [50], who showed how to simulate a distributed algorithm at a single vertex by exploring its neighborhood. For matching, this gives a (1/2,εn)(1/2,\varepsilon n)-estimate with ΔO(log⁡(Δ/ε))\Delta^{O(\log(\Delta/\varepsilon))} queries. Nguyen and Onak [46] introduced recursive local simulation of randomized greedy algorithms, and Yoshida, Yamamoto, and Ito [56] improved this approach to obtain a (1,εn)(1,\varepsilon n)-estimate with ΔO(1/ε2)\Delta^{O(1/\varepsilon^2)} queries. Applied to the standard bipartite double cover [1, Lemma 7], this estimator also estimates νf(G)\nu_f(G) within ±εn\pm\varepsilon n with the same query bound.

For LCAs, Mansour and Vardi [40] gave an approximation scheme with polylogarithmic query complexity for constant Δ\Delta and ε\varepsilon. Levi, Rubinfeld, and Yodpinyanee [38] adapted the method of [56] to obtain a multiplicative (1−ε)(1-\varepsilon)-approximation using (Δ/ε)O(1/ε2)polylog⁡(n)(\Delta/\varepsilon)^{O(1/\varepsilon^2)}\operatorname{polylog}(n) queries per invocation. This remains the best known bound of this form for general-graph matching LCAs. These approximation schemes use the augmenting-path framework of Hopcroft and Karp: in each of Θ(1/ε)\Theta(1/\varepsilon) phases, they augment along a maximal collection of vertex-disjoint paths of a prescribed length. Finding this collection amounts to computing a maximal independent set in the conflict graph of candidate paths. In the simulations of [38, 56], each phase recursively invokes earlier phases, and the costs compound to give the quadratic dependence on 1/ε1/\varepsilon in the degree exponent.

A parallel line of work seeks sublinear algorithms without assuming a small maximum degree. For fixed ε\varepsilon, Behnezhad [7] gave a (1/2,εn)(1/2,\varepsilon n)-estimate of matching size in O~(dˉ+1)\widetilde{O}(\bar d+1) time with adjacency-list queries, where dˉ\bar d is the average degree, and in O~(n)\widetilde{O}(n) time with adjacency-matrix queries. A multiplicative (1/2−ε)(1/2-\varepsilon)-estimate is also possible in O~(n)\widetilde{O}(n) time with adjacency-list queries. All three bounds are optimal up to polylogarithmic factors for fixed ε\varepsilon. Subsequent work improved the approximation ratio in n2−Ω(1)n^{2-\Omega(1)} time [9, 10, 12]. Finally, Bhattacharya, Kiss, and Saranurak [13] obtained a (1,εn)(1,\varepsilon n)-estimate in n2−Ωε(1)n^{2-\Omega_\varepsilon(1)} time using adjacency-matrix queries.

Known lower bounds. For over fifteen years, the only degree-dependent lower bound for matching LCAs was the Ω(Δ)\Omega(\Delta) bound of Parnas and Ron [50], based on hiding useful matching edges among many irrelevant neighbors. This hiding argument alone cannot give a superlinear dependence on Δ\Delta. Behnezhad, Roghani, and Rubinstein [9] first broke this barrier, showing that (2/3+Ω(1),εn)(2/3+\Omega(1),\varepsilon n)-estimation requires n1.2−o(1)n^{1.2-o(1)} queries for sufficiently small constant ε\varepsilon. Their construction, with Δ=Θ(n)\Delta=\Theta(n), also yields a Δ1.2−o(1)\Delta^{1.2-o(1)} lower bound per LCA query.

Open Problem 39 of sublinear.info [48] asked whether poly⁡(Δ/ε)\operatorname{poly}(\Delta/\varepsilon) queries suffice to estimate matching size within additive error εn\varepsilon n. Behnezhad, Roghani, and Rubinstein [8] answered this negatively, proving a ΔΩ(1/ε)\Delta^{\Omega(1/\varepsilon)} lower bound for both estimation and local computation, even on bipartite graphs, whenever ε≤0.01\varepsilon\le0.01 and log⁡4n≤Δ≤nε\log^4 n\le\Delta\le n^\varepsilon.

For dense graphs, Behnezhad, Roghani, and Rubinstein [11] subsequently proved that, for every fixed δ>0\delta>0, there is a constant ε=ε(δ)>0\varepsilon=\varepsilon(\delta)>0 such that additive εn\varepsilon n estimation requires Ω(n2−δ)\Omega(n^{2-\delta}) adjacency-list queries. This complements the n2−Ωε(1)n^{2-\Omega_\varepsilon(1)} upper bound of [13]. In the bounded-degree regime, the lower bound of [8] left a gap between linear and quadratic dependence on 1/ε1/\varepsilon in the degree exponent.

Our results

Our randomized algorithms close this gap for bipartite matching and its size estimation. On general graphs, they give the same bounds for half-integral fractional matching and estimation of νf(G)\nu_f(G).

Theorem 1.1 (Randomized local computation and estimation, informal). Let GG have n≥2n\ge2 vertices and maximum degree at most Δ≥2\Delta\ge2, and let 0<ε<1/20<\varepsilon<1/2.

(a) There is a single randomized LCA with the following guarantees. On bipartite graphs, it supports mate queries to a matching MM satisfying

P{∣M∣≥(1−ε)ν(G)}≥0.9.\mathbb{P}\left\{|M| \ge(1-\varepsilon)\nu(G)\right\} \ge0.9.

On arbitrary graphs, the same LCA supports edge queries to a half-integral fractional matching ff of value at least (1−ε)νf(G)(1-\varepsilon)\nu_f(G) with probability at least 0.9. Each mate or edge query uses (2Δ)O(1/ε)(2\Delta)^{O(1/\varepsilon)} graph queries. No bipartition or prior knowledge of whether GG is bipartite is required.

(b) For every 0<ζ<1/20 < \zeta< 1/2, a randomized size estimator returns ν^\hat{\nu} satisfying ∣ν^−νf(G)∣≤εn|\hat{\nu}-\nu_f(G)| \le\varepsilon n with probability at least 1−ζ1-\zeta, using

(2Δ)O(1/ε)log⁡(2/ζ)(2\Delta)^{O(1/\varepsilon)}\log(2/\zeta)

graph queries. On bipartite graphs, this estimates ν(G)\nu(G).

The same bounds hold separately for computational work in the model of § 2.1. All query and work bounds are worst case. The LCA’s feasibility and consistency hold for every realization of the shared randomness and in every query order, including adaptively chosen queries. Only the approximation guarantees are probabilistic.

For constant success probability, our upper bounds match the lower bound of Behnezhad et al. [8], in its applicable regime, up to a constant in the exponent. Thus, in that regime, the query complexity of bipartite matching and its size estimation is ΔΘ(1/ε)\Delta^{\Theta(1/\varepsilon)}.

For general graphs, ν(G)≤νf(G)≤32ν(G)\nu(G) \le\nu_f(G) \le\frac{3}{2}\nu(G). Consequently, scaling the estimate in part (b) by 2/32/3 gives a (2/3,εn)(2/3,\varepsilon n)-estimate of ν(G)\nu(G): with probability at least 1−ζ1-\zeta,

23ν(G)−εn≤23ν^≤ν(G)+εn.\frac{2}{3}\nu(G)-\varepsilon n \le\frac{2}{3}\hat{\nu} \le\nu(G)+\varepsilon n.

Whether integral (1,εn)(1,\varepsilon n)-approximate matchings in general graphs admit an LCA using (2Δ)O(1/ε)(2\Delta)^{O(1/\varepsilon)} graph queries per mate query remains the main open question left by our work. The lower bound of Behnezhad et al. [8] applies, while the general-graph algorithms of Levi et al. [38], Yoshida et al. [56] have quadratic dependence on 1/ε1/\varepsilon in the degree exponent.

Our construction also gives a deterministic LCA for fractional matching, with a larger query bound.

Theorem 1.2 (Deterministic fractional oracle, informal). Let GG, Δ\Delta, ε\varepsilon be as in Theorem 1.1. There is a deterministic LCA whose answers are consistent with one fractional matching ff satisfying

∑efe≥(1−ε)νf(G).\sum_e f_e \ge(1-\varepsilon)\nu_f(G).

Each edge query uses at most

(2Δ)O(ε−1log⁡(2Δ))(2\Delta)^{O(\varepsilon^{-1}\log(2\Delta))}

graph queries, all within distance O(ε−1log⁡(2Δ))O(\varepsilon^{-1}\log(2\Delta)) of the queried edge.

For every 0<ζ<1/20 < \zeta< 1/2, uniform random vertex sampling combined with this oracle gives an estimate of νf(G)\nu_f(G) within ±εn\pm\varepsilon n, with probability at least 1−ζ1-\zeta, using at most

(2Δ)O(ε−1log⁡(2Δ))log⁡(2/ζ)(2\Delta)^{O(\varepsilon^{-1}\log(2\Delta))}\log(2/\zeta)

graph queries in total. Only the vertex sampling in this estimator is randomized. The same bounds hold separately for computational work in the model of § 2.1. All query and work bounds are worst case.

The locality and structure of the deterministic updates give the following distributed consequence.

Corollary 1.3 (Deterministic distributed algorithm, informal). *Under the same assumptions, a deterministic distributed algorithm computes a fractional matching of value at least (1−ε)νf(G)(1-\varepsilon)\nu_f(G) in

O(log⁡(2Δ)ε)O\left(\frac{\log(2\Delta)}{\varepsilon}\right)

rounds. Each edge carries O(log⁡(2Δ/ε))O(\log(2\Delta/\varepsilon)) bits in each direction per round. The total computational work at a vertex vv is

(deg⁡(v)+1)poly⁡(log⁡(2Δ)ε).(\deg(v)+1)\operatorname{poly}\left(\frac{\log(2\Delta)}{\varepsilon}\right).

All bounds are worst case. This gives the stated round bound in LOCAL for every 0<ε<1/20<\varepsilon<1/2, and in CONGEST when ε≥n−O(1)\varepsilon\ge n^{-O(1)}.*

Fractional matching is a special case of fractional packing, which has been studied in distributed computing [36]. The deterministic algorithm of Li et al. [39] gives a (1−ε)(1-\varepsilon)-approximate fractional matching in O(ε−2log⁡(2Δ))O(\varepsilon^{-2}\log(2\Delta)) rounds. Simulating it by neighborhood exploration [50] gives a deterministic LCA using (2Δ)O(ε−2log⁡(2Δ))(2\Delta)^{O(\varepsilon^{-2}\log(2\Delta))} graph queries per edge query. Compared with these bounds, our construction improves the dependence on 1/ε1/\varepsilon from quadratic to linear, both in the LOCAL round complexity and in the exponent of the LCA query complexity.

Technical overview and roadmap

We first formulate fractional matching as a saddle-point problem and derive a deterministic optimization method with local updates (§ 3–§ 5). After T=O(ε−1log⁡(2Δ))T=O(\varepsilon^{-1}\log(2\Delta)) rounds, the method defines a nearly maximum fractional matching whose edge weights depend only on radius-O(T)O(T) neighborhoods. Evaluating the updates in these neighborhoods gives a deterministic LCA using (2Δ)O(T)=(2Δ)O(ε−1log⁡(2Δ))(2\Delta)^{O(T)}=(2\Delta)^{O(\varepsilon^{-1}\log(2\Delta))} queries and operations per edge query, and a deterministic distributed algorithm using O(T)O(T) communication rounds.

The key to improving the LCA bound is to sample from the distributions used by the optimizer without computing them explicitly. In § 6, we construct a recursive sampler that follows the optimization round by round. Producing a sample for a new round uses an expected constant number of calls to the preceding round’s sampling procedures. This replaces the recursive exploration of all neighbors by constant expected branching, giving 2O(T)=(2Δ)O(1/ε)2^{O(T)}=(2\Delta)^{O(1/\varepsilon)} expected queries and operations per sample.

We then use these samples to construct a fractional matching that can be queried consistently with (2Δ)O(1/ε)(2\Delta)^{O(1/\varepsilon)} worst-case work per query (§ 7). Rounding gives an integral matching on bipartite graphs and a half-integral fractional matching on general graphs (§ 9). The same sampler also gives our size estimator, without the rounding step (§ 8). The finite-precision implementation and its message-size bound are established in Section B. We next describe each ingredient and the challenges it addresses.

A saddle-point formulation of fractional matching

In § 3, we express fractional matching as a min–max problem over distributions and prices at the vertices. Every vertex acts both as a proposer, sending mass to its neighbors, and as a receiver, accepting mass from its neighbors. Its proposal distribution describes the mass it sends, while its price is associated with its role as a receiver.

Each vertex uu distributes one unit of mass among its neighbors and a private dummy, which represents unused mass. We call this probability vector quq_u its proposal distribution. The quantities quvq_{uv} and qvuq_{vu} represent mass sent in opposite directions and need not agree. Each vertex sends at most one unit to its neighbors, but may receive more than one unit. Write

References

  1. [1]Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. Distributed approximate maximum matching in the CONGEST model. In 32nd International Symposium on Distributed Computing (DISC 2018), volume 121 of LIPIcs, pages 6:1–6:17, 2018. URL https://doi.org/10.4230/LIPIcs.DISC.2018.6.
  2. [2]Kook Jin Ahn and Sudipto Guha. Access to data and number of iterations: Dual primal algorithms for maximum matching under resource constraints. ACM Transactions on Parallel Computing, 4(4), 2018. URL https://doi.org/10.1145/3154855. Conference version in SPAA 2015; arXiv:1307.4359.
  3. [3]Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1132–1139, 2012. URL https://doi.org/10.1137/1.9781611973099.89.
  4. [4]Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Semi-streaming bipartite matching in fewer passes and optimal space. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 627–669, 2022. URL https://doi.org/10.1137/1.9781611977073.29. arXiv:2011.03495.
  5. [5]Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, and Madhu Sudan. Lower bounds for non-adaptive local computation algorithms. In Proceedings of the 66th IEEE Symposium on Foundations of Computer Science (FOCS), pages 1488–1511, 2025. URL https://arxiv.org/abs/2505.00915.
  6. [6]Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Tight pair query lower bounds for matching and earth mover’s distance. In 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025, pages 2666–2693. IEEE, 2025. doi: 10.1109/FOCS63196.2025.00138. URL https://doi.org/10.1109/FOCS63196.2025.00138.
  7. [7]Soheil Behnezhad. Time-optimal sublinear algorithms for matching and vertex cover. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 873–884. IEEE, 2022.arxiv.org/abs/2106.02942
  8. [8]Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Local computation algorithms for maximum matching: New lower bounds. In Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS), pages 2322–2335, 2023. URL https://doi.org/10.1109/FOCS57990.2023.00143. arXiv:2311.09359.
  9. [9]Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Sublinear time algorithms and complexity of approximate maximum matching. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, page 267–280, New York, NY, USA, 2023. Association for Computing Machinery.arxiv.org/abs/2211.15843
  10. [10]Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, and Amin Saberi. Beating greedy matching in sublinear time. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3900–3945. SIAM, 2023.arxiv.org/abs/2206.13057
  11. [11]Soheil Behnezhad, Mohammad Roghani, and Aviad Rubinstein. Approximating maximum matching requires almost quadratic time. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 444–454, 2024.arxiv.org/abs/2406.08595
  12. [12]Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Sublinear algorithms for (1.5 + ϵ)-approximate matching. In Proceedings of the 55th ACM Symposium on Theory of Computing, STOC 2023, Orlando, Florida, 2023.
  13. [13]Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Dynamic (1 + ϵ)-approximate matching size in truly sublinear update time. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, 2023.arxiv.org/abs/2302.05030
  14. [14]Digvijay Boob, Saurabh Sawlani, and Di Wang. Faster width-dependent algorithm for mixed packing and covering LPs. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 15279–15288, 2019. URL https://proceedings.neurips.cc/paper/2019/hash/791d3a0048b9c200dceca07f99ddd178-Abstract.html.arxiv.org/abs/1909.12387
  15. [15]Kenneth L. Clarkson, Elad Hazan, and David P. Woodruff. Sublinear optimization for machine learning. Journal of the ACM, 59(5):Article 23, 2012. URL https://doi.org/10.1145/2371656.2371658.
  16. [16]Edith Cohen. Size-estimation framework with applications to transitive closure and reachability. Journal of Computer and System Sciences, 55(3):441–453, 1997. doi: 10.1006/jcss.1997.1534. URL https://doi.org/10.1006/jcss.1997.1534.
  17. [17]Edith Cohen and David D. Lewis. Approximating matrix multiplication for pattern recognition tasks. Journal of Algorithms, 30(2):211–252, 1999. doi: 10.1006/jagm.1998.0989. URL https://doi.org/10.1006/jagm.1998.0989.
  18. [18]Michael B. Cohen, Aaron Sidford, and Kevin Tian. Relative Lipschitzness in extragradient methods and a direct recipe for acceleration. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), volume 185 of LIPIcs, pages 62:1–62:18, 2021. URL https://doi.org/10.4230/LIPIcs.ITCS.2021.62.
  19. [19]Sameep Dahal and Jukka Suomela. Distributed half-integral matching and beyond. Theoretical Computer Science, 982:114278, 2024. URL https://arxiv.org/abs/2303.05250.
  20. [20]Petros Drineas, Ravi Kannan, and Michael W. Mahoney. Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication. SIAM Journal on Computing, 36(1):132–157, 2006. doi: 10.1137/S0097539704442684. URL https://doi.org/10.1137/S0097539704442684.
  21. [21]Iain S. Duff, K amer Kaya, and Bora Uçar. Design, implementation, and analysis of maximum transversal algorithms. ACM Transactions on Mathematical Software, 38(2):13:1–13:31, 2011. doi: 10.1145/2049673.2049677. URL https://doi.org/10.1145/2049673.2049677.
  22. [22]Shaddin Dughmi, Jason D. Hartline, Robert D. Kleinberg, and Rad Niazadeh. Bernoulli factories and black-box reductions in mechanism design. Journal of the ACM, 68(2):10:1–10:30, 2021. doi: 10.1145/3440988. URL https://doi.org/10.1145/3440988.
  23. [23]Jack Edmonds. Paths, trees, and flowers. Canadian Journal of Mathematics, 17:449–467, 1965. doi: 10.4153/CJM-1965-045-4. URL https://doi.org/10.4153/CJM-1965-045-4.
  24. [24]Jenő Egerváry. Mátrixok kombinatorius tulajdonságairól. Matematikai és Fizikai Lapok, 38:16–28, 1931. URL https://real-j.mtak.hu/7307/.
  25. [25]Manuela Fischer. Improved deterministic distributed matching via rounding. In 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of LIPIcs, pages 17:1–17:15, 2017. URL https://doi.org/10.4230/LIPIcs.DISC.2017.17.
  26. [26]Mohsen Ghaffari. Local computation of maximal independent set. In Proceedings of the 63rd IEEE Symposium on Foundations of Computer Science (FOCS), pages 438–449, 2022. URL https://doi.org/10.1109/FOCS54457.2022.00049. arXiv:2210.01104.
  27. [27]Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. URL https://doi.org/10.1080/01621459.1963.10500830.
  28. [28]Olga Holtz, Fedor Nazarov, and Yuval Peres. New coins from old, smoothly. Constructive Approximation, 33:331–363, 2011. URL https://doi.org/10.1007/s00365-010-9108-5.
  29. [29]Mark Huber. Nearly optimal Bernoulli factories for linear functions. Combinatorics, Probability and Computing, 25(4):577–591, 2016. doi: 10.1017/S0963548315000371. URL https://arxiv.org/abs/1308.1562.
  30. [30]Arun Jambulapati and Kevin Tian. Revisiting area convexity: Faster box-simplex games and spectrahedral generalizations. In Advances in Neural Information Processing Systems 36 (NeurIPS), pages 57583–57596, 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/hash/b3bec3f5ad96055b7f60c93edc3606c8-Abstract-Conference.html. arXiv:2303.15627.arxiv.org/abs/2303.15627
  31. [31]Arun Jambulapati, Aaron Sidford, and Kevin Tian. A direct Õ(1/ε) iteration parallel algorithm for optimal transport. In Advances in Neural Information Processing Systems 32 (NeurIPS), pages 11359–11370, 2019. URL https://proceedings.neurips.cc/paper/2019/hash/024d2d699e6c1a82c9ba986386f4d824-Abstract.html.
  32. [32]Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian. Regularized box-simplex games and dynamic decremental bipartite matching. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of LIPIcs, pages 77:1–77:20, 2022. URL https://doi.org/10.4230/LIPIcs.ICALP.2022.77.
  33. [33]Michael Kapralov, Slobodan Mitrović, Ashkan Norouzi-Fard, and Jakab Tardos. Space efficient approximation to maximum matching size from uniform edge samples. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1753–1772, 2020. URL https://doi.org/10.1137/1.9781611975994.107.
  34. [34]Michael S. Keane and George L. O’Brien. A Bernoulli factory. ACM Transactions on Modeling and Computer Simulation, 4(2):213–219, 1994. URL https://doi.org/10.1145/175007.175019.
  35. [35]Dénes König. Graphok és mátrixok. Matematikai és Fizikai Lapok, 38:116–119, 1931. URL https://real-j.mtak.hu/7307/.
  36. [36]Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. Journal of the ACM, 63(2):Article 17, 2016. URL https://doi.org/10.1145/2742012.
  37. [37]Harold W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1–2):83–97, 1955. doi: 10.1002/nav.3800020109. URL https://doi.org/10.1002/nav.3800020109.
  38. [38]Reut Levi, Ronitt Rubinfeld, and Anak Yodpinyanee. Local computation algorithms for graphs of non-constant degrees. Algorithmica, 77(4):971–994, 2017. URL https://doi.org/10.1007/s00453-016-0126-y.
  39. [39]Qian Li, Minghui Ouyang, and Yuyi Wang. A simple distributed algorithm for sparse fractional covering and packing problems. In 35th International Symposium on Algorithms and Computation (ISAAC 2024), LIPIcs, pages 45:1–45:8, 2024. URL https://arxiv.org/abs/2409.16168.
  40. [40]Yishay Mansour and Shai Vardi. A local computation approximation scheme to maximum matching. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2013), volume 8096 of Lecture Notes in Computer Science, pages 260–273. Springer, 2013. URL https://doi.org/10.1007/978-3-642-40328-6_19.
  41. [41]Colin McDiarmid. On the method of bounded differences. In Surveys in Combinatorics, 1989, volume 141 of London Mathematical Society Lecture Note Series, pages 148–188. Cambridge University Press, 1989. URL https://doi.org/10.1017/CBO9781107359949.008.
  42. [42]Andrew McGregor. Finding graph matchings in data streams. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 170–181. Springer, 2005.
  43. [43]Luis Mendo. An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series. Stochastic Processes and their Applications, 129(11):4366–4384, 2019. doi: 10.1016/j.spa.2018.11.017. URL https://arxiv.org/abs/1612.08923.
  44. [44]Șerban Nacu and Yuval Peres. Fast simulation of new coins from old. The Annals of Applied Probability, 15(1A):93–115, 2005. URL https://doi.org/10.1214/105051604000000549.
  45. [45]Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229–251, 2004. URL https://doi.org/10.1137/S1052623403425629.
  46. [46]Huy N. Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS), pages 327–336, 2008. URL https://doi.org/10.1109/FOCS.2008.81.
  47. [47]Rad Niazadeh, Renato Paes Leme, and Jon Schneider. Combinatorial Bernoulli factories: Matchings, flows, and other polytopes. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 833–846, 2021. doi: 10.1145/3406325.3451072. URL https://doi.org/10.1145/3406325.3451072.
  48. [48]Krzysztof Onak. Open problem 39: Approximating maximum matching size. Sublinear.info; suggested at the Bertinoro Workshop on Sublinear Algorithms, 2011. URL https://sublinear.info/index.php?title=Open_Problems:39.
  49. [49]OpenAI. Almost-linear-time maximum-cardinality matching in general graphs, 2026. URL https://github.com/openai/math/blob/main/preprints/Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs-September-24-2026/main.pdf. OpenAI Math Release preprint, September 24.
  50. [50]Michal Parnas and Dana Ron. Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theoretical Computer Science, 381(1–3):183–196, 2007. URL https://doi.org/10.1016/j.tcs.2007.04.040.
  51. [51]David Peleg. Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, 2000. doi: 10.1137/1.9780898719772. URL https://doi.org/10.1137/1.9780898719772.
  52. [52]Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. In Proceedings of Innovations in Computer Science (ICS), pages 223–238. Tsinghua University Press, 2011. URL https://arxiv.org/abs/1104.1377.
  53. [53]Sebastian M. Schmon, Arnaud Doucet, and George Deligiannidis. Bernoulli race particle filters. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 2350–2358. PMLR, 2019. URL https://proceedings.mlr.press/v89/schmon19a.html.arxiv.org/abs/1903.00939
  54. [54]Vihan Shah. Sublinear-time lower bounds for approximating matching size using non-adaptive queries. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5027–5065. SIAM, 2026.DOI
  55. [55]Jonah Sherman. Area-convexity, ℓ∞ regularization, and undirected multicommodity flow. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages 452–460, 2017. URL https://doi.org/10.1145/3055399.3055501.
  56. [56]Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. Improved constant-time approximation algorithms for maximum matchings and other optimization problems. SIAM Journal on Computing, 41(4):1074–1093, 2012. URL https://doi.org/10.1137/110828691.

Paper details

vlnc:W_48zqqrdm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 4

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Astra (OpenAI), Claude (Anthropic), Gemini (multiple versions)

View statement
Looking for related papers…
Contents