Publications
[DBLP]
Journal Publications:
H. Le and S. Solomon,
Truly Optimal Euclidean Spanners.
SIAM J. Computing (special issue of FOCS'19), 2022 (to appear).
S. Bhattacharya, F. Grandoni, J. Kulkarni, Q. Liu and S. Solomon,
Fully Dynamic (Δ+1)-Coloring in Constant Update Time.
ACM Transactions on Algorithms, 2022 (to appear).
H. Kaplan and S. Solomon,
Dynamic Representations of Sparse Distributed Networks: A Locality-Sensitive Approach.
ACM Transactions on Parallel Computing, 8(1): 1-26, 2021.
A. Filtser and S. Solomon,
The Greedy Spanner is Existentially Optimal.
SIAM J. Computing, 49(2), 429-447, 2020.
S. Solomon and N. Wein,
Improved Dynamic Graph Coloring.
ACM Transactions on Algorithms, 16(3), 41:1-41:24, 2020.
K. Onak, B. Schieber, S. Solomon and N. Wein,
Fully Dynamic MIS in Uniformly Sparse Graphs.
ACM Transactions on Algorithms, 16(2), 26:1-26:19, 2020.
M. Elkin and S. Solomon,
Fast Constructions of Light-Weight Spanners for General Graphs.
ACM Transactions on Algorithms, 12(3): 29, 2016.
O. Neiman and S. Solomon,
Simple Deterministic Algorithms for Fully Dynamic Maximal Matching.
ACM Transactions on Algorithms, 12(1): 7, 2016.
M. Elkin and S. Solomon,
Optimal Euclidean Spanners: Really Short, Thin and Lanky.
J. ACM, 62(5): 35, 2015.
M. Elkin and S. Solomon,
Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones.
SIAM J. Computing, 44(4): 996-1025, 2015.
M. Elkin, O. Neiman and S. Solomon,
SIAM J. Discrete Mathematics, 29(3): 1312-1321, 2015.
S. Solomon,
Euclidean Steiner Shallow-Light Trees.
J. Computational Geometry (special issue of SoCG 2014), 6(2): 113-139, 2015.
T.-H. H. Chan, M. Li, L. Ning and S. Solomon,
New Doubling Spanners: Better and Simpler.
SIAM J. Computing, 44(1): 37-53, 2015.
S. Solomon and M. Elkin,
Balancing Degree, Diameter and Weight in Euclidean Spanners.
SIAM J. Discrete Mathematics, 28(3): 1173-1198, 2014.
S. Solomon,
Sparse Euclidean Spanners with Tiny Diameter.
ACM Transactions on Algorithms (special issue of SODA 2011) 9(3): 28, 2013.
D. Berend, A. Sapir and S. Solomon,
The Tower of Hanoi Problem on Path Graphs.
Discrete Applied Mathematics, 160(10-11): 1465-1483, 2012.
S. Solomon,
The MST of Symmetric Disk Graphs (in Arbitrary Metric Spaces) is Light.
SIAM J. Discrete Mathematics, 26(1): 250-262, 2012.
M. Elkin and S. Solomon,
Narrow-Shallow-Low-Light Trees with and without Steiner Points.
SIAM J. Discrete Mathematics, 25(1): 181-210, 2011.
Y. Dinitz, M. Elkin and S. Solomon,
Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.
Discrete & Computational Geometry, 43(4): 736-783, 2010.
Invited by the Editors-In-Chief, J.E. Goodman, J. Pach and R. Pollack.
N. Solomon and S. Solomon,
A Natural Extension of Catalan Numbers.
J. integer sequences, 11: 08.3.5., 2008.
D. Azriel, N. Solomon and S. Solomon,
On an Infinite Family of Solvable Hanoi Graphs.
ACM Transactions on Algorithms, 5(1): 13, 2008.
Y. Dinitz and S. Solomon,
Optimality of an Algorithm Solving the Bottleneck Tower of Hanoi Problem.
ACM Transactions on Algorithms, 4(3): 25, 2008.
Conference Publications:
S. Bhattacharya, M. Costa, N. Panski and S. Solomon,
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time
Proc. of SODA 2024.
H.-C. Chang, J. Conroy, H. Le, L. Milenković, S. Solomon and C. Than,
Proc. of SODA 2024.
H.-C. Chang, J. Conroy, H. Le, L. Milenković, S. Solomon and C. Than,
Covering Planar Metrics (and Beyond): O(1) Trees Suffice.
Proc. of FOCS 2023.
H. Le, S. Solomon and C. Than,
Proc. of FOCS 2023.
H. Le, L. Milenković and S. Solomon,
Proc. of SoCG 2023.
S. Solomon and A. Uzrad,
Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set.
Proc. of STOC 2023.
H. Le and S. Solomon,
A Unified Framework for Light Spanners.
Proc. of STOC 2023.
O. Kahalon, H. Le, L. Milenković and S. Solomon,
Can't See The Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners.
Proc. of PODC 2022.
H. Le, L. Milenković and S. Solomon,
Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound.
Proc. of SoCG 2022.
H. Le, L. Milenković, S. Solomon and V. V. Williams,
Dynamic Matching Algorithms Under Vertex Updates
Proc. of ITCS 2022, 96:1-96:24. [Video@ITCS (by Lazar)]
Post-publication acknowledgement: [Brand, Nanongkai, Saranurak'19] achieves O(n^1.529) update time per vertex update for maintaining the maximum matching size in a bipartite graph where updates are on one side (referred to as the "BASIC-dynamic setting" in our work)
S. Antaki, Q. Liu and S. Solomon,
Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry-Breaking Problems.
Proc. of ITCS 2022, 7:1-7:25. [Video@ITCS (by Quanquan)]
H. Le and S. Solomon,
Near-Optimal Spanners for General Graphs in (Nearly) Linear Time.
Proc. of SODA 2022.
F. Grandoni, C. Schwiegelshohn, S. Solomon and A. Uzrad,
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds.
Proc. of SOSA 2022.
A. Morgan, S. Solomon and N. Wein,
Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial. [Video@DISC (by Adir)]
Proc. of DISC 2021, 33:1-33:19.
S. Assadi and S. Solomon,
Proc. of ESA 2021, 8:1-8:18.
N. Solomon and S. Solomon,
A Generalized Matching Reconfiguration Problem. [video@ITCS] [video2@ITCS]
Proc. of ITCS 2021, 57:1-57:20.
H. Le and S. Solomon,
Light Euclidean Spanners with Steiner Points.
Proc. of ESA 2020, 67:1-67:22.
L. Milenković and S. Solomon,
A Unified Sparsification Approach for Matching Problems in Graphs of Bounded Neighborhood Independence. [video@SPAA]
Proc. of SPAA 2020, 395-446.
H. Le and S. Solomon,
Truly Optimal Euclidean Spanners. [video@FOCS] [video@HALG] [Oded's choices]
Proc. of FOCS 2019, 1078-1100.
One of 6 highlighted papers at FOCS'19; Invited to SICOMP (special issue of FOCS'19).
S. Assadi and S. Solomon,
When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time.
Proc. of ICALP 2019, 17:1-17:17.
F. Grandoni, S. Leonardi, P. Sankowski, C. Schwiegelshohn and S. Solomon,
(1+ɛ)-Approximate Incremental Matching in Constant Deterministic Amortized Time.
Proc. of SODA 2019, 1886-1898.
S. Assadi, K. Onak, B. Schieber and S. Solomon,
Dynamic Maximal Independent Set with Sublinear in n Update Time.
Proc. of SODA 2019, 1919-1936.
S. Solomon and N. Wein,
Improved Dynamic Graph Coloring. [Eppstein's blog]
Proc. of ESA 2018, 72:1-72:16.
K. Onak, B. Schieber, S. Solomon and N. Wein,
Fully Dynamic MIS in Uniformly Sparse Graphs.
Proc. of ICALP 2018, 92:1-92:14.
M. Charikar and S. Solomon,
Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds.
Proc. of ICALP 2018, 33:1-33:14.
H. Kaplan and S. Solomon,
Dynamic Representations of Sparse Distributed Networks: A Locality-Sensitive Approach.
Proc. of SPAA 2018, 33-42.
S. Attali, M. Parter, D. Peleg and S. Solomon,
Proc. of SPAA 2018, 13-22.
S. Assadi, K. Onak, B. Schieber and S. Solomon,
Dynamic Maximal Independent Set with Sublinear Update Time.
Proc. of STOC 2018, 815-826.
S. Solomon,
Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs. [video@ITCS] [Oded's choices]
Proc. of ITCS 2018, 52:1-52:19.
S. Solomon,
Fully Dynamic Maximal Matching in Constant Update Time. [video@FOCS]
Proc. of FOCS 2016, 325-334.
A. Filtser and S. Solomon,
The Greedy Spanner is Existentially Optimal.
Proc. of PODC 2016, 9-17.
Received Best Student Paper Award.
D. Peleg and S. Solomon
Dynamic (1 + ɛ)-Approximate Matchings: A Density-Sensitive Approach.
Proc. of SODA 2016, 712-739.
M. Parter, D. Peleg and S. Solomon,
Local-On-Average Distributed Tasks.
Proc. of SODA 2016, 220-239.
M. Elkin, O. Neiman and S. Solomon,
Proc. of ICALP (1) 2014, 442-452.
T. Kopelowitz, R. Krauthgamer, E. Porat and S. Solomon,
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds.
Proc. of ICALP (2) 2014, 532-543.
S. Solomon,
Euclidean Steiner Shallow-Light Trees.
Proc. of SoCG 2014, 454-463.
L. Gottlieb and S. Solomon,
Light Spanners for Snowflake Metrics.
Proc.of SoCG 2014, 387-396.
S. Solomon,
Proc. of STOC 2014, 363-372.
The following slides (which correspond to a 90-minute talk) are devoted to the optimal degree construction.
N. Solomon and S. Solomon,
On the Average-Case Complexity of the Bottleneck Tower of Hanoi Problem.
Proc. of ANALCO 2014, 104-112.
T.-H. H. Chan, M. Li, L. Ning and S. Solomon,
New Doubling Spanners: Better and Simpler.
Proc. of ICALP 2013, 315-327.
O. Neiman and S. Solomon,
Simple Deterministic Algorithms for Fully Dynamic Maximal Matching.
Proc. of STOC 2013, 745-754.
M. Elkin and S. Solomon,
Optimal Euclidean Spanners: Really Short, Thin and Lanky.
Proc. of STOC 2013, 645-654.
M. Elkin and S. Solomon,
Fast Constructions of Light-Weight Spanners for General Graphs.
Proc. of SODA 2013, 513-525.
M. Elkin and S. Solomon,
Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones.
Proc. of FOCS 2011, 373-382.
S. Solomon,
The MST of Symmetric Disk Graphs (in Arbitrary Metric Spaces) is Light.
Proc. of WADS 2011, 692-703.
S. Solomon,
An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter.
Proc. of SODA 2011, 820-839.
Received Best Student Paper Award.
S. Solomon and M. Elkin,
Balancing Degree, Diameter and Weight in Euclidean Spanners.
Proc. of ESA 2010, 48-59.
M. Elkin and S. Solomon,
Narrow-Shallow-Low-Light Trees with and without Steiner Points.
Proc. of ESA 2009, 215-226.
Y. Dinitz and M. Elkin and S. Solomon,
Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.
Proc. of FOCS 2008, 519-528.
Y. Dinitz and S. Solomon,
On Optimal Solutions for the Bottleneck Tower of Hanoi Problem
Proc. of SOFSEM 2007, 248-259.
Y. Dinitz and S. Solomon,
Optimal Algorithms for Tower of Hanoi Problems with Relaxed Placement Rules.
Proc. of ISAAC 2006, 36-47.