1 citations · 2 across the 10 of their papers we have counts for
3 papers · 1 filter
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…