Haim Kaplan

Haim Kaplan

Auto-generated profile, based on publicly available information

Haim Kaplan

School of Computer Science, Tel Aviv University, Tel Aviv, Israel

Research Focus & Metrics

Academic Career Length

25Years (2002-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
25 April 2012 in Combinatorics, Probability and Computing
Verified
Journal Article
Closed access
PDF file
HKHaim Kaplan
Haim Kaplan
JMJiří Matoušek
Jiří Matoušek
ZSZuzana Safernová
Zuzana Safernová
MSMicha Sharir
Micha Sharir
We show that the number of unit distances determined bynpoints in ℝ3isO(n3/2), slightly improving the bound of Clarkson, Edelsbrunner, Guibas, Sharir and Welzl [5], established in 1990. The new proof uses the recently introduced polynomial partitioning technique of Guth and Katz [12]. While this paper was still in a draft stage, a similar proof of our main result was posted to the arXiv by Joshua Zahl [28].

22 September 2020 in Discrete & Computational Geometry
Verified
Journal Article
Open access
PDF file
HKHaim Kaplan
Haim Kaplan
WMWolfgang Mulzer
Wolfgang Mulzer
LRLiam Roditty
Liam Roditty
PSPaul Seiferth
Paul Seiferth
MSMicha Sharir
Micha Sharir
We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include $$L_p$$ L p -norms and additively weighted Euclidean distances. Our data structure supports general (convex, pairwise disjoint) sites that have constant description complexity (e.g., points, line segments, disks, etc.). Our structure uses $$O(n \log ^3 n)$$ O ( n log 3 n ) storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat, and Sharir which required $$O(n^{\varepsilon })$$ O ( n ε ) time for an update and $$O(\log n)$$ O ( log n ) time for a query [SICOMP 1999]. Our data structure has numerous applications. In all of them, it gives faster algorithms, typically reducing an $$O(n^{\varepsilon })$$ O ( n ε ) factor in the previous bounds to polylogarithmic. In addition, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph. To obtain this data structure, we combine and extend various techniques from the literature. Along the way, we obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for computing the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest-neighbor context, under both types of norm). To analyze this algorithm, we also improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we combine our vertical shallow cutting construction with Chan’s algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in $${{\mathbb {R}}}^3$$ R 3 . Along the way, we also revisit Chan’s technique and present a variant that uses a single binary counter, with a simpler analysis and improved amortized deletion time (by a logarithmic factor; the insertion and query costs remain asymptotically the same).

1 December 2002 in Distributed Computing
Verified
Journal Article
Closed access
PDF file
YAYehuda Afek
Yehuda Afek
ABAnat Bremler-Barr
Anat Bremler-Barr
HKHaim Kaplan
Haim Kaplan
ECEdith Cohen
Edith Cohen
MMMichael Merritt
Michael Merritt

24 November 2022 in Journal of the ACM
Verified
Journal Article
Open access
AHAvinatan Hassidim
Avinatan Hassidim
HKHaim Kaplan
Haim Kaplan
YMYishay Mansour
Yishay Mansour
YMYossi Matias
Yossi Matias
USUri Stemmer
Uri Stemmer
A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an adaptive adversary . We establish a connection between adversarial robustness of streaming algorithms and the notion of differential privacy . This connection allows us to design new adversarially robust streaming algorithms that outperform the current state-of-the-art constructions for many interesting regimes of parameters.

14 June 2015
Verified
Conference Paper
Open access
SAStephen Alstrup
Stephen Alstrup
HKHaim Kaplan
Haim Kaplan
MTMikkel Thorup
Mikkel Thorup
UZUri Zwick
Uri Zwick
We describe a way of assigning labels to the vertices of any undirected graph on up to n vertices, each composed of n/2+O(1) bits, such that given the labels of two vertices, and no other information regarding the graph, it is possible to decide whether or not the vertices are adjacent in the graph. This is optimal, up to an additive constant, and constitutes the first improvement in almost 50 years of an n/2+O(log n) bound of Moon. As a consequence, we obtain an induced-universal graph for n-vertex graphs containing only O(2n/2) vertices, which is optimal up to a multiplicative constant, solving an open problem of Vizing from 1968. We obtain similar tight results for directed graphs, tournaments and bipartite graphs.

4 January 2009
Verified
Conference Paper
Open access
ECEdith Cohen
Edith Cohen
NDNicholas Duffield
Nicholas Duffield
HKHaim Kaplan
Haim Kaplan
CLCarsten Lund
Carsten Lund
MTMikkel Thorup
Mikkel Thorup