Keren Censor-Hillel

David Vulakh

Distributed Comput., December, 2024

Faster Cycle Detection in the Congested Clique.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Tomer Even

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

Near-Optimal Fault Tolerance for Efficient Batch Matrix Multiplication via an Additive Combinatorics Lens.

[BibT_eX]

[DOI]

Yuka Machino

Pedro Soto

Proceedings of the Structural Information and Communication Complexity, 2024

On Distributed Computation of the Minimum Triangle Edge Transversal.

[BibT_eX]

[DOI]

Majd Khoury

Proceedings of the Structural Information and Communication Complexity, 2024

Fast Approximate Counting of Cycles.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Tomer Even

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

2023

Correction to: Distributed computations in fully-defective networks.

[BibT_eX]

[DOI]

Distributed Comput., December, 2023

Distributed computations in fully-defective networks.

[BibT_eX]

[DOI]

Distributed Comput., December, 2023

2022

Distributed Subgraph Finding: Progress and Challenges.

[BibT_eX]

[DOI]

CoRR, 2022

2022 Principles of Distributed Computing Doctoral Dissertation Award.

[BibT_eX]

[DOI]

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

Distributed Vertex Cover Reconfiguration.

[BibT_eX]

[DOI]

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

Quantum Distributed Algorithms for Detection of Cliques.

[BibT_eX]

[DOI]

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

2021

Smaller Cuts, Higher Lower Bounds.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2021

Distributed Spanner Approximation.

[BibT_eX]

[DOI]

Michal Dory

SIAM J. Comput., 2021

Special Section on the 48th Annual ACM Symposium on Theory of Computing (STOC 2016).

[BibT_eX]

[DOI]

SIAM J. Comput., 2021

2021 Edsger W. Dijkstra Prize in Distributed Computing.

[BibT_eX]

[DOI]

Bull. EATCS, 2021

Fast approximate shortest paths in the congested clique.

[BibT_eX]

[DOI]

Distributed Comput., 2021

Locally Checkable Labelings with Small Messages.

[BibT_eX]

[DOI]

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

Distance Computations in the Hybrid Network Model via Oracle Simulations.

[BibT_eX]

[DOI]

Volodymyr Polosukhin

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

On Sparsity Awareness in Distributed Computations.

[BibT_eX]

[DOI]

Volodymyr Polosukhin

Proceedings of the SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021

Finding Subgraphs in Highly Dynamic Networks.

[BibT_eX]

[DOI]

Victor I. Kolobov

Proceedings of the SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, 2021

Tight Distributed Listing of Cliques.

[BibT_eX]

[DOI]

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

Near-Optimal Scheduling in the Congested Clique.

[BibT_eX]

[DOI]

Yannic Maus

Volodymyr Polosukhin

Proceedings of the Structural Information and Communication Complexity, 2021

2021 Edsger W. Dijkstra Prize in Distributed Computing.

[BibT_eX]

[DOI]

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

Fault Tolerant Max-Cut.

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

Distributed Subgraph Finding: Progress and Challenges (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

The sparsest additive spanner via multiple weighted BFS trees.

[BibT_eX]

[DOI]

Ami Paz

Noam Ravid

Theor. Comput. Sci., 2020

Approximate proof-labeling schemes.

[BibT_eX]

[DOI]

Ami Paz

Mor Perry

Theor. Comput. Sci., 2020

Sparse matrix multiplication and triangle listing in the Congested Clique model.

[BibT_eX]

[DOI]

Elia Turner

Theor. Comput. Sci., 2020

Distributed reconfiguration of maximal independent sets.

[BibT_eX]

[DOI]

Mikaël Rabie

J. Comput. Syst. Sci., 2020

Derandomizing local distributed algorithms under bandwidth restrictions.

[BibT_eX]

[DOI]

Merav Parter

Distributed Comput., 2020

Fast distributed approximation for TAP and 2-edge-connectivity.

[BibT_eX]

[DOI]

Michal Dory

Distributed Comput., 2020

Fooling views: a new lower bound technique for distributed computations under congestion.

[BibT_eX]

[DOI]

Distributed Comput., 2020

Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs.

[BibT_eX]

[DOI]

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

On Distributed Listing of Cliques.

[BibT_eX]

[DOI]

François Le Gall

Virginia Vassilevska Williams

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

Distributed Approximation on Power Graphs.

[BibT_eX]

[DOI]

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

Fast Deterministic Algorithms for Highly-Dynamic Networks.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Principles of Distributed Systems, 2020

Distributed Distance Approximation.

[BibT_eX]

[DOI]

Proceedings of the 24th International Conference on Principles of Distributed Systems, 2020

2019

Algebraic methods in the congested clique.

[BibT_eX]

[DOI]

Distributed Comput., 2019

Making asynchronous distributed computations robust to noise.

[BibT_eX]

[DOI]

Ran Gelles

Bernhard Haeupler

Distributed Comput., 2019

Fast distributed algorithms for testing graph properties.

[BibT_eX]

[DOI]

Distributed Comput., 2019

Fast and Simple Deterministic Algorithms for Highly-Dynamic Networks.

[BibT_eX]

[DOI]

CoRR, 2019

Erasure Correction for Noisy Radio Networks.

[BibT_eX]

[DOI]

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

Hardness of Distributed Optimization.

[BibT_eX]

[DOI]

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

Distributed Optimization And Approximation: How Difficult Can It Be? (Keynote Abstract).

[BibT_eX]

[DOI]

Proceedings of the 23rd International Conference on Principles of Distributed Systems, 2019

Distributed Detection of Cliques in Dynamic Networks.

[BibT_eX]

[DOI]

Matthias Bonne

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

2018

On fast and robust information spreading in the Vertex-Congest model.

[BibT_eX]

[DOI]

Tariq Toukan

Theor. Comput. Sci., 2018

Concurrent use of write-once memory.

[BibT_eX]

[DOI]

Eitan Yaakobi

J. Parallel Distributed Comput., 2018

Erratum: Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity.

[BibT_eX]

[DOI]

J. ACM, 2018

Distributed construction of purely additive spanners.

[BibT_eX]

[DOI]

Distributed Comput., 2018

Sparse Matrix Multiplication with Bandwidth Restricted All-to-All Communication.

[BibT_eX]

[DOI]

Elia Turner

CoRR, 2018

Barriers due to Congestion and Two Ways to Deal With Them.

[BibT_eX]

[DOI]

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

Making Asynchronous Distributed Computations Robust to Channel Noise.

[BibT_eX]

[DOI]

Ran Gelles

Bernhard Haeupler

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

2017

Tight Bounds on Vertex Connectivity Under Sampling.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2017

Rumor Spreading with No Dependence on Conductance.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds.

[BibT_eX]

[DOI]

Reuven Bar-Yehuda

J. ACM, 2017

Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model.

[BibT_eX]

[DOI]

Seri Khoury

Ami Paz

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

Broadcasting in Noisy Radio Networks.

[BibT_eX]

[DOI]

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

Brief Announcement: Distributed Approximation for Tree Augmentation.

[BibT_eX]

[DOI]

Michal Dory

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

Distributed Approximation of Maximum Independent Set and Maximum Matching.

[BibT_eX]

[DOI]

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

Fast Distributed Approximation for Max-Cut.

[BibT_eX]

[DOI]

Rina Levy

Hadas Shachnai

Proceedings of the Algorithms for Sensor Systems, 2017

2016

Lower Bounds for Restricted-Use Objects.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Are Lock-Free Concurrent Algorithms Practically Wait-Free?

[BibT_eX]

[DOI]

Dan Alistarh

Nir Shavit

J. ACM, 2016

A Distributed $(2+ε)$-Approximation for Vertex Cover in $O(\logΔ/ε\log\logΔ)$ Rounds.

[BibT_eX]

[DOI]

Reuven Bar-Yehuda

CoRR, 2016

The one-out-of-k retrieval problem and linear network coding.

[BibT_eX]

[DOI]

Adv. Math. Commun., 2016

Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks.

[BibT_eX]

[DOI]

Amir Abboud

Seri Khoury

Proceedings of the Distributed Computing - 30th International Symposium, 2016

Optimal Dynamic Distributed MIS.

[BibT_eX]

[DOI]

Elad Haramaty

Zohar S. Karnin

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

A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds.

[BibT_eX]

[DOI]

Reuven Bar-Yehuda

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

2015

Distributed Algorithms as Combinatorial Structures.

[BibT_eX]

[DOI]

SIGACT News, 2015

Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity.

[BibT_eX]

[DOI]

J. ACM, 2015

Bounded-Contention Coding for the additive network model.

[BibT_eX]

[DOI]

Distributed Comput., 2015

Computing in Additive Networks with Bounded-Information Codes.

[BibT_eX]

[DOI]

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

Tight Bounds on Vertex Connectivity Under Vertex Sampling.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Help!

[BibT_eX]

[DOI]

Erez Petrank

Shahar Timnat

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

2014

Tight Bounds for Asynchronous Renaming.

[BibT_eX]

[DOI]

J. ACM, 2014

Structuring unreliable radio networks.

[BibT_eX]

[DOI]

Distributed Comput., 2014

A New Perspective on Vertex Connectivity.

[BibT_eX]

[DOI]

Mohsen Ghaffari

Fabian Kuhn

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

Distributed connectivity decomposition.

[BibT_eX]

[DOI]

Mohsen Ghaffari

Fabian Kuhn

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

Brief announcement: are lock-free concurrent algorithms practically wait-free?

[BibT_eX]

[DOI]

Dan Alistarh

Nir Shavit

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

2013

Order optimal information spreading using algebraic gossip.

[BibT_eX]

[DOI]

Distributed Comput., 2013

Atomic Snapshots in O(log3 n) Steps Using Randomized Helping.

[BibT_eX]

[DOI]

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

2012

Fast Information Spreading in Graphs with Large Weak Conductance.

[BibT_eX]

[DOI]

Hadas Shachnai

SIAM J. Comput., 2012

Polylogarithmic concurrent data structures from monotone circuits.

[BibT_eX]

[DOI]

J. ACM, 2012

Bounded-Contention Coding for Wireless Networks in the High SNR Regime.

[BibT_eX]

[DOI]

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

Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Lower bounds for restricted-use objects: extended abstract.

[BibT_eX]

[DOI]

Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures, 2012

Faster than optimal snapshots (for a while): preliminary version.

[BibT_eX]

[DOI]

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

2011

Optimal-time adaptive strong renaming, with applications to counting.

[BibT_eX]

[DOI]

Morteza Zadimoghaddam

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

2010

Probabilistic methods in distributed computing.

[BibT_eX]

[DOI]

PhD thesis, 2010

Approximate shared-memory counting despite a strong adversary.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Lower Bounds for Randomized Consensus under a Weak Adversary.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

Combining shared-coin algorithms.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 2010

Multi-sided shared coins and randomized set-agreement.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

Partial information spreading with application to distributed maximum coverage.

[BibT_eX]

[DOI]

Hadas Shachnai

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

2009

A review of PODC 2009.

[BibT_eX]

[DOI]

Christoph Lenzen

SIGACT News, 2009

Max registers, counters, and monotone circuits.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

2008

Tight bounds for asynchronous randomized consensus.

[BibT_eX]

[DOI]

J. ACM, 2008

Randomized consensus in expected O(n log n) individual work.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Principles of Distributed Computing, 2008

2006

The Positive Capacity Region of Two-Dimensional Run-Length-Constrained Channels.

[BibT_eX]

[DOI]