research
∙
07/27/2023
The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs
We study the reverse shortest path problem on disk graphs in the plane. ...
share
research
∙
06/27/2023
Insertion-Only Dynamic Connectivity in General Disk Graphs
Let S ⊆ℝ^2 be a set of n sites in the plane, so that every site s ∈ S ha...
research
∙
05/30/2023
Optimal energetic paths for electric cars
A weighted directed graph G=(V,A,c), where A⊆ V× V and c:A→ R, describes...
research
∙
02/27/2023
On Differentially Private Online Predictions
In this work we introduce an interactive variant of joint differential p...
research
∙
01/29/2023
Concurrent Shuffle Differential Privacy Under Continual Observation
We introduce the concurrent shuffle model of differential privacy. In th...
research
∙
01/08/2023
Dynamic Binary Search Trees: Improved Lower Bounds for the Greedy-Future Algorithm
Binary search trees (BSTs) are one of the most basic and widely used dat...
research
∙
12/26/2022
Codes for Load Balancing in TCAMs: Size Analysis
Traffic splitting is a required functionality in networks, for example f...
research
∙
09/16/2022
Fast approximation of search trees on trees with centroid trees
Search trees on trees (STTs) generalize the fundamental binary search tr...
research
∙
07/18/2022
Almost Tight Bounds for Online Facility Location in the Random-Order Model
We study the online facility location problem with uniform facility cost...
research
∙
05/20/2022
Expander Decomposition with Fewer Inter-Cluster Edges Using a Spectral Cut Player
A (ϕ,ϵ)-Expander-decomposition of a graph G is a partition of V into clu...
research
∙
02/10/2022
Monotone Learning
The amount of training-data is one of the key factors which determines t...
research
∙
12/29/2021
Optimal Weighted Load Balancing in TCAMs
Traffic splitting is a required functionality in networks, for example f...
research
∙
12/29/2021
Differentially-Private Clustering of Easy Instances
Clustering is a fundamental problem in data analysis. In differentially ...
research
∙
11/26/2021
A Note on Sanitizing Streams with Differential Privacy
The literature on data sanitization aims to design algorithms that take ...
research
∙
11/07/2021
Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds
A dynamic algorithm against an adaptive adversary is required to be corr...
research
∙
10/19/2021
FriendlyCore: Practical Differentially Private Aggregation
Differentially private algorithms for common metric aggregation tasks, s...
research
∙
10/11/2021
Differentially Private Approximate Quantiles
In this work we study the problem of differentially private (DP) quantil...
research
∙
06/28/2021
Dynamic Connectivity in Disk Graphs
Let S be a set of n sites, each associated with a point in ℝ^2 and a rad...
research
∙
06/05/2021
Differentially Private Multi-Armed Bandits in the Shuffle Model
We give an (ε,δ)-differentially private algorithm for the multi-armed ba...
research
∙
04/12/2021
Online Weighted Bipartite Matching with a Sample
We study the classical online bipartite matching problem: One side of th...
research
∙
01/31/2021
Online Markov Decision Processes with Aggregate Bandit Feedback
We study a novel variant of online finite-horizon Markov Decision Proces...
research
∙
01/26/2021
Separating Adaptive Streaming from Oblivious Streaming
We present a streaming problem for which every adversarially-robust stre...
research
∙
01/12/2021
Locality Sensitive Hashing for Efficient Similar Polygon Retrieval
Locality Sensitive Hashing (LSH) is an effective method of indexing a se...
research
∙
10/02/2020
The Sparse Vector Technique, Revisited
We revisit one of the most basic and widely applicable techniques in the...
research
∙
06/22/2020
Duality-based approximation algorithms for depth queries and maximum depth
We design an efficient data structure for computing a suitably defined a...
research
∙
05/17/2020
Output sensitive algorithms for approximate incidences and their applications
An ϵ-approximate incidence between a point and some geometric object (li...
research
∙
05/11/2020
On Radial Isotropic Position: Theory and Algorithms
We review the theory of, and develop algorithms for transforming a finit...
research
∙
04/16/2020
Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
We present a differentially private learner for halfspaces over a finite...
research
∙
04/15/2020
Locality Sensitive Hashing for Set-Queries, Motivated by Group Recommendations
Locality Sensitive Hashing (LSH) is an effective method to index a set o...
research
∙
04/13/2020
Adversarially Robust Streaming Algorithms via Differential Privacy
A streaming algorithm is said to be adversarially robust if its accuracy...
research
∙
03/30/2020
How to Find a Point in the Convex Hull Privately
We study the question of how to compute a point in the convex hull of an...
research
∙
02/23/2020
Near-optimal Regret Bounds for Stochastic Shortest Path
Stochastic shortest path (SSP) is a well-known problem in planning and c...
research
∙
11/22/2019
Privately Learning Thresholds: Closing the Exponential Gap
We study the sample complexity of learning threshold functions under the...
research
∙
11/05/2019
Apprenticeship Learning via Frank-Wolfe
We consider the applications of the Frank-Wolfe (FW) algorithm for Appre...
research
∙
07/31/2019
Influence Maximization with Few Simulations
Influence maximization (IM) is the problem of finding a set of s nodes i...
research
∙
07/11/2019
Competitive Analysis with a Sample and the Secretary Problem
We extend the standard online worst-case model to accommodate past exper...
research
∙
07/03/2019
Triangles and Girth in Disk Graphs and Transmission Graphs
Let S ⊂R^2 be a set of n sites, where each s ∈ S has an associated radiu...
research
∙
06/21/2019
Thompson Sampling for Adversarial Bit Prediction
We study the Thompson sampling algorithm in an adversarial setting, spec...
research
∙
05/23/2019
Average reward reinforcement learning with unknown mixing times
We derive and analyze learning algorithms for policy evaluation, apprent...
research
∙
03/17/2019
General techniques for approximate incidences and their application to the camera posing problem
We consider the classical camera pose estimation problem that arises in ...
research
∙
02/26/2019
Planning in Hierarchical Reinforcement Learning: Guarantees for Using Local Policies
We consider a settings of hierarchical reinforcement learning, in which ...
research
∙
02/13/2019
Differentially Private Learning of Geometric Concepts
We present differentially private efficient algorithms for learning unio...
research
∙
02/13/2019
Learning and Generalization for Matching Problems
We study a classic algorithmic problem through the lens of statistical l...
research
∙
10/24/2018
Approximate Minimum-Weight Matching with Outliers under Translation
Our goal is to compare two planar point sets by finding subsets of a giv...
research
∙
06/22/2018
Improved bounds for multipass pairing heaps and path-balanced binary search trees
We revisit multipass pairing heaps and path-balanced binary search trees...
research
∙
04/21/2018
Differentially Private k-Means with Constant Multiplicative Error
We design new differentially private algorithms for the Euclidean k-mean...
research
∙
03/13/2018
Hierarchical Reinforcement Learning: Approximating Optimal Discounted TSP Using Local Policies
In this work, we provide theoretical guarantees for reward decomposition...
research
∙
02/26/2018
Representations of Sparse Distributed Networks: A Locality-Sensitive Approach
In 1999, Brodal and Fagerberg (BF) gave an algorithm for maintaining a l...
research
∙
02/20/2018
Selection from heaps, row-sorted matrices and X+Y using soft heaps
We use soft heaps to obtain simpler optimal algorithms for selecting the...
research
∙
01/09/2018