I am a PhD student at the Weizmann Institute, Faculty of Mathematics and Computer Science, advised by Prof. Robert Krauthgamer.
Broadly, my research interest is in analyzing algorithms, especially those using sublinear space. More specifically, given an input (possibly a vector, a matrix or a graph), represent it using space that is sublinear in its size. This scheme is well described by sketching, streaming or sparsification algorithms.
Previously, I earned a MSc in computer science at Weizmann and a double BSc in electrical engineering and physics at the Technion.
Contact: shay.sapir@weizmann.ac.il
Publications
Connectivity Labelings in Faulty Colored Graphs.
With Asaf Petruschka and Elad Tzalik.
Manuscript, 2024. arXiv
Moderate Dimension Reduction for k-Center Clustering.
With Shaofeng H.-C. Jiang and Robert Krauthgamer.
To appear in SOCG 2024. arXiv
Color Fault-Tolerant Spanners.
With Asaf Petruschka and Elad Tzalik.
ITCS 2024. arXiv Proceeding
Lower Bounds for Pseudo-Deterministic Counting in a Stream.
With Vladimir Braverman, Robert Krauthgamer and Aditya Krishnan.
ICALP 2023. arXiv Proceeding
Comparison of Matrix Norm Sparsification.
With Robert Krauthgamer.
Algorithmica 2023. arXiv ProceedingÂSmoothness of Schatten Norms and Sliding-Window Matrix Streams.
With Robert Krauthgamer.
IPL 2022. arXiv ProceedingNear-Optimal Entrywise Sampling of Numerically Sparse Matrices.
With Vladimir Braverman, Robert Krauthgamer and Aditya Krishnan.
COLT 2021. arXiv Proceeding
Recorded talks (1:30 min and 17 min)