Shay Solomon

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 84

Top Venues

CoRR

SODA

ACM Trans. Algorithms

SoCG

Publications

Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than
Optimal Euclidean Tree Covers. CoRR (2024)
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
Arboricity-Dependent Algorithms for Edge Coloring. SWAT (2024)
Shay Solomon, Amitai Uzrad, Tianyi Zhang
A Lossless Deamortization for Dynamic Greedy Set Cover. CoRR (2024)
Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, Tianyi Zhang
Faster (Δ + 1)-Edge Coloring: Breaking the m √n Time Barrier. CoRR (2024)
Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than
Optimal Euclidean Tree Covers. SoCG (2024)
Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than
Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More. SODA (2024)
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time. SODA (2024)
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
Arboricity-Dependent Algorithms for Edge Coloring. CoRR (2023)
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
Density-Sensitive Algorithms for (Δ+1)-Edge Coloring. CoRR (2023)
Hung Le, Shay Solomon
A Unified Framework for Light Spanners. STOC (2023)
Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than
Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions. CoRR (2023)
Anton Bukov, Shay Solomon, Tianyi Zhang
Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-f Time Barrier. CoRR (2023)
Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than
Shortcut Partitions in Minor-Free Graphs: Steiner Point Removal, Distance Oracles, Tree Covers, and More. CoRR (2023)
Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than
Covering Planar Metrics (and Beyond): O(1) Trees Suffice. FOCS (2023)
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time. CoRR (2023)
Hsien-Chih Chang, Jonathan Conroy, Hung Le, Lazar Milenkovic, Shay Solomon, Cuong Than
Covering Planar Metrics (and Beyond): O(1) Trees Suffice. CoRR (2023)
Shay Solomon, Amitai Uzrad
Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set. STOC (2023)
Hung Le, Lazar Milenkovic, Shay Solomon
Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function. SoCG (2023)
Shay Solomon, Amitai Uzrad
Dynamic ((1+ε)ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set. CoRR (2023)
Hung Le, Shay Solomon, Cuong Than
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier. FOCS (2023)
Hung Le, Shay Solomon, Cuong Than
Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω(log n) Lightness Barrier. CoRR (2023)
Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C. Liu, Shay Solomon
(1) Update Time. ACM Trans. Algorithms 18 (2) (2022)
Hung Le, Lazar Milenkovic, Shay Solomon, Virginia Vassilevska Williams
Dynamic Matching Algorithms Under Vertex Updates. ITCS (2022)
Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon, Amitai Uzrad
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds. SOSA (2022)
Shiri Antaki, Quanquan C. Liu, Shay Solomon
Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems. ITCS (2022)
Hung Le, Lazar Milenkovic, Shay Solomon
Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound. SoCG (2022)
Hung Le, Shay Solomon
Near-Optimal Spanners for General Graphs in (Nearly) Linear Time. SODA (2022)
Omri Kahalon, Hung Le, Lazar Milenkovic, Shay Solomon
Can't See the Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners. PODC (2022)
Shay Solomon
Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs. CoRR (2021)
Omri Kahalon, Hung Le, Lazar Milenkovic, Shay Solomon
Can't See The Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners. CoRR (2021)
Adir Morgan, Shay Solomon, Nicole Wein
Simple Combinatorial Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs. CoRR (2021)
Hung Le, Lazar Milenkovic, Shay Solomon
Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound. CoRR (2021)
Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon, Amitai Uzrad
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds. CoRR (2021)
Hung Le, Shay Solomon
Near-Optimal Spanners for General Graphs in (Nearly) Linear Time. CoRR (2021)
Adir Morgan, Shay Solomon, Nicole Wein
Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial. DISC (2021)
Hung Le, Shay Solomon
A Unified Framework of Light Spanners II: Fine-Grained Optimality. CoRR (2021)
Hung Le, Shay Solomon
Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions. CoRR (2021)
Sepehr Assadi, Shay Solomon
Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach. CoRR (2021)
Sepehr Assadi, Shay Solomon
Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach. ESA (2021)
Haim Kaplan, Shay Solomon
Dynamic Representations of Sparse Distributed Networks: A Locality-sensitive Approach. ACM Trans. Parallel Comput. 8 (1) (2021)
Noam Solomon, Shay Solomon
A Generalized Matching Reconfiguration Problem. ITCS (2021)
Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein
Fully Dynamic MIS in Uniformly Sparse Graphs. ACM Trans. Algorithms 16 (2) (2020)
Hung Le, Shay Solomon
Light Euclidean Spanners with Steiner Points. CoRR (2020)
Arnold Filtser, Shay Solomon
The Greedy Spanner Is Existentially Optimal. SIAM J. Comput. 49 (2) (2020)
Hung Le, Shay Solomon
A Unified and Fine-Grained Approach for Light Spanners. CoRR (2020)
Shay Solomon, Nicole Wein
Improved Dynamic Graph Coloring. ACM Trans. Algorithms 16 (3) (2020)
Shiri Antaki, Quanquan C. Liu, Shay Solomon
Dynamic Distributed MIS with Improved Bounds. CoRR (2020)
Sepehr Assadi, Shay Solomon
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear-Time. CoRR (2020)
Lazar Milenkovic, Shay Solomon
A Unified Sparsification Approach for Matching Problems in Graphs of Bounded Neighborhood Independence. SPAA (2020)
Hung Le, Shay Solomon
Light Euclidean Spanners with Steiner Points. ESA (2020)
Shay Solomon, Nicole Wein
Improved Dynamic Graph Coloring. CoRR (2019)
Hung Le, Shay Solomon
Truly Optimal Euclidean Spanners. CoRR (2019)
Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, Shay Solomon
(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time. SODA (2019)
Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C. Liu, Shay Solomon
Fully Dynamic (Δ+1)-Coloring in Constant Update Time. CoRR (2019)
Sepehr Assadi, Shay Solomon
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time. ICALP (2019)
Hung Le, Shay Solomon
Truly Optimal Euclidean Spanners. FOCS (2019)
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time. SODA (2019)
Haim Kaplan, Shay Solomon
Representations of Sparse Distributed Networks: A Locality-Sensitive Approach. CoRR (2018)
Shay Solomon
Dynamic Approximate Matchings with an Optimal Recourse Bound. CoRR (2018)
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time. CoRR (2018)
Shirel Attali, Merav Parter, David Peleg, Shay Solomon
Wireless Expanders. SPAA (2018)
Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein
Fully Dynamic MIS in Uniformly Sparse Graphs. CoRR (2018)
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon
Fully Dynamic Maximal Independent Set with Sublinear Update Time. CoRR (2018)
Haim Kaplan, Shay Solomon
Dynamic Representations of Sparse Distributed Networks: A Locality-Sensitive Approach. SPAA (2018)
Shirel Attali, Merav Parter, David Peleg, Shay Solomon
Wireless Expanders. CoRR (2018)
Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein
Fully Dynamic MIS in Uniformly Sparse Graphs. ICALP (2018)
Shay Solomon, Nicole Wein
Improved Dynamic Graph Coloring. ESA (2018)
Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon
Fully dynamic maximal independent set with sublinear update time. STOC (2018)
Moses Charikar, Shay Solomon
Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier. ICALP (2018)
Shay Solomon
Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs. ITCS (2018)
Moses Charikar, Shay Solomon
Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds. CoRR (2017)
David Peleg, Shay Solomon
Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach. SODA (2016)
Arnold Filtser, Shay Solomon
The Greedy Spanner is Existentially Optimal. CoRR (2016)
Merav Parter, David Peleg, Shay Solomon
Local-on-Average Distributed Tasks. SODA (2016)
Shay Solomon
Fully Dynamic Maximal Matching in Constant Update Time. CoRR (2016)
Arnold Filtser, Shay Solomon
The Greedy Spanner is Existentially Optimal. PODC (2016)
Shay Solomon
Fully Dynamic Maximal Matching in Constant Update Time. FOCS (2016)
Michael Elkin, Shay Solomon
Fast Constructions of Lightweight Spanners for General Graphs. ACM Trans. Algorithms 12 (3) (2016)
Ofer Neiman, Shay Solomon
Simple Deterministic Algorithms for Fully Dynamic Maximal Matching. ACM Trans. Algorithms 12 (1) (2016)
Michael Elkin, Ofer Neiman, Shay Solomon
Light Spanners. SIAM J. Discret. Math. 29 (3) (2015)
Michael Elkin, Shay Solomon
Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones. SIAM J. Comput. 44 (4) (2015)
Shay Solomon
Euclidean Steiner shallow-light trees. J. Comput. Geom. 6 (2) (2015)
T.-H. Hubert Chan, Mingfei Li, Li Ning, Shay Solomon
New Doubling Spanners: Better and Simpler. SIAM J. Comput. 44 (1) (2015)
Michael Elkin, Shay Solomon
Optimal Euclidean Spanners: Really Short, Thin, and Lanky. J. ACM 62 (5) (2015)
Lee-Ad Gottlieb, Shay Solomon
Light spanners for Snowflake Metrics. SoCG (2014)
Michael Elkin, Ofer Neiman, Shay Solomon
Light Spanners. CoRR (2014)
Shay Solomon, Michael Elkin
Balancing Degree, Diameter, and Weight in Euclidean Spanners. SIAM J. Discret. Math. 28 (3) (2014)
Lee-Ad Gottlieb, Shay Solomon
Light spanners for snowflake metrics. CoRR (2014)
Shay Solomon
Euclidean Steiner Shallow-Light Trees. SoCG (2014)
Michael Elkin, Ofer Neiman, Shay Solomon
Light Spanners. ICALP (1) (2014)
Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, Shay Solomon
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. ICALP (2) (2014)
Noam Solomon, Shay Solomon
On The Average-Case Complexity of the Bottleneck Tower of Hanoi Problem. ANALCO (2014)
Shay Solomon
From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics. STOC (2014)
Shay Solomon
Sparse Euclidean Spanners with Tiny Diameter. ACM Trans. Algorithms 9 (3) (2013)
T.-H. Hubert Chan, Mingfei Li, Li Ning, Shay Solomon
New Doubling Spanners: Better and Simpler. ICALP (1) (2013)
Michael Elkin, Shay Solomon
Fast Constructions of Light-Weight Spanners for General Graphs. SODA (2013)
Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, Shay Solomon
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds. CoRR (2013)
Ofer Neiman, Shay Solomon
Simple deterministic algorithms for fully dynamic maximal matching. STOC (2013)
Shay Solomon
From Hierarchical Partitions to Hierarchical Covers: Optimal Fault-Tolerant Spanners for Doubling Metrics CoRR (2013)
Michael Elkin, Shay Solomon
Optimal euclidean spanners: really short, thin and lanky. STOC (2013)

Shay Solomon.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Shay Solomon