Arrow Research search

Author name cluster

Benny Sudakov

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.

11 papers
1 author row

Possible papers

11

STOC Conference 2012 Conference Paper

Nearly complete graphs decomposable into large induced matchings and their applications

  • Noga Alon
  • Ankur Moitra
  • Benny Sudakov

We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on N vertices with ( N 2 )-o(N 2 ) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N 1-o(1) . The second construction provides a covering of all edges of the complete graph K N by two graphs, each being the edge disjoint union of at most N 2-δ induced matchings, where δ>0.076. This disproves (in a strong form) a conjecture of Meshulam, substantially improves a result of Birk, Linial and Meshulam on communicating over a shared channel, and (slightly) extends the analysis of Hastad and Wigderson of the graph test of Samorodnitsky and Trevisan for linearity. Additionally, our constructions settle a combinatorial question of Vempala regarding a candidate rounding scheme for the directed Steiner tree problem.

Details

FOCS Conference 2010 Conference Paper

All-Pairs Shortest Paths in O(n 2 ) Time with High Probability

  • Yuval Peres
  • Dmitry Sotnikov
  • Benny Sudakov
  • Uri Zwick

We present an all-pairs shortest path algorithm whose running time on a complete directed graph on n vertices whose edge weights are chosen independently and uniformly at random from [0, 1] is O(n 2 ), in expectation and with high probability. This resolves a long standing open problem. The algorithm is a variant of the dynamic all-pairs shortest paths algorithm of Demetrescu and Italiano. The analysis relies on a proof that the number of locally shortest paths in such randomly weighted graphs is O(n 2 ), in expectation and with high probability. We also present a dynamic version of the algorithm that recomputes all shortest paths after a random edge update in O(log 2 n) expected time.

Details

FOCS Conference 2005 Conference Paper

Additive Approximation for Edge-Deletion Problems

  • Noga Alon
  • Asaf Shapira
  • Benny Sudakov

A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following edge-deletion problem; given a monotone property P and a graph G, compute the smallest number of edge deletions that are needed in order to turn G into a graph satisfying P. We denote this quantity by E/sub P/'(G). The first result of this paper states that the edge-deletion problem can be efficiently approximated for any monotone property. 1) For any /spl epsiv/ > 0 and any monotone property P, there is a deterministic algorithm, which given a graph G of size n, approximates E/sub P/'(G) in time O(n/sup 2/) to within an additive error of /spl epsiv/n/sup 2/. Given the above, a natural question is for which monotone properties one can obtain better additive approximations of E/sub P/'. Our second main result essentially resolves this problem by giving a precise characterization of the monotone graph properties for which such approximations exist; 1. If there is a bipartite graph that does not satisfy P, then there is a /spl delta/ > 0 for which it is possible to approximate E/sub P/' to within an additive error of n/sup 2-/spl delta// in polynomial time. 2) On the other hand, if all bipartite graphs satisfy P, then for any /spl delta/ > 0 it is NP-hard to approximate E/sub P/' to within an additive error of n/sup 2-/spl delta//. While the proof of (1) is simple, the proof of (2) requires several new ideas and involves tools from extremal graph theory together with spectral techniques. This approach may be useful for obtaining other hardness of approximation results. Interestingly, prior to this work it was not even known that computing E/sub P/' precisely for the properties in (2) is NP-hard. We thus answer (in a strong form) a question of Yannakakis [1981], who asked in 1981 if it is possible to find a large and natural family of graph properties for which computing E/sub P/' is NP-hard.

Details

STOC Conference 2005 Conference Paper

Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors

  • Boaz Barak
  • Guy Kindler
  • Ronen Shaltiel
  • Benny Sudakov
  • Avi Wigderson

A distribution X over binary strings of length n has min-entropy k if every string has probability at most 2 - k in X . We say that X is a δ-source if its rate k ⁄ n is at least δ.We give the following new explicit instructions (namely, poly(n)- time computable functions) of deterministic extractors, dispersers and related objects. All work for any fixed rate δ>0. No previous explicit construction was known for either of these, for any δ‹1⁄2. The first two constitute major progress to very long-standing open problems. Bipartite Ramsey f 1 : (0,1) n ) 2 →0,1, such that for any two independent δ-sources X 1 , X 2 we have f 1 ( X 1 , X 2 ) = 0,1 This implies a new explicit construction of 2N -vertex bipartite graphs where no induced N δ by N δ subgraph is complete or empty. Multiple source extraction f 2 : (0,1 n ) 3 →0,1 such that for any three independent δ-sources X 1 , X 2 , X 3 we have that f 2 ( X 1 , X 2 , X 3 ) is ( o (1)-close to being) an unbiased random bit. Constant seed condenser 2 f 3 : n →(0,1 m ) c , such that for any δ-source X , one of the c output distributions f 3 ( X ) i , is a 0.9-source over 0,1 m . Here c is a constant depending only on δ. Subspace Ramsey f 4: 0,1 n →0,1 such that for any affine -δ-source 3 X we have f 4 ( X )= 0,1.

Details

FOCS Conference 2002 Conference Paper

Learning a Hidden Matching

  • Noga Alon
  • Richard Beigel
  • Simon Kasif
  • Steven Rudich
  • Benny Sudakov

We consider the problem of learning a matching (i. e. , a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a ( 1/2 +o(1))(n/2) upper bound and a nearly matching 0. 32(n/2) lower bound for the minimum possible number of queries. In contrast, if we allow randomness then we obtain (by a randomized, nonadaptive algorithm) a much lower O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

Details