Uri Zwick | Academic Influence

Uri Zwick's AcademicInfluence.com Rankings

Uri Zwick

Computer Science

#2704

World Rank

#2829

Historical Rank

Database

#7312

World Rank

#7571

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Uri Zwick's Degrees

PhD Computer Science Tel Aviv University
Masters Computer Science Tel Aviv University
Bachelors Computer Science Tel Aviv University

Similar Degrees You Can Earn

Why Is Uri Zwick Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Uri Zwick is an Israeli computer scientist and mathematician known for his work on graph algorithms, in particular on distances in graphs and on the color-coding technique for subgraph isomorphism. With Howard Karloff, he is the namesake of the Karloff–Zwick algorithm for approximating the MAX-3SAT problem of Boolean satisfiability. He and his coauthors won the David P. Robbins Prize in 2011 for their work on the block-stacking problem.

(See a Problem?)

Uri Zwick's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Approximate distance oracles (2001) (628)
Reachability and distance queries via 2-hop labels (2002) (607)
Finding and counting given length cycles (1997) (525)
The Complexity of Mean Payoff Games on Graphs (1996) (510)
Color-coding (1995) (461)
All pairs shortest paths using bridging sets and rectangular matrix multiplication (2000) (300)
Fast sparse matrix multiplication (2004) (260)
All pairs almost shortest paths (1996) (249)
A deterministic subexponential algorithm for solving parity games (2006) (247)
Compact routing schemes (2001) (241)
A 7/8-approximation algorithm for MAX 3SAT? (1997) (220)
On Dynamic Shortest Paths Problems (2004) (207)
Exact and Approximate Distances in Graphs - A Survey (2001) (176)
Deterministic Constructions of Approximate Distance Oracles and Spanners (2005) (165)
Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint (1998) (160)
Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems (2002) (159)
Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor (2010) (152)
Approximate distance oracles (2001) (148)
Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to MAX CUT and other problems (1999) (138)
Spanners and emulators with sublinear distance errors (2006) (136)
All pairs shortest paths in undirected graphs with integer weights (1999) (136)
A fully dynamic reachability algorithm for directed graphs with an almost linear update time (2004) (130)
Dynamic approximate all-pairs shortest paths in undirected graphs (2004) (113)
Selecting the median (1995) (112)
Improved dynamic reachability algorithms for directed graphs (2002) (109)
SOKOBAN and other motion planning problems (1999) (100)
All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms (1998) (98)
Deterministic rendezvous, treasure hunts and strongly universal exploration sequences (2007) (91)
All-pairs small-stretch paths (1997) (89)
Finding Even Cycles Even Faster (1994) (85)
A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems (2001) (85)
Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (1994) (82)
Replacement paths and k simple shortest paths in unweighted directed graphs (2005) (80)
Subexponential lower bounds for randomized pivoting rules for the simplex algorithm (2011) (76)
Roundtrip spanners and roundtrip routing in directed graphs (2002) (73)
Shrinkage of de Morgan formulae under restriction (1991) (70)
Detecting short directed cycles using rectangular matrix multiplication and dynamic programming (2004) (69)
Listing Triangles (2014) (64)
Finding almost-satisfying assignments (1998) (57)
Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs (1999) (57)
A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths (2004) (55)
The Complexity of Mean Payoff Games (1995) (51)
Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems (1996) (51)
Computer assisted proof of optimal approximability results (2002) (51)
Adjacency Labeling Schemes and Induced-Universal Graphs (2014) (51)
Answering distance queries in directed graphs using fast matrix multiplication (2005) (47)
An Optimal Randomised Logarithmic Time Connectivity Algorithm for the EREW PRAM (1996) (46)
Combinatorial approximation algorithms for the maximum directed cut problem (2001) (44)
MAX CUT in cubic graphs (2002) (43)
An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and Its Applications to Orienting Protein Networks (2008) (42)
All-Pairs Bottleneck Paths in Vertex Weighted Graphs (2007) (40)
Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT (2005) (39)
Optimal carry save networks (1992) (36)
Spatial codes and the hardness of string folding problems (1998) (36)
Growth Functions and Automatic Groups (1996) (32)
Faster k-SAT algorithms using biased-PPSZ (2019) (31)
Tighter Lower Bounds on the Exact Complexity of String Matching (1995) (31)
Optimal deterministic approximate parallel prefix sums and their applications (1995) (31)
The Smallest Networks on Which the Ford-Fulkerson Maximum Flow Procedure may Fail to Terminate (1995) (31)
Median Selection Requires (2+epsilon)n Comparisons (2001) (30)
Finding and Counting Given Length Cycles (Extended Abstract) (1994) (30)
A 4n Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions (1991) (30)
Multicriteria Global Minimum Cuts (2004) (29)
Faster circuits and shorter formulae for multiple addition, multiplication and symmetric Boolean functions (1990) (28)
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm (2015) (28)
Cell Identification Codes for Tracking Mobile Users (1999) (27)
Approximating MIN 2-SAT and MIN 3-SAT (2005) (26)
The complexity of mean payo games on graphs (1996) (26)
An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (extended abstract) (1994) (25)
Maximum matching in graphs with an excluded minor (2007) (25)
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths (2009) (24)
Coloring k-colorable graphs using relatively small palettes (2001) (24)
All-Pairs Shortest Paths in O(n²) Time with High Probability (2010) (24)
Union-Find with Constant Time Deletions (2005) (23)
Lower Bounds for Howard's Algorithm for Finding Minimum Mean-Cost Cycles (2010) (23)
Selection from heaps, row-sorted matrices and X+Y using soft heaps (2018) (22)
A subexponential lower bound for the random facet algorithm for parity games (2011) (21)
Coloring k-colorable graphs using smaller palettes (2001) (20)
The communication complexity of the universal relation (1997) (19)
Constructing worst case instances for semidefinite programming based approximation algorithms (2001) (19)
Shallow circuits and concise formulae for multiple addition and multiplication (1993) (18)
Connection caching (1999) (18)
The Memory Game (1993) (18)
Analyzing the MAX 2-SAT and MAX DI-CUT approximation algorithms of Feige and Goemans (2000) (18)
Maximum overhang (2007) (17)
Approximating MIN k-SAT (2002) (16)
Melding priority queues (2004) (15)
Amplification and Percolation (1992) (15)
Overhang (2007) (14)
Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT (2005) (14)
Improved upper bounds for Random-Edge and Random-Jump on abstract cubes (2014) (13)
On Lower Bounds for Selecting the Median (2001) (13)
All pairs lightest shortest paths (1999) (13)
An Extension of Khrapchenko's Theorem (1991) (13)
Finding the αn-th largest element (1996) (12)
Hollow Heaps (2015) (12)
Connection caching under various models of communication (2000) (12)
Amplification by Read-Once Formulas (1997) (12)
How Do Read-Once Formulae Shrink? (1994) (10)
A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths (2006) (10)
Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles (2014) (10)
A simpler implementation and analysis of Chazelle's soft heaps (2009) (10)
Public vs. Private Randomness in Simultaneous Multi-party Communication Complexity (2016) (10)
Competitive Analysis of the LRFU Paging Algorithm (2001) (9)
Median selection requires (2+/spl epsiv/)n comparisons (1996) (9)
Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges (2019) (8)
Faster Parallel String Matching via Larger Deterministic Samples (1994) (8)
Connection caching: model and algorithms (2003) (7)
Soft Heaps Simplified (2013) (7)
A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games (2019) (7)
Fibonacci Heaps Revisited (2014) (7)
Which bases admit non-trivial shrinkage of formulae? (2002) (7)
A note on busy beavers and other creatures (1996) (6)
Random-Facet and Random-Bland require subexponential time even for shortest paths (2014) (6)
On the Approximability of Reachability-Preserving Network Orientations (2011) (6)
Shallow multiplication circuits (1991) (6)
Lecture notes on “Analysis of Algorithms”: Directed Minimum Spanning Trees (More complete but still unfinished) (2013) (5)
Efficient algorithms for the 2-gathering problem (2009) (5)
Which patterns are hard to find (1993) (5)
Meldable RAM priority queues and minimum directed spanning trees (2004) (4)
A Forward-Backward Single-Source Shortest Paths Algorithm (2013) (4)
Amplification and percolation (probabilistic Boolean functions) (1992) (4)
Random-Edge Is Slower Than Random-Facet on Abstract Cubes (2016) (4)
Algorithms - ESA 2003 (2003) (3)
Algorithmic trade-offs for girth approximation in undirected graphs (2022) (3)
Bottleneck Paths and Trees and Deterministic Graphical Games (2016) (3)
Finding percentile elements (1995) (3)
On the Mysteries of MAX NAE-SAT (2020) (3)
Lecture notes on “ Analysis of Algorithms ” : Directed Minimum Spanning Trees Lecturer : (2013) (3)
On the Number of ANDs Versus the Number of ORs in Monotone Boolean Circuits (1996) (3)
On Neciporuk's Theorem for Branching Programs (1989) (3)
Shallow multiplication circuits and wise financial investments (1992) (3)
Subexponential lower bounds for randomized pivoting rules for solving linear programs (2010) (3)
Improved circuits and formulae for multiple addition, multiplication and symmetric Boolean functions (1990) (2)
Algorithms -- ESA 2003 : 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003 : proceedings (2003) (2)
Ampliication by Read-once Formulae (1995) (2)
An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem (2008) (2)
The amortized cost of finding the minimum (2015) (2)
Improved bounds for multipass pairing heaps and path-balanced binary search trees (2018) (2)
Competitive Analysis of the LRFU Paging Algorithm (2002) (2)
Finding simple paths and cycles in graphs ∗ ( Extended Abstract ) (2002) (1)
Pairing heaps: the forward variant (2017) (1)
Dynamic Ordered Sets with Approximate Queries, Approximate Heaps and Soft Heaps (2019) (1)
Which formulae shrink under random restrictions? (2001) (1)
New Bounds for the Nearly Equitable Edge Coloring Problem (2007) (1)
Semidefinite Programming Based Approximation Algorithms (2001) (1)
Simulating a stack using queues (2022) (1)
Sokoban and Other Motion Planning Problems (extended Abstract) (1995) (1)
Optimal resizable arrays (2022) (1)
Overhang Mike Paterson (0)
Improved girth approximation in weighted undirected graphs (2023) (0)
Lecture notes for “ Analysis of Algorithms ” : Global minimum cuts ( Draft ) Lecturer : (2011) (0)
Bottleneck paths and trees and deterministic graphical (2018) (0)
Lecture notes for “ Analysis of Algorithms ” : Global minimum cuts Lecturer : (2008) (0)
Looking for MUM and DAD: Text-Text Comparisons Do Help (1995) (0)
D S ] 2 2 O ct 2 01 5 Hollow Heaps ∗ (2015) (0)
Lecture Series in IRIF : Games on Graphs and Linear Programming Abstractions (2019) (0)
Which patterns are hard to find? (String matching) (1993) (0)
Lecture notes for “ Analysis of Algorithms ” : Minimum Spanning Trees Lecturer : (2013) (0)
Finding Strong Components Using Depth-First Search (2022) (0)
Separating MAX 2-AND, MAX DI-CUT and MAX CUT (2022) (0)
Collapse (2019) (0)
Optimal Carry Save (2007) (0)
Lecture notes for “ Analysis of Algorithms ” : Maximum matching in general graphs Lecturer : (2006) (0)
Ampliication and Percolation Size O(n ) That Amplify ( (2007) (0)
Erratum: Finding and counting given length cycles (2015) (0)
Proceedings of the 9th international conference on Approximation Algorithms for Combinatorial Optimization Problems, and 10th international conference on Randomization and Computation (2006) (0)
Simple Stochastic Games, Mean Payoff Games, Parity Games (2008) (0)
A sort of an adversary (2019) (0)
Lecture notes for “ Advanced Graph Algorithms ” : Verification of Minimum Spanning Trees (2009) (0)
Maximum Overhang (extended Abstract) (2007) (0)
Lecture notes for “ Analysis of Algorithms ” : Computing shortest paths and detecting negative cycles Lecturer : (2006) (0)
TheoretiCS (2021) (0)
ON LOWER BOUNDS FOR SELECTING THE MEDIAN DORIT DOR (1996) (0)
A rigorous study of some satisflability problems (2008) (0)
A Graduate Course on Algorithms 7.1.2 Known Results (2007) (0)
Amplification and Percolat ion (1992) (0)
Lecture notes for “ Analysis of Algorithms ” : Minimum cost flow and weighted bipartite matching Lecturer : (2006) (0)

This paper list is powered by the following services:

Other Resources About Uri Zwick

en.wikipedia.org

What Schools Are Affiliated With Uri Zwick?

Uri Zwick is affiliated with the following schools: