1 citations · 2 across the 10 of their papers we have counts for
14 papers
Is Randomness Necessary for Adaptive Data Analysis?
Edith Cohen, Haim Kaplan, Yishay Mansour +2
The Adaptive Data Analysis (ADA) problem formalizes the challenge of preventing false discovery and overfitting when a dataset is repeatedly reused. Formally, our input is a datase…
Load Balancing under Adaptive Bin Deletions
Haim Kaplan, Shay Sapir, Uri Stemmer
We analyze a balls-and-bins game against an adaptive adversary that sequentially deletes bins. Starting with balls distributed across bins, the adversary deletes a bin in e…
Dimension Reduction for Clustering: The Curious Case of Discrete Centers
Shaofeng H. -C. Jiang, Robert Krauthgamer, Shay Sapir +2
The Johnson-Lindenstrauss transform is a fundamental method for dimension reduction in Euclidean spaces, that can map any dataset of points into dimension with low…
On the Adversarial Robustness of Online Importance Sampling
Yotam Kenneth-Mordoch, Shay Sapir
This paper studies the adversarial-robustness of importance-sampling (aka sensitivity sampling); a useful algorithmic technique that samples elements with probabilities proportiona…
Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures
Jie Gao, Rajesh Jayaram, Benedikt Kolbe +4
Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction…
The Power of Recursive Embeddings for Metrics
Robert Krauthgamer, Nir Petruschka, Shay Sapir
Metric embedding is a powerful tool used extensively in mathematics and computer science. We devise a new method of using metric embeddings recursively, which turns out to be parti…
Parks and Recreation: Color Fault-Tolerant Spanners Made Local
Merav Parter, Asaf Petruschka, Shay Sapir +1
We provide new algorithms for constructing spanners of arbitrarily edge- or vertex-colored graphs, that can endure up to failures of entire color classes. The failure of even a…
Connectivity Labeling in Faulty Colored Graphs
Asaf Petruschka, Shay Sapir, Elad Tzalik
Fault-tolerant connectivity labelings are schemes that, given an -vertex graph and , produce succinct yet informative labels for the elements of the graph. Gi…
Moderate Dimension Reduction for -Center Clustering
Shaofeng H. -C. Jiang, Robert Krauthgamer, Shay Sapir
The Johnson-Lindenstrauss (JL) Lemma introduced the concept of dimension reduction via a random linear map, which has become a fundamental technique in many computational settings.…
Color Fault-Tolerant Spanners
Asaf Petruschka, Shay Sapir, Elad Tzalik
We initiate the study of spanners in arbitrarily vertex- or edge-colored graphs (with no "legality" restrictions), that are resilient to failures of entire color classes. When a co…
Lower Bounds for Pseudo-Deterministic Counting in a Stream
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan +1
Many streaming algorithms provide only a high-probability relative approximation. These two relaxations, of allowing approximation and randomization, seem necessary -- for many str…
Comparison of Matrix Norm Sparsification
Robert Krauthgamer, Shay Sapir
A well-known approach in the design of efficient algorithms, called matrix sparsification, approximates a matrix with a sparse matrix . Achlioptas and McSherry [2007] initi…
Smoothness of Schatten Norms and Sliding-Window Matrix Streams
Robert Krauthgamer, Shay Sapir
Large matrices are often accessed as a row-order stream. We consider the setting where rows are time-sensitive (i.e. they expire), which can be described by the sliding-window row-…
Near-Optimal Entrywise Sampling of Numerically Sparse Matrices
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan +1
Many real-world data sets are sparse or almost sparse. One method to measure this for a matrix is the \emph{numerical sparsity}, denoted $\mathsf{ns}(…