Merav Parter

CoRR, April, 2025

New Oracles and Labeling Schemes for Vertex Cut Queries.

[BibT_eX]

[DOI]

Yonggang Jiang

CoRR, January, 2025

New Distributed Interactive Proofs for Planarity: A Matter of Left and Right.

[BibT_eX]

[DOI]

Yuval Gil

Proceedings of the 39th International Symposium on Distributed Computing, 2025

Connectivity Certificate against Bounded-Degree Faults: Simpler, Better and Supporting Vertex Faults.

[BibT_eX]

[DOI]

Elad Tzalik

Proceedings of the 2025 Symposium on Simplicity in Algorithms, 2025

Parks and Recreation: Color Fault-Tolerant Spanners Made Local.

[BibT_eX]

[DOI]

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

Having Hope in Missing Spanners: New Distance Preservers and Light Hopsets.

[BibT_eX]

[DOI]

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

Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition.

[BibT_eX]

[DOI]

Julia Chuzhoy

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

Brief Announcement: New Distributed Interactive Proofs for Planarity: A Matter of Left and Right.

[BibT_eX]

[DOI]

Yuval Gil

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2025

All-to-All Communication with Mobile Edge Adversary: Almost Linearly More Faults, For Free.

[BibT_eX]

[DOI]

Orr Fischer

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2025

Distributed Maximum Flow in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2025

2024

Brief Announcement: Distributed Maximum Flow in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Distributed Computing, 2024

Connectivity Labeling and Routing with Multiple Vertex Failures.

[BibT_eX]

[DOI]

Seth Pettie

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Fault-Tolerant Spanners against Bounded-Degree Edge Failures: Linearly More Faults, Almost For Free.

[BibT_eX]

[DOI]

Bernhard Haeupler

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

Graphs Shortcuts: New Bounds and Algorithms (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

The Algorithmic Power of the Greene-Kleitman Theorem.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

Giving Some Slack: Shortcuts and Transitive Closure Compressions.

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual European Symposium on Algorithms, 2024

2023

Connectivity Labeling for Multiple Vertex Failures.

[BibT_eX]

[DOI]

Seth Pettie

CoRR, 2023

Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers.

[BibT_eX]

[DOI]

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

Distributed CONGEST Algorithms against Mobile Adversaries.

[BibT_eX]

[DOI]

Orr Fischer

Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, 2023

Secure Distributed Network Optimization Against Eavesdroppers.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

New Additive Emulators.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Secure Computation Meets Distributed Universal Optimality.

[BibT_eX]

[DOI]

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

Towards Bypassing Lower Bounds for Graph Shortcuts.

[BibT_eX]

[DOI]

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Õptimal Vertex Fault-Tolerant Spanners in Õptimal Time: Sequential, Distributed and Parallel.

[BibT_eX]

[DOI]

CoRR, 2022

Õptimal Dual Vertex Failure Connectivity Labels.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Near-Optimal Distributed Computation of Small Vertex Cuts.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Broadcast CONGEST Algorithms Against Eavesdroppers.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Distributed Computing, 2022

Nearly optimal vertex fault-tolerant spanners in optimal time: sequential, distributed, and parallel.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the Barrier.

[BibT_eX]

[DOI]

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

A Graph Theoretic Approach for Resilient Distributed Algorithms.

[BibT_eX]

[DOI]

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

Beating Matrix Multiplication for n^{1/3}-Directed Shortcuts.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Nonuniform SINR+Voronoi diagrams are effectively uniform.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the √n Barrier.

[BibT_eX]

[DOI]

CoRR, 2021

General CONGEST Compilers against Adversarial Edges.

[BibT_eX]

[DOI]

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

Broadcast CONGEST Algorithms against Adversarial Edges.

[BibT_eX]

[DOI]

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

Invited Talk: Resilient Distributed Algorithms.

[BibT_eX]

[DOI]

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

Deterministic Replacement Path Covering.

[BibT_eX]

[DOI]

Karthik C. S.

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

Low-Congestion Shortcuts in Constant Diameter Graphs.

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

Fault-Tolerant Labeling and Compact Routing Schemes.

[BibT_eX]

[DOI]

Michal Dory

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

Component Stability in Low-Space Massively Parallel Computation.

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

Improved Deterministic (Δ+1) Coloring in Low-Space MPC.

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs.

[BibT_eX]

[DOI]

Proceedings of the PODC '21: ACM Symposium on Principles of Distributed Computing, 2021

2020

Round-Efficient Distributed Byzantine Computation.

[BibT_eX]

[DOI]

CoRR, 2020

Fault Tolerant Approximate BFS Structures with Additive Stretch.

[BibT_eX]

[DOI]

Algorithmica, 2020

Distributed Planar Reachability in Nearly Optimal Time.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Distributed Constructions of Dual-Failure Fault-Tolerant Distance Preservers.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Spiking Neural Networks Through the Lens of Streaming Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.

[BibT_eX]

[DOI]

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

The Power of Distributed Verifiers in Interactive Proofs.

[BibT_eX]

[DOI]

Moni Naor

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

New (<i>α, β</i>) Spanners and Hopsets.

[BibT_eX]

[DOI]

Uri Ben-Levy

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

Exponentially Faster Shortest Paths in the Congested Clique.

[BibT_eX]

[DOI]

Michal Dory

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Simple, Deterministic, Constant-Round Coloring in the Congested Clique.

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

The Computational Cost of Asynchronous Neural Communication.

[BibT_eX]

[DOI]

Gur Perri

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

On Packing Low-Diameter Spanning Trees.

[BibT_eX]

[DOI]

Julia Chuzhoy

Zihan Tan

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

New Fault Tolerant Subset Preservers.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Planar Diameter via Metric Compression.

[BibT_eX]

[DOI]

Jason Li

CoRR, 2019

New (α, β) Spanners and Hopsets.

[BibT_eX]

[DOI]

Uri Ben-Levy

CoRR, 2019

Winner-Take-All Computation in Spiking Neural Networks.

[BibT_eX]

[DOI]

Nancy A. Lynch

CoRR, 2019

Small Cuts and Connectivity Certificates: A Fault Tolerant Approach.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Planar diameter via metric compression.

[BibT_eX]

[DOI]

Jason Li

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Parallel Balanced Allocations: The Heavily Loaded Case.

[BibT_eX]

[DOI]

Christoph Lenzen

Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019

Distributed Algorithms Made Secure: A Graph Theoretic Approach.

[BibT_eX]

[DOI]

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

Low Congestion Cycle Covers and Their Applications.

[BibT_eX]

[DOI]

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

Secure Distributed Computing Made (Nearly) Optimal.

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Local Computation Algorithms for Spanners.

[BibT_eX]

[DOI]

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Optimal Short Cycle Decomposition in Almost Linear Time.

[BibT_eX]

[DOI]

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

Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons.

[BibT_eX]

[DOI]

Proceedings of the 27th Annual European Symposium on Algorithms, 2019

2018

The topology of wireless communication on a line.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

(Δ+1) Coloring in the Congested Clique Model.

[BibT_eX]

[DOI]

CoRR, 2018

Congested Clique Algorithms for Graph Spanners.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds.

[BibT_eX]

[DOI]

Hsin-Hao Su

Proceedings of the 32nd International Symposium on Distributed Computing, 2018

Efficient Oracles and Routing Schemes for Replacement Paths.

[BibT_eX]

[DOI]

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Wireless Expanders.

[BibT_eX]

[DOI]

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

Optimal Vertex Fault Tolerant Spanners (for fixed stretch).

[BibT_eX]

[DOI]

Michael Dinitz

Virginia Vassilevska Williams

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

(Delta+1) Coloring in the Congested Clique Model.

[BibT_eX]

[DOI]

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

2017

Distributed Computing Made Secure: A New Cycle Cover Theorem.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2017

Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks.

[BibT_eX]

[DOI]

Nancy A. Lynch

Proceedings of the 31st International Symposium on Distributed Computing, 2017

Improved Deterministic Distributed Construction of Spanners.

[BibT_eX]

[DOI]

Ofer Grossman

Proceedings of the 31st International Symposium on Distributed Computing, 2017

Near-Optimal Distributed DFS in Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Distributed Computing, 2017

Derandomizing Local Distributed Algorithms under Bandwidth Restrictions.

[BibT_eX]

[DOI]

Keren Censor-Hillel

Gregory Schwartzman

Proceedings of the 31st International Symposium on Distributed Computing, 2017

Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks.

[BibT_eX]

[DOI]

Nancy A. Lynch

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Preserving Distances in Very Faulty Graphs.

[BibT_eX]

[DOI]

Fabrizio Grandoni

Virginia Vassilevska Williams

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Sparse Fault-Tolerant BFS Structures.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Fault-Tolerant Logical Network Structures.

[BibT_eX]

[DOI]

Bull. EATCS, 2016

Near-Optimal Distributed Algorithms for Fault-Tolerant Tree Structures.

[BibT_eX]

[DOI]

Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, 2016

Local-on-Average Distributed Tasks.

[BibT_eX]

[DOI]

Shay Solomon

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

A Polylogarithmic Gossip Algorithm for Plurality Consensus.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

MST in Log-Star Rounds of Congested Clique.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015

Nonuniform SINR+Voroni Diagrams Are Effectively Uniform.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 29th International Symposium, 2015

Computing in Additive Networks with Bounded-Information Codes.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 29th International Symposium, 2015

Fault Tolerant BFS Structures: A Reinforcement-Backup Tradeoff.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

Dual Failure Resilient BFS Structure.

[BibT_eX]

[DOI]

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

On the Relations Between SINR Diagrams and Voronoi Diagrams.

[BibT_eX]

[DOI]

Proceedings of the Ad-hoc, Mobile, and Wireless Networks - 14th International Conference, 2015

2014

DISC 2014 Review.

[BibT_eX]

[DOI]

Edward Talmage

SIGACT News, 2014

Testing the irreducibility of nonsquare Perron-Frobenius systems.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2014

Randomized distributed decision.

[BibT_eX]

[DOI]

Distributed Comput., 2014

Vertex Fault Tolerant Additive Spanners.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 28th International Symposium, 2014

Fault Tolerant Approximate BFS Structures.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Bypassing Erdős' Girth Conjecture: Hybrid Stretch and Sourcewise Spanners.

[BibT_eX]

[DOI]

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

2013

Generalized Perron-Frobenius Theorem for Nonsquare Matrices.

[BibT_eX]

[DOI]

CoRR, 2013

Braess's Paradox in Wireless Networks: The Danger of Improved Technology.

[BibT_eX]

[DOI]

Michael Dinitz

Proceedings of the Distributed Computing - 27th International Symposium, 2013

Generalized Perron-Frobenius Theorem for Multiple Choice Matrices, and Applications.

[BibT_eX]

[DOI]

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

Sparse Fault-Tolerant BFS Trees.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2013, 2013

Secluded Connectivity Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2013, 2013

2012

Randomized Distributed Decision.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 26th International Symposium, 2012

SINR diagram with interference cancellation.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

The topology of wireless communication.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

Distributed power control in the SINR model.

[BibT_eX]

[DOI]

Proceedings of the INFOCOM 2011. 30th IEEE International Conference on Computer Communications, 2011

2008

Facilitated Variation: How Evolution Learns from Past Environments To Generalize to New Environments.

[BibT_eX]

[DOI]