Arrow Research search

Author name cluster

Uri Zwick

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.

73 papers
2 author rows

Possible papers

73

SODA Conference 2024 Conference Paper

Tight approximability of MAX 2-SAT and relatives, under UGC

  • Joshua Brakensiek
  • Neng Huang 0001
  • Uri Zwick

Austrin showed that the approximation ratio β ≈ 0. 94016567 obtained by the MAX 2-SAT approximation algorithm of Lewin, Livnat and Zwick (LLZ) is optimal modulo the Unique Games Conjecture (UGC) and modulo a Simplicity Conjecture that states that the worst performance of the algorithm is obtained on so called simple configurations. We prove Austrin's conjecture, thereby showing the optimality of the LLZ approximation algorithm, relying only on the Unique Games Conjecture. Our proof uses a combination of analytic and computational tools. We also present new approximation algorithms for two restrictions of the MAX 2-SAT problem. For MAX HORN-{1, 2}-SAT, i. e. , MAX CSP, in which clauses are not allowed to contain two negated literals, we obtain an approximation ratio of 0. 94615981. For MAX CSP, i. e. , when 2-clauses are not allowed to contain negated literals, we obtain an approximation ratio of 0. 95397990. By adapting Austrin's and our arguments for the MAX 2-SAT problem we show that these two approximation ratios are also tight, modulo only the UGC conjecture. This completes a full characterization of the approximability of the MAX 2-SAT problem and its restrictions. * The full version of the paper can be accessed at https: //arxiv. org/abs/2310. 12911

Details

SODA Conference 2023 Conference Paper

Improved girth approximation in weighted undirected graphs

  • Avi Kadria
  • Liam Roditty
  • Aaron Sidford
  • Virginia Vassilevska Williams
  • Uri Zwick

Let G = ( V, E, ℓ) be a n -nodes m -edges weighted undirected graph, where ℓ: E → (0, ∞) is a real length function defined on its edges. Let g be the length of the shortest cycle in G. We present an algorithm that in O ( kn 1+1/ k log n + m(k + log n )) expected running time finds a cycle of length at most, for every integer k ≥ 1. This improves upon the previous best algorithm that in O((n 1+1/k log n + m ) log( nM )) time, where ℓ: E → [1, M ] is an integral length function, finds a cycle of length at most 2 kg [KRS + 22]. For k = 1 our algorithm also improves the result of Roditty and Tov [RT13].

Details

FOCS Conference 2023 Conference Paper

Separating MAX 2-AND, MAX DI-CUT and MAX CUT

  • Joshua Brakensiek
  • Neng Huang 0001
  • Aaron Potechin
  • Uri Zwick

Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is $\alpha_{\text {CUT}} \simeq 0. 87856$, obtained by the celebrated SDP-based approximation algorithm of Goemans and Williamson. Currently, the best approximation algorithm for MAX DI-CUT, i. e. , the MAX CUT problem in directed graphs, achieves a ratio of about 0. 87401, leaving open the question whether MAX DI-CUT can be approximated as well as MAX CUT. We obtain a slightly improved algorithm for MAX DI-CUT and a new UG-Chardness result for it, showing that $0. 87446 \leq \alpha_{\text {DI-CUT}} \leq 0. 87461$, where $\alpha_{\text {DI-CUT}}$ is the best approximation ratio that can be obtained in polynomial time for MAX DI-CUT under UGC. The new upper bound separates MAX DI-CUT from MAX CUT, i. e. , shows that MAX DI-CUT cannot be approximated as well as MAX CUT, resolving a question raised by Feige and Goemans. A natural generalization of MAX DI-CUT is the MAX 2-AND problem in which each constraint is of the form $z_{1} \wedge {z_{2}}$, where $z_{1}$ and ${z_{2}}$ are literals, i. e. , variables or their negations. (In MAX DI-CUT each constraint is of the form $\bar{x}_{1} \wedge {x_{2}}$, where $x_{1}$ and ${x_{2}}$ are variables.) Austrin separated MAX 2-AND from MAX CUT by showing that $\alpha_{2 \mathrm{AND}} \leq 0. 87435$ and conjectured that MAX 2-AND and MAX DI-CUT have the same approximation ratio. Our new lower bound on MAX DI-CUT refutes this conjecture, completing the separation of the three problems MAX 2-AND, MAX DI-CUT and MAX CUT. We also obtain a new lower bound for MAX 2-AND showing that $0. 87414 \leq \alpha_{2 \text {AND}} \leq 0. 87435$. Our upper bound on MAXDI-CUT is achieved via a simple analytical proof. The new lower bounds on MAX DI-CUT and MAX 2-AND, i. e. , the new approximation algorithms, use experimentally-discovered distributions of rounding functions which are then verified via computer-assisted proofs. 1 1 Code for the project: https: //github. com/jbrakensiek/max-dicut

Details

SODA Conference 2022 Conference Paper

Simulating a stack using queues

  • Haim Kaplan
  • Robert Endre Tarjan
  • Or Zamir
  • Uri Zwick

It is well known that a queue can be simulated by two stacks using a constant number of stack operations per queue operation. In this paper we consider the forgotten converse problem of simulating a stack using several queues. We consider several variants of this problem. For the offline variant, we obtain a tight upper and lower bounds for the worst-case number of queue operations needed to simulate a sequence of n stack operations using k queues. For the online variant, when the number of queues k is constant, and n is the maximum number of items in the stack at any given time, we obtain tight Θ( n 1/ k ) upper and lower bounds on the worst-case and amortized number of queue operations needed to simulate one stack operation. When k is allowed to grow with n, we prove an upper bound of O ( n 1/ k + log k n ) and a lower bound of on the amortized number of queue operations per stack operation. We also prove an upper bound of O ( kn 1/ k ) and a lower bound of Ω( n 1/ k + log k n ) on the worst-case number of queue operations per stack operation. We also show that the specific but interesting sequence of n pushes followed by n pops can be implemented much faster using a total number of only Θ( n log k n ) queue operations, for every k ≥ 2, an amortized number of Θ(log k n ) queue operations per stack operation, and this bound is tight. On the other hand, we show that the same sequence requires at least Ω( n 1/ k ) queue operations per stack operation in the worst case.

Details

SODA Conference 2021 Conference Paper

On the Mysteries of MAX NAE-SAT

  • Joshua Brakensiek
  • Neng Huang 0001
  • Aaron Potechin
  • Uri Zwick

MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if all clauses have the same size k, for some k ≥ 2. We refer to this problem as MAX NAE-{ k }-SAT. For k = 2, it is essentially the celebrated MAX CUT problem. For k = 3, it is related to the MAX CUT problem in graphs that can be fractionally covered by triangles. For k ≥ 4, it is known that an approximation ratio of, obtained by choosing a random assignment, is optimal, assuming P ≠ NP. For every k ≥ 2, an approximation ratio of at least 7/8 can be obtained for MAX NAE-{ k }-SAT. There was some hope, therefore, that there is also a 7/8-approximation algorithm for MAX NAE-SAT, where clauses of all sizes are allowed simultaneously. Our main result is that there is no 7/8-approximation algorithm for MAX NAE-SAT, assuming the unique games conjecture (UGC). In fact, even for almost satisfiable instances of MAX NAE-{3, 5}-SAT (i. e. , MAX NAE-SAT where all clauses have size 3 or 5), the best approximation ratio that can be achieved, assuming UGC, is at most. Using calculus of variations, we extend the analysis of O'Donnell and Wu for MAX CUT to MAX NAE-{3}-SAT. We obtain an optimal algorithm, assuming UGC, for MAX NAE-{3}-SAT, slightly improving on previous algorithms. The approximation ratio of the new algorithm is ≈ 0. 9089. This gives a full understanding of MAX NAE-{ k }-SAT for every k ≥ 2. Interestingly, the rounding function used by this optimal algorithm is the solution of an integral equation. We complement our theoretical results with some experimental results. We describe an approximation algorithm for almost satisfiable instances of MAX NAE-{3, 5}-SAT with a conjectured approximation ratio of 0. 8728, and an approximation algorithm for almost satisfiable instances of MAX NAE-SAT with a conjectured approximation ratio of 0. 8698. We further conjecture that these are essentially the best approximation ratios that can be achieved for these problems, assuming the UGC. Somewhat surprisingly, the rounding functions used by these approximation algorithms are non-monotone step functions that assume only the values ±1.

Details

TCS Journal 2020 Journal Article

Public vs. private randomness in simultaneous multi-party communication complexity

  • Orr Fischer
  • Rotem Oshman
  • Uri Zwick

In simultaneous number-in-hand multi-party communication protocols, we have k players, who each receive a private input, and wish to compute a joint function of their inputs. The players simultaneously each send a single message to a referee, who then outputs the value of the function. The cost of the protocol is the total number of bits sent to the referee. For two players, it is known that giving the players a public (shared) random string is much more useful than private randomness: public-coin protocols can be unboundedly better than deterministic protocols, while private-coin protocols can only give a quadratic improvement on deterministic protocols. We extend the two-player gap to multiple players, and show that the private-coin communication complexity of a k-player function f is at least Ω ( D ( f ) ) for any k ≥ 2. Perhaps surprisingly, this bound is tight: although one might expect the gap between private-coin and deterministic protocols to grow with the number of players, we show that the All-Equality function, where each player receives n bits of input and the players must determine if their inputs are all the same, can be solved by a private-coin protocol with O ˜ ( n k + k ) bits. Since All-Equality has deterministic complexity Θ ( n k ), this shows that sometimes the gap scales only as the square root of the number of players, and consequently the number of bits each player needs to send actually decreases as the number of players increases. We also consider the Exists-Equality function, where we ask whether there is a pair of players that received the same input, and prove a nearly-tight bound of Θ ˜ ( k n ) for it.

Details DOI

Highlights Conference 2020 Conference Abstract

Randomized and deterministic algorithms for 2-player turn-based stochastic and non-stochastic games, part I

  • Uri Zwick

We describe the fastest known randomized algorithm for solving 2-player 0-sum turn-based stochastic games. The running time of the algorithm is sub-exponential, i. e. , roughly of the form 2^{O(n^{1/2})}, where n is the number of states of the games. The algorithm is based on randomized pivoting rules for the simplex algorithm developed by Kalai (1992) and Matousek, Sharir and Welzl (1992). Various versions of such algorithms were developed by Ludwig (1995), Bj\”{o}rklund and Vorobyov (2005), Halman (2007), with slight improvements by Hansen and Zwick (2015).

Details

Highlights Conference 2020 Conference Abstract

Randomized and deterministic algorithms for 2-player turn-based stochastic and non-stochastic games, part II

  • Uri Zwick

We describe the fastest known deterministic algorithms for solving Energy Games (EGs) and Mean Payoff Games (MPGs). For general edge costs the running time is about 2^{n/2}, where n is the number of vertices (states) of the game. When edge costs are integers of absolute value at most M, the running time becomes O(mnM). The algorithms described are based on a paper of Brim et al. (2011), and extensions of results that appeared in a recent paper of Dorfman, Kaplan and Zwick (2019).

Details

SODA Conference 2019 Conference Paper

A sort of an adversary

  • Haim Kaplan
  • Or Zamir
  • Uri Zwick

We describe an efficient deterministic adversary that forces any comparison-based sorting algorithm to perform at least n log n comparisons. This improves on previous efficient adversaries of Atallah and Kosaraju (1981), Richards and Vaidya (1988), and of Brodal et al. (1996) that force any sorting algorithm to perform at least ψ n log n comparisons.

Details

STOC Conference 2019 Conference Paper

Faster k -SAT algorithms using biased-PPSZ

  • Thomas Dueholm Hansen
  • Haim Kaplan
  • Or Zamir
  • Uri Zwick

The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k -SAT problem, for every k >3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k ≥ 3. For k =3 we also improve on Herli’s result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from 1.308 n to 1.307 n .

Details

FOCS Conference 2019 Conference Paper

Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges

  • Jacob Holm
  • Valerie King
  • Mikkel Thorup
  • Or Zamir
  • Uri Zwick

Each vertex of an arbitrary simple graph on n vertices chooses k random incident edges. What is the expected number of edges in the original graph that connect different connected components of the sampled subgraph? We prove that the answer is O(n/k), when k ≥ c log n, for some large enough c. We conjecture that the same holds for smaller values of k, possibly for any k ≥ 2. Such a result is best possible for any k ≥ 2. As an application, we use this sampling result to obtain a one-way communication protocol with private randomness for finding a spanning forest of a graph in which each vertex sends only O (√n log n) bits to a referee.

Details

MFCS Conference 2018 Conference Paper

Pairing heaps: the forward variant

  • Dani Dorfman
  • Haim Kaplan
  • László Kozma 0002
  • Uri Zwick

The pairing heap is a classical heap data structure introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. It is remarkable both for its simplicity and for its excellent performance in practice. The "magic" of pairing heaps lies in the restructuring that happens after the deletion of the smallest item. The resulting collection of trees is consolidated in two rounds: a left-to-right pairing round, followed by a right-to-left accumulation round. Fredman et al. showed, via an elegant correspondence to splay trees, that in a pairing heap of size n all heap operations take O(log n) amortized time. They also proposed an arguably more natural variant, where both pairing and accumulation are performed in a combined left-to-right round (called the forward variant of pairing heaps). The analogy to splaying breaks down in this case, and the analysis of the forward variant was left open. In this paper we show that inserting an item and deleting the minimum in a forward-variant pairing heap both take amortized time O(log(n) * 4^(sqrt(log n))). This is the first improvement over the O(sqrt(n)) bound showed by Fredman et al. three decades ago. Our analysis relies on a new potential function that tracks parent-child rank-differences in the heap.

Details

STOC Conference 2015 Conference Paper

Adjacency Labeling Schemes and Induced-Universal Graphs

  • Stephen Alstrup
  • Haim Kaplan
  • Mikkel Thorup
  • Uri Zwick

We describe a way of assigning labels to the vertices of any undirected graph on up to n vertices, each composed of n/2+O(1) bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an n/2+O(log n) bound of Moon. As a consequence, we obtain an induced-universal graph for n-vertex graphs containing only O(2 n/2 ) vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments and bipartite graphs.

Details

SODA Conference 2015 Conference Paper

The amortized cost of finding the minimum

  • Haim Kaplan
  • Or Zamir
  • Uri Zwick

We obtain an essentially optimal tradeoff between the amortized cost of the three basic priority queue operations insert, delete and find-min in the comparison model. More specifically, we show that for any fixed ε > 0, where n is the number of items in the priority queue and A (insert), A (delete) and A (find-min) are the amortized costs of the insert, delete and find-min operations, respectively. In particular, if A (insert) + A (delete) = O (1), then A (find-min) = Ω( n ), and A (find-min) = O ( n α ), for some α < 1, only if A (insert) + A (delete) = Ω(log n ). (We can, of course, have A (insert) = O (1), A (delete) = O (log n ), or vice versa, and A (find-min) = O (1).) Our lower bound holds even if randomization is allowed. Surprisingly, such fundamental bounds on the amortized cost of the operations were not known before. Brodal, Chaudhuri and Rad-hakrishnan, obtained similar bounds for the worst-case complexity of find-min.

Details

SODA Conference 2014 Conference Paper

Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles

  • Thomas Dueholm Hansen
  • Haim Kaplan
  • Uri Zwick

Dantzig's pivoting rule is one of the most studied pivoting rules for the simplex algorithm. While the simplex algorithm with Dantzig's rule may require an exponential number of pivoting steps on general linear programs, and even on min cost flow problems, Orlin showed that O ( mn 2 log n ) Dantzig's pivoting steps suffice to solve shortest paths problems, where n and m are the number of vertices and edges, respectively, in the graph. Post and Ye recently showed that the simplex algorithm with Dantzig's rule requires only O ( m 2 n 3 log 2 n ) pivoting steps to solve deterministic MDPs with the same discount factor for each edge, and only O ( m 3 n 5 log 2 n ) pivoting steps to solve deterministic MDPs with possibly a distinct discount factor for each edge. We improve Orlin's bound for shortest paths and Post and Ye's bound for deterministic MDPs with the same discount factor by a factor of n to O ( mn log n ), and O ( m 2 n 2 log 2 n ), respectively. We also improve by a factor of n the bound for deterministic MDPs with varying discounts when all discount factors are sufficiently close to 1. These bounds follow from a new proof technique showing that after a certain number of steps, either many edges are excluded from participating in further policies, or there is a large decrease in the value. We also obtain an Ω( n 2 ) lower bound on the number of Dantzig's pivoting steps required to solve shortest paths problems, even when m = Θ( n ). Finally, we describe a reduction from the problem of finding a minimum cost to time ratio cycle to the problem of finding an optimal policy for a discounted deterministic MDP with varying discount factors that tend to 1. This gives a strongly polynomial time algorithm for the problem that does not use Megiddo's parametric search technique.

Details

FOCS Conference 2013 Conference Paper

A Forward-Backward Single-Source Shortest Paths Algorithm

  • David Bruce Wilson
  • Uri Zwick

We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the out-going and incoming adjacency lists of the vertices appear in nondecreasing order of weight. (Spira's algorithm makes the same assumption about the out-going adjacency lists, but does not use incoming adjacency lists.) The running time of the algorithm on a complete directed graph on n vertices with independent exponential edge weights is O(n), with very high probability. This improves on the previously best result of O(n log n), which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms. As a consequence, we also get a new all-pairs shortest paths algorithm. The expected running time of the algorithm on complete graphs with independent exponential edge weights is O(n 2 ), matching a recent result of Peres et al. Furthermore, the probability that the new algorithm requires more than O(n 2 ) time is exponentially small, improving on the polynomially small probability of Peres et al.

Details

SODA Conference 2011 Conference Paper

A subexponential lower bound for the Random Facet algorithm for Parity Games

  • Oliver Friedmann
  • Thomas Dueholm Hansen
  • Uri Zwick

Parity Games form an intriguing family of infinite duration games whose solution is equivalent to the solution of important problems in automatic verification and automata theory. They also form a very natural subclass of Deterministic Mean Payoff Games, which in turn is a very natural subclass of turn-based Stochastic Mean Payoff Games. It is a major open problem whether these game families can be solved in polynomial time. The currently theoretically fastest algorithms for the solution of all these games are adaptations of the randomized algorithms of Kalai and of Matousek, Sharir and Welzl for LP-type problems, an abstract generalization of linear programming. The expected running time of both algorithms is subexponential in the size of the game, i. e. ,, where n is the number of vertices in the game. We focus in this paper on the algorithm of Matousek, Sharir and Welzl and refer to it as the Random Facet algorithm. Matoušek constructed a family of abstract optimization problems such that the expected running time of the Random Facet algorithm, when run on a random instance from this family, is close to the subexponential upper bound given above. This shows that in the abstract setting, the upper bound on the complexity of the Random Facet algorithm is essentially tight. It is not known, however, whether the abstract optimization problems constructed by Matoušek correspond to games of any of the families mentioned above. There was some hope, therefore, that the Random Facet algorithm, when applied to, say, parity games, may run in polynomial time. We show, that this, unfortunately, is not the case by constructing explicit parity games on which the expected running time of the Random Facet algorithm is close to the subexponential upper bound. The games we use mimic the behavior of a randomized counter. They are also the first explicit LP-type problems on which the Random Facet algorithm is not polynomial.

Details

SODA Conference 2011 Conference Paper

Collapse

  • Günter Rote
  • Uri Zwick

The problem of checking whether a given tower of bricks is stable can be easily answered by checking whether a system of linear inequalities has a feasible solution. A more challenging problem is to determine how an unstable tower of bricks collapses. We use Gauß’ principle of least restraint to show that this, and more general rigid-body simulation problems in which many parts touch each other, can be reduced to solving a sequence of convex quadratic programs, with linear constraints, corresponding to a discretization of time. The first of these quadratic programs gives an exact description of initial infinitesimal collapse. The results of the subsequent programs need to be integrated over time to yield an approximation of the global motion of the system.

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

STOC Conference 2004 Conference Paper

A fully dynamic reachability algorithm for directed graphs with an almost linear update time

  • Liam Roditty
  • Uri Zwick

We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of O ( m + n log n ) and a worst-case query time of O ( n ), where m is the current number of edges in the graph, and n is the number of vertices in the graph. Each update operation either inserts a set of edges that touch the same vertex, or deletes an arbitrary set of edges. The algorithm is deterministic and uses fairly simple data structures. This is the first algorithm that breaks the O ( n 2 ) update barrier for all graphs with o ( n 2 ) edges.One of the ingredients used by this new algorithm may be interesting in its own right. It is a new dynamic algorithm for strong connectivity in directed graphs with an interesting persistency property. Each insert operation creates a new version of the graph. A delete operation deletes edges from emphall versions. Strong connectivity queries can be made on each version of the graph. The algorithm handles each update in O ( mα ( m , n )) amortized time, and each query in O (1) time, where α ( m , n ) is a functional inverse of Ackermann's function appearing in the analysis of the union-find data structure. Note that the update time of O ( mα ( m , n )), in case of a delete operation, is the time needed for updating all versions of the graph.

Details

FOCS Conference 2004 Conference Paper

Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs

  • Liam Roditty
  • Uri Zwick

We obtain three dynamic algorithms for the approximate all-pairs shortest paths problem in unweighted undirected graphs: 1) For any fixed /spl epsiv/ > 0, a decremental algorithm with an expected total running time of O(mn), where m is the number of edges and n is the number of vertices in the initial graph. Each distance query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 1 + /spl epsiv/. The algorithm uses O(n/sup 2/) space; 2) For any fixed integer k /spl ges/ 1, a decremental algorithm with an expected total running time of O(mn). Each query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 2k - 1. This algorithm uses, however, only O(m + n/sup 1+1/k/) space. It is obtained by dynamizing techniques of Thorup and Zwick. In addition to being more space efficient, this algorithm is also one of the building blocks used to obtain the first algorithm; 3) For any fixed /spl epsiv/, /spl delta/ > 0 and every t /spl les/ m/sup 1/2-/spl delta//, a fully dynamic algorithm with an expected amortized update time of O(mn/t) and worst-case query time of O(t). The stretch of the returned distances is at most 1+/spl epsiv/. All algorithms can also be made to work on undirected graphs with small integer edge weights. If the largest edge weight is b, then all bounds on the running times are multiplied by b.

Details

FOCS Conference 2002 Conference Paper

Improved Dynamic Reachability Algorithms for Directed Graphs

  • Liam Roditty
  • Uri Zwick

We obtain several new dynamic algorithms for maintaining the transitive closure of a directed graph, and several other algorithms for answering reachability queries without explicitly maintaining a transitive closure matrix. Among our algorithms are: (i) a decremental algorithm for maintaining the transitive closure of a directed graph, through an arbitrary sequence of edge deletions, in O(mn) total expected time, essentially the time needed for computing the transitive closure of the initial graph. Such a result was previously known only for acyclic graphs; (ii) two fully dynamic algorithms for answering reachability queries. The first is deterministic and has an amortized insert/delete time of O(m/spl radic/n), and worst-case query time of O(/spl radic/n). The second is randomized and has an amortized insert/delete time of O(m/sup 0. 58/n) and worst-case query time of O(m/sup 0. 43/). This significantly improves the query times of algorithms with similar update times; and (iii) a fully dynamic algorithm for maintaining the transitive closure of an acyclic graph. The algorithm is deterministic and has a worst-case insert time of O(m), constant amortized delete time of O(1), and a worst-case query time of O(n/ log n). Our algorithms are obtained by combining several new ideas, one of which is a simple sampling idea used for detecting decompositions of strongly connected components, with techniques of Even and Shiloach (1981), Italiano (1988), Henzinger and King (1995), and Frigioni et al. (2001). We also adapt results of Cohen (1997) on estimating the size of the transitive closure to the dynamic setting.

Details

FOCS Conference 1999 Conference Paper

All Pairs Shortest Paths in Undirected Graphs with Integer Weights

  • Avi Shoshan
  • Uri Zwick

We show that the all pairs shortest paths (APSP) problem for undirected graphs with integer edge weights taken from the range {1, 2, .. ., M} can be solved using only a logarithmic number of distance products of matrices with elements in the range (1, 2, .. ., M). As a result, we get an algorithm for the APSP problem in such graphs that runs in O~(Mn/sup /spl omega//) time, where n is the number of vertices in the input graph, M is the largest edge weight in the graph, and /spl omega/<2. 376 is the exponent of matrix multiplication. This improves, and also simplifies, an O~(M/sup (/spl omega/+1)/2/n/sup /spl omega//) time algorithm of Galil and Margalit (1997).

Details

FOCS Conference 1998 Conference Paper

All Pairs Shortest Paths in Weighted Directed Graphs ¾ Exact and Almost Exact Algorithms

  • Uri Zwick

We present two new algorithms for solving the All Pairs Shortest Paths (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms. The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in O/spl tilde/(n/sup 2+/spl mu//) time, where /spl mu/ satisfies the equation /spl omega/(1, /spl mu/, 1)=1+2/spl mu/ and /spl omega/(1, /spl mu/, 1) is the exponent of the multiplication of an n/spl times/n/sup /spl mu// matrix by an n/sup /spl mu///spl times/n matrix. The currently best available bounds on /spl omega/(1, /spl mu/, 1), obtained by Coppersmith and Winograd, and by Huang and Pan, imply that /spl mu/ 0 is an error parameter and W is the largest edge weight in the graph, after the edge weights are scaled so that the smallest non-zero edge weight in the graph is 1. It returns estimates of all the distances in the graph with a stretch of at most 1+/spl epsiv/. Corresponding paths can also be found efficiently.

Details

FOCS Conference 1997 Conference Paper

A 7/8-Approximation Algorithm for MAX 3SAT?

  • Howard J. Karloff
  • Uri Zwick

We describe a randomized approximation algorithm which takes an instance of MAX 3SAT as input. If the instance-a collection of clauses each of length at most three-is satisfiable, then the expected weight of the assignment found is at least 7/8 of optimal. We provide strong evidence (but not a proof) that the algorithm performs equally well on arbitrary MAX 3SAT instances. Our algorithm uses semidefinite programming and may be seen as a sequel to the MAX CUT algorithm of Goemans and Williamson (1995) and the MAX 2SAT algorithm of Feige and Goemans (1995). Though the algorithm itself is fairly simple, its analysis is quite complicated as it involves the computation of volumes of spherical tetrahedra. Hastad has recently shown that, assuming P/spl ne/NP, no polynomial-time algorithm for MAX 3SAT can achieve a performance ratio exceeding 7/8, even when restricted to satisfiable instances of the problem. Our algorithm is therefore optimal in this sense. We also describe a method of obtaining direct semidefinite relaxations of any constraint satisfaction problem of the form MAX CSP(F), where F is a finite family of Boolean functions. Our relaxations are the strongest possible within a natural class of semidefinite relaxations.

Details

FOCS Conference 1996 Conference Paper

All Pairs Almost Shortest Paths

  • Dorit Dor
  • Shay Halperin
  • Uri Zwick

Let G=(V, E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of D. Aingworth et al. (1996), we describe an O/spl tilde/(min{n/sup 3/2/m/sup 1/2/, n/sup 7/3/}) time algorithm APASP/sub 2/ for computing all distances in G with an additive one-sided error of at most 2. The algorithm APASP/sub 2/ is simple, easy to implement, and faster than the fastest known matrix multiplication algorithm. Furthermore, for every even k>2, we describe an O/spl tilde/(min{n/sup 2-(2)/(k+2)/m/sup (2)/(k+2)/, n/sup 2+(2)/(3k-2)/}) time algorithm APASP/sub k/ for computing all distances in G with an additive one-sided error of at most k. We also give an O/spl tilde/(n/sup 2/) time algorithm APASP/sub /spl infin// for producing stretch 3 estimated distances in an unweighted and undirected graph on n vertices. No constant stretch factor was previously achieved in O/spl tilde/(n/sup 2/) time. We say that a weighted graph F=(V, E') k-emulates an unweighted graph G=(V, E) if for every u, v/spl isin/V we have /spl delta//sub G/(u, v)/spl les//spl delta//sub F/(u, v)/spl les//spl delta//sub G/(u, v)+k. We show that every unweighted graph on n vertices has a 2-emulator with O/spl tilde/(n/sup 3/2/) edges and a 4-emulator with O/spl tilde/(n/sup 4/3/) edges. These results are asymptotically tight. Finally, we show that any weighted undirected graph on n vertices has a 3-spanner with O/spl tilde/(n/sup 3/2/) edges and that such a 3-spanner can be built in O/spl tilde/(mn/sup 1/2/) time. We also describe an O/spl tilde/(n(m/sup 2/3/+n)) time algorithm for estimating all distances in a weighted undirected graph on n vertices with a stretch factor of at most 3.

Details

FOCS Conference 1996 Conference Paper

Median Selection Requires (2+epsilon)n Comparisons

  • Dorit Dor
  • Uri Zwick

Improving a long standing result of Bent and John (1985), we obtain a (2+/spl epsiv/)n lower bound (for some fixed /spl epsiv/>0) on the number of comparisons required, in the worst case, for selecting the median of n elements. The new lower bound is obtained using a weight function that allows us to combine leaf counting and adversary arguments.

Details

FOCS Conference 1992 Conference Paper

Amplification and Percolation

  • Moshe Dubiner
  • Uri Zwick

The authors extend R. B. Boppana's results (1989) in two ways. They first show that his two lower bounds hold for general read-once formulae, not necessarily monotone, that may even include exclusive-or gates. They are then able to join his two lower bounds together and show that any read-once, not necessarily monotone, formula that amplifies (p-/sup 1///sub n/, p+/sup 1///sub n/) to (2/sup -n/, 1-2/sup -n/) has size of at least Omega (n/sup alpha +2/). This result does not follow from Boppana's arguments and it shows that the amount of amplification achieved by L. G. Valiant (1984) is the maximal achievable using read-once formulae. >

Details

FOCS Conference 1991 Conference Paper

Shrinkage of de~Morgan formulae under restriction

  • Mike Paterson
  • Uri Zwick

It is shown that a random restriction leaving only a fraction in of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor of O( in /sup 1. 63/). This is an improvement over previous results. The new exponent yields an increased lower bound of approximately n/sup 2. 63/ for the de Morgan formula size of a function in P defined by A. E. Andreev (1987). This is the largest lower bound known, even for functions in NP. >

Details

FOCS Conference 1990 Conference Paper

Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions

  • Mike Paterson
  • Nicholas Pippenger
  • Uri Zwick

A general theory is developed for constructing the shallowest possible circuits and the shortest possible formulas for the carry-save addition of n numbers using any given basic addition unit. More precisely, it is shown that if BA is a basic addition unit with occurrence matrix N, then the shortest multiple carry-save addition formulas that could be obtained by composing BA units are of size n/sup 1/p+o(1)/, where p is the unique real number for which the L/sub p/ norm of the matrix N equals 1. An analogous result connects the delay matrix M of the basic addition unit BA and the minimal q such that multiple carry-save addition circuits of depth (q+o(1)) log n could be constructed by combining BA units. On the basis of these optimal constructions of multiple carry-save adders, the shallowest known multiplication circuits are constructed. >

Details