Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)
Haim Kaplan, Shay Sapir, and Uri Stemmer. Load Balancing Under Adaptive Bin Deletions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 54:1-54:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)
@InProceedings{kaplan_et_al:LIPIcs.APPROX/RANDOM.2026.54,
author = {Kaplan, Haim and Sapir, Shay and Stemmer, Uri},
title = {{Load Balancing Under Adaptive Bin Deletions}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
pages = {54:1--54:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-449-9},
ISSN = {1868-8969},
year = {2026},
volume = {392},
editor = {Singh, Mohit and Gur, Tom},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.54},
URN = {urn:nbn:de:0030-drops-277711},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2026.54},
annote = {Keywords: Balls and Bins, Adaptive Adversary}
}
Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)
Yotam Kenneth-Mordoch and Shay Sapir. On the Adversarial Robustness of Online Importance Sampling. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 113:1-113:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)
@InProceedings{kennethmordoch_et_al:LIPIcs.ESA.2026.113,
author = {Kenneth-Mordoch, Yotam and Sapir, Shay},
title = {{On the Adversarial Robustness of Online Importance Sampling}},
booktitle = {34th Annual European Symposium on Algorithms (ESA 2026)},
pages = {113:1--113:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-445-1},
ISSN = {1868-8969},
year = {2026},
volume = {388},
editor = {Bille, Philip and Pettie, Seth and Storandt, Sabine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.113},
URN = {urn:nbn:de:0030-drops-272491},
doi = {10.4230/LIPIcs.ESA.2026.113},
annote = {Keywords: Importance sampling, Adversarial robustness, Streaming algorithms, Coresets, Cut sparsification, Subspace embedding}
}
Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)
Shaofeng H.-C. Jiang, Robert Krauthgamer, Shay Sapir, Sandeep Silwal, and Di Yue. Dimension Reduction for Clustering: The Curious Case of Discrete Centers. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 82:1-82:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)
@InProceedings{jiang_et_al:LIPIcs.ITCS.2026.82,
author = {Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Sapir, Shay and Silwal, Sandeep and Yue, Di},
title = {{Dimension Reduction for Clustering: The Curious Case of Discrete Centers}},
booktitle = {17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
pages = {82:1--82:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-410-9},
ISSN = {1868-8969},
year = {2026},
volume = {362},
editor = {Saraf, Shubhangi},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.82},
URN = {urn:nbn:de:0030-drops-253698},
doi = {10.4230/LIPIcs.ITCS.2026.82},
annote = {Keywords: dimension reduction, clustering, k-median, k-means, doubling dimension}
}
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Shaofeng H.-C. Jiang, Robert Krauthgamer, and Shay Sapir. Moderate Dimension Reduction for k-Center Clustering. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jiang_et_al:LIPIcs.SoCG.2024.64,
author = {Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Sapir, Shay},
title = {{Moderate Dimension Reduction for k-Center Clustering}},
booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)},
pages = {64:1--64:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-316-4},
ISSN = {1868-8969},
year = {2024},
volume = {293},
editor = {Mulzer, Wolfgang and Phillips, Jeff M.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.64},
URN = {urn:nbn:de:0030-drops-200095},
doi = {10.4230/LIPIcs.SoCG.2024.64},
annote = {Keywords: Johnson-Lindenstrauss transform, dimension reduction, clustering, streaming algorithms}
}
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Asaf Petruschka, Shay Sapir, and Elad Tzalik. Color Fault-Tolerant Spanners. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 88:1-88:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{petruschka_et_al:LIPIcs.ITCS.2024.88,
author = {Petruschka, Asaf and Sapir, Shay and Tzalik, Elad},
title = {{Color Fault-Tolerant Spanners}},
booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
pages = {88:1--88:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-309-6},
ISSN = {1868-8969},
year = {2024},
volume = {287},
editor = {Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.88},
URN = {urn:nbn:de:0030-drops-196160},
doi = {10.4230/LIPIcs.ITCS.2024.88},
annote = {Keywords: Fault tolerance, Graph spanners}
}
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Vladimir Braverman, Robert Krauthgamer, Aditya Krishnan, and Shay Sapir. Lower Bounds for Pseudo-Deterministic Counting in a Stream. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{braverman_et_al:LIPIcs.ICALP.2023.30,
author = {Braverman, Vladimir and Krauthgamer, Robert and Krishnan, Aditya and Sapir, Shay},
title = {{Lower Bounds for Pseudo-Deterministic Counting in a Stream}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {30:1--30:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-278-5},
ISSN = {1868-8969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.30},
URN = {urn:nbn:de:0030-drops-180827},
doi = {10.4230/LIPIcs.ICALP.2023.30},
annote = {Keywords: streaming algorithms, pseudo-deterministic, approximate counting}
}