Arrow Research search

Author name cluster

Soheil Behnezhad

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

32 papers
2 author rows

Possible papers

32

ICML Conference 2025 Conference Paper

Correlation Clustering Beyond the Pivot Algorithm

  • Soheil Behnezhad
  • Moses Charikar
  • Vincent Cohen-Addad
  • Alma Ghafari
  • Weiyun Ma

We study the classic correlation clustering problem. Given $n$ objects and a complete labeling of the object-pairs as either “similar” or “dissimilar”, the goal is to partition the objects into arbitrarily many clusters while minimizing disagreements with the labels. A classic Pivot algorithm for this problem, due to [Ailon et al STOC’05], obtains a 3-approximation for this problem. Over the years, this algorithm has been successfully implemented in various settings. The downside of the Pivot algorithm is that the approximation analysis of 3 is tight for it. While better approximations have been achieved in some settings, these algorithms are often hard to implement in various settings. For example, [Behnezhad et al FOCS19] showed that the output of Pivot can be maintained in polylog time per update in a dynamic setting, a bound that was improved to constant by [Dalirrooyfard et al ICML’24]. But obtaining a better approximation remains open. In this paper, we present Modified Pivot, an algorithm that locally improves the output of Pivot. Our Modified Pivot algorithm can be implemented just as efficiently as Pivot in various settings. Our experiments show that the output of Modified Pivot on average makes less than 77% of the mistakes made by Pivot. More surprisingly, we prove theoretically that Modified Pivot has approximation ratio $3-\epsilon_0$ for some absolute constant $\epsilon_0 > 0$. This, e. g. , leads to a better than 3 approximation in the dynamic setting in polylog time, improving the 3-approximation obtained by [Behnezhad et al FOCS’19] and [Dalirrooyfard et al ICML’24].

Details

FOCS Conference 2025 Conference Paper

Lower Bounds for Non-adaptive Local Computation Algorithms

  • Amir Azarmehr
  • Soheil Behnezhad
  • Alma Ghafari
  • Madhu Sudan 0001

We study non-adaptive Local Computation Algorithms (LCA). A reduction of Parnas and Ron (TCS’07) turns any distributed algorithm into a non-adaptive LCA. Plugging known distributed algorithms, this leads to non-adaptive LCAs for constant approximations of maximum matching (MM) and minimum vertex cover (MVC) with complexity $\Delta^{O(\log \Delta / \log \log \Delta)}$, where $\Delta$ is the maximum degree of the graph. Allowing adaptivity, this bound can be significantly improved to $\operatorname{poly}(\Delta)$, but is such a gap necessary or are there better non-adaptive LCAs? Adaptivity as a resource has been studied extensively across various areas. Beyond this, we further motivate the study of non-adaptive LCAs by showing that even a modest improvement over the Parnas-Ron bound for the MVC problem would have major implications in the Massively Parallel Computation (MPC) setting. In particular, it would lead to faster truly sublinear space MPC algorithms for approximate MM, a major open problem of the area. Our main result is a lower bound that rules out this avenue for progress. Specifically, we prove that $\Delta^{\Omega(\log \Delta / \log \log \Delta)}$ queries are needed for any non-adaptive LCA computing a constant approximation of MM or MVC. This is the first separation between non-adaptive and adaptive LCAs, and already matches (up to constants in the exponent) the algorithm obtained by the black-box reduction of Parnas and Ron. Our proof blends techniques from two separate lines of work: sublinear time lower bounds and distributed lower bounds. Particularly, we adopt techniques such as couplings over acyclic subgraphs from the recent sublinear time lower bounds of Behnezhad, Roghani, and Rubinstein (STOC’23, FOCS’23, STOC’24). We apply these techniques on a very different instance, particularly (a modified version of) the construction of Kuhn, Moscibroda and Wattenhoffer (JACM’16) from distributed computing. Our proof reveals that the (modified) KMW instance has the rather surprising property that any random walk of any length has a tiny chance $\left(\Delta^{-\Omega(\log \Delta / \log \log \Delta)}\right)$ of identifying a matching edge. In contrast, the work of KMW only proves that short walks (i. e. , walks of depth $O(\log \Delta / \log \log \Delta)$) are not useful.

Details

FOCS Conference 2025 Conference Paper

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance

  • Amir Azarmehr
  • Soheil Behnezhad
  • Mohammad Roghani
  • Aviad Rubinstein

How many adjacency matrix queries (also known as pair queries) are required to estimate the size of a maximum matching in an n-vertex graph G? We study this fundamental question in this paper. On the upper bound side, an algorithm of Bhattacharya, Kiss, and Saranurak [FOCS’23] gives an estimate that is within $\varepsilon n$ of the right bound with $n^{2-\Omega_{\varepsilon}(1)}$ queries, which is subquadratic in n (and thus sublinear in the matrix size) for any fixed $\varepsilon\gt0$. On the lower bound side, while there has been a lot of progress in the adjacency list model, no non-trivial lower bound has been established for algorithms with adjacency matrix query access. In particular, the only known lower bound is a folklore bound of $\Omega(n)$, leaving a huge gap. In this paper, we present the first superlinear in n lower bound for this problem. In fact, we close the gap mentioned above entirely by showing that the algorithm of [BKS’23] is optimal. Formally, we prove that for any fixed $\delta\gt0$, there is a fixed $\varepsilon\gt0$ such that an estimate that is within $\varepsilon n$ of the true bound requires $\Omega\left(n^{2-\delta}\right)$ adjacency matrix queries. Our lower bound also has strong implications for estimating the earth mover’s distance between distributions. For this problem, Beretta and Rubinstein [STOC’24] gave an $n^{2-\Omega_{\varepsilon}(1)}$ time algorithm that obtains an additive $\varepsilon$-approximation and works for any distance function. Whether this can be improved generally, or even for metric spaces, had remained open. Our lower bound rules out the possibility of any improvements over this bound, even under the strong assumption that the underlying distances are in a (1, 2)-metric.

Details

ICML Conference 2024 Conference Paper

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS

  • Amir Azarmehr
  • Soheil Behnezhad
  • Mohammad Roghani

Maximum matching is one of the most fundamental combinatorial optimization problems with applications in various contexts such as balanced clustering, data mining, resource allocation, and online advertisement. In many of these applications, the input graph is massive. The sheer size of these inputs makes it impossible to store the whole graph in the memory of a single machine and process it there. Graph sparsification has been an extremely powerful tool to alleviate this problem. In this paper, we study a highly successful and versatile sparsifier for the matching problem: the edge-degree constrained subgraph (EDCS) introduced first by Bernstein & Stein 2015 The EDCS has a parameter $\beta \geq 2$ which controls the density of the sparsifier. It has been shown through various proofs in the literature that by picking a subgraph with $O(n\beta)$ edges, the EDCS includes a matching of size at least $2/3-O(1/\beta)$ times the maximum matching size. As such, by increasing $\beta$ the approximation ratio of EDCS gets closer and closer to $2/3$. In this paper, we propose a new approach for analyzing the approximation ratio of EDCS. Our analysis is tight for any value of $\beta$. Namely, we pinpoint the precise approximation ratio of EDCS for any sparsity parameter $\beta$. Our analysis reveals that one does not necessarily need to increase $\beta$ to improve approximation, as suggested by previous analysis. In particular, the best choice turns out to be $\beta = 6$, which achieves an approximation ratio of $. 677$! This is arguably surprising as it is even better than $2/3 \sim. 666$, the bound that was widely believed to be the limit for EDCS.

Details

FOCS Conference 2024 Conference Paper

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs

  • Soheil Behnezhad
  • Alma Ghafari

We study the fully dynamic maximum matching problem. In this problem, the goal is to efficiently maintain an approximate maximum matching of a graph that is subject to edge insertions and deletions. Our focus is particularly on algorithms that maintain the edges of a $(1-\varepsilon)$ -approximate maximum matching for an arbitrarily small constant $\varepsilon > 0$. Until recently, the fastest known algorithm for this problem required $\Theta(n)$ time per update where $n$ is the number of vertices. This bound was slightly improved to $n/(\log^{\ast}n)^{\Omega(1)}$ by Assadi, Behnezhad, Khanna, and Li [STOC'23] and very recently to $n/2_{-}^{\Omega(\sqrt{\log n})}$ by Liu [FOCS'24]. Whether this can be improved to $n^{1-\Omega(1)}$ remains a major open problem. In this paper, we introduce Ordered Ruzsa-Szemerédi (ORS) graphs (a generalization of Ruzsa-Szemerédi graphs) and show that the complexity of dynamic matching is closely tied to them. For $\delta > 0$, define ORS $(\delta n)$ to be the maximum number of matchings $M_{1}, \ldots, 1M_{t}$, each of size $\delta n$, that one can pack in an n-vertex graph such that each matching $M_{i}$ is an induced matching in subgraph $M_{1}\cup\ldots\cup M_{i}$. We show that there is a randomized algorithm that maintains a $(1-\varepsilon)$ -approximate maximum matching of a fully dynamic graph in amortized update-time. While the value of $\text{ORS}(\Theta(n))$ remains unknown and is only upper bounded by $n^{1-o(1)}$, the densest construction known from more than two decades ago only achieves $ORS (\Theta(n))\geq n^{1/\Theta(\log\log n)}=n^{o(1)}$ [Fischer et al. STOC'02]. If this is close to the right bound, then our algorithm achieves an update-time of $\sqrt{n^{1+O(\varepsilon)}}^{-}$, resolving the aforementioned longstanding open problem in dynamic algorithms in a strong sense.

Details

SODA Conference 2023 Conference Paper

Beating Greedy Matching in Sublinear Time

  • Soheil Behnezhad
  • Mohammad Roghani
  • Aviad Rubinstein
  • Amin Saberi

We study sublinear time algorithms for estimating the size of maximum matching in graphs. Our main result is a (½ + Ω(1))-approximation algorithm which can be implemented in O ( n 1+ε ) time, where n is the number of vertices and the constant ε > 0 can be made arbitrarily small. The best known lower bound for the problem is Ω( n ), which holds for any constant approximation. Existing algorithms either obtain the greedy bound of ½-approximation [Behnezhad FOCS'21], or require some assumption on the maximum degree to run in o ( n 2 )-time [Yoshida, Yamamoto, and Ito STOC'09]. We improve over these by designing a less “adaptive” augmentation algorithm for maximum matching that might be of independent interest.

Details

SODA Conference 2023 Conference Paper

Dynamic Algorithms for Maximum Matching Size

  • Soheil Behnezhad

We study fully dynamic algorithms for maximum matching. This is a well-studied problem, known to admit several update-time/approximation trade-offs. For instance, it is known how to maintain a 1/2-approximate matching in (poly log n) update time or a 2/3-approximate match­ing in update time, where n is the number of vertices. It has been a long-standing open problem to determine whether either of these bounds can be improved. In this paper, we show that when the goal is to maintain just the size of the matching (and not its edge-set), then these bounds can indeed be improved. First, we give an algorithm that takes (polylog n ) update-time and maintains a. 501-approximation (. 585-approximation if the graph is bipartite). Second, we give an algorithm that maintains a (2/3 + Ω(1))-approximation in time for bipartite graphs. Our results build on new connections to sublinear time algorithms. In particular, a key tool for both is an algorithm of the author for estimating the size of maximal matchings in Õ ( n ) time [Behnezhad; FOCS 2021]. Our second result also builds on the edge-degree constrained subgraph (EDCS) of Bernstein and Stein [ICALP'15, SODA'16]. In particular, while it has been known that EDCS may not include a better than 2/3-approximation, we give a new characterization of such tight instances which allows us to break it. We believe this characterization might be of independent interest.

Details

FOCS Conference 2023 Conference Paper

Local Computation Algorithms for Maximum Matching: New Lower Bounds

  • Soheil Behnezhad
  • Mohammad Roghani
  • Aviad Rubinstein

We study local computation algorithms (LCA) for maximum matching. An LCA does not return its output entirely, but reveals parts of it upon query. For matchings, each query is a vertex v; the LCA should return whether v is matched—and if so to which neighbor—while spending a small time per query. In this paper, we prove that any LCA that computes a matching that is at most an additive of $\epsilon n$ smaller than the maximum matching in n-vertex graphs of maximum degree $\Delta$ must take at least $\Delta^{\Omega(1 / \varepsilon)}$ time. This comes close to the existing upper bounds that take $(\Delta / \epsilon)^{O\left(1 / \epsilon^{2}\right)} \operatorname{polylog}(n)$ time. In terms of sublinear time algorithms, our techniques imply that any algorithm that estimates the size of maximum matching up to an additive error of $\epsilon n$ must take $\Delta^{\Omega(1 / \epsilon)}$ time. This negatively resolves a decade old open problem of the area (see Open Problem 39 of sublinear. info) on whether such estimates can be achieved in $\operatorname{poly}(\Delta / \epsilon)$ time.

Details

STOC Conference 2023 Conference Paper

On Regularity Lemma and Barriers in Streaming and Dynamic Matching

  • Sepehr Assadi
  • Soheil Behnezhad
  • Sanjeev Khanna
  • Huan Li 0002

We present a new approach for finding matchings in dense graphs by building on Szemerédi’s celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n -vertex graphs: A deterministic single-pass streaming algorithm that finds a (1− o (1))-approximate matching in o ( n 2 ) bits of space. This constitutes the first single-pass algorithm for this problem in sublinear space that improves over the 1/2-approximation of the greedy algorithm. A randomized fully dynamic algorithm that with high probability maintains a (1− o (1))-approximate matching in o ( n ) worst-case update time per each edge insertion or deletion. The algorithm works even against an adaptive adversary. This is the first o ( n ) update-time dynamic algorithm with approximation guarantee arbitrarily close to one. Given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some (log * n ) Θ(1) factor. Nevertheless, in each case, they show that the “right” answer to the problem is not what is dictated by the previous bounds. Finally, in the streaming model, we also present a randomized (1− o (1))-approximation algorithm whose space can be upper bounded by the density of certain Ruzsa-Szemerédi (RS) graphs. While RS graphs by now have been used extensively to prove streaming lower bounds, ours is the first to use them as an upper bound tool for desigining improved streaming algorithms.

Details

SODA Conference 2023 Conference Paper

Single-Pass Streaming Algorithms for Correlation Clustering

  • Soheil Behnezhad
  • Moses Charikar
  • Weiyun Ma
  • Li-Yang Tan

We study correlation clustering in the streaming setting. This problem has been studied extensively and numerous algorithms have been developed, most requiring multiple passes over the stream. For the important case of single-pass algorithms, recent work of Assadi and Wang [8] obtains a c -approximation using Õ( n ) space where c > 10 5 is a constant and n is the number of vertices to be clustered. We present a single-pass algorithm that obtains a 5-approximation using O(n) space. The algorithm itself is extremely simple and has implications beyond the streaming setting (such as for dynamic and local computation algorithms). The approximation analysis, on the other hand, is delicate and in fact tight.

Details

STOC Conference 2023 Conference Paper

Sublinear Time Algorithms and Complexity of Approximate Maximum Matching

  • Soheil Behnezhad
  • Mohammad Roghani
  • Aviad Rubinstein

Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic side. For instance, an algorithm of [Behnezhad; FOCS’21] obtains a 1/2-approximation in O ( n ) time for n -vertex graphs. A more recent algorithm by [Behnezhad, Roghani, Rubinstein, and Saberi; SODA’23] obtains a slightly-better-than-1/2 approximation in O ( n 1+є ) time (for arbitrarily small constant ε>0). On the lower bound side, [Parnas and Ron; TCS’07] showed 15 years ago that obtaining any constant approximation of maximum matching size requires Ω( n ) time. Proving any super-linear in n lower bound, even for (1−є)-approximations, has remained elusive since then. In this paper, we prove the first super-linear in n lower bound for this problem. We show that at least n 1.2 − o (1) queries in the adjacency list model are needed for obtaining a (2/3 + Ω(1))-approximation of the maximum matching size. This holds even if the graph is bipartite and is promised to have a matching of size Θ( n ). Our lower bound argument builds on techniques such as correlation decay that to our knowledge have not been used before in proving sublinear time lower bounds. We complement our lower bound by presenting two algorithms that run in strongly sublinear time of n 2−Ω(1) . The first algorithm achieves a (2/3−ε)-approximation (for any arbitrarily small constant ε>0); this significantly improves prior close-to-1/2 approximations. Our second algorithm obtains an even better approximation factor of (2/3+Ω(1)) for bipartite graphs. This breaks 2/3-approximation which has been a barrier in various settings of the matching problem, and importantly shows that our n 1.2− o (1) time lower bound for (2/3+Ω(1))-approximations cannot be improved all the way to n 2− o (1) .

Details

FOCS Conference 2022 Conference Paper

Almost 3-Approximate Correlation Clustering in Constant Rounds

  • Soheil Behnezhad
  • Moses Charikar
  • Weiyun Ma
  • Li-Yang Tan

We study parallel algorithms for correlation clustering. Each pair among n objects is labeled as either “similar” or “dissimilar”. The goal is to partition the objects into arbitrarily many clusters while minimizing the number of disagreements with the labels. Our main result is an algorithm that for any $\varepsilon>0$ obtains a (3 + $\varepsilon$)-approximation in $O(1/\varepsilon$) rounds (of models such as massively parallel computation, local, and semi-streaming). This is a culminating point for the rich literature on parallel correlation clustering. On the one hand, the approximation (almost) matches a natural barrier of 3 for combinatorial algorithms. On the other hand, the algorithm’s round-complexity is essentially constant. To achieve this result, we introduce a simple $O(1/\varepsilon$)-round parallel algorithm. Our main result is to provide an analysis of this algorithm, showing that it achieves a (3 + $\varepsilon$)-approximation. Our analysis draws on new connections to sublinear-time algorithms. Specifically, it builds on the work of Yoshida, Yamamoto, and Ito [1] on bounding the “query complexity” of greedy maximal independent set. To our knowledge, this is the first application of this method in analyzing the approximation ratio of any algorithm. Full version. Due to the page limit, this version of the paper does not include all the proofs. The full version of the paper is available at [2].

Details

SODA Conference 2022 Conference Paper

New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS

  • Soheil Behnezhad
  • Sanjeev Khanna

We study the maximum matching problem in fully dynamic graphs: a graph is undergoing both edge insertions and deletions, and the goal is to efficiently maintain a large matching after each edge update. This problem has received considerable attention in recent years. The known algorithms naturally exhibit a trade-off between the quality of the matching maintained (i. e. , the approximation ratio) and the time needed per update. While several interesting results have been obtained, the optimal behavior of this trade-off remains largely unclear. Our main contribution is a new approach to designing fully dynamic approximate matching algorithms that in a unified manner not only (essentially) recovers all previously known trade-offs that were achieved via very different techniques, but reveals some new ones as well. Specifically, we introduce a generalization of the edge-degree constrained subgraph (EDCS) of Bernstein and Stein (2015) that we call the hierarchical EDCS (HEDCS). We also present a randomized algorithm for efficiently maintaining an HEDCS. In an m -edge graph with maximum degree Δ, for any integer k ≥ 0 that is essentially the number of levels of the hierarchy in HEDCS, our algorithm takes Õ (min{Δ 1/( k + 1), m 1/(2 k +2) }) worst-case update-time and maintains an (almost) α ( k )-approximate matching where we show: • These bounds recover all previous trade-offs known for dynamic matching in the literature up to logarithmic factors in the update-time. • α (2) >. 612 for bipartite graphs, and α (2) >. 609 for general graphs. Note that these approximations are obtained in Õ (min{Δ 1/3, m 1/6 }) update-time. • α (3) >. 563 for bipartite graphs, and α (3) >. 532 for general graphs. Note that these approximations are obtained in Õ (min{Δ 1/4, m 1/8 }) update-time.

Details

SODA Conference 2022 Conference Paper

Stochastic Vertex Cover with Few Queries

  • Soheil Behnezhad
  • Avrim Blum
  • Mahsa Derakhshan

We study the minimum vertex cover problem in the following stochastic setting. Let G be an arbitrary given graph, p ∊ (0, 1] a parameter of the problem, and let G p be a random subgraph that includes each edge of G independently with probability p. We are unaware of the realization G p, but can learn if an edge e exists in G p by querying it. The goal is to find an approximate minimum vertex cover (MVC) of G p by querying few edges of G non-adaptively. This stochastic setting has been studied extensively for various problems such as minimum spanning trees, matroids, shortest paths, and matchings. To our knowledge, however, no non-trivial bound was known for MVC prior to our work. In this work, we present a: (2 + ∊ )-approximation for general graphs which queries edges per vertex, and a 1. 367-approximation for bipartite graphs which queries poly(1/ p ) edges per vertex. Additionally, we show that at the expense of a triple-exponential dependence on p –1 in the number of queries, the approximation ratio can be improved down to (1 + ∊ ) for bipartite graphs. Our techniques also lead to improved bounds for bipartite stochastic matching. We obtain a 0. 731-approximation with nearly-linear in 1/ p per-vertex queries. This is the first result to break the prevalent (2/3∼ 0. 66)-approximation barrier in the poly(1/ p ) query regime, improving algorithms of [Behnezhad et al. , SODA'19] and [Assadi and Bernstein, SOSA'19].

Details

FOCS Conference 2021 Conference Paper

Time-Optimal Sublinear Algorithms for Matching and Vertex Cover

  • Soheil Behnezhad

We study the problem of estimating the size of maximum matching and minimum vertex cover in sub linear time. Denoting the number of vertices by $n$ and the average degree in the graph by $\overline{d}$, we obtain the following results for both problems which are all provably time-optimal up to polylogarithmic factors: 1 1 The $\tilde{O}(\cdot)$ notation hides polylog $n$ factors throughout the paper. •A multiplicative $(2+\varepsilon)$ -approximation that takes $\tilde{O}(n/\varepsilon^{2})$ time using adjacency list queries. •A multiplicative-additive $(2, \ \varepsilon n)$ -approximation that takes $\tilde{O}((\overline{d}+1)/\varepsilon^{2})$ time using adjacency list queries. •A multiplicative-additive $(2, \ \varepsilon n)$ -approximation that takes $\tilde{O}(n/\varepsilon^{3})$ time using adjacency matrix queries. Our main contribution and the key ingredient of the bounds above is a near-tight analysis of the average query complexity of randomized greedy maximal matching which improves upon a seminal result of Yoshida, Yamamoto, and Ito $[\text{STOC}^{\prime} 09]$.

Details

SODA Conference 2020 Conference Paper

Fully Dynamic Matching: Beating 2-Approximation in Δ ϵ Update Time

  • Soheil Behnezhad
  • Jakub Lacki
  • Vahab Mirrokni

In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and despite extensive studies, all known algorithms that maintain a 2 – Ω(1) approximate matching are much slower. Understanding this gap and, in particular, determining the best possible update time for algorithms providing a better-than-2 approximate matching is a major open question. In this paper, we show that for any constant ϵ > 0, there is a randomized algorithm that with high probability maintains a 2 – Ω(1) approximate maximum matching of a fully-dynamic general graph in worst-case update time O (Δ ϵ + polylog n ), where Δ is the maximum degree. Previously, the fastest fully dynamic matching algorithm providing a better-than-2 approximation had O ( m 1/4 ) update-time [Bernstein and Stein, SODA 2016]. A faster algorithm with update-time O ( n ϵ ) was known, but worked only for maintaining the size (and not the edges) of the matching in bipartite graphs [Bhattacharya, Henzinger, and Nanongkai, STOC 2016].

Details

STOC Conference 2020 Conference Paper

Stochastic matching with few queries: (1-ε) approximation

  • Soheil Behnezhad
  • Mahsa Derakhshan
  • MohammadTaghi Hajiaghayi

Suppose that we are given an arbitrary graph G =( V , E ) and know that each edge in E is going to be realized independently with some probability p . The goal in the stochastic matching problem is to pick a sparse subgraph Q of G such that the realized edges in Q , in expectation, include a matching that is approximately as large as the maximum matching among the realized edges of G . The maximum degree of Q can depend on p , but not on the size of G . This problem has been subject to extensive studies over the years and the approximation factor has been improved gradually from 0.5 to eventually 2/3 which is a known barrier. In this work, we analyze a natural sampling-based algorithm and show that it can obtain a (1−є) approximation, for any constant є > 0. A key and of possible independent interest component of our analysis is an algorithm that constructs a matching on a stochastic graph, which among some other important properties, guarantees that each vertex is matched independently from the vertices that are sufficiently far. This allows us to bypass a previously known barrier towards achieving (1−є) approximation based on existence of dense Ruzsa-Szemerédi graphs.

Details

FOCS Conference 2020 Conference Paper

Stochastic Weighted Matching: (Stochastic Weighted Matching: (1-ε) Approximation -\varepsilon$) Approximation

  • Soheil Behnezhad
  • Mahsa Derakhshan

Let $G= (V, E)$ be a given edge-weighted graph and let its realization $\mathcal{G}$ be a random subgraph of $G$ that includes each edge $e\in E$ independently with probability $p$. We study a stochastic matching problem where the goal is to non-adaptively pick a sparse subgraph $Q$ of $G$ (without knowing the realization $\mathcal{G}$ ), such that the maximum weight matching among the realized edges of $Q$ (i. e. graph $Q\cap \mathcal{G}$ ) in expectation approximates the maximum weight matching of the whole realization $\mathcal{G}$. In this paper, we prove that for any $\varepsilon\in(0, 1)$, every graph $G$ has a subgraph $Q$ that has maximum degree only $O_{\varepsilon, p}(1)$ and guarantees a ( $1-\varepsilon$ ) -approximation. That is, the maximum degree of $Q$ depends only on $\varepsilon$ and $p$ (both of which are known to be necessary) and not for example on the number of nodes in $G$, the edge-weights, etc. The stochastic matching problem has been studied extensively on both weighted and unweighted graphs. Previously, only existence of (close to) half-approximate subgraphs was known for weighted graphs [Yamaguchi and Maehara, SODA'18; Behnezhad et al. , SODA'19]. Our result substantially improves over these works, matches the state-of-the-art for unweighted graphs [Behnezhad et al. , STOC'20], and settles the approximation factor.

Details

FOCS Conference 2019 Conference Paper

Exponentially Faster Massively Parallel Maximal Matching

  • Soheil Behnezhad
  • MohammadTaghi Hajiaghayi
  • David G. Harris 0001

The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, however, we still have a far more limited understanding of maximal matching which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximal matching either take polylogarithmic time which is considered inefficient, or require a strictly super-linear space of n1+ (1) per machine. In this work, we close this gap by providing a novel analysis of an extremely simple algorithm. This affirmatively resolves the conjecture of Czumaj et al. [STOC’18] that a variant of this algorithm might work. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition. We show that this algorithm drastically reduces the vertex degrees. This, among some other results, leads to an O(log log ) round algorithm for maximal matching with O(n) space (or even mildly sublinear in n using standard techniques). As an immediate corollary, we get a 2 approximate minimum vertex cover in essentially the same rounds and space. This is the best possible approximation factor under standard assumptions, culminating a long line of research. It also leads to an improved O(log log ) round algorithm for 1+" approximate matching. All these results can also be implemented in the congested clique model within the same number of rounds.

Details

FOCS Conference 2019 Conference Paper

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time

  • Soheil Behnezhad
  • Mahsa Derakhshan
  • MohammadTaghi Hajiaghayi
  • Cliff Stein 0001
  • Madhu Sudan 0001

We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph-which undergoes both edge insertions and deletions-in polylogarithmic time. Our algorithm is randomized and, per update, takes O(log 2 Δ log 2 n) expected time. Furthermore, the algorithm can be adjusted to have O(log 2 Δ log 4 n) worst-case update-time with high probability. Here, n denotes the number of vertices and Δ is the maximum degree in the graph. The MIS problem in fully dynamic graphs has attracted significant attention after a breakthrough result of Assadi, Onak, Schieber, and Solomon [STOC'18] who presented an algorithm with O(m 3/4 ) update-time (and thus broke the natural Ω(m) barrier) where m denotes the number of edges in the graph. This result was improved in a series of subsequent papers, though, the update-time remained polynomial. In particular, the fastest algorithm prior to our work had Õ(min{√n, m 1/3 }) update-time [Assadi et al. SODA'19]. Our algorithm maintains the lexicographically first MIS over a random order of the vertices. As a result, the same algorithm also maintains a 3-approximation of correlation clustering. We also show that a simpler variant of our algorithm can be used to maintain a random-order lexicographically first maximal matching in the same update-time.

Details

FOCS Conference 2019 Conference Paper

Near-Optimal Massively Parallel Graph Connectivity

  • Soheil Behnezhad
  • Laxman Dhulipala
  • Hossein Esfandiari
  • Jakub Lacki
  • Vahab Mirrokni

Identifying the connected components of a graph, apart from being a fundamental problem with countless applications, is a key primitive for many other algorithms. In this paper, we consider this problem in parallel settings. Particularly, we focus on the Massively Parallel Computations (MPC) model, which is the standard theoretical model for modern parallel frameworks such as MapReduce, Hadoop, or Spark. We consider the truly sublinear regime of MPC for graph problems where the space per machine is n δ for some desirably small constant δ ϵ (0, 1). We present an algorithm that for graphs with diameter D in the wide range [log ε n, n], takes O(log D) rounds to identify the connected components and takes O(log log n) rounds for all other graphs. The algorithm is randomized, succeeds with high probability, does not require prior knowledge of D, and uses an optimal total space of O(m). We complement this by showing a conditional lower-bound based on the widely believed TwoCycle conjecture that Ω(log D) rounds are indeed necessary in this setting. Studying parallel connectivity algorithms received a resurgence of interest after the pioneering work of Andoni etal [FOCS 2018] who presented an algorithm with O(log D log log n) round-complexity. Our algorithm improves this result for the whole range of values of D and almost settles the problem due to the conditional lower-bound. Additionally, we show that with minimal adjustments, our algorithm can also be implemented in a variant of (CRCW) PRAM in asymptotically the same number of rounds.

Details

SODA Conference 2018 Conference Paper

From Battlefields to Elections: Winning Strategies of Blotto and Auditing Games

  • Soheil Behnezhad
  • Avrim Blum
  • Mahsa Derakhshan
  • MohammadTaghi Hajiaghayi
  • Mohammad Mahdian
  • Christos H. Papadimitriou
  • Ronald L. Rivest
  • Saeed Seddighin

Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a ( u, p )-maxmin strategy which ensures receiving a minimum utility of u with probability at least p. We then give approximation algorithms for the problem of finding a ( u, p )-maxmin strategy for these games. The first game that we consider is Colonel Blotto, a well-studied game that was introduced in 1921. In the Colonel Blotto game, two colonels divide their troops among a set of battlefields. Each battlefield is won by the colonel that puts more troops in it. The payoff of each colonel is the weighted number of battlefields that she wins. We show that maximizing the expected payoff of a player does not necessarily maximize her winning probability for certain applications of Colonel Blotto. For example, in presidential elections, the players’ goal is to maximize the probability of winning more than half of the votes, rather than maximizing the expected number of votes that they get. We give an exact algorithm for a natural variant of continuous version of this game. More generally, we provide constant and logarithmic approximation algorithms for finding ( u, p )-maxmin strategies. We also introduce a security game version of Colonel Blotto which we call auditing game. It is played between two players, a defender and an attacker. The goal of the defender is to prevent the attacker from changing the outcome of an instance of Colonel Blotto. Again, maximizing the expected payoff of the defender is not necessarily optimal. Therefore we give a constant approximation for ( u, p )-maxmin strategies.

Details

NeurIPS Conference 2017 Conference Paper

Affinity Clustering: Hierarchical Clustering at Scale

  • MohammadHossein Bateni
  • Soheil Behnezhad
  • Mahsa Derakhshan
  • MohammadTaghi Hajiaghayi
  • Raimondas Kiveris
  • Silvio Lattanzi
  • Vahab Mirrokni

Graph clustering is a fundamental task in many data-mining and machine-learning pipelines. In particular, identifying a good hierarchical structure is at the same time a fundamental and challenging problem for several applications. The amount of data to analyze is increasing at an astonishing rate each day. Hence there is a need for new solutions to efficiently compute effective hierarchical clusterings on such huge data. The main focus of this paper is on minimum spanning tree (MST) based clusterings. In particular, we propose affinity, a novel hierarchical clustering based on Boruvka's MST algorithm. We prove certain theoretical guarantees for affinity (as well as some other classic algorithms) and show that in practice it is superior to several other state-of-the-art clustering algorithms. Furthermore, we present two MapReduce implementations for affinity. The first one works for the case where the input graph is dense and takes constant rounds. It is based on a Massively Parallel MST algorithm for dense graphs that improves upon the state-of-the-art algorithm of Lattanzi et al. (SPAA 2011). Our second algorithm has no assumption on the density of the input graph and finds the affinity clustering in $O(\log n)$ rounds using Distributed Hash Tables (DHTs). We show experimentally that our algorithms are scalable for huge data sets, e. g. , for graphs with trillions of edges.

PDF Details

AAAI Conference 2017 Conference Paper

Faster and Simpler Algorithm for Optimal Strategies of Blotto Game

  • Soheil Behnezhad
  • Sina Dehghani
  • Mahsa Derakhshan
  • MohammadTaghi Hajiaghayi
  • Saeed Seddighin

In the Colonel Blotto game, which was initially introduced by Borel in 1921, two colonels simultaneously distribute their troops across different battlefields. The winner of each battle- field is determined independently by a winner-take-all rule. The ultimate payoff of each colonel is the number of battlefields he wins. This game is commonly used for analyzing a wide range of applications such as the U. S presidential election, innovative technology competitions, advertisements, etc. There have been persistent efforts for finding the optimal strategies for the Colonel Blotto game. After almost a century Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin provided a poly-time algorithm for finding the optimal strategies. They first model the problem by a Linear Program (LP) with exponential number of constraints and use Ellipsoid method to solve it. However, despite the theoretical importance of their algorithm, it is highly impractical. In general, even Simplex method (despite its exponential running-time) performs better than Ellipsoid method in practice. In this paper, we provide the first polynomial-size LP formulation of the optimal strategies for the Colonel Blotto game. We use linear extension techniques. Roughly speaking, we project the strategy space polytope to a higher dimensional space, which results in a lower number of facets for the polytope. We use this polynomial-size LP to provide a novel, simpler and significantly faster algorithm for finding the optimal strategies for the Colonel Blotto game. We further show this representation is asymptotically tight in terms of the number of constraints. We also extend our approach to multi-dimensional Colonel Blotto games, and implement our algorithm to observe interesting properties of Colonel Blotto; for example, we observe the behavior of players in the discrete model is very similar to the previously studied continuous model.

PDF Details
v2026.09.13