Arrow Research search

Author name cluster

Haim Kaplan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

77 papers
2 author rows

Possible papers

77

FOCS Conference 2025 Conference Paper

A Little Clairvoyance Is All You Need

  • Anupam Gupta 0001
  • Haim Kaplan
  • Alexander Lindermayr
  • Jens Schlöter
  • Sorrachai Yingchareonthawornchai

We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Shortest Remaining Processing Time (SRPT) algorithm is optimal (i. e. , 1-competitive) when the job sizes are known upfront [Schrage, 1968]. But in the non-clairvoyant setting where job sizes are revealed only when the job finishes, no algorithm can be constant-competitive [Motwani, Phillips, and Torng, 1994]. We consider the $\varepsilon$-clairvoyant setting, where $\varepsilon \in[0, 1]$, and each job’s processing time becomes known once its remaining processing time equals an $\varepsilon$ fraction of its processing time. This captures settings where the system user uses the initial $(1-\varepsilon)$ fraction of a job’s processing time to learn its true length, which it can then reveal to the algorithm. The model was proposed by Yingchareonthawornchai and Torng (2017), and it smoothly interpolates between the clairvoyant setting (when $\varepsilon=1$) and the non-clairvoyant setting (when $\varepsilon=0$). In a concrete sense, we are asking: how much knowledge is required to circumvent the hardness of this problem? We show that a little knowledge is enough, and that a constant competitive algorithm exists for every constant $\varepsilon\gt 0$. More precisely, for all $\varepsilon \in(0, 1)$, we present a deterministic $\left\lceil\frac{1}{\varepsilon}\right\rceil$-competitive algorithm, which is optimal for deterministic algorithms. We also present a matching lower bound (up to a constant factor) for randomized algorithms. Our algorithm to achieve this bound is remarkably simple and applies the “optimism in the face of uncertainty” principle. For each job, we form an optimistic estimate of its length, based on the information revealed thus far and run SRPT on these optimistic estimates. The proof relies on maintaining a matching between the jobs in OPT’s queue and the algorithm’s queue, with small prefix expansion. We achieve this by carefully choosing a set of jobs to arrive earlier than their release times without changing the algorithm, and possibly helping the adversary. These early arrivals allow us to maintain structural properties inductively, giving us the tight guarantee.

Details

ICML Conference 2025 Conference Paper

Nearly Optimal Sample Complexity for Learning with Label Proportions

  • Róbert Busa-Fekete
  • Travis Dick
  • Claudio Gentile
  • Haim Kaplan
  • Tomer Koren
  • Uri Stemmer

We investigate Learning from Label Proportions (LLP), a partial information setting where examples in a training set are grouped into bags, and only aggregate label values in each bag are available. Despite the partial observability, the goal is still to achieve small regret at the level of individual examples. We give results on the sample complexity of LLP under square loss, showing that our sample complexity is essentially optimal. From an algorithmic viewpoint, we rely on carefully designed variants of Empirical Risk Minimization, and Stochastic Gradient Descent algorithms, combined with ad hoc variance reduction techniques. On one hand, our theoretical results improve in important ways on the existing literature on LLP, specifically in the way the sample complexity depends on the bag size. On the other hand, we validate our algorithmic solutions on several datasets, demonstrating improved empirical performance (better accuracy for less samples) against recent baselines.

Details

STOC Conference 2025 Conference Paper

On Differentially Private Linear Algebra

  • Haim Kaplan
  • Yishay Mansour
  • Shay Moran
  • Uri Stemmer
  • Nitzan Tur

We introduce efficient differentially private (DP) algorithms for several linear algebraic tasks, including solving linear equalities over arbitrary fields, linear inequalities over the reals, and computing affine spans and convex hulls. As an application, we obtain efficient DP algorithms for learning halfspaces and affine subspaces. Our algorithms addressing equalities are strongly polynomial, whereas those addressing inequalities are weakly polynomial. Furthermore, this distinction is inevitable: no DP algorithm for linear programming can be strongly polynomial-time efficient.

Details

NeurIPS Conference 2025 Conference Paper

Private Set Union with Multiple Contributions

  • Travis Dick
  • Haim Kaplan
  • Alex Kulesza
  • Uri Stemmer
  • Ziteng Sun
  • Ananda Theertha Suresh

In the private set union problem each user owns a bag of at most $k$ items (from some large universe of items), and we are interested in computing the union of the items in the bags of all of the users. This is trivial without privacy, but a differentially private algorithm must be careful about reporting items contained in only a small number of bags. We consider differentially private algorithms that always report a subset of the union, and define the utility of an algorithm to be the expected size of the subset that it reports. Because the achievable utility varies significantly with the dataset, we introduce the *utility ratio*, which normalizes utility by a dataset-specific upper bound and characterizes a mechanism by its lowest normalized utility across all datasets. We then develop algorithms with guaranteed utility ratios and complement them with bounds on the best possible utility ratio. Prior work has shown that a single algorithm can be simultaneously optimal for all datasets when $k=1$, but we show that instance-optimal algorithms do not exist when $k>1$, and characterize how performance degrades as $k$ grows. At the same time, we design a private algorithm that achieves the maximum possible utility, regardless of $k$, when the item histogram matches a prior prediction (for instance, from a previous data release) and degrades gracefully with the $L_\infty$ distance between the prediction and the actual histogram when the prediction is imperfect.

PDF Details

NeurIPS Conference 2024 Conference Paper

Learning-Augmented Algorithms with Explicit Predictors

  • Marek Eliáš
  • Haim Kaplan
  • Yishay Mansour
  • Shay Moran

Recent advances in algorithmic design show how to utilize predictions obtained by machine learning models from past and present data. These approaches have demonstrated an enhancement in performance when the predictions are accurate, while also ensuring robustness by providing worst-case guarantees when predictions fail. In this paper we focus on online problems; prior research in this context was focused on a paradigm where the algorithms are oblivious of the predictors' design, treating them as a black box. In contrast, in this work, we unpack the predictor and integrate the learning problem it gives rise for within the algorithmic challenge. In particular we allow the predictor to learn as it receives larger parts of the input, with the ultimate goal of designing online learning algorithms specifically tailored for the algorithmic task at hand. Adopting this perspective, we focus on a number of fundamental problems, including caching and scheduling, which have been well-studied in the black-box setting. For each of the problems, we introduce new algorithms that take advantage of explicit and carefully designed learning rules. These pairings of online algorithms with corresponding learning rules yields improvements in the overall performance in comparison with previous work.

PDF Details DOI

NeurIPS Conference 2023 Conference Paper

Black-Box Differential Privacy for Interactive ML

  • Haim Kaplan
  • Yishay Mansour
  • Shay Moran
  • Kobbi Nissim
  • Uri Stemmer

In this work we revisit an interactive variant of joint differential privacy, recently introduced by Naor et al. [2023], and generalize it towards handling online processes in which existing privacy definitions seem too restrictive. We study basic properties of this definition and demonstrate that it satisfies (suitable variants) of group privacy, composition, and post processing. In order to demonstrate the advantages of this privacy definition compared to traditional forms of differential privacy, we consider the basic setting of online classification. We show that any (possibly non-private) learning rule can be effectively transformed to a private learning rule with only a polynomial overhead in the mistake bound. This demonstrates a stark difference with traditional forms of differential privacy, such as the one studied by Golowich and Livni [2021], where only a double exponential overhead in the mistake bound is known (via an information theoretic upper bound).

PDF Details

ICML Conference 2023 Conference Paper

Concurrent Shuffle Differential Privacy Under Continual Observation

  • Jay Tenenbaum
  • Haim Kaplan
  • Yishay Mansour
  • Uri Stemmer

We introduce the concurrent shuffle model of differential privacy. In this model we have multiple concurrent shufflers permuting messages from different, possibly overlapping, batches of users. Similarly to the standard (single) shuffler model, the privacy requirement is that the concatenation of all shuffled messages should be differentially private. We study the private continual summation problem (a. k. a. the counter problem) and show that the concurrent shuffle model allows for significantly improved error compared to a standard (single) shuffler model. Specifically, we give a summation algorithm with error $\tilde{O}(n^{1/(2k+1)})$ with $k$ concurrent shufflers on a sequence of length $n$. Furthermore, we prove that this bound is tight for any $k$, even if the algorithm can choose the sizes of the batches adaptively. For $k=\log n$ shufflers, the resulting error is polylogarithmic, much better than $\tilde{\Theta}(n^{1/3})$ which we show is the smallest possible with a single shuffler. We use our online summation algorithm to get algorithms with improved regret bounds for the contextual linear bandit problem. In particular we get optimal $\tilde{O}(\sqrt{n})$ regret with $k= \tilde{\Omega}(\log n)$ concurrent shufflers.

Details

ICML Conference 2022 Conference Paper

Differentially Private Approximate Quantiles

  • Haim Kaplan
  • Shachar Schnapp
  • Uri Stemmer

In this work we study the problem of differentially private (DP) quantiles, in which given dataset $X$ and quantiles $q_1, .. ., q_m \in [0, 1]$, we want to output $m$ quantile estimations which are as close as possible to the true quantiles and preserve DP. We describe a simple recursive DP algorithm, which we call Approximate Quantiles (AQ), for this task. We give a worst case upper bound on its error, and show that its error is much lower than of previous implementations on several different datasets. Furthermore, it gets this low error while running time two orders of magnitude faster that the best previous implementation.

Details

ICML Conference 2022 Conference Paper

FriendlyCore: Practical Differentially Private Aggregation

  • Eliad Tsfadia
  • Edith Cohen
  • Haim Kaplan
  • Yishay Mansour
  • Uri Stemmer

Differentially private algorithms for common metric aggregation tasks, such as clustering or averaging, often have limited practicality due to their complexity or to the large number of data points that is required for accurate results. We propose a simple and practical tool $\mathsf{FriendlyCore}$ that takes a set of points ${\cal D}$ from an unrestricted (pseudo) metric space as input. When ${\cal D}$ has effective diameter $r$, $\mathsf{FriendlyCore}$ returns a “stable” subset ${\cal C} \subseteq {\cal D}$ that includes all points, except possibly few outliers, and is guaranteed to have diameter $r$. $\mathsf{FriendlyCore}$ can be used to preprocess the input before privately aggregating it, potentially simplifying the aggregation or boosting its accuracy. Surprisingly, $\mathsf{FriendlyCore}$ is light-weight with no dependence on the dimension. We empirically demonstrate its advantages in boosting the accuracy of mean estimation and clustering tasks such as $k$-means and $k$-GMM, outperforming tailored methods.

Details

SODA Conference 2022 Conference Paper

Online Weighted Matching with a Sample

  • Haim Kaplan
  • David Naori
  • Danny Raz

We study the greedy-based online algorithm for edge-weighted matching with (one-sided) vertex arrivals in bipartite graphs, and edge arrivals in general graphs. This algorithm was first studied more than a decade ago by Korula and Pál for the bipartite case in the random-order model. While the weighted bipartite matching problem is solved in the random-order model, this is not the case in recent and exciting online models in which the online player is provided with a sample, and the arrival order is adversarial. The greedy-based algorithm is arguably the most natural and practical algorithm to be applied in these models. Despite its simplicity and appeal, and despite being studied in multiple works, the greedy-based algorithm was not fully understood in any of the studied online models, and its actual performance remained an open question for more than a decade. We provide a thorough analysis of the greedy-based algorithm in several online models. For vertex arrivals in bipartite graphs, we characterize the exact competitive-ratio of this algorithm in the random-order model, for any arrival order of the vertices subsequent to the sampling phase (adversarial and random orders in particular). We use it to derive tight analysis in the recent adversarial-order model with a sample (AOS model) for any sample size, providing the first result in this model beyond the simple secretary problem. Then, we generalize and strengthen the black box method of converting results in the random-order model to single-sample prophet inequalities, and use it to derive the state-of-the-art single-sample prophet inequality for the problem. Finally, we use our new techniques to analyze the greedy-based algorithm for edge arrivals in general graphs and derive results in all the mentioned online models. In this case as well, we improve upon the state-of-the-art single-sample prophet inequality.

Details

SODA Conference 2022 Conference Paper

Simulating a stack using queues

  • Haim Kaplan
  • Robert Endre Tarjan
  • Or Zamir
  • Uri Zwick

It is well known that a queue can be simulated by two stacks using a constant number of stack operations per queue operation. In this paper we consider the forgotten converse problem of simulating a stack using several queues. We consider several variants of this problem. For the offline variant, we obtain a tight upper and lower bounds for the worst-case number of queue operations needed to simulate a sequence of n stack operations using k queues. For the online variant, when the number of queues k is constant, and n is the maximum number of items in the stack at any given time, we obtain tight Θ( n 1/ k ) upper and lower bounds on the worst-case and amortized number of queue operations needed to simulate one stack operation. When k is allowed to grow with n, we prove an upper bound of O ( n 1/ k + log k n ) and a lower bound of on the amortized number of queue operations per stack operation. We also prove an upper bound of O ( kn 1/ k ) and a lower bound of Ω( n 1/ k + log k n ) on the worst-case number of queue operations per stack operation. We also show that the specific but interesting sequence of n pushes followed by n pops can be implemented much faster using a total number of only Θ( n log k n ) queue operations, for every k ≥ 2, an amortized number of Θ(log k n ) queue operations per stack operation, and this bound is tight. On the other hand, we show that the same sequence requires at least Ω( n 1/ k ) queue operations per stack operation in the worst case.

Details

NeurIPS Conference 2021 Conference Paper

Differentially Private Multi-Armed Bandits in the Shuffle Model

  • Jay Tenenbaum
  • Haim Kaplan
  • Yishay Mansour
  • Uri Stemmer

We give an $(\varepsilon, \delta)$-differentially private algorithm for the Multi-Armed Bandit (MAB) problem in the shuffle model with a distribution-dependent regret of $O\left(\left(\sum_{a: \Delta_a>0}\frac{\log T}{\Delta_a}\right)+\frac{k\sqrt{\log\frac{1}{\delta}}\log T}{\varepsilon}\right)$, and a distribution-independent regret of $O\left(\sqrt{kT\log T}+\frac{k\sqrt{\log\frac{1}{\delta}}\log T}{\varepsilon}\right)$, where $T$ is the number of rounds, $\Delta_a$ is the suboptimality gap of the action $a$, and $k$ is the total number of actions. Our upper bound almost matches the regret of the best known algorithms for the centralized model, and significantly outperforms the best known algorithm in the local model.

PDF Details

ICML Conference 2021 Conference Paper

Differentially-Private Clustering of Easy Instances

  • Edith Cohen
  • Haim Kaplan
  • Yishay Mansour
  • Uri Stemmer
  • Eliad Tsfadia

Clustering is a fundamental problem in data analysis. In differentially private clustering, the goal is to identify k cluster centers without disclosing information on individual data points. Despite significant research progress, the problem had so far resisted practical solutions. In this work we aim at providing simple implementable differentrially private clustering algorithms when the the data is "easy, " e. g. , when there exists a significant separation between the clusters. For the easy instances we consider, we have a simple implementation based on utilizing non-private clustering algorithms, and combining them privately. We are able to get improved sample complexity bounds in some cases of Gaussian mixtures and k-means. We complement our theoretical algorithms with experiments of simulated data.

Details

NeurIPS Conference 2020 Conference Paper

Adversarially Robust Streaming Algorithms via Differential Privacy

  • Avinatan Hasidim
  • Haim Kaplan
  • Yishay Mansour
  • Yossi Matias
  • 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.

PDF Details

AAAI Conference 2020 Conference Paper

Apprenticeship Learning via Frank-Wolfe

  • Tom Zahavy
  • Alon Cohen
  • Haim Kaplan
  • Yishay Mansour

We consider the applications of the Frank-Wolfe (FW) algorithm for Apprenticeship Learning (AL). In this setting, we are given a Markov Decision Process (MDP) without an explicit reward function. Instead, we observe an expert that acts according to some policy, and the goal is to find a policy whose feature expectations are closest to those of the expert policy. We formulate this problem as finding the projection of the feature expectations of the expert on the feature expectations polytope – the convex hull of the feature expectations of all the deterministic policies in the MDP. We show that this formulation is equivalent to the AL objective and that solving this problem using the FW algorithm is equivalent wellknown Projection method of Abbeel and Ng (2004). This insight allows us to analyze AL with tools from convex optimization literature and derive tighter convergence bounds on AL. Specifically, we show that a variation of the FW method that is based on taking “away steps” achieves a linear rate of convergence when applied to AL and that a stochastic version of the FW algorithm can be used to avoid precise estimation of feature expectations. We also experimentally show that this version outperforms the FW baseline. To the best of our knowledge, this is the first work that shows linear convergence rates for AL.

PDF Details

ICML Conference 2020 Conference Paper

Near-optimal Regret Bounds for Stochastic Shortest Path

  • Aviv Rosenberg 0002
  • Alon Cohen
  • Yishay Mansour
  • Haim Kaplan

Stochastic shortest path (SSP) is a well-known problem in planning and control, in which an agent has to reach a goal state in minimum total expected cost. In the learning formulation of the problem, the agent is unaware of the environment dynamics (i. e. , the transition function) and has to repeatedly play for a given number of episodes, while learning the problem’s optimal solution. Unlike other well-studied models in reinforcement learning (RL), the length of an episode is not predetermined (or bounded) and is influenced by the agent’s actions. Recently, \cite{tarbouriech2019noregret} studied this problem in the context of regret minimization, and provided an algorithm whose regret bound is inversely proportional to the square root of the minimum instantaneous cost. In this work we remove this dependence on the minimum cost—we give an algorithm that guarantees a regret bound of $\widetilde{O}(B^{3/2} S \sqrt{A K})$, where $B$ is an upper bound on the expected cost of the optimal policy, $S$ is the number of states, $A$ is the number of actions and $K$ is the total number of episodes. We additionally show that any learning algorithm must have at least $\Omega(B \sqrt{S A K})$ regret in the worst case.

Details

NeurIPS Conference 2020 Conference Paper

Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity

  • Haim Kaplan
  • Yishay Mansour
  • Uri Stemmer
  • Eliad Tsfadia

We present a differentially private learner for halfspaces over a finite grid $G$ in $\R^d$ with sample complexity $\approx d^{2. 5}\cdot 2^{\log^*|G|}$, which improves the state-of-the-art result of [Beimel et al. , COLT 2019] by a $d^2$ factor. The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem: Given a feasible collection of $m$ linear constraints of the form $Ax\geq b$, the task is to {\em privately} identify a solution $x$ that satisfies {\em most} of the constraints. Our algorithm is iterative, where each iteration determines the next coordinate of the constructed solution $x$.

PDF Details

UAI Conference 2020 Conference Paper

Unknown mixing times in apprenticeship and reinforcement learning

  • Tom Zahavy
  • Alon Cohen
  • Haim Kaplan
  • Yishay Mansour

We derive and analyze learning algorithms for apprenticeship learning, policy evaluation and policy gradient for average reward criteria. Existing algorithms explicitly require an upper bound on the mixing time. In contrast, we build on ideas from Markov chain theory and derive sampling algorithms that do not require such an upper bound. For these algorithms, we provide theoretical bounds on their sample-complexity and running time.

Details

SODA Conference 2019 Conference Paper

A sort of an adversary

  • Haim Kaplan
  • Or Zamir
  • Uri Zwick

We describe an efficient deterministic adversary that forces any comparison-based sorting algorithm to perform at least n log n comparisons. This improves on previous efficient adversaries of Atallah and Kosaraju (1981), Richards and Vaidya (1988), and of Brodal et al. (1996) that force any sorting algorithm to perform at least ψ n log n comparisons.

Details

ICML Conference 2019 Conference Paper

Differentially Private Learning of Geometric Concepts

  • Haim Kaplan
  • Yishay Mansour
  • Yossi Matias
  • Uri Stemmer

We present differentially private efficient algorithms for learning union of polygons in the plane (which are not necessarily convex). Our algorithms achieve $(\alpha, \beta)$-PAC learning and $(\epsilon, \delta)$-differential privacy using a sample of size $\tilde{O}\left(\frac{1}{\alpha\epsilon}k\log d\right)$, where the domain is $[d]\times[d]$ and $k$ is the number of edges in the union of polygons.

Details

STOC Conference 2019 Conference Paper

Faster k -SAT algorithms using biased-PPSZ

  • Thomas Dueholm Hansen
  • Haim Kaplan
  • Or Zamir
  • Uri Zwick

The PPSZ algorithm, due to Paturi, Pudlak, Saks and Zane, is currently the fastest known algorithm for the k -SAT problem, for every k >3. For 3-SAT, a tiny improvement over PPSZ was obtained by Hertli. We introduce a biased version of the PPSZ algorithm using which we obtain an improvement over PPSZ for every k ≥ 3. For k =3 we also improve on Herli’s result and get a much more noticeable improvement over PPSZ, though still relatively small. In particular, for Unique 3-SAT, we improve the current bound from 1.308 n to 1.307 n .

Details

NeurIPS Conference 2019 Conference Paper

Learning to Screen

  • Alon Cohen
  • Avinatan Hassidim
  • Haim Kaplan
  • Yishay Mansour
  • Shay Moran

Imagine a large firm with multiple departments that plans a large recruitment. Candidates arrive one-by-one, and for each candidate the firm decides, based on her data (CV, skills, experience, etc), whether to summon her for an interview. The firm wants to recruit the best candidates while minimizing the number of interviews. We model such scenarios as an assignment problem between items (candidates) and categories (departments): the items arrive one-by-one in an online manner, and upon processing each item the algorithm decides, based on its value and the categories it can be matched with, whether to retain or discard it (this decision is irrevocable). The goal is to retain as few items as possible while guaranteeing that the set of retained items contains an optimal matching. We consider two variants of this problem: (i) in the first variant it is assumed that the $n$ items are drawn independently from an unknown distribution $D$. (ii) In the second variant it is assumed that before the process starts, the algorithm has an access to a training set of $n$ items drawn independently from the same unknown distribution (e. g. \ data of candidates from previous recruitment seasons). We give tight bounds on the minimum possible number of retained items in each of these variants. These results demonstrate that one can retain exponentially less items in the second variant (with the training set). Our algorithms and analysis utilize ideas and techniques from statistical learning theory and from discrete algorithms.

PDF Details

AAAI Conference 2018 Conference Paper

Clustering Small Samples With Quality Guarantees: Adaptivity With One2all PPS

  • Edith Cohen
  • Shiri Chechik
  • Haim Kaplan

Clustering of data points is a fundamental tool in data analysis. We consider points X in a relaxed metric space, where the triangle inequality holds within a constant factor. A clustering of X is a partition of X defined by a set of points Q (centroids), according to the closest centroid. The cost of clustering X by Q is V (Q) = x∈X dxQ. This formulation generalizes classic k-means clustering, which uses squared distances. Two basic tasks, parametrized by k ≥ 1, are cost estimation, which returns (approximate) V (Q) for queries Q such that |Q| = k and clustering, which returns an (approximate) minimizer of V (Q) of size |Q| = k. When the data set X is very large, we seek efficient constructions of small samples that can act as surrogates for performing these tasks. Existing constructions that provide quality guarantees, however, are either worst-case, and unable to benefit from structure of real data sets, or make explicit strong assumptions on the structure. We show here how to avoid both these pitfalls using adaptive designs. The core of our design are the novel one2all probabilities, computed for a set M of centroids and α ≥ 1: The clustering cost of each Q with cost V (Q) ≥ V (M)/α can be estimated well from a sample of size O(α|M| −2 ). For cost estimation, we apply one2all with a bicriteria approximate M, while adaptively balancing |M| and α to optimize sample size per quality. For clustering, we present a wrapper that adaptively applies a base clustering algorithm to a sample S, using the smallest sample that provides the desired statistical guarantees on quality. We demonstrate experimentally the huge gains of using our adaptive instead of worst-case methods.

PDF Details

NeurIPS Conference 2018 Conference Paper

Differentially Private k-Means with Constant Multiplicative Error

  • Uri Stemmer
  • Haim Kaplan

We design new differentially private algorithms for the Euclidean k-means problem, both in the centralized model and in the local model of differential privacy. In both models, our algorithms achieve significantly improved error guarantees than the previous state-of-the-art. In addition, in the local model, our algorithm significantly reduces the number of interaction rounds. Although the problem has been widely studied in the context of differential privacy, all of the existing constructions achieve only super constant approximation factors. We present, for the first time, efficient private algorithms for the problem with constant multiplicative error. Furthermore, we show how to modify our algorithms so they compute private coresets for k-means clustering in both models.

PDF Details

MFCS Conference 2018 Conference Paper

Pairing heaps: the forward variant

  • Dani Dorfman
  • Haim Kaplan
  • László Kozma 0002
  • Uri Zwick

The pairing heap is a classical heap data structure introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. It is remarkable both for its simplicity and for its excellent performance in practice. The "magic" of pairing heaps lies in the restructuring that happens after the deletion of the smallest item. The resulting collection of trees is consolidated in two rounds: a left-to-right pairing round, followed by a right-to-left accumulation round. Fredman et al. showed, via an elegant correspondence to splay trees, that in a pairing heap of size n all heap operations take O(log n) amortized time. They also proposed an arguably more natural variant, where both pairing and accumulation are performed in a combined left-to-right round (called the forward variant of pairing heaps). The analogy to splaying breaks down in this case, and the analysis of the forward variant was left open. In this paper we show that inserting an item and deleting the minimum in a forward-variant pairing heap both take amortized time O(log(n) * 4^(sqrt(log n))). This is the first improvement over the O(sqrt(n)) bound showed by Fredman et al. three decades ago. Our analysis relies on a new potential function that tracks parent-child rank-differences in the heap.

Details

EWRL Workshop 2018 Workshop Paper

Planning in Hierarchical Reinforcement Learning: Guarantees for Using Local Policies

  • Tom Zahavy
  • Avinatan Hasidim
  • Haim Kaplan
  • Yishay Mansour

We provide theoretical guarantees for reward decomposition in deterministic MDPs with collectible rewards. Reward decomposition is a special case of hierarchical reinforcement learning, in which we view the reward as a sum, and we assemble a policy from policies for its components. Our approach builds on formulating this problem as a maximum traveling salesman problem with discounted reward. In particular, we focus on approximate solutions that are local, i.e., solutions that only observe information about the current state. Local policies are easy to implement and do not require substantial computational resources since they do not perform learning nor planning. Local deterministic policies, like Nearest Neighbor (NN), are being used in practice for hierarchical reinforcement learning, in particular, for 3D navigation. We propose three stochastic policies and prove that they guarantee better performance than any deterministic policy in the worst case. We then show experimentally that these policies outperform NN in deterministic MDPs with optimal options, and also in stochastic MDPs and during learning.

PDF Details

SODA Conference 2018 Conference Paper

Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic Õ ( n 5/3 ) Time

  • Pawel Gawrychowski
  • Haim Kaplan
  • Shay Mozes
  • Micha Sharir
  • Oren Weimann

We present an efficient construction of additively weighted Voronoi diagrams on planar graphs. Let G be a planar graph with n vertices and b sites that lie on a constant number of faces. We show how to preprocess G in Õ ( nb 2 ) time 1 so that one can compute any additively weighted Voronoi diagram for these sites in Õ ( b ) time. We use this construction to compute the diameter of a directed planar graph with real arc lengths in Õ ( n 5/3 ) time. This improves the recent breakthrough result of Cabello (SODA’17), both by improving the running time (from Õ ( n 11/6 )), and by providing a deterministic algorithm. It is in fact the first truly subquadratic deterministic algorithm for this problem. Our use of Voronoi diagrams to compute the diameter follows that of Cabello, but he used abstract Voronoi diagrams, which makes his diameter algorithm more involved, more expensive, and randomized. As in Cabello's work, our algorithm can also compute the Wiener index of a planar graph (i. e. , the sum of all pairwise distances) within the same bound. Our construction of Voronoi diagrams for planar graphs is of independent interest. It has already been used to obtain fast exact distance oracles for planar graphs [Cohen-Addad et al. , FOCS’17].

Details

SODA Conference 2017 Conference Paper

(1 + ∊)-Approximate f -Sensitive Distance Oracles

  • Shiri Chechik
  • Sarel Cohen
  • Amos Fiat
  • Haim Kaplan

An f -Sensitive Distance Oracle with stretch a preprocesses a graph G ( V, E ) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set F ⊂ E of at most f edges, and vertices s and t. The oracle answers a query (F, s. ,t) by returning a value d which is equal to the length of some path between s and t in the graph G\F (the graph obtained from G by discarding all edges in F). Moreover, d is at most a times the length of the shortest path between s and t in G \ F. The oracle can also construct a path between s and t in G\F of length d. To the best of our knowledge we give the first nontrivial f -sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any and a fixed ∊ > 0 our oracle answers queries ( F, s, t ) in time O (l) with (1 + ∊) stretch using a data structure of size n 2+0(1) For comparison, the naive alternative requires m f n 2 space for sublinear query time.

Details

SODA Conference 2017 Conference Paper

Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications

  • Haim Kaplan
  • Wolfgang Mulzer
  • Liam Roditty
  • Paul Seiferth
  • 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 that includes L p -norms and additively weighted Euclidean distances, and for general (convex, pair- wise disjoint) sites that have constant description complexity (line segments, disks, etc.). Our data structure has a polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat and Sharir that required O ( n ∊ ) time for an update and O (log n ) time for a query [1]. Our data structure has numerous applications, and in all of them it gives faster algorithms, typically reducing an O ( n ∊ ) factor in the bounds to polylogarithmic. To further demonstrate its effectiveness, 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 and 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 finding 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). To analyze this algorithm, we improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we plug our vertical shallow cutting construction into Chan's algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in ℝ 3. While doing this, we also revisit Chan's technique and present a variant that uses a single binary counter, with a simpler analysis and an improved amortized deletion time.

Details

SODA Conference 2017 Conference Paper

Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays

  • Yossi Azar
  • Ashish Chiplunkar
  • Haim Kaplan

We consider the problem of online Min-cost Perfect Matching with Delays (MPMD) recently introduced by Emek et al, (STOC 2016). This problem is defined on an underlying n -point metric space. An adversary presents real-time requests online at points of the metric space, and the algorithm is required to match them, possibly after keeping them waiting for some time. The cost incurred is the sum of the distances between matched pairs of requests (the connection cost), and the sum of the waiting times of the requests (the delay cost). We prove the first logarithmic upper bound and the first polylogarithmic lower bound on the randomized competitive ratio of this problem. We present an algorithm with a competitive ratio of O (log n ), which improves the upper bound of O log 2 n + logΔ) of Emek et al, by removing the dependence on Δ, the aspect ratio of the metric space (which can be unbounded as a function of n ). The core of our algorithm is a deterministic algorithm for MPMD on metrics induced by edge-weighted trees of height h, whose cost is guaranteed to be at most O (1) times the connection cost plus O (h) times the delay cost of every feasible solution. The reduction from MPMD on arbitrary metrics to MPMD on trees is achieved using the result on embedding n -point metric spaces into distributions over weighted hierarchically separated trees of height O (log n ), with distortion O (log n ). We also prove a lower bound of on the competitive ratio of any randomized algorithm. This is the first lower bound which increases with n, and is attained on the metric of n equally spaced points on a line.

Details

SODA Conference 2016 Conference Paper

Approximating the k -Level in Three-Dimensional Plane Arrangements

  • Sariel Har-Peled
  • Haim Kaplan
  • Micha Sharir

Let H be a set of n non-vertical planes in three dimensions, and let r < n be a parameter. We give a simple alternative proof of the existence of a O (1/ r )-cutting of the first n / r levels of ( H ), which consists of O ( r ) semi-unbounded vertical triangular prisms. The same construction yields an approximation of the ( n / r )-level by a terrain consisting of O ( r / ∊ 3 ) triangular faces, which lies entirely between the levels (1 ± ∊ ) n / r. The proof does not use sampling, and exploits techniques based on planar separators and various structural properties of levels in three-dimensional arrangements and of planar maps. The proof is constructive, and leads to a simple randomized algorithm, that computes the terrain in O ( n + r 2 ∊ –6 log 3 r ) expected time. An application of this technique allows us to mimic Matoušek's construction of cuttings in the plane [36], to obtain a similar construction of “layered” (1/ r )-cutting of the entire arrangement ( H ), of optimal size O ( r 3 ). Another application is a simplified optimal approximate range counting algorithm in three dimensions, competing with that of Afshani and Chan [1].

Details

STOC Conference 2015 Conference Paper

Adjacency Labeling Schemes and Induced-Universal Graphs

  • Stephen Alstrup
  • Haim Kaplan
  • Mikkel Thorup
  • 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(2 n/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.

Details

SODA Conference 2015 Conference Paper

The amortized cost of finding the minimum

  • Haim Kaplan
  • Or Zamir
  • Uri Zwick

We obtain an essentially optimal tradeoff between the amortized cost of the three basic priority queue operations insert, delete and find-min in the comparison model. More specifically, we show that for any fixed ε > 0, where n is the number of items in the priority queue and A (insert), A (delete) and A (find-min) are the amortized costs of the insert, delete and find-min operations, respectively. In particular, if A (insert) + A (delete) = O (1), then A (find-min) = Ω( n ), and A (find-min) = O ( n α ), for some α < 1, only if A (insert) + A (delete) = Ω(log n ). (We can, of course, have A (insert) = O (1), A (delete) = O (log n ), or vice versa, and A (find-min) = O (1).) Our lower bound holds even if randomization is allowed. Surprisingly, such fundamental bounds on the amortized cost of the operations were not known before. Brodal, Chaudhuri and Rad-hakrishnan, obtained similar bounds for the worst-case complexity of find-min.

Details

SODA Conference 2014 Conference Paper

Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles

  • Thomas Dueholm Hansen
  • Haim Kaplan
  • Uri Zwick

Dantzig's pivoting rule is one of the most studied pivoting rules for the simplex algorithm. While the simplex algorithm with Dantzig's rule may require an exponential number of pivoting steps on general linear programs, and even on min cost flow problems, Orlin showed that O ( mn 2 log n ) Dantzig's pivoting steps suffice to solve shortest paths problems, where n and m are the number of vertices and edges, respectively, in the graph. Post and Ye recently showed that the simplex algorithm with Dantzig's rule requires only O ( m 2 n 3 log 2 n ) pivoting steps to solve deterministic MDPs with the same discount factor for each edge, and only O ( m 3 n 5 log 2 n ) pivoting steps to solve deterministic MDPs with possibly a distinct discount factor for each edge. We improve Orlin's bound for shortest paths and Post and Ye's bound for deterministic MDPs with the same discount factor by a factor of n to O ( mn log n ), and O ( m 2 n 2 log 2 n ), respectively. We also improve by a factor of n the bound for deterministic MDPs with varying discounts when all discount factors are sufficiently close to 1. These bounds follow from a new proof technique showing that after a certain number of steps, either many edges are excluded from participating in further policies, or there is a large decrease in the value. We also obtain an Ω( n 2 ) lower bound on the number of Dantzig's pivoting steps required to solve shortest paths problems, even when m = Θ( n ). Finally, we describe a reduction from the problem of finding a minimum cost to time ratio cycle to the problem of finding an optimal policy for a discounted deterministic MDP with varying discount factors that tend to 1. This gives a strongly polynomial time algorithm for the problem that does not use Megiddo's parametric search technique.

Details

SODA Conference 2013 Conference Paper

Computing the Discrete Fréchet Distance in Subquadratic Time

  • Pankaj K. Agarwal
  • Rinat Ben Avraham
  • Haim Kaplan
  • Micha Sharir

The Fréchet distance is a similarity measure between two curves A and B that takes into account the location and ordering of the points along the two curves: Informally, it is the minimum length of a leash required to connect a dog, walking along A, and its owner, walking along B, as they walk without backtracking along their respective curves from one endpoint to the other. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on n and m specific stones on the curves A and B, respectively. These frogs hop from one stone to the next without backtracking, and the discrete Fréchet distance is the minimum length of a “leash” that connects the frogs and allows them to execute such a sequence of hops. It can be computed in quadratic time by a straightforward dynamic programming algorithm. We present the first subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane. Assuming m ≤ n, the algorithm runs in time, in the standard RAM model, using O ( n ) storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automaton.

Details

MFCS Conference 2013 Conference Paper

Minimal Indices for Successor Search - (Extended Abstract)

  • Sarel Cohen
  • Amos Fiat
  • Moshik Hershcovitch
  • Haim Kaplan

Abstract We give a new successor data structure which improves upon the index size of the Pǎtraşcu-Thorup data structures, reducing the index size from O ( n w 4/5 ) bits to O ( n log w ) bits, with optimal probe complexity. Alternatively, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z -fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra O (log w ) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of O ( n log w ) bits is known to be optimal for any such data structure. The technical contributions include highly efficient single word indices, with out-degree w /log w (compared to the w 1/5 out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest.

Details

FOCS Conference 2010 Conference Paper

Improved Bounds for Geometric Permutations

  • Natan Rubin
  • Haim Kaplan
  • Micha Sharir

We show that the number of geometric permutations of an arbitrary collection of n pairwise disjoint convex sets in R d, for d ≥ 3, is O(n 2d-3 log n), improving Wenger's 20 years old bound of O(n 2d-2 ).

Details

TCS Journal 2007 Journal Article

A simpler analysis of Burrows–Wheeler-based compression

  • Haim Kaplan
  • Shir Landau
  • Elad Verbin

In this paper, we present a new technique for worst-case analysis of compression algorithms which are based on the Burrows–Wheeler Transform. We mainly deal with the algorithm proposed by Burrows and Wheeler in their first paper on the subject [M. Burrows, D. J. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, Palo Alto, California, 1994], called bw0. This algorithm consists of the following three essential steps: (1) Obtain the Burrows–Wheeler Transform of the text, (2) Convert the transform into a sequence of integers using the move-to-front algorithm, (3) Encode the integers using Arithmetic code or any order-0 encoding (possibly with run-length encoding). We achieve a strong upper bound on the worst-case compression ratio of this algorithm. This bound is significantly better than bounds known to date and is obtained via simple analytical techniques. Specifically, we show that for any input string s, and μ > 1, the length of the compressed string is bounded by μ ⋅ | s | H k ( s ) + log ( ζ ( μ ) ) ⋅ | s | + μ g k + O ( log n ) where H k is the k th order empirical entropy, g k is a constant depending only on k and on the size of the alphabet, and ζ ( μ ) = 1 1 μ + 1 2 μ + ⋯ is the standard zeta function. As part of the analysis, we prove a result on the compressibility of integer sequences, which is of independent interest. Finally, we apply our techniques to prove a worst-case bound on the compression ratio of a compression algorithm based on the Burrows–Wheeler Transform followed by distance coding, for which worst-case guarantees have never been given. We prove that the length of the compressed string is bounded by 1. 7286 ⋅ | s | H k ( s ) + g k + O ( log n ). This bound is better than the bound we give for bw0.

Details DOI

TCS Journal 2005 Journal Article

Performance aspects of distributed caches using TTL-based consistency

  • Edith Cohen
  • Eran Halperin
  • Haim Kaplan

The web is the largest distributed database deploying time-to-live-based weak consistency. Each object has a lifetime-duration assigned to it by its origin server. A copy of the object fetched from its origin server is received with maximum time-to-live (TTL) that equals its lifetime duration. In contrast a copy obtained through a cache have shorter TTL since the age (elapsed time since fetched from the origin) is deducted from its lifetime duration. A request served by a cache constitutes a hit if the cache has a fresh copy of the object. Otherwise, the request is considered a miss and is propagated to another server. It is evident that the number of cache misses depends on the age of the copies the cache receives. Thus, a cache that sends requests to another cache would suffer more misses than a cache that sends requests directly to an authoritative server. In this paper, we model and analyze the effect of age on the performance of various cache configurations. We consider a low-level cache that fetches objects either from their origin servers or from other caches and analyze its miss-rate as function of its fetching policy. We distinguish between three basic fetching policies, namely, fetching always from the origin, fetching always from the same high-level cache, and fetching from a “random” high-level cache. We explore the relationships between these policies in terms of the miss-rate achieved by the low-level cache, both on worst-case sequences, and on sequences generated using particular probability distributions. Guided by web caching practice, we consider two variations of the basic policies. In the first variation the high-level cache uses pre-term refreshes to keep a copy with lower age. In the second variation the low-level cache uses extended lifetime duration. We analyze how these variations affect the miss-rates. Our theoretical results help to understand how age may affect the miss-rate, and imply guidelines for improving performance of web caches.

Details DOI

FOCS Conference 2003 Conference Paper

Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs

  • Haim Kaplan
  • Moshe Lewenstein
  • Nira Shafrir
  • Maxim Sviridenko

A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem one can represent such a multigraph as a combination of at most n/sup 2/ cycle covers each taken with an appropriate multiplicity. We prove that if the d-regular multigraph does not contain more than /spl lfloor/d/2/spl rfloor/ copies of any 2-cycle then we can find a similar decomposition into 0(n/sup 2/) pairs of cycle covers where each 2-cycle occurs in at most one component of each pair. Our proof is constructive and gives a polynomial algorithm to find such decomposition. Since our applications only need one such a pair of cycle covers whose weight is at least the average weight of all pairs, we also give a simpler algorithm to extract a single such pair. This combinatorial theorem then comes handy in rounding a fractional solution of an LP relaxation of the maximum and minimum TSP problems. For maximum TSP, we obtain a tour whose weight is at least 2/3 of the weight of the longest tour, improving a previous 5/8 approximation. For minimum TSP we obtain a tour whose weight is at most 0. 842log/sub 2/ n times the optimal, improving a previous 0. 999log/sub 2/ n approximation. Utilizing a reduction from maximum TSP to the shortest superstring problem we obtain a 2. 5-approximation algorithm for the latter problem which is again much simpler than the previous one. Other applications of the rounding procedure are approximation algorithms for maximum 3-cycle cover (factor 2/3, previously 3/5) and maximum asymmetric TSP with triangle inequality (factor 10/13, previously 3/4 ).

Details

STOC Conference 2002 Conference Paper

Meldable heaps and boolean union-find

  • Haim Kaplan
  • Nira Shafrir
  • Robert Endre Tarjan

In the classical meldable heap data type we maintain an item-disjoint collection of heaps under the operations find-min , insert , delete , decrease-key , and meld . In the usual definition decrease-key and delete get the item and the heap containing it as parameters. We consider the modified problem where decrease-key and delete get only the item but not the heap containing it. We show that for this problem one of the operations find-min , decrease-key , or meld must take non-constant time. This is in contrast with the original data type in which data structures supporting all these three operations in constant time are known (both in an amortized and a worst-case setting).To establish our results for meldable heaps we consider a weaker version of the union-find problem that is of independent interest, which we call Boolean union-find . In the Boolean union-find problem the find operation is a binary predicate that gets an item x and a set A and answers positively if and only if χ ε A . We prove that the lower bounds which hold for union-find in the cell probe model hold for Boolean union-find as well.We also suggest new heap data structures implementing the modified meldable heap data type that are based on redundant binary counters. Our data structures have good worst-case bounds. The best of our data structures matches the worst-case lower bounds which we establish for the problem. The simplest of our data structures is an interesting generalization of binomial queues.

Details

FOCS Conference 1996 Conference Paper

A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems

  • Sanjeev Arora
  • Alan M. Frieze
  • Haim Kaplan

We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional matching satisfies any linear inequality, then with high probability, the new matching satisfies that linear inequality in an approximate sense. This extends the well-known LP rounding procedure of Raghavan and Thompson (1987), which is usually used to round fractional solutions of linear programs. It also solves an open problem of Luby and Nisan (1993) ("Design an NC procedure for converting near-optimum fractional matchings to near-optimum matchings. ") We use the rounding procedure to design n/sup 0(logn//spl epsiv/(2)/) time algorithms for the following: (i) an additive approximation to the 0-1 Quadratic Assignment problem (QAP); (ii) a (1+E)-approximation for "dense" instances of many well-known NP-hard problems, including (an optimization formulation of) GRAPH-ISOMORPHISM, MIN-CUT-LINEAR-ARRANGEMENT, MAX-ACYCLIC-SUBGRAPH, MIN-LINEAR-ARRANGEMENT, and BETWEENNESS. (A "dense" graph is one in which the number of edges is /spl Omega/(n/sup 2/); denseness for the other problems is defined in an analogous way).

Details

FOCS Conference 1994 Conference Paper

Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping

  • Haim Kaplan
  • Ron Shamir
  • Robert Endre Tarjan

We study the parameterized complexity of several NP-Hard graph completion problems: The minimum fill-in problem is to decide if a graph can be triangulated by adding at most k edges. We develop an O(k/sup 5/ mn+f(K)) algorithm for the problem on a graph with n vertices and m edges. In particular, this implies that the problem is fixed parameter tractable (FPT). proper interval graph completion problems, motivated by molecular biology, ask for adding edges in order to obtain a proper interval graph, so that a parameter in that graph does not exceed k. We show that the problem is FPT when k is the number of added edges. For the problem where k is the clique size, we give an O(f(k)n/sup k-1/) algorithm, so it is polynomial for fixed k. On the other hand, we prove its hardness in the parameterized hierarchy, so it is probably not FPT. Those results are obtained even when a set of edges which should not be added is given. That set can be given either explicitly or by a proper vertex coloring which the added edges should respect. >

Details