How far off the edge of the table can we reach by stacking n identical blocks of length 1? A classical solution achieves an overhang of 1
Abstract Maximum Overhang (extended abstract) ∗ (2008)
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
Zohar Naor, Hanoch Levy, Uri Zwick
Abstract. The minimization of the wireless cost of tracking mobile users is a crucial issue in wireless networks. Some of the previous strategies addressing this issue leave an open gap, by requiring...
Noga Alon, Sloan Foundation, Raphy Yuster, Uri Zwick
We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a given graph G = (V, E). The...
Improved Approximation Algorithms for MAX NAE-SAT and MAX (2008)
Adi Avidor, Ido Berkovitch, Uri Zwick
Abstract. MAX SAT and MAX NAE-SAT are central problems in theoretical computer science. We present an approximation algorithm for MAX NAE-SAT with a conjectured performance guarantee of 0.8279. This...
Approximate Distance Oracles MIKKEL THORUP AT&T Labs—Research AND (2008)
Abstract. Let G = (V, E) beanundirected weighted graph with |V | = n and |E | = m. Let k ≥ 1beaninteger. We show that G = (V, E) can be preprocessed in O(kmn1/k)expected time, constructing a data...
Union-Find with Constant Time Deletions (2008)
Stephen Alstrup, Inge Li Gørtz, Theis Rauhe, Mikkel Thorup, Uri Zwick
Abstract. A union-find data structure maintains a collection of disjoint sets under makeset, union and find operations. Kaplan, Shafrir and Tarjan [SODA 2002] designed data structures for an...
Abstract Spatial Codes and the Hardness of String Folding Problems (Extended Abstract) (2008)
Ashwin Nayak, Alistair Sinclair, Uri Zwick
We present the first proof of NP-hardness (under random-ized polynomial time reductions) for string folding prob-lems over a finite alphabet. All previous such intractability results have required an...
Approximate Distance Oracles Weighted (2008)
algorithm mn time n 2 space n by n distance matrix Input: A weighted undirected graph G=(V,E), where |E|=m and |V|=n. Output: An n × n distance matrix.
Approximating MIN�-SAT� (2008)
Abstract. We obtain substantially improved approximation algorithms for the MIN�-SAT problem, for���. More specifically, we obtain a 1.1037approximation algorithm for the MIN 2-SAT problem,...
A 4n LOWER BOUND ON THE COMBINATIONAL COMPLEXITY OVER (2008)
Of Certain Symmetric, Uri Zwick
A simple and easy to check property of a symmetric boolean function is shown to imply a 4n 9 lower bound on the circuit complexity of the function over U 2 = B 2 f; g. Among the functions to which...
and Tel Aviv University (2007)
Noga Alon, Raphael Yuster, Uri Zwick
We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a given graph G = (V; E). The...
connectivity algorithm for the EREW PRAM (2007)
An optimal randomised logarithmic time
Abstract. Moore and Shannon have shown that relays with arbitrarily high reliability can be built from relays with arbitrarily poor reliability. Valiant used similar methods to construct monotone...
Looking for MUM and DAD: text-text comparisons do help (2007)
Mike Paterson, Shlomit Tassa, Uri Zwick
. It is known that about 4n 3 comparisons are needed, in the worst case, to find all the occurrences of the string aba in a text of length n if only pattern--text comparisons are allowed. We show...
Optimal Carry Save Networks (2007)
Michael S. Paterson, Nicholas Pippenger, Uri Zwick
A general theory is developed for constructing the asymptotically shallowest networks and the asymptotically smallest networks (with respect to formula size) for the carry save addition of n numbers...
Moore and Shannon have shown that relays with arbitrarily high reliability can be built from relays with arbitrarily poor reliability. Valiant used similar methods to construct monotone readonce...
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
Liam Roditty, Mikkel Thorup, Uri Zwick
We introduce the notion of roundtrip-spanners of weighted directed graphs and describe ecient algorithms for their construction. For every integer k 1 and any > 0, we show that any directed graph...
Connection caching: Model and algorithms (2007)
Edith Cohen, Haim Kaplan, Uri Zwick
We introduce a theoretical model for connection caching. In our model each host maintains (caches) a limited number of open connections to other hosts. A request may utilize an open connection in...
Abstract Reachability and distance queries via 2-hop labels (2007)
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick
The paper considers the exact number of character comparisons needed to nd all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line algorithms,...
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...
Which Patterns Are Hard to Find? (2007)
Richard Cole, Ramesh Hariharan, Michael S. Paterson, Uri Zwick
The paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line...
Which Formulae Shrink under Random Restrictions? (2007)
We show that the shrinkage exponent, under random restrictions, of formulae over a nite complete basis B of Boolean functions is strictly greater than 1 if and only if all the functions in B are...
Edith Cohen, Haim Kaplan, Uri Zwick
Abstract. We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive...
Chapter 1 Selecting the median (2007)
Improving a long standing result of Schonhage, Paterson and Pippenger we show that the median of a set containing n elements can be found using at most 2:95n comparisons. 1
Finding and counting given length cycles (Extended Abstract) (2007)
Noga Alon, Raphael Yuster, Uri Zwick
Abstract. We present an assortment of methods for nding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of...
Coloring K-Colorable Graphs Using Relatively Small Palettes (2007)
Eran Halperin Ram, Ram Nathaniel, Uri Zwick
We obtain the following new coloring results: A 3-colorable graph on n vertices with maximum degree can be colored, in polynomial time, using O(( log ) log n) colors. This slightly improves an O(( )...
We present several new algorithms for detecting short fixed length cycles in digraphs. The new algorithms utilize fast rectangular matrix multiplication algorithms together with a dynamic programming...
The complexity of mean payoff games (2007)
Uri Zwick, Michael S. Paterson
We study the complexity of nding the values and optimal strategies of mean payoff games, a family of perfect information games introduced by Ehrenfeucht and Mycielski. We describe a pseudo-polynomial...
Which Bases Admit Non-Trivial Shrinkage of Formulae? (2007)
We show that the shrinkage exponent, under random restrictions, of formulae over a nite complete basis B of Boolean functions is strictly greater than 1 if and only if all the functions in B are...
How far off the edge of the table can we reach by stacking $n$ identical, homogeneous, frictionless blocks of length 1? A classical solution achieves an overhang of $1/2 H_n$, where $H_n ~ \ln n$ is...
Paterson, Mike, Peres, Yuval, Thorup, Mikkel, Winkler, Peter, Zwick, Uri
How far can a stack of $n$ identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
All-Pairs Bottleneck Paths in Vertex Weighted Graphs (2007)
Asaf Shapira, Raphael Yuster, Uri Zwick
Let G = (V, E, w) be a directed graph, where w: V → R is an arbitrary weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex...
Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, Uri Zwick
How far can a stack of n identical blocks be made to hang over the edge of a table? The question dates back to at least the middle of the 19th century and the answer to it was widely believed to be...
All-Pairs Bottleneck Paths in Vertex Weighted Graphs (2007)
Asaf Shapira, Raphael Yuster, Uri Zwick
Let G = (V, E, w) be a directed graph, where w: V → R is an arbitrary weight function defined on its vertices. The bottleneck weight, or the capacity, of a path is the smallest weight of a vertex...
Maximum matching in graphs with an excluded minor (2007)
Abstract We present a new randomized algorithm for findinga maximum matching in H-minor free graphs. Forevery fixed H, our algorithm runs in O(n3!/(!+3)) < O(n1.326) time, where n is the number of...
A deterministic subexponential algorithm for solving parity games (2006)
Marcin Jurdziński, Mike Paterson, Uri Zwick
The existence of polynomial time algorithms for the solution of parity games is a major open problem. The fastest known algorithms for the problem are randomized algorithms that run in subexponential...
On the value of preemption in scheduling (2006)
Bartal, Yair, Leonardi, Stefano, Shallom, Gill, Sitters, Rene, Diaz, Josep, Jansen, Klaus, ...
A fully dynamic reachability algorithm for directed graphs with an almost linear update time (2004)
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...
Melding Priority Queues (2004)
Ran Mendelson, Robert E. Tarjan, Mikkel Thorup, Uri Zwick
We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) time, when n is an upper bound on the number of elements in the priority queue, can be...
Melding Priority Queues (2004)
Ran Mendelson, Robert E. Tarjan, Mikkel Thorup, Uri Zwick
We show that any priority queue data structure that supports insert, delete, and find-min operations in pq(n) time, when there are up to n elements in the priority queue, can be converted into a...
A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time (2004)
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...
Multicriteria global minimum cuts (2004)
We consider two multicriteria versions of the global minimum cut problem in undirected graphs. In the k-criteria setting, each edge of the input graph has k non-negative costs associated with it....
Algorithms and Experiments for the Webgraph (2003)
Laura, Luigi, Leonardi, Stefano, Millozzi, Stefano, Meyer, Ulrich, Sibeyn, Jop F., Di Battista, Giuseppe, ...
Approximating Energy Efficient Paths in Wireless Multi-hop Networks (2003)
Funke, Stefan, Matijevic, Domagoj, Sanders, Peter, Di Battista, Giuseppe, Zwick, Uri
Given the positions of $n$ sites in a radio network we consider the problem of finding routes between any pair of sites that minimize energy consumption and do not use more than some constant number...
A Practical Minimum Spanning Tree Algorithm Using the Cycle Property (2003)
Katriel, Irit, Sanders, Peter, Träff, Jesper Larsson, Di Battista, Giuseppe, Zwick, Uri
Granados, Miguel, Hachenberger, Peter, Hert, Susan, Kettner, Lutz, Mehlhorn, Kurt, Seel, Michael, ...
We describe a data structure for three-dimensional Nef complexes, algorithms for boolean operations on them, and our implementation of data structure and algorithms. Nef polyhedra were introduced by...
Eisenbrand, Friedrich, Funke, Stefan, Reichel, Joachim, Schömer, Elmar, Di Battista, Giuseppe, Zwick, Uri
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to...
Eisenbrand, Friedrich, Funke, Stefan, Reichel, Joachim, Schömer, Elmar, Di Battista, Giuseppe, Zwick, Uri
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to...
I/O-Efficient Undirected Shortest Paths (2003)
Meyer, Ulrich, Zeh, Norbert, Di Battista, Giuseppe, Zwick, Uri
Fast integer programming in fixed dimension (2003)
Eisenbrand, Friedrich, Di Battista, Guiseppe, Zwick, Uri
It is shown that the optimum of an integer program in fixed dimension, which is defined by a fixed number of constraints, can be computed with $O(s)$ basic arithmetic operations, where $s$ is the...
Constructing worst case instances for semidefinite programming based approximation algorithms (2002)
Noga Alon, Benny Sudakov, Uri Zwick
Semide nite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...
Reachability and Distance Queries via 2-hop Labels (2002)
Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick
1 Reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to Internet routing. Some of these applications involve huge graphs...
All pairs shortest paths using bridging sets and rectangular matrix multiplication (2002)
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 rst algorithm solves...
Constructing worst case instances for semidefinite programming based approximation algorithms (2002)
Noga Alon, Benny Sudakov, Uri Zwick
Semide nite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...
Improved Dynamic Reachability Algorithms for Directed Graphs (2002)
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...
Computer Assisted Proof of Optimal Approximability Results (2002)
We obtain computer assisted proofs of several spherical volume inequalities that appear in the analysis of semidefinite programming based approximation algorithms for Boolean constraint satisfaction...
Improved dynamic reachability algorithms for directed graphs (2002)
Abstract We obtain several new dynamic algorithms for maintainingthe transitive closure of a directed graph, and several other algorithms for answering reachability queries without ex-plicitly...
All pairs shortest paths using bridging sets and rectangular matrix multiplication (2002)
The second algorithm solves the APSP problem almost exactly for directed graphs with arbitrary non-negative real weights. The algorithm runs in ~O((n!=ffl) log(W=ffl)) time, where ffl? 0 is an error...
Coloring k-colorable graphs using relatively small palettes (2001)
Halperin, Eran, Nathaniel, Ram, Zwick, Uri
We obtain the following new coloring results: * A 3-colorable graph on $n$ vertices with maximum degree~$\Delta$ can be colored, in polynomial time, using $O((\Delta \log\Delta)^{1/3} \cdot\log{n})$...
Competitive analysis of the LRFU paging algorithm (2001)
Edith Cohen, Haim Kaplan, Uri Zwick
We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive ratio of LRFU...
Coloring k-colorable graphs using smaller palettes (2001)
Eran Halperin, Ram Nathaniel, Uri Zwick
We obtain the following new coloring results: ffl A 3-colorable graph on n vertices with maximum degree \Delta can be colored, in polynomial time, using O((\Delta log \Delta) 1=3 \Delta log n)...
Approximate distance oracles (2001)
Let G = (V; E) be an undirected weighted graph with jV j = n and jEj = m. Let k 1 be an integer. We show that G = (V; E) can be preprocessed in O(kmn
Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms (2001)
Noga Alon, Benny Sudakov, Uri Zwick
Semide nite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...
Compact Routing Schemes (2001)
We describe several compact routing schemes for general weighted undirected networks. Our schemes are simple and easy to implement. The routing tables stored at the nodes of the network are all very...
Combinatorial Approximation Algorithms for the Maximum Directed Cut Problem (2001)
We describe several combinatorial algorithms for the maximum directed cut problem. Among our results is a simple linear time 9/20-approximation algorithm for the problem, and a somewhat slower...
Coloring k-Colorable Graphs Using Smaller Palettes (2001)
Eran Halperin, Ram Nathaniel, Uri Zwick
We obtain the following new coloring results: A 3-colorable graph on n vertices with maximum degree can be colored, in polynomial time, using O(( log ) log n) colors. This slightly improves an O(( )...
Exact and Approximate Distances in Graphs - a survey (2001)
We survey recent and not so recent results related to the computation of exact and approximate distances, and corresponding shortest, or almost shortest, paths in graphs. We consider many different...
MAX CUT in cubic graphs (2001)
Eran Halperin, Dror Livnat, Uri Zwick
We present an improved semidefinite programming based approximation algorithm for the MAX CUT problem in graphs of maximum degree at most 3. The approximation ratio of the new algorithm is at least...
We obtain improved semidefinite programming based approximation algorithms for all the natural maximum bisection problems of graphs. Among the problems considered are: MAX n/2-BISECTION -- partition...
Approximate Distance Oracles (2001)
Let G = (V, E) be an undirected weighted graph with |V| = n and |E| = m. Let k ≥ 1 be an integer. We show that G = (V, E) can be preprocessed in O(kmn ) expected time, constructing a data...
Competitive analysis of the LRFU paging algorithm (2001)
Edith Cohen Haim, Edith Cohen, Haim Kaplan, Uri Zwick
We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least Frequently Used) paging algorithms. We show that the competitive ratio of LRFU...
Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms (2001)
Noga Alon, Benny Sudakov, Uri Zwick
SL,BAEb#[1 programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...
Approximate distance oracles (2001)
Let G = (V,E) be an undirected weighted graph with |V | = n and |E | = m. Let k ≥ 1 be an integer. We show that G = (V,E) can be preprocessed in O(kmn 1/k) expected time, constructing a data...
All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication (2000)
We present two new algorithms for solving the {\em All Pairs Shortest Paths} (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms. The first...
Analyzing the MAX 2-SAT and MAX DI-CUT approximation algorithms of Feige and Goemans (2000)
We present a complete analysis of the MAX 2-SAT and MAX DI-CUT approximation algorithms of Feige and Goemans using various analytical and computational tools. By fine-tuning the rotation functions...
Connection Caching under (2000)
Various Models Of, Edith Cohen, Haim Kaplan, Uri Zwick
Motivated by Web applications, we recently introduced the following theoretical model for connection-caching: Each host on a network can maintain (cache) a limited number of connections to other...
All-Pairs Small-Stretch Paths (2000)
length is at most t times the distance between u and v in the graph. We consider the problem of finding small-stretch paths between all pairs of vertices in the graph G.
Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs (1999)
Karloff and Zwick obtained recently an optimal 7=8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7=8-approximation algorithm for MAX SAT,...
Edith Cohen, Haim Kaplan, Uri Zwick
Communication between clients and servers in the Web is performed using TCP (Transmission Control Protocol). TCP first opens a connection between the two nodes and then sends data packets via this...
We present a tool, outward rotations, for enhancing the performance of several semidefinite programming based approximation algorithms. Using outward rotations, we obtain an approximation algorithm...
Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs (1999)
. Karloff and Zwick obtained recently an optimal 7=8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7=8-approximation algorithm for MAX...
All Pairs Lightest Shortest Paths (1999)
Two vertices in a weighted directed graph may be connected by many shortest paths. Although all these paths are shortest in terms of weight, the number of edges on them may vary substantially. This...
All Pairs Shortest Paths in Undirected Graphs with Integer Weights (1999)
We show that the All Pairs Shortest Paths (APSP) problem for undirected graphs with integer edge weights taken from the range f1; 2; : : : ; Mg can be solved using only a logarithmic number of...
Edith Cohen Haim, Edith Cohen, Haim Kaplan, Uri Zwick
Communication between clients and servers in the Web is performed using TCP (Transmission Control Protocol) . TCP first opens a connection between the two nodes and then sends data packets via this...
An instance of MAX 3CSP is a collection of m clauses of the form f i (z i1; z i2; z i3), where the z ij 's are literals, or constants, from the set f0; 1; x 1; : : : ; xn; x 1; : : : ; xng, and...
Spatial codes and the hardness of string folding problems (1998)
Ashwin Nayak, Alistair Sinclair, Uri Zwick
We present a general technique for proving NP-hardness (under randomized polynomial time reductions) of string folding problems over a finite alphabet. All previous such intractability results have...
Spatial codes and the hardness of string folding problems (1998)
Ashwin Nayak, Alistair Sinclair, Uri Zwick
We present a general technique for proving NP-hardness (under randomized polynomial time reductions) of string folding problems over a finite alphabet. All previous such intractability results have...
Finding almost-satisfying assignments (1998)
Schaefer showed, long ago, that there are, essentially, only three non-trivial classes of conjunctive Boolean formulae (or constraint satisfaction problems) for which satisability can be decided in...
Finding almost-satisfying assignments (1998)
Schaefer showed, long ago, that there are, essentially, only three non-trivial classes of conjunctive Boolean formulae (or constraint satisfaction problems) for which satisfiability can be decided in...
Spatial Codes and the Hardness of String Folding Problems (Extended Abstract) (1998)
Ashwin Nayak, Alistair Sinclair, Uri Zwick
) Ashwin Nayak Alistair Sinclair y Uri Zwick z Abstract We present the first proof of NP-hardness (under randomized polynomial time reductions) for string folding problems over a finite alphabet. All...
Spatial Codes and the Hardness of String Folding Problems (1998)
Exte Nd Ed, Ashwin Nayak, Alistair Sinclair, Uri Zwick
) Ashwin Nayak Alistair Sinclair y Uri Zwick z Abstract We present the first proof of NP-hardness (under randomized polynomial time reductions) for string folding problems over a finite alphabet. All...
An instance of MAX 3CSP is a collection of m clauses of the form f i (z i1 ; z i2 ; z i3 ), where the z ij 's are literals, or constants, from the set f0; 1; x 1 ; : : : ; xn ; ¯ x 1 ; : : : ;...
Finding and counting given length cycles (1997)
Noga Alon, Raphael Yuster, Uri Zwick
We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the...
Finding and counting given length cycles (1997)
Noga Alon, Raphael Yuster, Uri Zwick
We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the...
All-Pairs Small-Stretch Paths (1997)
Let G = (V; E) be a weighted undirected graph. A path between u; v 2 V is said to be of stretch t if its length is at most t times the distance between u and v in the graph. We consider the problem...
All Pairs Almost Shortest Paths (1997)
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...
The Communication Complexity of the Universal Relation (1997)
Gábor Tardos, G Abor Tardos, Uri Zwick
Consider the following communication problem. Alice gets a word x 2 f0; 1g n and Bob gets a word y 2 f0; 1g n . Alice and Bob are told that x 6= y. Their goal is to find an index 1 i n such that x i...
A 7/8-Approximation Algorithm for MAX 3SAT? (Extended Abstract) (1997)
Howard Karloff Uri Zwick April 28, 1997 Modified: August 17, 1997 Abstract We describe a randomized approximation algorithm which takes an instance of MAX 3SAT as input.
A 7/8-Approximation Algorithm for MAX 3SAT? (1997)
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...
Growth functions and automatic groups (1996)
Epstein, David B. A., Iano-Fletcher, Anthony R., Zwick, Uri
In this paper we study growth functions of automatic and hyperbolic groups. In addition to standard growth functions, we also want to count the number of finite graphs isomorphic to a given finite...
All pairs almost shortest paths (1996)
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...
On lower bounds for selecting the median (1996)
Dorit Dor, Staoean Ulfberg, Uri Zwick
We present a reformulation of the 2n+o(n) lower bound of Bent and John for the number of comparisons needed for selecting the median of n elements. Our reformulation uses a weight function. Apart...
We present the first randomized O(log n) time and O(m+n) work EREW PRAM algorithm for finding a spanning forest of an undirected graph G = (V; E) with n vertices and m edges. Our algorithm is optimal...
Median selection requires (2+ffl)n comparisons (1996)
Improving a long standing result of Bent and John, and extending a recent result of Dor, Hastad, Ulfbeg and Zwick, we obtain a (2+ffl)n lower bound (for some fixed ffl? 0) on the number of...
On lower bounds for selecting the median (1996)
Dorit Dor, Staoean Ulfberg, Uri Zwick
We present a reformulation of the 2n+o(n) lower bound of Bent and John for the number of comparisons needed for selecting the median of n elements. Our reformulation uses a weight function. Apart...
Median Selection Requires (2+ε)n Comparisons (1996)
Improving a long standing result of Bent and John, we obtain a (2+)n lower bound (for some fixed > 0) on the number of comparisons required, in the worst case, for selecting the median of n...
Finding Even Cycles Even Faster (1996)
We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every k 2, there is an O(V 2 ) time algorithm that decides whether an...
Median Selection Requires (2+ε)n Comparisons (1996)
Improving a long standing result of Bent and John, we obtain a (2+ffl)n lower bound (for some fixed ffl ? 0) on the number of comparisons required, in the worst case, for selecting the median of n...
Growth Functions and Automatic Groups (1996)
this paper we study growth functions of automatic and hyperbolic groups. In addition to standard growth functions, we also want to count the number of finite graphs isomorphic to a given finite graph...
We present the first randomized O(logn) time and O(m + n) work EREW PRAM algorithm for finding a spanning forest of an undirected graph G = (V; E) with n vertices and m edges. Our algorithm is...
The Complexity of Mean Payoff Games on Graphs (1996)
We study the complexity of finding the values and optimal strategies of mean payoff games on graphs, a family of perfect information games introduced by Ehrenfeucht and Mycielski and considered by...
On the number of ANDs versus the number of ORs in monotone Boolean circuits (1996)
Alon and Boppana showed that if a monotone Boolean function f of n variables can be computed by a monotone circuit containing k AND gates, where k > 1, then it can also be computed using a...
Tighter Lower Bounds on the Exact Complexity of String Matching (1995)
Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick
. The paper considers the exact number of character comparisons needed to find all occurrences of a pattern of length m in a text of length n using on-line and general algorithms. For on-line...
SOKOBAN and other motion planning problems (1995)
We consider a natural family of motion planning problems with movable obstacles and obtain hardness results for them. Some members of the family are shown to be PSPACE-complete thus improving and...
Noga Alon, Raphy Yuster, Uri Zwick
We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a given graph G = (V; E). The...
Improving a long standing result of Schonhage, Paterson and Pippenger we show that the median of a set containing n elements can always be found using at most 2:95n comparisons. 1 Introduction The...
Improving a long standing result of Schonhage, Paterson and Pippenger we show that the median of a set containing n elements can always be found using at most 2:95n comparisons. 1 Introduction The...
Optimal Deterministic Approximate Parallel Prefix Sums and Their Applications (1995)
We show that extremely accurate approximation to the prefix sums of a sequence of n integers can be computed deterministically in O(log log n) time using O(n= log log n) processors in the Common CRCW...
Improving a long standing result of Schonhage, Paterson and Pippenger we show that the median of a set containing n elements can always be found using at most c \Delta n comparisons, where c ! 2:95.
SOKOBAN and other motion planning problems (Extended Abstract) (1995)
We consider a natural family of motion planning problems with movable obstacles and obtain hardness results for them. Some members of the family are shown to be PSPACE-complete thus improving and...
Improving a long standing result of Schonhage, Paterson and Pippenger we show that the median of a set containing n elements can always be found using at most 2:95n comparisons. 1 Introduction The...
Finding and Counting Given Length Cycles (1995)
Noga Alon, Raphael Yuster, Uri Zwick
We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the...
It is widely known that the Ford-Fulkerson procedure for finding the maximum flow in a network need not terminate if some of the capacities of the network are irrational. Ford and Fulkerson gave as...
Noga Alon, Raphael Yuster, Uri Zwick
We describe a novel randomized method, the method of color-coding for finding simple paths and cycles of a specified length k, and other small subgraphs, within a given graph G = (V, E). The...
Finding even cycles even faster (1994)
Abstract. We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every k ≥ 2, there is an O(V 2) time algorithm that decides...
Finding even cycles even faster (1994)
We describe efficient algorithms for finding even cycles in undirected graphs. Our main results are the following: (i) For every k 2, there is an O(V 2) time algorithm that decides whether an...
Finding the αn-th Largest Element (1994)
We describe an algorithm for selecting the ffn-th largest element (where 0 ! ff ! 1), from a totally ordered set of n elements, using at most (1 + (1 + o(1))H(ff)) \Delta n comparisons, where H(ff)...
Shay Halperin Uri Zwick Department of Computer Science Tel Aviv University Tel Aviv, 69978 Israel Abstract Improving a long chain of works we obtain a randomized EREW PRAM algorithm for nding the...
How Do Read-Once Formulae Shrink? (1994)
Let f be a de Morgan read-once function of n variables. Let f " be the random restriction obtained by independently assigning to each variable of f , the value 0 with probability (1 \Gamma...
) Shay Halperin Uri Zwick Department of Computer Science Tel Aviv University Tel Aviv, 69978 Israel Abstract Improving a long chain of works we obtain a randomized EREW PRAM algorithm for finding the...
Extended Abstract, Noga Alon, Raphy Yuster, Uri Zwick
Noga Alon yz Institute for Advanced Study and Tel Aviv University Raphy Yuster Uri Zwick Tel Aviv University Abstract We describe a novel randomized method, the method of color-coding for nding...
Shallow Circuits And Concise (1993)
Formulae For Multiple, Michael Paterson, Uri Zwick
A theory is developed for the construction of carry-save networks with minimal delay, using a given collection of carry-save adders each of which may receive inputs and produce outputs using several...
Uri Zwick, Michael S. Paterson
The memory game, or concentration, as it is sometimes called, is a popular card game played by children and adults around the world. Good memory is one of the qualities required in order to succeed...
Shrinkage of de Morgan formulae under restriction (1993)
Michael S. Paterson, Coventry Cv Al, Uri Zwick
It is shown that a random restriction leaving only a fraction " of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor of O("...
Amplification and Percolation (1992)
Moore and Shannon had shown that relays with arbitrarily high reliability can be built from relays with arbitrarily poor reliability. Valiant used similar methods to construct monotone read-once...