Shay Solomon

Tianyi Zhang

CoRR, 2023

Density-Sensitive Algorithms for (Δ+1)-Edge Coloring.

[BibT_eX]

[DOI]

CoRR, 2023

Resolving the Steiner Point Removal Problem in Planar Graphs via Shortcut Partitions.

[BibT_eX]

[DOI]

CoRR, 2023

Dynamic ((1+ε) ln n)-Approximation Algorithms for Minimum Set Cover and Dominating Set.

[BibT_eX]

[DOI]

Amitai Uzrad

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

A Unified Framework for Light Spanners.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier.

[BibT_eX]

[DOI]

Cuong Than

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Covering Planar Metrics (and Beyond): O(1) Trees Suffice.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Computational Geometry, 2023

2022

Fully Dynamic (Δ +1)-Coloring in <i>O</i>(1) Update Time.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2022

Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds.

[BibT_eX]

[DOI]

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

Near-Optimal Spanners for General Graphs in (Nearly) Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Can't See the Forest for the Trees: Navigating Metric Spaces by Bounded Hop-Diameter Spanners.

[BibT_eX]

[DOI]

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Dynamic Matching Algorithms Under Vertex Updates.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Near-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems.

[BibT_eX]

[DOI]

Shiri Antaki

Quanquan C. Liu

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

Dynamic Representations of Sparse Distributed Networks: A Locality-sensitive Approach.

[BibT_eX]

[DOI]

Haim Kaplan

ACM Trans. Parallel Comput., 2021

A Unified Framework of Light Spanners II: Fine-Grained Optimality.

[BibT_eX]

[DOI]

CoRR, 2021

Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions.

[BibT_eX]

[DOI]

CoRR, 2021

Simple Combinatorial Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs.

[BibT_eX]

[DOI]

Adir Morgan

Nicole Wein

CoRR, 2021

Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial.

[BibT_eX]

[DOI]

Adir Morgan

Nicole Wein

Proceedings of the 35th International Symposium on Distributed Computing, 2021

A Generalized Matching Reconfiguration Problem.

[BibT_eX]

[DOI]

Noam Solomon

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.

[BibT_eX]

[DOI]

Sepehr Assadi

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

Improved Dynamic Graph Coloring.

[BibT_eX]

[DOI]

Nicole Wein

ACM Trans. Algorithms, 2020

Fully Dynamic MIS in Uniformly Sparse Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

The Greedy Spanner Is Existentially Optimal.

[BibT_eX]

[DOI]

Arnold Filtser

SIAM J. Comput., 2020

Dynamic Distributed MIS with Improved Bounds.

[BibT_eX]

[DOI]

Shiri Antaki

Quanquan C. Liu

CoRR, 2020

A Unified and Fine-Grained Approach for Light Spanners.

[BibT_eX]

[DOI]

CoRR, 2020

A Unified Sparsification Approach for Matching Problems in Graphs of Bounded Neighborhood Independence.

[BibT_eX]

[DOI]

Proceedings of the SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, 2020

Light Euclidean Spanners with Steiner Points.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual European Symposium on Algorithms, 2020

2019

Fully Dynamic (Δ+1)-Coloring in Constant Update Time.

[BibT_eX]

[DOI]

CoRR, 2019

Fully Dynamic Maximal Independent Set with Sublinear in n Update Time.

[BibT_eX]

[DOI]

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

(1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time.

[BibT_eX]

[DOI]

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

When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time.

[BibT_eX]

[DOI]

Sepehr Assadi

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Truly Optimal Euclidean Spanners.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Dynamic Approximate Matchings with an Optimal Recourse Bound.

[BibT_eX]

[DOI]

CoRR, 2018

Representations of Sparse Distributed Networks: A Locality-Sensitive Approach.

[BibT_eX]

[DOI]

Haim Kaplan

CoRR, 2018

Fully dynamic maximal independent set with sublinear update time.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Wireless Expanders.

[BibT_eX]

[DOI]

Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, 2018

Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Worst-Case Time Barrier.

[BibT_eX]

[DOI]

Moses Charikar

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Fully Dynamic Almost-Maximal Matching: Breaking the Polynomial Barrier for Worst-Case Time Bounds.

[BibT_eX]

[DOI]

Moses Charikar

CoRR, 2017

2016

Simple Deterministic Algorithms for Fully Dynamic Maximal Matching.

[BibT_eX]

[DOI]

Ofer Neiman

ACM Trans. Algorithms, 2016

Fast Constructions of Lightweight Spanners for General Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach.

[BibT_eX]

[DOI]

David Peleg

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Local-on-Average Distributed Tasks.

[BibT_eX]

[DOI]

Merav Parter

David Peleg

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Fully Dynamic Maximal Matching in Constant Update Time.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Light Spanners.

[BibT_eX]

[DOI]

Ofer Neiman

SIAM J. Discret. Math., 2015

Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

New Doubling Spanners: Better and Simpler.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

Euclidean Steiner shallow-light trees.

[BibT_eX]

[DOI]

J. Comput. Geom., 2015

Optimal Euclidean Spanners: Really Short, Thin, and Lanky.

[BibT_eX]

[DOI]

J. ACM, 2015

2014

Balancing Degree, Diameter, and Weight in Euclidean Spanners.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Orienting Fully Dynamic Graphs with Worst-Case Time Bounds.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Light spanners for Snowflake Metrics.

[BibT_eX]

[DOI]

Lee-Ad Gottlieb

Proceedings of the 30th Annual Symposium on Computational Geometry, 2014

On The Average-Case Complexity of the Bottleneck Tower of Hanoi Problem.

[BibT_eX]

[DOI]

Noam Solomon

Proceedings of the 2014 Proceedings of the Eleventh Workshop on Analytic Algorithmics and Combinatorics, 2014

2013

Sparse Euclidean Spanners with Tiny Diameter.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2013

Fast Constructions of Light-Weight Spanners for General Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

The MST of Symmetric Disk Graphs (in Arbitrary Metric Spaces) is Light.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2012

The Tower of Hanoi problem on Path<sub>h</sub> graphs.

[BibT_eX]

[DOI]

Daniel Berend

Amir Sapir

Discret. Appl. Math., 2012

Fault-Tolerant Spanners for Doubling Metrics: Better and Simpler

[BibT_eX]

[DOI]

CoRR, 2012

Deterministic Algorithms for Fully Dynamic Maximal Matching

[BibT_eX]

[DOI]

Ofer Neiman

CoRR, 2012

2011

Narrow-Shallow-Low-Light Trees with and without Steiner Points.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

The MST of Symmetric Disk Graphs (in Arbitrary Metrics) is Light

[BibT_eX]

[DOI]

CoRR, 2011

An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2010

An Optimal-Time Construction of Euclidean Sparse Spanners with Tiny Diameter

[BibT_eX]

[DOI]

CoRR, 2010

2008

Optimality of an algorithm solving the Bottleneck Tower of Hanoi problem.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2008

On an infinite family of solvable Hanoi graphs.

[BibT_eX]

[DOI]

Dany Azriel

Noam Solomon

ACM Trans. Algorithms, 2008

Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners

[BibT_eX]

[DOI]

CoRR, 2008

Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

On Optimal Solutions for the Bottleneck Tower of Hanoi Problem.

[BibT_eX]

[DOI]

Proceedings of the SOFSEM 2007: Theory and Practice of Computer Science, 2007

2006

Optimal Algorithms for Tower of Hanoi Problems with Relaxed Placement Rules.

[BibT_eX]

[DOI]