Shay Sapir

According to our database, Shay Sapir authored at least 13 papers between 2021 and 2026.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2026

Connectivity Labeling in Faulty Colored Graphs.

Asaf Petruschka, Shay Sapir, Elad Tzalik

Distributed Comput., June, 2026

Dimension Reduction for Clustering: The Curious Case of Discrete Centers.

Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir, Sandeep Silwal, Di Yue

Proceedings of the 17th Innovations in Theoretical Computer Science Conference, 2026

2025

On the Adversarial Robustness of Online Importance Sampling.

Yotam Kenneth-Mordoch, Shay Sapir

CoRR, July, 2025

The Power of Recursive Embeddings for ℓ_p Metrics.

Robert Krauthgamer, Nir Petruschka, Shay Sapir

CoRR, March, 2025

Parks and Recreation: Color Fault-Tolerant Spanners Made Local.

Merav Parter, Asaf Petruschka, Shay Sapir, Elad Tzalik

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures.

Jie Gao, Rajesh Jayaram, Benedikt Kolbe, Shay Sapir, Chris Schwiegelshohn, Sandeep Silwal, Erik Waingarten

Proceedings of the Forty-second International Conference on Machine Learning, 2025

The Power of Recursive Embeddings for ℓp Metrics.

Robert Krauthgamer, Nir Petruschka, Shay Sapir

Proceedings of the 66th IEEE Annual Symposium on Foundations of Computer Science, 2025

2024

Color Fault-Tolerant Spanners.

Asaf Petruschka, Shay Sapir, Elad Tzalik

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Moderate Dimension Reduction for k-Center Clustering.

Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2023

Comparison of Matrix Norm Sparsification.

Robert Krauthgamer, Shay Sapir

Algorithmica, December, 2023

Lower Bounds for Pseudo-Deterministic Counting in a Stream.

Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Smoothness of Schatten norms and sliding-window matrix streams.

Robert Krauthgamer, Shay Sapir

Inf. Process. Lett., 2022

2021

Near-Optimal Entrywise Sampling of Numerically Sparse Matrices.

Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, Shay Sapir

Proceedings of the Conference on Learning Theory, 2021