James Aspnes

Theor. Comput. Sci., 2025

2024

Special Issue on the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022).

[BibT_eX]

[DOI]

Othon Michail

J. Comput. Syst. Sci., May, 2024

2023

Why Extension-Based Proofs Fail.

[BibT_eX]

[DOI]

SIAM J. Comput., August, 2023

Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model.

[BibT_eX]

[DOI]

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

2021

Optimizing in the Dark: Learning Optimal Network Resource Reservation Through a Simple Request Interface.

[BibT_eX]

[DOI]

IEEE/ACM Trans. Netw., 2021

Clocked population protocols.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2021

2020

Notes on Randomized Algorithms.

[BibT_eX]

[DOI]

CoRR, 2020

Notes on Theory of Distributed Systems.

[BibT_eX]

[DOI]

CoRR, 2020

Message Complexity of Population Protocols.

[BibT_eX]

[DOI]

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

Brief Announcement: Why Extension-Based Proofs Fail.

[BibT_eX]

[DOI]

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

Approximate Majority with Catalytic Inputs.

[BibT_eX]

[DOI]

Talley Amir

John Lazarsfeld

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

2019

Consensus with Max Registers.

[BibT_eX]

[DOI]

Heyang Er

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

Optimizing in the Dark: Learning an Optimal Solution through a Simple Request Interface.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, 2019

2018

Concurrent use of write-once memory.

[BibT_eX]

[DOI]

Keren Censor-Hillel

Eitan Yaakobi

J. Parallel Distributed Comput., 2018

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

[BibT_eX]

[DOI]

J. ACM, 2018

Communication-efficient randomized consensus.

[BibT_eX]

[DOI]

Distributed Comput., 2018

Allocate-On-Use Space Complexity of Shared-Memory Algorithms.

[BibT_eX]

[DOI]

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

Space-Optimal Majority in Population Protocols.

[BibT_eX]

[DOI]

Dan Alistarh

Rati Gelashvili

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

The FuzzyLog: A Partially Ordered Shared Log.

[BibT_eX]

[DOI]

Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation, 2018

Toward the First SDN Programming Capacity Theorem on Realizing High-Level Programs on Low-Level Datapaths.

[BibT_eX]

[DOI]

Proceedings of the 2018 IEEE Conference on Computer Communications, 2018

2017

Time-Space Trade-offs in Population Protocols.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Brief Announcement: Object Oriented Consensus.

[BibT_eX]

[DOI]

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

2016

Special Section on the Forty-Fifth Annual ACM Symposium on the Theory of Computing (STOC 2013).

[BibT_eX]

[DOI]

Yuval Ishai

Peter Bro Miltersen

SIAM J. Comput., 2016

Lower Bounds for Restricted-Use Objects.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Depth of a Random Binary Search Tree with Concurrent Insertions.

[BibT_eX]

[DOI]

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

Time and Space Optimal Counting in Population Protocols.

[BibT_eX]

[DOI]

Proceedings of the 20th International Conference on Principles of Distributed Systems, 2016

2015

Spreading Alerts Quietly and the Subgroup Escape Problem.

[BibT_eX]

[DOI]

J. Cryptol., 2015

Network construction with subgraph connectivity constraints.

[BibT_eX]

[DOI]

Lev Reyzin

J. Comb. Optim., 2015

Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity.

[BibT_eX]

[DOI]

J. ACM, 2015

Faster randomized consensus with an oblivious adversary.

[BibT_eX]

[DOI]

Distributed Comput., 2015

Counting with Population Protocols.

[BibT_eX]

[DOI]

Proceedings of the 14th IEEE International Symposium on Network Computing and Applications, 2015

2014

Tight Bounds for Adopt-Commit Objects.

[BibT_eX]

[DOI]

Faith Ellen

Theory Comput. Syst., 2014

Tight Bounds for Asynchronous Renaming.

[BibT_eX]

[DOI]

J. ACM, 2014

Effective storage capacity of labeled graphs.

[BibT_eX]

[DOI]

Inf. Comput., 2014

Dynamic Task Allocation in Asynchronous Shared Memory.

[BibT_eX]

[DOI]

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

2013

On the learnability of shuffle ideals.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2013

Mutation systems.

[BibT_eX]

[DOI]

Raonne Barbosa Vargas

Int. J. Comput. Math., 2013

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

[BibT_eX]

[DOI]

Keren Censor-Hillel

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

Randomized loose renaming in O(log log n) time.

[BibT_eX]

[DOI]

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

2012

Low-contention data structures.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 2012

Polylogarithmic concurrent data structures from monotone circuits.

[BibT_eX]

[DOI]

Keren Censor-Hillel

J. ACM, 2012

Randomized load balancing by joining and splitting bins.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2012

A modular approach to shared-memory consensus, with applications to the probabilistic-write model.

[BibT_eX]

[DOI]

Distributed Comput., 2012

A one-bit swap object using test-and-sets and a max register

[BibT_eX]

[DOI]

CoRR, 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

On the Learnability of Shuffle Ideals.

[BibT_eX]

[DOI]

Aryeh Kontorovich

Proceedings of the Algorithmic Learning Theory - 23rd International Conference, 2012

2011

Randomized Consensus in Expected O(n 2) Total Work Using Single-Writer Registers.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 25th International Symposium, 2011

Sub-logarithmic Test-and-Set against a Weak Adversary.

[BibT_eX]

[DOI]

Dan Alistarh

Proceedings of the Distributed Computing - 25th International Symposium, 2011

Tight bounds for anonymous adopt-commit objects.

[BibT_eX]

[DOI]

Faith Ellen

Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 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

The Complexity of Renaming.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Optimally learning social networks with activations and suppressions.

[BibT_eX]

[DOI]

Lev Reyzin

Theor. Comput. Sci., 2010

Approximate shared-memory counting despite a strong adversary.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2010

Combining shared-coin algorithms.

[BibT_eX]

[DOI]

J. Parallel Distributed Comput., 2010

Slightly smaller splitter networks

[BibT_eX]

[DOI]

CoRR, 2010

Storage Capacity of Labeled Graphs.

[BibT_eX]

[DOI]

Proceedings of the Stabilization, Safety, and Security of Distributed Systems, 2010

Inferring Social Networks from Outbreaks.

[BibT_eX]

[DOI]

Lev Reyzin

Proceedings of the Algorithmic Learning Theory, 21st International Conference, 2010

k + Decision Trees - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Algorithms for Sensor Systems, 2010

2009

Learning Acyclic Probabilistic Circuits Using Test Paths.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2009

Learning a circuit by injecting values.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2009

The expansion and mixing time of skip graphs with applications.

[BibT_eX]

[DOI]

Udi Wieder

Distributed Comput., 2009

Max registers, counters, and monotone circuits.

[BibT_eX]

[DOI]

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

An Introduction to Population Protocols.

[BibT_eX]

[DOI]

Proceedings of the Middleware for Network Eccentric and Mobile Applications, 2009

2008

Self-stabilizing population protocols.

[BibT_eX]

[DOI]

ACM Trans. Auton. Adapt. Syst., 2008

Learning large-alphabet and analog circuits with value injection queries.

[BibT_eX]

[DOI]

Mach. Learn., 2008

Fast computation by population protocols with a leader.

[BibT_eX]

[DOI]

Distributed Comput., 2008

A simple population protocol for fast robust approximate majority.

[BibT_eX]

[DOI]

Distributed Comput., 2008

Ranged hash functions and the price of churn.

[BibT_eX]

[DOI]

Muli Safra

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

2007

Towards a theory of data entanglement.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

Skip graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2007

An Introduction to Population Protocols.

[BibT_eX]

Bull. EATCS, 2007

Editorial.

[BibT_eX]

[DOI]

Distributed Comput., 2007

The computational power of population protocols.

[BibT_eX]

[DOI]

Distributed Comput., 2007

Path-independent load balancing with unreliable machines.

[BibT_eX]

[DOI]

Yang Richard Yang

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

O(logn)-Time Overlay Network Construction from Graphs with Out-Degree 1.

[BibT_eX]

[DOI]

Yinghua Wu

Proceedings of the Principles of Distributed Systems, 11th International Conference, 2007

Worm Versus Alert: Who Wins in a Battle for Control of a Large-Scale Network?.

[BibT_eX]

[DOI]

Navin Rustagi

Jared Saia

Proceedings of the Principles of Distributed Systems, 11th International Conference, 2007

2006

A Theory of Network Localization.

[BibT_eX]

[DOI]

Tolga Eren

David Kiyoshi Goldenberg

IEEE Trans. Mob. Comput., 2006

Inoculation strategies for victims of viruses and the sum-of-squares partition problem.

[BibT_eX]

[DOI]

Kevin L. Chang

Aleksandr Yampolskiy

J. Comput. Syst. Sci., 2006

Eight Open Problems in Distributed Computing.

[BibT_eX]

Alexander A. Shvartsman

Paul G. Spirakis

Roger Wattenhofer

Bull. EATCS, 2006

Relationships between broadcast and shared memory in reliable anonymous distributed systems.

[BibT_eX]

[DOI]

Faith Ellen Fich

Distributed Comput., 2006

Computation in networks of passively mobile finite-state sensors.

[BibT_eX]

[DOI]

Distributed Comput., 2006

Stably computable predicates are semilinear.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006

2005

Compositional competitiveness for distributed algorithms.

[BibT_eX]

[DOI]

J. Algorithms, 2005

Fast construction of overlay networks.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

On the Power of Anonymous One-Way Communication.

[BibT_eX]

[DOI]

Proceedings of the Principles of Distributed Systems, 9th International Conference, 2005

Skip B-Trees.

[BibT_eX]

[DOI]

Ittai Abraham

Jian Yuan

Proceedings of the Principles of Distributed Systems, 9th International Conference, 2005

Stably Computable Properties of Network Graphs.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing in Sensor Systems, 2005

Distributed Data Structures for Peer-to-Peer Systems.

[BibT_eX]

[DOI]

Proceedings of the Handbook on Theoretical and Algorithmic Aspects of Sensor, 2005

2004

Load balancing and locality in range-queriable data structures.

[BibT_eX]

[DOI]

Jonathan Kirsch

Arvind Krishnamurthy

Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Towards a Theory of Data Entanglement: (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Computer Security, 2004

On the Computational Complexity of Sensor Network Localization.

[BibT_eX]

[DOI]

David Kiyoshi Goldenberg

Yang Richard Yang

Proceedings of the Algorithmic Aspects of Wireless Sensor Networks: First International Workshop, 2004

2003

Randomized protocols for asynchronous consensus.

[BibT_eX]

[DOI]

Distributed Comput., 2003

2002

A Combinatorial Toolbox for Protein Sequence Design and Landscape Analysis in the Grand Canonical Model.

[BibT_eX]

[DOI]

J. Comput. Biol., 2002

Fast deterministic consensus in a noisy environment.

[BibT_eX]

[DOI]

J. Algorithms, 2002

Wait-free consensus with infinite arrivals.

[BibT_eX]

[DOI]

Jatin Shah

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Fault-tolerant routing in peer-to-peer systems.

[BibT_eX]

[DOI]

Zoë Diamadi

Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, 2002

2001

Towards understanding the predictability of stock markets from the perspective of computational complexity.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

2000

Opportunity Cost Algorithms for Combinatorial Auctions

[BibT_eX]

[DOI]

CoRR, 2000

1998

Spreading Rumors Rapidly Despite an Adversary.

[BibT_eX]

[DOI]

William Hurwood

J. Algorithms, 1998

Fairness in Scheduling

[BibT_eX]

[DOI]

J. Algorithms, 1998

Lower Bounds for Distributed Coin-Flipping and Randomized Consensus.

[BibT_eX]

[DOI]

J. ACM, 1998

1997

On-line routing of virtual circuits with applications to load balancing and machine scheduling.

[BibT_eX]

[DOI]

J. ACM, 1997

1996

Randomized Consensus in Expected O(n log² n) Operations Per Processor.

[BibT_eX]

[DOI]

SIAM J. Comput., 1996

Modular Competitiveness for Distributed Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Spreading Rumors Rapidly Despite and Adversary.

[BibT_eX]

[DOI]

William Hurwood

Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, 1996

Competitive Analysis of Distributed Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Online Algorithms, 1996

1995

A Modular Measure of Competitiveness for Distributed Algorithms (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, 1995

1994

Counting Networks.

[BibT_eX]

[DOI]

Nir Shavit

J. ACM, 1994

The Expressive Power of Voting Polynomials.

[BibT_eX]

[DOI]

Comb., 1994

Competitiveness in Distributed Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, 1994

A Theory of Competitive Analysis for Distributed Algorithms

[BibT_eX]

[DOI]

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Time- and Space-Efficient Randomized Consensus.

[BibT_eX]

[DOI]

J. Algorithms, 1993

On-line load balancing with applications to machine scheduling and virtual circuit routing.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992

Randomized Consensus in Expected O(n log ^2 n) Operations Per Processor

[BibT_eX]

[DOI]

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1991

Counting Networks and Multi-Processor Coordination

[BibT_eX]

[DOI]

Nir Shavit

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

1990

Fast Randomized Consensus Using Shared Memory.

[BibT_eX]

[DOI]

J. Algorithms, 1990

Wait-Free Data Structures in the Asynchronous PRAM Model.

[BibT_eX]

[DOI]