On-line available papers of Uri Zwick

-----
 

    APPROXIMATION ALGORITHMS

  1. Howard Karloff, Uri Zwick,
    A 7/8-approximation algorithm for MAX 3SAT?
    Proc. of 38th FOCS (1997), 406-415.
    Remark: Conjectures 4.3 and 4.5 are now proven.
    [Proceedings version]  [Slightly extended version]

  2. Uri Zwick,
    Approximation algorithms for constraint satisfaction problems
    involving at most three variables per constraint
    Proc. of 9th SODA (1998), 201-210.
    [Proceedings version]  [Slightly extended version]

  3. Uri Zwick,
    Finding almost satisfying assignments
    Proc. of 30th STOC (1998), 551-560.
    [Proceedings version]  [Slightly extended version]

  4. Uri Zwick,
    5. Outward rotations: a tool for rounding solutions of
    semidefinite programming relaxations, with applications
    to MAX CUT and other problems
    Proc. of 31th STOC (1999), 679-687.
    [Proceedings version]
     
  5. Eran Halperin, Uri Zwick,
    6. Approximation algorithms for MAX 4-SAT
    and rounding procedures for semidefinite programs
    Journal of Algorithms 40, 184-211 (2001).
    Preliminary version in Proc. of 7th IPCO (1999), 202-217.
    [Proceedings version]  [Draft of journal version]  [Link to journal article]
     
  6. Uri Zwick,
    7. Analyzing the MAX 2-SAT and MAX DI-CUT
    approximation algorithms of Feige and Goemans
    [manuscript]
     
  7. Noga Alon, Benny Sudakov, Uri Zwick,
    8. Constructing worst case instances for semidefinite
    programming based approximation algorithms
    SIAM Journal on Discrete Mathematics 15, 58-72 (2002).
    Preliminary version in Proc. of 12th SODA (2001), 92-100.
    [Proceedings version]  [Draft of journal version]  [Link to journal article] [Slides of a talk]
     
  8. Eran Halperin, Uri Zwick,
    9. Combinatorial approximation algorithms for the maximum directed cut problem
    Proc. of 12th SODA (2001), 1-7.
    [Proceedings version]
     
  9. Eran Halperin, Ram Nathaniel, Uri Zwick,
    10. Coloring k-colorable graphs using smaller palettes
    Proc. of 12th SODA (2001), 319-326.
    [Proceedings version]  [Journal submission]  [PowerPoint presentation]
     
  10. Eran Halperin, Uri Zwick,
    11. A unified framework for obtaining improved
    approximation algorithms for maximum graph bisection problems
    Proc. of 8th IPCO (2001), 210-225.
    To appear in Random Structures and Algorithms.
    [Proceedings version]  [Draft of journal version]
     
  11. Uri Zwick,
    12. Computer assisted proof of optimal approximability results
    Proc. of 13th SODA (2002), 496-505.
    [Proceedings version]  [PowerPoint presentation]
     
  12. Eran Halperin, Dror Livnat, Uri Zwick,
    13. MAX CUT in cubic graphs
    Proc. of 13th SODA (2002), 506-513.
    [Proceedings version]
     
  13. Uri Zwick,
    14. Semidefinite Programming based approximation algorithms
    [PowerPoint presentation]
  14. Dror Livnat, Michael Lewin, Uri Zwick,
    15. Improved rounding techniques for the MAX 2-SAT and MAX DI-CUT problems
    Proc. of 9th IPCO (2002), 67-82.
    [Draft of proceedings version]   [Link to proceedings version]  

  15. Adi Avidor, Uri Zwick,
    16. Approximating MIN k-SAT (title of proceedings version)
    Approximating MIN 2-SAT and MIN 3-SAT (title of journal version)
    Journal version submitted for publication.
    Preliminary version in the Proc. of 13th ISAAC (2002), 465-475.
    [Draft of proceedings version]   [Link to proceedings version]   [Draft of journal version]


    CIRCUIT COMPLEXITY

  1. Uri Zwick,
    2. A 4n lower bound on the combinatorial complexity of certain symmetric
    Boolean functions over the basis of unate dyadic Boolean functions
    SIAM Journal on Computing 20, 499-505 (1991)
    [Draft of journal paper]
     
  2. Michael S. Paterson, Nicholas Pippenger, Uri Zwick,
    3. Faster circuits and shorter formulae for multiple addition,
    multiplication and symmetric Boolean functions
    Proc. 31st FOCS (1990), 642-650.
    (Not available online, see next item.)
     
  3. Michael S. Paterson, Nicholas Pippenger, Uri Zwick,
    4. Optimal carry save networks
    In "Boolean Function Complexity", M.S. Paterson, editor,
    London Mathematical Society Lecture Note Series 169, pp. 174-201,
    Cambridge Univ. Press, 1992.
    [Draft of full version]
     
  4. Michael S. Paterson, Uri Zwick,
    5. Shallow circuits and concise formulae for multiple addition and multiplication
    Computational Complexity 3, 262-291 (1993)
    [Draft of full version]
     
  5. Michael S. Paterson, Uri Zwick,
    6. Shrinkage of de Morgan formulae under restriction
    Random Structures and Algorithms 4, 135-150 (1993).
    Preliminary version in Proc. 32nd FOCS (1991), 324-333.
    [Draft of full version]
     
  6. Moshe Dubiner, Uri Zwick,
    7. Amplification and Percolation
    Proc. of 33rd FOCS (1992), 258-267.
    [Proceedings version]
     
  7. Moshe Dubiner, Uri Zwick,
    8. Amplification by read-once formulae
    SIAM Journal on Computing 26, 15-38 (1997).
    [Draft of full version]  [Link to journal article]
     
  8. Moshe Dubiner, Uri Zwick,
    9. How do read-once formulae shrink?
    Combinatorics, Probability & Computing 3, 455-469 (1994).
    [Draft of full version]
     
  9. Uri Zwick,
    10. On the numbe of ANDs versus the number of ORs in monotone Boolean circuits
    Information Processing Letters 59, 29-30 (1996)
    [Draft of full version]
     
  10. Gabor Tardos, Uri Zwick,
    11. The Communication Complexity of the Universal Relation
    Proc. of 12th IEEE Conference on Computational Complexity (CCC'97), 247-259.
    [Proceedings version]
     
  11. Hana Chockler, Uri Zwick,
    12. Which formulae shrink under random restriction?
    Which bases admit non-trivial shrinkage of formulae?
    Computational Complexity 10, 28-40 (2001).
    Preliminary version in Proc. of 12th SODA (2001), 702-708.
    [Proceedings version]  [Draft of journal version]  [Link to journal version]


DATA STRUCTURES

  1. Ran Mendelson, Mikkel Thorup, Uri Zwick,
    Meldable RAM priority queues and minimum directed spanning trees
    Proc. of 15th SODA (2004), 40-48.
    [Draft of proceedings version (ps)]  [Link to proceedings version]

  2. Ran Mendelson, Robert E. Tarjan, Mikkel Thorup, Uri Zwick,
    Melding priority queues
    Full version submitted for publication
    Preliminary version in Proc. of 9th SWAT (2004), 223-235.
    [Draft of proceedings version (pdf)]  [Link to proceedings version]
    [Draft of full version]  [Presentation (ppt)]


DISTANCES AND SHORTEST PATHS

  1. Dorit Dor, Shay Halperin, Uri Zwick,
    2. All Pairs Almost Shortest Paths
    SIAM Journal on Computing 29, 1740-1759 (2000).
    Preliminary version in Proc. of 37th FOCS (1996), 452-461.
    [Proceedins version]   [Draft of full version]   [Link to journal article]
     
  2. Edith Cohen, Uri Zwick,
    3. All-Pairs Small-Stretch Paths
    Journal of Algorithms 38, 335-353 (2001).
    Proc. of 8th SODA (1997), 93-102.
    [Proceedings version]   [Draft of journal version]   [Link to journal article]
     
  3. Uri Zwick,
    4. All Pairs Shortest Paths in weighted directed graphs - exact and almost exact algorithms
    Proc. of 39th FOCS (1998), 310-319.
    [Proceedings version]  (For journal version, see next item)
     
  4. Uri Zwick,
    5. All Pairs Shortest Paths using bridging sets and rectangular matrix multiplication
    Journal of the ACM, 49, 289--317 (2002).
    [Draft of journal version (ps)]  [Link to journal article]  [Slides of a talk]
     
  5. Uri Zwick,
    6. All Pairs Lightest Shortest Paths
    Proc. of 31st STOC (1999), 61-69.
    [Proceedings version]
     
  6. Avi Shoshan, Uri Zwick,
    7. All Pairs Shortest Paths in Undirected Graphs with Integer Weights
    Proc. of 40th FOCS (1999), 605-614.
    [Proceedings version]   [Slides of a talk]
     
  7. Mikkel Thorup, Uri Zwick,
    8. Approximate Distance Oracles
    Journal of the ACM, 52, 1-24 (2005).
    Preliminary version in Proc. of 33rd STOC (2001), 183-192.
    [Draft of Proceedings version]  [Link to Proceedings version]  [Draft of journal version (ps)]  [Link to journal article]  [Presentation (ppt)]
     
  8. Uri Zwick,
    9. Exact and Approximate Distances in Graphs - A survey
    Proc. of 9th ESA (2001), 33-48.
    [Draft of proceedings version (slightly updated)]  [Link to proceedings version]  [Presentation (ppt)]
     
  9. Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick,
    10. Reachability and distance queries via 2-hop labels
    SIAM Journal on Computing 32, 1338--1355 (2003).
    Preliminary version in Proc. of 13th SODA (2002), 937-946.
    [Draft of proceedings version]  [Link to proceedings version]
    [Draft of journal version]  [Link to journal version]


DYNAMIC GRAPH ALGORITHMS

  1. Liam Roditty,  Uri Zwick,
    2. Improved dynamic reachability algorithms for directed graphs
    Proc. of 43rd FOCS (2002), 679-688.
    [Proceedins version (ps)]   [Presentation (ppt)]

  2. Liam Roditty,  Uri Zwick,
    A fully dynamic reachability algorithm for directed graphs with an almost linear update time
    Proc. of 36th STOC (2004), 184-191.
    [Preliminary version (ps)]  [Link to proceedings version]

  3. Liam Roditty,  Uri Zwick,
    On dynamic shortest paths problems
    Proc. of 12th ESA (2004), 580-591.
    [Preliminary version (ps)]   [Presentation (ppt)]


  4. Liam Roditty,  Uri Zwick,
    Dynamic approximate all-pairs shortest paths in undirected graphs
    Proc. of 45th FOCS (2004), 499-508.
    [Preliminary version (ps)]   [Presentation (ppt)]


GRAPH ALGORITHMS
  1. Uri Zwick,
    2. The smallest networks on which the Ford-Fulkerson
    maximum flow procedure may fail to terminate
    Theoretical Computer Science 148, 165-170 (1995).
    [Draft of full version]
     
  2. Noga Alon, Raphael Yuster, Uri Zwick,
    3. Color-coding
    Preliminary verison in Proc. of 26th STOC (1994), 326-335.
    Journal of the ACM 42, 844-856 (1995).
    [Proceedings version]  [Draft of full version]  [Link to journal article]
     
  3. Raphael Yuster, Uri Zwick,
    4. Finding even cycles even faster
    SIAM Journal on Discrete Mathematics 10, 209-222 (1997).
    Preliminary version in Proc. of 21st ICALP (1994), 532-543.
    [Proceedings version]  [Draft of full version]   [Link to journal article]
     
  4. Noga Alon, Raphael Yuster, Uri Zwick,
    5. Finding and counting given length cycles
    Algorithmica 17, 209--223 (1997).
    Preliminary verison in Proc. of 2nd ESA (1994), 354-364.
    [Proceedings version]  [Draft of full version]  [Link to journal article]

  5. Raphael Yuster, Uri Zwick,
    Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
    Proc. of 15th SODA (2004), 247-253.
    [Draft of proceedings version (ps)]  [Link to proceedings version]  [Presentation (ppt)]


    MATHEMATICAL GAMES

  1. Uri Zwick,
    Michael S. Paterson,
    2. The memory game
    Theoretical Computer Science 110, 169-196 (1993).
    [Draft of journal paper]
     
  2. Uri Zwick,
    Michael S. Paterson,
    3. The complexity of mean payoff games on graphs
    Theoretical Computer Science 158, 343-359 (1996).
    Preliminary version in Proc. of 1st COCOON (1995), 1-10.
    [Proceedings version]  [Draft of journal paper]
     
  3. Dorit Dor, Uri Zwick,
    4. SOKOBAN and other motion planning problems
    Computational Geometry: Theory and Applications 13, 215-228 (1999).
    [Draft of journal paper]
     
  4. Uri Zwick,
    5. Jenga
    Proc. of 13th SODA (2002), 243-246.
    [Draft of proceedings version (pdf)]  [Link to proceedings version]
    [Presentation (ppt)]  [Longer presentation (ppt)]


MATRIX MULTIPLICATION

  1. Raphael Yuster, Uri Zwick,
    2. Fast sparse matrix multiplication
    Full version submitted for publication.
    Preliminary version in Proc. of 12th ESA (2004), 604-615.
    [Draft of journal paper (pdf)] [Presentation (ppt)] 


    ON-LINE ALGORITHMS

  1. Haim Kaplan, Edith Cohen, Uri Zwick,
    2. Connection caching
    Proc. of 31st STOC (1999), 612-621.
    [Proceedings version]
     
  2. Haim Kaplan, Edith Cohen, Uri Zwick,
    3. Connection caching under various models of communication
    Proc. of 11th SPAA (2000), 54-63.
    [Proceedings version]
     
  3. Haim Kaplan, Edith Cohen, Uri Zwick,
    4. Competitive analysis of the LRFU paging algorithm
    Proc. of 7th WADS (2001), 148-154.
    To appear in Algorithmica.
    [Proceedings version]  [Journal submission]


PARALLEL ALGORITHMS

  1. Shay Halperin, Uri Zwick,
    2. An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM
    Journal of Computer and System Sciences 53, 395-416 (1996).
    A preliminary version appeared in Proc. of 6th SPAA (1994), 1-10.
    [Proceedings version]  [Draft of journal version]  [Link to journal article]
     
  2. Shay Halperin, Uri Zwick,
    3. Optimal randomized EREW PRAM algorithms for finding spanning forests
    and for other basic graph connectivity problems
    Journal of Algorithms 39, 1-46 (2001).
    A preliminary version appeared in Proc. of 7th SODA (1996), 438-447.
    [Proceedings version]  [Draft of journal version]  [Link to journal article]
     
  3. Tal Goldberg, Uri Zwick,
    4. Optimal deterministic approximate parallel prefix sums and their applications
    Proc. of 3th ISTCS (1995), 220-228.
    [Proceedings version]

    ROUTING

  1. Mikkel Thorup, Uri Zwick,
    2. Compact routing schemes
    Proc. of 13th SPAA (2001), 1-10.
    [Proceedings version] [PowerPoint presentation]
     
  2. Liam Roditty, Mikkel Thorup, Uri Zwick,
    3. Roundtrip spanners and roundtrip routing in directed graphs
    Proc. of 13th SODA (2002), 844-851.
    [Proceedings version]
      

    SELECTING THE MEDIAN

  1. Dorit Dor, Uri Zwick,
    2. Finding the alpha*n-th largest element
    Combinatorica 16, 41-58 (1996).
    Preliminary version in Proc. of 3rd ISTCS (1995), 88-97.
    [Draft of journal version]
     
  2. Dorit Dor, Uri Zwick,
    3. Selecting the median
    SIAM Journal on Computing 28, 1722-1758 (1999).
    Preliminary version in Proc. of 6th SODA (1995), 28-37.
    [Proceedings version]  [Draft of journal version]  [Link to journal article]
     
  3. Dorit Dor, Johan Håstad, Staffan Ulfberg, Uri Zwick,
    4. On lower bounds for median selection
    SIAM Journal on Discrete Mathematics 14, 299-311 (2001).
    [Draft of journal version]  [Link to journal article]
     
  4. Dorit Dor, Uri Zwick,
    5. Median selection requires (2+eps)n comparisons
    SIAM Journal on Discrete Mathematics 14, 312-325 (2001).
    Preliminary version in Proc. of 37th FOCS (1996), 125-134.
    [Proceedings version]  [Draft of journal version]  [Link to journal article]


    STRING FOLDING

  1. Ashwin Nayak, Alistair Sinclair, Uri Zwick,
    2. Spatial codes and the hardness of string folding problems
    Journal of Computational Biology 6, 13-36 (1999).
    Proc. of 9th SODA (1998), 639-648.
    [Proceedings version]  [Draft of journal paper]


STRING MATCHING

  1. Richard Cole, Ramesh Hariharan, Michael S. Paterson, Uri Zwick,
    Tighter lower bounds on the exact complexity of string matching
    SIAM Journal on Computing 24, 30-45 (1995).
    Preliminary version appeared, under a different title in
    Proc. of 2nd ISTCS (1993), 59-68.
    [Proceedings version]  [Draft of journal paper]

  2. Michael S. Paterson, Shlomit Tassa, Uri Zwick,
    Looking for MUM and DAD: text-text comparisons do help
    Proc. of 15th FSTTCS (1995), 1-10.
    [Proceedings version]

Back to Home Page