Uri Zwick's home page

Uri Zwick

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)

·         Algorithms (Undergraduate) (October 2019 – February 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 – Goldberg’s 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)

·         APPROXIMATION ALGORITHMS

·         CIRCUIT COMPLEXITY

·         DATA STRUCTURES

·         DISTANCES and SHORTEST PATHS

·         DYNAMIC GRAPH ALGORITHMS

·         GRAPH ALGORITHMS

·         MATHEMATICAL GAMES

·         MATRIX MULTIPLICATION

·         ONLINE ALGORITHMS

·         PARALLEL ALGORITHMS

·         ROUTING

·         SELECTING THE MEDIAN

·         STRING MATCHING

·         STRING FOLDING

-----

Very very old class notes (NOT MAINTAINED)

·         Boolean Circuit Complexity (Fall 94/95, Tel Aviv)

·         Boolean Circuit Complexity (Fall 96/97, Berkeley)