Uri Zwick

According to our database1, Uri Zwick authored at least 144 papers between 1989 and 2019.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2019
Faster k-SAT algorithms using biased-PPSZ.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

A sort of an adversary.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Selection from Heaps, Row-Sorted Matrices, and X+Y Using Soft Heaps.
Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Pairing heaps: the forward variant.
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

Improved Bounds for Multipass Pairing Heaps and Path-Balanced Binary Search Trees.
Proceedings of the 26th Annual European Symposium on Algorithms, 2018

2016
Color Coding.
Encyclopedia of Algorithms, 2016

Bottleneck Paths and Trees and Deterministic Graphical Games.
Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Public vs. Private Randomness in Simultaneous Multi-party Communication Complexity.
Proceedings of the Structural Information and Communication Complexity, 2016

Random-Edge Is Slower Than Random-Facet on Abstract Cubes.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Adjacency Labeling Schemes and Induced-Universal Graphs.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

The amortized cost of finding the minimum.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Hollow Heaps.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2014
Deterministic Rendezvous, Treasure Hunts, and Strongly Universal Exploration Sequences.
ACM Trans. Algorithms, 2014

Union-Find with Constant Time Deletions.
ACM Trans. Algorithms, 2014

Improved upper bounds for Random-Edge and Random-Jump on abstract cubes.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Listing Triangles.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
Soft Heaps Simplified.
SIAM J. Comput., 2013

All-pairs shortest paths in O(n2) time with high probability.
J. ACM, 2013

A Forward-Backward Single-Source Shortest Paths Algorithm.
Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2011
On the Approximability of Reachability-Preserving Network Orientations.
Internet Mathematics, 2011

Subexponential lower bounds for randomized pivoting rules for the simplex algorithm.
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Collapse.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

A subexponential lower bound for the Random Facet algorithm for Parity Games.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor.
Proceedings of the Innovations in Computer Science, 2011

2010
Lower Bounds for Howard's Algorithm for Finding Minimum Mean-Cost Cycles.
Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

All-Pairs Shortest Paths in O(n2) Time with High Probability.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009
Efficient algorithms for the 2-gathering problem.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Discounted deterministic Markov decision processes and discounted all-pairs shortest paths.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

A simpler implementation and analysis of Chazelle's soft heaps.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008
Color Coding.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem.
J. Graph Algorithms Appl., 2008

An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and Its Applications to Orienting Protein Networks.
Proceedings of the Algorithms in Bioinformatics, 8th International Workshop, 2008

Maximum overhang.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Simple Stochastic Games, Mean Payoff Games, Parity Games.
Proceedings of the Computer Science, 2008

2007
Maximum matching in graphs with an excluded minor.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Deterministic rendezvous, treasure hunts and strongly universal exploration sequences.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

All-pairs bottleneck paths in vertex weighted graphs.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

New Bounds for the Nearly Equitable Edge Coloring Problem.
Proceedings of the Algorithms and Computation, 18th International Symposium, 2007

2006
A Slightly Improved Sub-Cubic Algorithm for the All PairsShortest Paths Problem with Real Edge Lengths.
Algorithmica, 2006

Spanners and emulators with sublinear distance errors.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Overhang.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

A deterministic subexponential algorithm for solving parity games.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

2005
Approximating MIN 2-SAT and MIN 3-SAT.
Theory Comput. Syst., 2005

Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT.
Proceedings of the Approximation and Online Algorithms, Third International Workshop, 2005

Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Deterministic Constructions of Approximate Distance Oracles and Spanners.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Union-Find with Constant Time Deletions.
Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

Answering distance queries in directed graphs using fast matrix multiplication.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT.
Proceedings of the Approximation, 2005

2004
Melding Priority Queues.
Proceedings of the Algorithm Theory, 2004

A fully dynamic reachability algorithm for directed graphs with an almost linear update time.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Detecting short directed cycles using rectangular matrix multiplication and dynamic programming.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Meldable RAM priority queues and minimum directed spanning trees.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Multicriteria Global Minimum Cuts.
Proceedings of the Algorithms and Computation, 15th International Symposium, 2004

Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Fast Sparse Matrix Multiplication.
Proceedings of the Algorithms, 2004

On Dynamic Shortest Paths Problems.
Proceedings of the Algorithms, 2004

2003
Connection caching: model and algorithms.
J. Comput. Syst. Sci., 2003

2002
Cell Identification Codes for Tracking Mobile Users.
Wireless Networks, 2002

Coloring k-colorable graphs using relatively small palettes.
J. Algorithms, 2002

All pairs shortest paths using bridging sets and rectangular matrix multiplication.
J. ACM, 2002

Computer assisted proof of optimal approximability results.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Jenga.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Roundtrip spanners and roundtrip routing in directed graphs.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

MAX CUT in cubic graphs.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Reachability and distance queries via 2-hop labels.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Approximating MIN k-SAT.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems.
Proceedings of the Integer Programming and Combinatorial Optimization, 2002

Improved Dynamic Reachability Algorithms for Directed Graphs.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
On Lower Bounds for Selecting the Median.
SIAM J. Discrete Math., 2001

Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests.
J. Algorithms, 2001

Which bases admit non-trivial shrinkage of formulae?
Computational Complexity, 2001

Competitive Analysis of the LRFU Paging Algorithm.
Proceedings of the Algorithms and Data Structures, 7th International Workshop, 2001

Approximate distance oracles.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Compact routing schemes.
Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

Combinatorial approximation algorithms for the maximum directed cut problem.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Coloring k-colorable graphs using smaller palettes.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Which formulae shrink under random restrictions?
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Constructing worst case instances for semidefinite programming based approximation algorithms.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

A Unified Framework for Obtaining Improved Approximation Algorithms for Maximum Graph Bisection Problems.
Proceedings of the Integer Programming and Combinatorial Optimization, 2001

Semidefinite Programming Based Approximation Algorithms.
Proceedings of the FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science, 2001

Exact and Approximate Distances in Graphs - A Survey.
Proceedings of the Algorithms, 2001

2000
All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication
Electronic Colloquium on Computational Complexity (ECCC), 2000

Connection caching under vaious models of communication.
Proceedings of the Twelfth annual ACM Symposium on Parallel Algorithms and Architectures, 2000

1999
Spatial Codes and the Hardness of String Folding Problems.
Journal of Computational Biology, 1999

SOKOBAN and other motion planning problems.
Comput. Geom., 1999

Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

All Pairs Lightest Shortest Paths.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Connection Caching.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs.
Proceedings of the Integer Programming and Combinatorial Optimization, 1999

All Pairs Shortest Paths in Undirected Graphs with Integer Weights.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Finding Almost-Satisfying Assignments.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Spatial Codes and the Hardness of String Folding Problems (Extended Abstract).
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

All Pairs Shortest Paths in Weighted Directed Graphs ¾ Exact and Almost Exact Algorithms.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
Amplification by Read-Once Formulas.
SIAM J. Comput., 1997

All Pairs Almost Shortest Paths
Electronic Colloquium on Computational Complexity (ECCC), 1997

Finding and Counting Given Length Cycles.
Algorithmica, 1997

All-Pairs Small-Stretch Paths.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

A 7/8-Approximation Algorithm for MAX 3SAT?
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

The Communication Complexity of the Universal Relation.
Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996
The Complexity of Mean Payoff Games on Graphs.
Theor. Comput. Sci., 1996

A Note on Busy Beavers and Other Creatures.
Mathematical Systems Theory, 1996

An Optimal Randomised Logarithmic Time Connectivity Algorithm for the EREW PRAM.
J. Comput. Syst. Sci., 1996

On the Number of ANDs Versus the Number of ORs in Monotone Boolean Circuits.
Inf. Process. Lett., 1996

Growth Functions and Automatic Groups.
Experimental Mathematics, 1996

Finding The alpha n-Th Largest Element.
Combinatorica, 1996

Optimal randomized EREW PRAM Algorithms for Finding Spanning Forests and for other Basic Graph Connectivity Problems.
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Median Selection Requires (2+epsilon)n Comparisons.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

All Pairs Almost Shortest Paths.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
The Smallest Networks on Which the Ford-Fulkerson Maximum Flow Procedure may Fail to Terminate.
Theor. Comput. Sci., 1995

Tighter Lower Bounds on the Exact Complexity of String Matching.
SIAM J. Comput., 1995

Color-Coding.
J. ACM, 1995

The Complexity of Mean Payoff Games on Graphs
Electronic Colloquium on Computational Complexity (ECCC), 1995

Selecting the Median
Electronic Colloquium on Computational Complexity (ECCC), 1995

Selecting the Median.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Optimal deterministic approximate parallel prefix sums and their applications.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Finding percentile elements.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Looking for MUM and DAD: Text-Text Comparisons Do Help.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1995

The Complexity of Mean Payoff Games.
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

1994
Faster Parallel String Matching via Larger Deterministic Samples.
J. Algorithms, 1994

Color-Coding
Electronic Colloquium on Computational Complexity (ECCC), 1994

How Do Read-Once Formulae Shrink?
Combinatorics, Probability & Computing, 1994

Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

An Optimal Randomized Logarithmic Time Connectivity algorithm for the EREW PRAM (Extended Abstract).
Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

Finding Even Cycles Even Faster.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

Finding and Counting Given Length Cycles (Extended Abstract).
Proceedings of the Algorithms, 1994

1993
The Memory Game.
Theor. Comput. Sci., 1993

Shrinkage of de Morgan Formulae under Restriction.
Random Struct. Algorithms, 1993

Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication.
Computational Complexity, 1993

Which Patterns are Hard to Find?
Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

1992
Shallow Multiplication Circuits and Wise Financial Investments
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Amplification and Percolation
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991
A 4n Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions.
SIAM J. Comput., 1991

An Extension of Khrapchenko's Theorem.
Inf. Process. Lett., 1991

Shrinkage of de~Morgan formulae under restriction
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

Shallow multiplication circuits.
Proceedings of the 10th IEEE Symposium on Computer Arithmetic, 1991

1990
Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
On Neciporuk's Theorem for Branching Programs.
Theor. Comput. Sci., 1989


  Loading...