Uri Zwick's home
page
Uri Zwick
Dept. of Computer Science
Tel Aviv University
Tel Aviv 69978
Israel
E-mail: zwick at tau dot ac dot il
TEL: +972 3
6409610
FAX: +972 3 6409357
Current Courses
·
Games on
Graphs (Graduate) (October 2020 February 2021)
·
Algorithms
in Action (Undergraduate+Graduare) (October 2020 February 2021)
Past Courses
·
Algorithms
Seminar (Undergraduate) (March-June 2020)
·
Games on
Graphs (Graduate) (October 2019 February 2020)
·
Algorithms
in Action (Undergraduate) (March-June 2018)
·
Analysis of
Algorithms (Graduate) (October 2017 February 2018)
·
Algorithms
Seminar (Undergraduate) (October 2017 January 2018)
·
Algorithms
in Action (Undergraduate) (February-June 2017)
·
Advanced
Algorithms (Graduate) (November 2016 February 2016)
·
Algorithms
in Action (Undergraduate) (February-June 2016)
·
Algorithms
Seminar (Undergraduate) (February-June 2016)
·
Analysis of
Algorithms (Graduate) (October 2015 February 2016)
·
Advanced
Algorithms (Graduate) (March-June 2015)
·
Analysis of
Algorithms (Graduate) (March-June 2014)
Teaching material (Undergraduate courses)
·
Lists (Data Structures)
· Amortization
(Data Structures)
· Binary
Search Trees (Introduction) (Data Structures)
· Red-black
Trees (Data Structures)
· WAVL Trees
(Balanced Search Trees) (Data Structures)
· B-Trees
(Data Structures)
· Binary
heaps (Data Structures)
· Binomial
and Fibonacci heaps (Data Structures)
· Hashing
(Data Structures)
· Union-Find
(Disjoint Sets) (Data Structures)
· Sorting
algorithms (Algorithms)
· Selection
algorithms (Algorithms)
· Fast Fourier
Transform (Algorithms 2)
· Multiplicative
Weight Updates (Algorithms 2)
· SDP-based
approximation algorithms (Algorithms 2)
Teaching material (Graduate courses)
·
Minimum Spanning
Trees Deterministic Algorithms (Advanced Graph
Algorithms)
· Minimum
Spanning Trees Verification (Advanced Graph
Algorithms)
·
Minimum
Spanning Trees Randomized linear time algorithm (Advanced
Graph Algorithms)
·
Minimum Directed
Spanning Trees (Optimal Branchings) (Advanced Graph Algorithms)
·
Shortest
Paths Goldbergs scaling algorithm (Advanced
Graph Algorithms)
·
Maximum
non-bipartite matching (Advanced Graph Algorithms)
·
Weighted
non-bipartite matching (Advanced Graph Algorithms)
·
Matrix
Multiplication Based Graph Algorithms (Advanced
Graph Algorithms)
·
Sorting
Networks (Batcher, AKS) (Advanced Algorithms)
·
Integer
Sorting Algorithms (on the word-RAM) (Advanced
Algorithms)
·
Analysis
of Linear Probing (Advanced
Algorithms)
Survey talks
·
Randomized
Pivoting Rules for the Simplex Algorithm (AAAC
2018)
· Linear
Programming in Small Dimension (Parametrized
Complexity 2018)
· Stochastic
and non-stochastic games (2014)
· Randomized
pivoting rules for the simplex algorithm - Upper bounds (MDS
Summer School 2012)
· Randomized
pivoting rules for the simplex algorithm - Lower bounds (MDS
Summer School 2012)
· Policy
Iteration Algorithms (Dagstuhl
2010)
· Matrix
Multiplication and Graph Algorithms (NoNA Summer School 2009)
· Approximating
Distances in Graphs (Warsaw 2007)
· Approximate
Distance Oracles and Spanners with sublinear surplus (NHC
2005)
· Exact and
Approximate Distances in Graphs (ESA 2001)
Resereach talks
·
Selection
from heaps, sorted matrices and X+Y using soft heaps (2018)
· An
improved version of the Random-Facet algorithm for linear programming (STOC 2015)
·
Random-Edge
is slower than Random-Facet on abstract cubes (ICALP
2016)
· Adjacency
labeling schemes and induced-universal graphs (STOC
2015)
· Improved
upper bounds for Random-Edge and Random-Jump on abstract cubes (SODA 2014)
· A
Forward-Backward Single-Source Shortest Paths Algorithm (FOCS 2013, SICOMP 2015)
· Subexponential lower bounds for randomized pivoting rules
for the simplex algorithm (STOC 2011)
· All-pairs
shortest paths in O(n^2) time with high probability (FOCS 2010, JACM 2013)
· Discounted
deterministic Markov decision processes and discounted all-pairs shortest paths
(SODA 2009, TALG 2010)
· Soft Heaps
Simplified (SODA 2009, SICOMP 2013)
· Maximum
Overhang (SODA 2008, AMM 2009)
· A
Deterministic Subexponential Algorithm for Solving
Parity Games (SODA 2007, SICOMP 2008)
· Deterministic
rendezvous, treasure hunts and strongly universal exploration sequences (SODA 2007, TALG 2014)
· Overhang (SODA 2006, AMM 2009)
· Spanners and
emulators with sublinear distance errors (SODA
2006)
· Answering distance
queries in directed graphs using fast matrix multiplication (FOCS 2005)
· Union-Find with
Constant Time Deletions (ICALP 2005, TALG 2014)
· Melding
Priority Queues (SWAT 2004, TALG 2006)
· On Dynamic
Shortest Paths Problems (ESA 2004)
· Fast Sparse
Matrix Multiplication (ESA 2004, TALG 2005)
· Detecting short
directed cycles using rectangular matrix multiplication and dynamic programming
(SODA 2004)
· Improved
Dynamic Reachability Algorithms for Directed Graphs (FOCS
2002, SICOMP 2008)
· Jenga (SODA 2002)
· Computer assisted
proof of optimal approximability results (SODA 2002)
· Approximate
distance oracles (STOC 2001, JACM 2005)
· Coloring
k-colorable graphs using relatively small palettes (SODA
2001, JALG 2002)
· Compact routing
schemes (SPAA 2001)
On-line available papers, slides and presentations (VERY OLD, NOT
MAINTAINED)
· DISTANCES and SHORTEST PATHS
· ROUTING
Very very old class notes (NOT MAINTAINED)
· Boolean Circuit Complexity (Fall 94/95, Tel Aviv)
· Boolean Circuit Complexity (Fall 96/97, Berkeley)
