betaFeedback

WorksComputer Science

Randomized Greedy MIS Is Fast at Every Node of a Tree

Abstract

The Randomized Greedy MIS (RGMIS) algorithm computes a maximal independent set (MIS) by processing the vertices in a uniformly random order and greedily adding each vertex to the independent set whenever possible. Despite its simplicity, this algorithm has proved effective in a range of parallel, distributed, and dynamic settings. For sufficiently small maximum degree, Nguyen and Onak (FOCS~'08) and Yoshida, Yamamoto, and Ito (STOC~'09) showed that a recursive simulation of RGMIS can be used to estimate the sizes of matching and vertex cover in sublinear time. The key subroutine in their approach is the following local query procedure: given a vertex vv, to determine whether vv belongs to the MIS, recursively evaluate the neighbors of vv that precede vv in the random order. If any such neighbor is found to belong to the MIS, the procedure immediately concludes that vv is not in the MIS; otherwise, it concludes that vv is in the MIS. For graphs of maximum degree ΔΔ, Nguyen and Onak showed that, in expectation over the random ordering, this procedure makes O(exp⁡(Δ))O(\exp(Δ)) recursive calls from a worst-case starting vertex. No better upper bound is known even for trees. We prove that on trees, from any starting vertex, this recursive RGMIS procedure makes poly(Δ)\mathrm{poly}(Δ) recursive calls in expectation.

Introduction

In a graph G=(V,E)G = (V, E), a set of vertices I⊆VI \subseteq V is independent if no two vertices in II are adjacent. A maximum independent set is an independent set of largest possible cardinality, while a maximal independent set is one that is inclusion-wise maximal. Finding a maximum independent set is computationally intractable in general [16], whereas a maximal independent set can be computed by a simple greedy algorithm in linear time. Throughout the paper, MIS stands for maximal independent set.

In 2008, Nguyen and Onak [23] initiated the study of determining, in sublinear time, whether a queried vertex u∈Vu \in V belongs to the MIS produced by the following random-order greedy process:1

  • For each u∈Vu \in V, assign rank r(u)r(u) chosen uniformly at random from [0,1][0, 1];

  • Greedily augment independent set II by iterating over VV from smallest to largest vertex with respect to their ranks.

We refer to this random-order greedy process as randomized greedy MIS (RGMIS). Nguyen and Onak then studied the following recursive simulation of RGMIS: to determine whether uu belongs to the MIS, one recursively evaluates every neighbor ww of uu with r(w)<r(u)r(w) < r(u). Then uu belongs to the MIS if and only if none of these neighbors do. Letting Δ\Delta denote the maximum degree of the input graph, the authors proved that the expected number of recursive calls made by this procedure is eO(Δ)e^{O(\Delta)}. In fact, this upper bound is tight even on trees.2 The authors also observed that a natural search-pruning heuristic may asymptotically improve this recursive process: if, for some neighbor ww of uu with r(w)<r(u)r(w) < r(u), the recursive call returns that ww belongs to the MIS, then it immediately follows that uu does not belong to the MIS, and hence no other neighbor of uu needs to be explored. We refer to RGMIS implemented with this heuristic as pruned RGMIS (see Algorithm 1). The authors conjectured that pruned RGMIS is significantly faster than the unpruned one, and left that direction for future research.

A year later, Yoshida, Yamamoto, and Ito [YYI09] proved that this pruning step drastically improves the average-case complexity of RGMIS. More precisely, they showed that when the query vertex is chosen uniformly at random, pruned RGMIS makes only ∣E(G)∣/∣V(G)∣|E(G)|/|V(G)| recursive calls in expectation. In particular, on trees, the expected number of recursive calls made by pruned RGMIS from a uniformly random query vertex is less than 1. Very recently, Dalirrooyfard, Makarychev, and Mitrović [10] gave a considerably simpler analysis of the result of [YYI09].

However, works [YYI09, DMM26] leave open whether pruned RGMIS may still require exp⁡(Θ(Δ))\exp(\Theta(\Delta)) recursive calls from a worst-case vertex. This raises the question of whether, at least on trees, the average-case and worst-case complexities of pruned RGMIS coincide. Karger, Mitrović, Norouzi-Fard, and Tardos [18] ruled this out by showing that the two can differ substantially. More formally, they show that for every constant ε>0\varepsilon> 0, there exist a tree and a vertex uu in that tree such that pruned RGMIS invoked on uu makes Ωε(Δ2−ε)\Omega_{\varepsilon}(\Delta^{2-\varepsilon}) recursive calls in expectation.3 Thus, even on trees, pruned RGMIS exhibits a substantial gap between average-case and worst-case behavior: the average complexity is constant, while the worst-case complexity is at least polynomial in Δ\Delta. This already shows that the tree case captures a nontrivial aspect of the problem.

Although Ghaffari [15] gives a local computation algorithm for MIS with query complexity poly⁡(Δ)\operatorname{poly}(\Delta) in expectation4, this does not address the complexity of the specific recursive process induced by RGMIS. Studying this process is natural in its own right: RGMIS is an especially simple and canonical randomized greedy procedure, and related versions of it have been studied in several areas beyond local computation. For instance, random-order greedy processes of this kind long predate their local-computation applications: closely related versions were studied already in Flory’s 1939 work in chemistry [13], and later in the random sequential adsorption literature [12]. It has also served as a useful primitive in a number of later algorithmic works.

Since [23], techniques for analyzing RGMIS and related randomized greedy processes have found applications in local and sublinear-time algorithms for vertex cover, matching, set cover, and minimum dominating set [23 YYI09, 24, 4]. Related ideas have also appeared in subsequent work on dynamic and sublinear-time matching, as well as in several other algorithmic settings [7, 5 MRT25, MRTV25, 22, 26, 3, 1, 9]. However, these developments do not seem to yield progress on the expected query complexity of RGMIS from a worst-case queried vertex. A closely analogous difficulty was noted explicitly by Behnezhad [4] in the context of randomized greedy maximal matching, where they wrote that “analyzing the expected query-complexity for a given edge seems to be challenging.” In the RGMIS setting, the analogous question concerns a worst-case queried vertex.

The question we study goes back to Nguyen and Onak [23], who conjectured in their concluding remarks that their exponential analysis might be far from tight, writing that the complexity may grow “quasi-polynomially, not exponentially, in Δ\Delta.” Despite subsequent progress, this question remains open even on trees.

What is the expected complexity of pruned RGMIS from a worst-case vertex in a tree?

Our result

In this paper we focus on the pruned RGMIS, and hence refer to it as RGMIS for simplicity. We say that a vertex xx queries a neighbor yy if the recursive execution of RGMIS at xx invokes RGMIS on yy. Given an input tree and a query vertex vv, we root the tree at vv. Thus, every recursive call proceeds from a vertex to one of its children, and every query path is simply a path of successive queries starting at vv.

The run-time of RGMIS is within O(Δ)O(\Delta) factor of the size of the recursion tree produced by the RGMIS algorithm (see Algorithm 1). The Δ\Delta factor comes from each recursive call having to inspect the adjacency list of a new vertex in the tree and initiating subsequent recursive calls. The run-time bound is also a bound on the portion of the input tree that is inspected by the algorithm. Thus, up to polynomial factor, it suffices to bound the size of the recursion tree, which we henceforth call the query tree, produced by the RGMIS algorithm.

We prove that the expected size of the RGMIS query tree over a worst-case starting vertex (see Definition 2.1) obtained from the RGMIS algorithm is polynomial in Δ\Delta on trees.

Theorem 1.1. There exists an absolute constant C>0C > 0 such that for every integer Δ>2\Delta> 2, every tree TT with maximum degree Δ\Delta and every vertex uu in TT, the expected size of the query tree Q(T,u,r)Q(T,u,r) from uu over uniformly assigned random ranks rr is at most ΔC\Delta^{C}, i.e.,

Er[∣Q(T,u,r)∣]≤ΔC.\mathbb{E}_{r}\left[|Q(T,u,r)|\right] \le\Delta^{C}.

Other related work

A closely related body of work arises in the framework of local computation algorithms (LCAs), where one seeks to answer local queries while remaining consistent with a single global solution. The LCA model was introduced by Rubinfeld, Tamir, Vardi, and Xie [25] and further developed by Alon, Rubinfeld, Vardi, and Xie [2]. Maximal independent set has been one of the central benchmark problems in this area. In particular, beyond the recursive simulation of randomized greedy orders considered in the present line of work, subsequent papers obtained improved LCAs for MIS and related problems, including deterministic and stateless algorithms [11], algorithms for non-constant-degree graphs [20], and, very recently, an LCA for MIS with query complexity poly⁡(Δ)log⁡n\operatorname{poly}(\Delta) \log n [15]. More broadly, many other problems have been studied in the centralized local model as well; we refer the reader to the survey of Levi and Medina [19] for a general overview.

There is also a separate probabilistic line of work that studies the random greedy independent set via branching-process and local-limit methods, especially on random trees and sparse random graphs. This includes analyses on regular graphs of large girth [14], random graphs with prescribed degree sequences [6], and more recent frameworks that explicitly involve Galton–Watson trees or related branching objects [17, 8]. These works are close in spirit, since they also analyze the random greedy MIS process, but their focus is typically on the size or density of the resulting independent set in random graph models, or on the behavior seen from a typical root, rather than on the worst-case query complexity from a fixed vertex in an arbitrary tree. For this reason, it is not clear that their techniques directly apply to the setting studied here.

Overview of our approach

As already discussed, without pruning, running unpruned RGMIS from the root of a Δ\Delta-ary tree makes Θ(eΔ)\Theta(e^{\Delta}) queries in expectation. Hence, to show that pruned RGMIS has significantly lower complexity, the main task is to quantify the effect of pruning. To illustrate our starting idea, consider the following thought experiment.

Suppose we want to count the number of recursive calls made at vertices with ranks in (1/2,1)(1/2,1), and ignore all work performed at vertices of rank below 1/21/2. Moreover, we count a recursive call from uu to vv only if vv itself queries some vertex ww, and the ranks of uu, vv, and ww all lie in (1/2,1)(1/2,1). How many vertices with ranks in (1/2,1)(1/2,1) are then queried?

Consider a vertex uu with rank r(u)∈(1/2,1)r(u) \in(1/2,1) that is reached by the recursion. At that point, among all randomness in the subtree rooted at uu, only the rank r(u)r(u) has been revealed. Suppose that uu queries a child vv, which in turn queries some vertex ww with r(w)∈(1/2,1)r(w) \in(1/2,1). For this to happen, it must be the case that all children w′w' of vv with r(w′)<1/2r(w') < 1/2 are not in the MIS. Otherwise, the RGMIS procedure would stop exploring the children of vv upon reaching such a vertex w′w', and as a result would never query ww.

We thus consider the set of promising vertices vv, defined as follows: let AA be the set of children vv of uu such that no child ww of vv with r(w)<1/2r(w) < 1/2 belongs to the MIS. In expectation, how many vertices in AA with ranks at least 1/21/2 are queried by uu? To answer this, observe that membership in AA is determined by the subtree below each v∈Av \in A, and therefore does not reveal any information about r(v)r(v) itself. Hence, conditioned on AA, each rank r(v)r(v) for v∈Av \in A remains uniformly distributed in [0,1][0,1]. A naive estimate therefore gives only that the expected number of vertices in AA with rank at least 1/21/2 queried by uu is at most ∣A∣/2|A|/2. However, pruning gives a much stronger bound. Indeed, suppose that some v∈Av \in A satisfies r(v)≤1/2r(v) \le1/2. Then r(v)<r(u)r(v) < r(u), so uu queries vv before any child v′v' with r(v′)>1/2r(v') > 1/2. Moreover, by the definition of AA, no child of vv with smaller rank belongs to the MIS, and hence vv itself belongs to the MIS. It follows that u∉MISu \notin\mathrm{MIS}, so the exploration stops at uu before any child of uu with rank larger than 1/21/2 is queried. Therefore, children in AA with rank at least 1/21/2 are queried only if every vertex in AA has rank at least 1/21/2. Since the ranks {r(v):v∈A}\{r(v) : v \in A\} remain independent and uniform in [0,1][0,1], this event occurs with probability 2−∣A∣2^{-|A|}. Thus, conditioned on AA, the expected number of queried vertices in AA with ranks in (1/2,1)(1/2,1) is at most 2−∣A∣⋅∣A∣2^{-|A|} \cdot|A| which is at most a constant.

This thought experiment captures the basic mechanism behind our proof, but turning it into a full proof requires overcoming two obstacles. First, what about the cost of exploring vertices with ranks below 1/21/2, which we have so far ignored? Second, and a major challenge in our work, how can one continue this reasoning recursively once previously revealed randomness creates dependencies that were absent in the definition of AA? We address these obstacles in two stages.

Interval decomposition, encodings, and the first obstacle (Section 3). We begin with the first obstacle, namely, that the thought experiment ignores all work performed at vertices of rank below 1/21/2. To handle this, we partition the rank space into intervals of the form [2−j,2−j+1)[2^{-j},2^{-j+1}) and use these intervals to encode paths according to the scale of the ranks they encounter. For a fixed such encoding, we then enlarge the class of paths we consider and work with candidate paths, namely paths whose vertices lie in the prescribed intervals, even if they are not necessarily queried by the recursion. Thus, the interval decomposition is what both organizes the analysis and defines the larger family of paths on which we work.

The point of passing to candidate paths is that they reveal only coarse information about the ranks along the path – namely, the interval in which each rank lies, but not its exact value inside that interval. This is exactly the amount of information we can afford to reveal. It preserves enough randomness so that the relative order of vertices that fall within the same interval remains hidden. As a result, the probability that a candidate path is a query path is roughly 1/(k1!⋯km!)1/(k_1! \cdots k_m!), where kik_i denotes the number of vertices on the candidate path that lie in the interval (1/2i,1/2i−1)(1/2^i,1/2^{i-1}).

Refined encodings and the second obstacle (Section 4). The second obstacle is that the “clean” independence used in the thought experiment breaks down under recursion. In the thought experiment, the set AA was useful because we could determine membership in AA without revealing the actual ranks of the vertices in AA themselves. In the recursive process, however, once we move one level deeper, some information in the relevant subtrees has already been revealed. Thus, even after passing to candidate paths, one cannot simply repeat the same argument at every level.

This is where the main technical tool of the proof enters, namely a refined path encoding. At each step, there is a natural threshold coming from the interval of the next vertex on the path. The refined encoding records how much this threshold needs to be “lowered”, and uses flags to mark a sparse set of levels where such lowering is genuinely necessary. Informally, these are the levels where we must pay for a large branching event; at the other levels, we avoid revealing comparable information. This is what allows the thought-experiment intuition to be applied repeatedly without exposing too much randomness along the way. Combined with the exponential tail bound for such large-branching events – which we already saw informally in the thought experiment – this yields an exponentially decaying contribution for each valid encoding. Summing over all encodings then gives the desired bound on the number of candidate paths.

Statement on AI use

All of the text in this paper was written by the (human) authors of this submission. AI was used only for proofreading: to identify grammatical and mathematical errors. All comments and suggestions made by AI were thoroughly reviewed by the authors. All proofs and technical ideas in this paper were developed solely by the authors, without any AI involvement.

Preliminaries

The randomized greedy MIS algorithm is outlined in Algorithm 1.

Algorithm 1 The RGMIS algorithm
1: procedure RGMIS($G$, $u$, $r$)
   Input: A graph $G$, vertex $u$ and distinct ranks $r : V(G) \to [0,1)$.
   Output: Does $u$ belong to the MIS in the greedy algorithm that processes the vertices in increasing order of $r$?
2: Obtain $\Gamma(u)$, the list of neighbors of $u$.
3: for each $w \in \Gamma(u)$ with $r(w) < r(u)$ in increasing order of $r(w)$ do
4:    if RGMIS($G$, $w$, $r$) = YES then
5:       return NO
6: return YES

In this paper, we are interested in the (expected) size and depth of the recursion tree produced by Algorithm 1 starting from a worst-case vertex vv of a tree, where expectation is taken over uniformly sampled vertex ranks.

Definition 2.1 (Query tree and size). Given a graph GG, vertex u∈V(G)u \in V(G) and rank r:V(G)→[0,1)r : V(G) \to[0,1), we denote by Q(G,u,r)Q(G,u,r), the recursion tree obtained from the execution of RGMIS(G,u,rG,u,r). We use ∣Q(G,u,r)∣|Q(G,u,r)| to denote the size (number of vertices) of the tree Q(G,u,r)Q(G,u,r).

Definition 2.2 (Query path). We say that a path P=(u0,u1,…uL−1)P = (u_0, u_1, \ldots u_{L-1}) in a tree T\mathcal{T} is a query path if the execution of RGMIS(T,ui,r\mathcal{T},u_i,r) directly invokes RGMIS(T,ui+1,r\mathcal{T},u_{i+1},r) for each i=0,1,…L−2i = 0,1,\ldots L-2. For simplicity, we say that uiu_i queries ui+1u_{i+1} if RGMIS(T,ui,r\mathcal{T},u_i,r) invokes RGMIS(T,ui+1,r\mathcal{T},u_{i+1},r).

Definition 2.3 (Worst case expected query complexity). For an integer Δ≥1\Delta\ge1, let Tree(Δ\Delta) denote the set of all trees of maximum degree Δ\Delta. The worst case expected query complexity of Algorithm 1 on a tree of maximum degree Δ\Delta is given by,

max⁡G∈Tree⁡(Δ),v∈GEr[∣Q(G,v,r)∣]\max_{\substack{G \in\operatorname{Tree}(\Delta),\\v\in G}} \mathbb{E}_{r}\left[|Q(G,v,r)|\right]

Technicality of distinct ranks. In Definition 2.3, we assume that the ranks r:V(G)→[0,1)r : V(G) \to[0,1) are sampled uniformly and independently for each vertex v∈V(G)v \in V(G). However, Algorithm 1 requires that the ranks are distinct for each vertex. In our analysis we will assume that rr is distinct for all vertices, which is an almost sure event. Hence, our analysis also applies to the version of RGMIS that samples a uniform permutation π\pi and sets the rank as r(u)=π(u)/nr(u) = \pi(u)/n where π(u)∈{0,1,…n−1}\pi(u) \in\{0,1,\ldots n-1\}.

Counting the number of query paths

In this section, we give the proof of Theorem 1.1 assuming a technical lemma (Lemma 3.12). We prove Lemma 3.12 in § 4. We start by introducing some definitions and explaining the intuition behind them.

Setup and notation. Consider a rooted tree T\mathcal{T} and let u0u_0 be its root. Consider the execution of RGMIS(T,u0,r)(\mathcal{T}, u_0, r) over uniformly sampled rank r:V(T)→[0,1)r: V(\mathcal{T}) \to[0,1). We denote by Tv\mathcal{T}_v, the sub-tree beneath vertex vv in the rooted tree. We denote by Γ(v)\Gamma(v) the set of children of vv in the rooted tree T\mathcal{T}. More formally, Γ(v)\Gamma(v) is the set of neighbors of vv that are farther than vv from u0u_0.

We show that the expected number of query paths starting at the root is at most poly⁡(Δ)\operatorname{poly}(\Delta), where Δ\Delta is the maximum number of children of any vertex in the tree when rooted at u0u_0. Observe that the maximum degree is at most Δ+1\Delta+ 1 and hence the poly⁡(Δ)\operatorname{poly}(\Delta) claim also holds with Δ\Delta being the maximum degree in the tree. Our strategy will be to partition the interval [0,1)[0,1) into sub-intervals with geometrically decreasing sizes.

References

  1. [1][ABGR25] Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, and Ronitt Rubinfeld. Stochastic matching via in-n-out local computation algorithms. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC 2025), pages 1055–1066, 2025.arxiv.org/abs/2411.08805
  2. [2][ARVX12] Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie. Space-efficient local computation algorithms. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1132–1139. SIAM, 2012.
  3. [3][BCMT22] Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li-Yang Tan. Almost 3-approximate correlation clustering in constant rounds. In Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2022), pages 720–731. IEEE, 2022.arxiv.org/abs/2205.03710
  4. [4][Beh21] Soheil Behnezhad. Time-optimal sublinear algorithms for matching and vertex cover. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021), pages 873–884. IEEE, 2021.arxiv.org/abs/2106.02942
  5. [5][Beh23] Soheil Behnezhad. Dynamic algorithms for maximum matching size. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), pages 129–162. SIAM, 2023.arxiv.org/abs/2207.07607
  6. [6][BJL17] Graham Brightwell, Svante Janson, and Malwina Luczak. The greedy independent set in a random graph with given degrees. Random Structures & Algorithms, 51(4):565–586, 2017.arxiv.org/abs/1510.05560
  7. [7][BKS23] Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Dynamic (1 + ε)-approximate matching size in truly sublinear update time. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023), pages 1563–1588. IEEE, 2023.arxiv.org/abs/2302.05030
  8. [8][Con22] Alice Contat. Surprising identities for the greedy independent set on cayley trees. Journal of Applied Probability, 59(4):1042–1058, 2022.arxiv.org/abs/2103.03800
  9. [9]Rathish Das and William Kuszmaul. History-independent maximal matchings can be surprisingly efficient, and lead to better worst-case guarantees. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pages 3999–4022. SIAM, 2026.DOI
  10. [10]Mina Dalirrooyfard, Konstantin Makarychev, and Slobodan Mitrović. A simple average-case analysis of recursive randomized greedy MIS. In Proceedings of the SIAM Symposium on Simplicity in Algorithms (SOSA 2026), pages 241–246. SIAM, 2026.
  11. [11]Guy Even, Moti Medina, and Dana Ron. Best of two local models: Centralized local and distributed local algorithms. Information and Computation, 262:69–89, 2018.
  12. [12]James W Evans. Random and cooperative sequential adsorption. Reviews of modern physics, 65(4):1281, 1993.DOI
  13. [13]Paul J Flory. Intramolecular reaction between neighboring substituents of vinyl polymers. Journal of the American Chemical Society, 61(6):1518–1521, 1939.DOI
  14. [14]David Gamarnik and David A Goldberg. Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections. Combinatorics, Probability and Computing, 19(1):61–85, 2010.arxiv.org/abs/0807.1277
  15. [15]Mohsen Ghaffari. Local computation of maximal independent set. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 438–449. IEEE, 2022.
  16. [16]Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 85–103. Plenum Press, New York, 1972.
  17. [17]Michael Krivelevich, Tamás Mészáros, Peleg Michaeli, and Clara Shikhelman. Greedy maximal independent sets via local limits. Random Structures & Algorithms, 64(4):986–1015, 2024.arxiv.org/abs/1907.07216
  18. [18]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 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 1753–1772. SIAM, 2020.arxiv.org/abs/1907.05725
  19. [19]Reut Levi, Moti Medina, et al. A (centralized) local guide. Bulletin of EATCS, 2(122), 2017.
  20. [20]Reut Levi, Ronitt Rubinfeld, and Anak Yodpinyanee. Local computation algorithms for graphs of non-constant degrees. In Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, pages 59–61, 2015.
  21. [22]Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian. Sublinear metric steiner forest via maximal independent set. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pages 5941–5959. SIAM, 2026.
  22. [23]Huy N Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local improvements. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 327–336. IEEE, 2008.DOI
  23. [24]Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld. A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pages 1123–1131. SIAM, 2012.
  24. [25]Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie. Fast local computation algorithms. arXiv preprint arXiv:1104.1377, 2011.arxiv.org/abs/1104.1377
  25. [26]Nithin Varma and Yuichi Yoshida. Average sensitivity of graph algorithms. SIAM Journal on Computing, 52(4):1039–1081, 2023.

Paper details

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

views · 10

downloads · 0

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

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents