Surveys

1. Persistent data structures   H. Kaplan
   In Handbook on Data Structures and Applications, D. Mehta and S. Sahni, editors, CRC Press, 2005
2. The Time-to-Live based consistency mechanism: Understanding performance issues and their impact   E. Cohen and H. Kaplan
   In Web Content Delivery; Web Information Systems Engineering and Internet Technologies Book Series, Vol. 2, X. Tang, X. Xueyan, X. Jianliang, and S.T. Chanson, editors, Springer, 2005

Recent stuff, yet unpublished

1. I/O Efficient Dynamic Data Structures for Longest Prefix Queries   M. Hershcovitch and H. Kaplan
   To appear in SWAT 2008
2. Tighter Estimation using Bottom-k Sketches   E. Cohen and H. Kaplan
   To appear in VLDB 2008
3. Finding path minima in incremental unrooted trees   H. Kaplan and N. Shafrir
   To appear in ESA 2008

Journal papers

1. Range Minima Queries with Respect to a Random Permutation, and Approximate Range Counting   H. Kaplan, E. Ramos, and H. Kaplan
   submitted (Preliminary version with somewhat worse results in SODA'06)
2. Processing Top-k Queries from Samples   E. Cohen, N. Grossuag, and H. Kaplan
   To appear in Computer Networks (Perliminary version in CoNEXT'06)
3. Linear-time pointer-machine algorithms for path-evaluation problems on trees and graphs   A.L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R.E. Tarjan, and J.R. Westbrook
   To appear in SIAM J. Comput. (Perliminary version in STOC'98)
4. Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra.   H.~Kaplan, N.~Rubin, and M.~Sharir
   To appear in Algorithmica (Perliminary version in ESA'07)
5. Weak epsilon-nets and interval chains   N. Alon, H. Kaplan, G. Nivasch, M. Sharir, and S. Smorodinsky
   To appear in Journal of the ACM (Perliminary version in SODA'08)
6. Online conflict free coloring for halfplanes, congruent disks, and axis-parallel rectangles   K. Chen, H. Kaplan, and M. Sharir
   To appear in ACM transactions on algorithms
7. Guarding a terrain by two watchtowers   P.K. Agarwal, S. Bereg, O. Daescu, H. Kaplan, S. Ntafos, M. Sharir, and B. Zhu
   To appear in Algorithmica (Perliminary version in SoCG'05)
8. Counting colors in boxes   H. Kaplan, N. Rubin, M. Sharir, and E. Verbin
   To appear in SIAM J. Comput. (Perliminary version in SODA'07)
9. Kinetic and dynamic data structures for closest pairs and all nearest neighbors   P. K. Agarwal, H. Kaplan, and M. Sharir
   To appear in ACM Transactions on Algorithms
10. Thin heaps, thick heaps   H. Kaplan and R.E. Tarjan
    ACM Transactions on Algorithms 4:1 (2008) article 3
11. A simpler analysis of Burrows-Wheeler based compression   H. Kaplan, S. Landau, and E. Verbin
    Theoretical Computer Science 387:3 (2007), 220-235, special issue on the Burrow-Wheeler transform (CPM 2006, best paper award)
12. Associative search in peer to peer networks: Harnessing latent semantics   E. Cohen, A Fiat, and H. Kaplan
    Computer Networks 51:8 (2007), 1861-1881
    (Based on Efficient sequences of trials in SODA'03 and Search in peer to peer networks: Harnessing latent semantics in INFOCOM'03)
13. A comparison of labeling schemes for ancestor queries   H. Kaplan, T. Milo, and R. Shabo
    Theory of Computing Systems 40:1 (2007), 55-99 (Perliminary version in SODA'02)
14. An addendum to scalable secure storage when half the system is faulty   N. Alon, H. Kaplan, M. Krivelevich, D. Malkhi, and J. Stern
    Information and Computation 205:7 (2007), 1114--1116
15. Online conflict-free coloring for intervals   K. Chen, A. Fiat, H. Kaplan, M. Levy, J. Matousek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, and E. Welzl
    SIAM J. Comput. (2006), 1342-1359
16. Kinetic and dynamic data structures for convex hulls and upper envelopes   G. Alexandron, H. Kaplan and M. Sharir
    Computational Geometry: Theory and Applications 36:2 (2007), 144-158 (Perliminary version WADS'05)
17. Spatially-decaying aggregation over a network: Model and algorithms   E. Cohen and H. Kaplan
    Journal of Computer and System Sciences 73:3 (2007), 265-288, special issue on database theoey (Perliminary version SIGMOD'04)
18. Compact labeling schemes for ancestor queries   S. Abiteboul, S. Alstrup, H. Kaplan, T. Milo, and T. Rauhe
    SIAM J. Comput. 36:5 (2006), 1295-1309 (Perliminary versions SODA'01 and SODA'02).
19. The greedy algorithm for edit distance with moves   H. Kaplan and N. Shafrir
    Information Processing Letters 97:1 (2006), 23-27.
20. Partial alphabetic trees   A. Barkan and H. Kaplan
    Journal of algorithms 58:2 (2006), 81-103 (Perliminary version ESA'02)
21. Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs   H. Kaplan, M. Lewenstein, N. Shafrir, and M. Sviridenko
    Journal of the ACM 52:4 (2005), 602-626 (Perliminary version FOCS'03)
22. Sorting signed permutations by reversals, revisited   H. Kaplan and E. Verbin
    Journal of Computer and System Sciences 70:3 (2005), 321-341, Special Issue on Bioinformatics (Perliminary version CPM'03)
23. Cell flipping in permutation diagrams   M.C. Golumbic, H. Kaplan, and E. Verbin
    Discrete Mathematics 296:1 (2005), 25-41 (Perliminary version STACS'98)
24. Performance aspects of distributed caches using TTL-based consistency   E. Cohen, E. Halperin, and H. Kaplan
    Theoretical Computer Science 331:1 (2005), 73-96 (issue of invited papers from ICALP'01)
25. The greedy algorithm for shortest superstrings   H. Kaplan and N. Shafrir
    Information Processing Letters 93:1 (2005), 13--17.
26. Nearest common ancestors: A survey and a new distributed algorithm   S. Alstrup, C. Gavoille, H. Kaplan, and T. Rauhe
    Theory of Computing Systems 37:3 (2004), 441--456 (Perliminary version in SPAA'02)
27. Balanced-replication algorithms for distribution trees   E. Cohen and H. Kaplan
    SIAM J. Comput. 34:1 (2004), 227-247 (Perliminary version ESA'02)
28. Optimal oblivious routing in polynomial time   Y. Azar, E. Cohen, A. Fiat, H. Kaplan, and H. Räcke
    Journal of Computer and System Sciences 69:3 (2004), 383-394 (Special issue of invited papers from STOC 2003)
29. Predicting and bypassing end-to-end internet service degradations   A. Bremler-Barr, E. Cohen, H. Kaplan and Y. Mansour
    IEEE Journal on Selected Areas in Communications 21:6 (2003), 961-978, Special issue on internet and WWW measurement, mapping, and modeling (Perliminary version IMW'02)
30. Making data structures confluently persistent   A. Fiat and H. Kaplan
    Journal of Algorithms 48:1 (2003), 16-58 (Special issue of invited papers from SODA 2001)
31. Reachability and distance queries via 2-hop labels   E. Cohen, E. Halperin, H. Kaplan, and U. Zwick
    SIAM J. Comput. 32:5 (2003), 1338-1355 (Preliminary version in SODA'02)
32. Connection caching: Model and algorithms   E. Cohen, H. Kaplan, U. Zwick
    Journal of Computer and System Sciences 67:1 (2003), 92-126 (Preliminary versions in STOC'99 and SPAA'00)
33. Proactive caching of DNS records: Addressing a performance bottleneck   E. Cohen, H. Kaplan
    Computer Networks 41:6 (2003), 707-726 (Preliminary version SAINT 2001)
34. Restoration by path concatenation: Fast recovery of MPLS paths   Y. Afek, A. Bremler-Barr, H. Kaplan, E. Cohen, and M. Merritt
    Distributed Computing 15:4 (2002), 273--283 (Special issue of invited papers from PODC 2001)
35. Scalable secure storage when half the system is faulty   N. Alon, H. Kaplan, M. Krivelevich, D. Malkhi, and J. Stern
    Information and Computation 174:2 (2002), 203--213 (Preliminary version in ICALP'00)
36. Competitive analysis of the LRFU paging algorithm   E. Cohen and H. Kaplan, U. Zwick
    Algorithmica 33:4 (2002), 511--516 (Preliminary version in WADS'01)
37. Prefetching the means for document transfer: A new approach for reducing Web latency   E. Cohen, H. Kaplan
    Computer Networks 39:4 (2002), 437-455 (Preliminary version in INFOCOM'00)
38. Refreshment policies for Web content caches   E. Cohen, H. Kaplan
    Computer networks 38:6 (2002), 795-808 (Preliminary version in INFOCOM 2001)
39. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems   S. Arora, A. Frieze, and H. Kaplan
    Mathematical Programming 92:1 (2002), 1-36 (Preliminary version in FOCS'96)
40. Exploiting regularities in Web traffic patterns for cache replacement   E. Cohen and H. Kaplan
    Algorithmica 33:3 (2002), 300-334 (Preliminary version in STOC'99)
41. Caching documents with variable sizes and fetching costs: An LP-based approach   E. Cohen and H. Kaplan
    Algorithmica 41:4 (2001), 41-53 (Preliminary version in SODA'99)
42. Aging through cascaded caches: Performance issues in the distribution of Web content   E. Cohen and H. Kaplan
    Computer Communication Review 41:4 (2001), 41-53 (Issue of SIGCOMM'01 papers)
43. Unique maximum matching algorithms,   H. N. Gabow, H. Kaplan, R. E. Tarjan
    Journal of Algorithms 40 (2001), 159--183 (Preliminary version in STOC'99)
44. Simple confluently persistent catenable lists  
    H. Kaplan, C. Okasaki, and R. E. Tarjan
    SIAM J. Comput. 31:11-16 (1999) 1709-1723 (Preliminary version in SWAT'98)
45. Purely functional, real-time deques with catenation   H. Kaplan and R. E. Tarjan
    journal of the ACM 31:11-16 (1999) 1709-1723 (Preliminary version in STOC'95 titled: "Persistent lists with catenation via recursive slow-down")
46. Managing TCP connections under persistent HTTP   E. Cohen, H. Kaplan, J. D. Oldham
    WWW8/Computer Networks 31:11-16 (1999) 1709-1723
47. Faster and simpler algorithm for sorting signed permutations by reversals   H. Kaplan, R. Shamir, R. E. Tarjan
    SIAM J. Comput. 29:3 (1999) 880-892 (Preliminary version in SODA'97)
48. Tractability of parameterized completion problems on chordal, strongly chordal, and proper interval graphs   H. Kaplan, R. Shamir, R. E. Tarjan
    SIAM J. Comput. 28:5 (1999) 1906-1922 (Preliminary version in FOCS'94 titled "Tractability of parameterized completion problems on chordal and interval graphs: Minimum fill-in and physical mapping.")
49. Bounded degree interval sandwich problems   H. Kaplan, R. Shamir
    Algorithmica 24:2 (1999) 96-104 (Preliminary version in ISTCS'96 titled: "Physical maps and interval sandwich problems: Bounded degrees help")
50. A new, simpler linear-time dominators algorithm   A. L. Buchsbaum, H. Kaplan, A. Rogers, and J. R. Westbrook
    ACM Transactions on Programming Languages and Systems (TOPLAS) 20:6 (1998) 1265-1296
51. Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques   H. Kaplan, R. Shamir
    SIAM J. Comput. 25:3 (1996), 540-561
52. Graph sandwich problems   M. C. Golumbic, H. Kaplan, R. Shamir
    Journal of Algorithms 19 (1995), 449-473 (Preliminary version in WG'93 titled: "Algorithms and complexity of sandwich problems in graphs")
53. Four strikes against physical mapping of DNA   P. W. Goldberg, M. C. Golumbic, H. Kaplan, R. Shamir
    Journal of Computational Biology 2:1 (1995), 139-152
54. On the complexity of DNA physical mapping   M. C. Golumbic, H. Kaplan, R. Shamir
    Advances in Applied Mathematics 15 (1994), 251-261
55. The domatic number problem on some perfect graph families   H. Kaplan, R. Shamir
    Information Processing Let. 49 (1994), 51-56.

Papers in conference proceedings

1. Summarizing data using bottom-k sketches
   E. Cohen and H. Kaplan, PODC'07
2. Algorithms and estimators for accurate summarization of internet traffic
   E. Cohen, N. Duffield, H. Kaplan, C. Lund and M. Thorup, IMC'07
3. Most Burrows-Wheeler based compressors are not optimal
   H. Kaplan and E. Verbin, CPM'07
4. Sketching unaggregated data streams for subpopulation-size queries
   E. Cohen, N. Duffield, H. Kaplan, C. Lund, and M. Thorup, PODS'07
5. Strong price of anarchy for machine load balancing
   A. Fiat, H. Kaplan, M. Levy, and S. Olonetsky, ICALP'07
6. Better landmarks within reach
   A.V. Goldberg, H. Kaplan, and R. Werneck, WEA'07
7. Computing the volume of the union of cubes
   P. K. Agarwal, H. Kaplan, and M. Sharir, SoCG'07
8. Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
   Y. Giyora and H. Kaplan, SODA'07
9. Finding the position of the k-mismatch and approximate tandem repeats
   H. Kaplan, E. Porat, and N. Shafrir, SWAT'06
10. A simpler linear-time recognition of circular-arc graphs
    H. Kaplan and Y. Nussbaum, SWAT'06
11. Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
    H. Kaplan and Y. Nussbaum, WG'06
12. Colored intersection searching via sparse rectangular matrix multiplication.
    H. Kaplan, M. Sharir, and E. Verbin, SoCG'06
13. On the price of stability for designing undirected networks with fair cost allocations.
    A. Fiat, H. Kaplan, M. Levy, S. Olonetsky, and R. Shabo, ICALP'06
14. Reach for A*: Efficient point-to-point shortest path algorithms
    A.V. Goldberg, H. Kaplan, and R. Werneck, ALENEX'06   Microsoft research technical report
15. Searching in dynamic three-dimensional convex hulls and planar Voronoi diagrams, and approximate range counting
    H. Kaplan and M. Sharir, SODA'06
16. Learning with Attribute Costs.
    H. Kaplan, E. Kushilevitz and Y. Mansour, STOC'05
17. Guarding a terrain by two watchtowers
    P. K. Agarwal, S. Bereg, O. Daescu, H. Kaplan, S. Ntafos and B. Zhu, SoCG'05
18. Efficient estimation algorithms for neighborhood variance and other moments
    E. Cohen and H. Kaplan, SODA'04
19. Dynamic rectangular intersection with priorities
    H. Kaplan, E. Molad, and R. E. Tarjan, STOC'03
20. A case for associative peer to peer overlays
    E. Cohen, A. Fiat, and H. Kaplan, First Workshop on Hot Topics in Networks (HotNets-I), 2002. (Appeared as a special issue of the Journal Computer Communication Review 33(1), 95-100 2003.)
21. Dynamic tree labeling with clues
    E. Cohen, H. Kaplan, and T. Milo, PODS'02
22. Meldable heaps and boolean union find
    H. Kaplan, N. Shafrir, and R. E. Tarjan, STOC'02
23. Union-find with deletions
    H. Kaplan, N. Shafrir, and R. E. Tarjan, SODA'02
24. Short and simple labels for small distances and other functions
    H. Kaplan and T. Milo, WADS'01
25. The age penalty and its effect on cache performance,
    E. Cohen, H. Kaplan, USITS 2001 , HTML version
26. Faster kinetic heaps and their use in broadcast scheduling,
    H. Kaplan, R. E. Tarjan, K. Tsioutsiouliklis, SODA 2001.
27. On-line complexity of monotone set systems
    H. Kaplan and M. Szegedy, SODA'99
28. Just the fax--differentiating voice and fax phone lines using call billing data (abstract)
    H. Kaplan, M. Strauss, and M. Szedegy, SODA'99 and also Proceedings of the Symposium on Quantitative Analysis for Decision Making, AT&T, 1998
29. Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators
    A. L. Buchsbaum, H. Kaplan, A. Rogers, and J. R. Westbrook, STOC'98

30. Purely functional representations of catenable sorted lists
    H. Kaplan and R. E. Tarjan, STOC'96