# James Aspnes

According to our database

Collaborative distances:

^{1}, James Aspnes authored at least 110 papers between 1988 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2019

Why extension-based proofs fail.

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

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

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

2018

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

J. ACM, 2018

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

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

Space-Optimal Majority in Population Protocols.

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

The FuzzyLog: A Partially Ordered Shared Log.

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.

Proceedings of the 2018 IEEE Conference on Computer Communications, 2018

2017

Time-Space Trade-offs in Population Protocols.

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

Clocked Population Protocols.

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

Brief Announcement: Object Oriented Consensus.

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).

SIAM J. Comput., 2016

Lower Bounds for Restricted-Use Objects.

SIAM J. Comput., 2016

Depth of a Random Binary Search Tree with Concurrent Insertions.

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

Concurrent Use of Write-Once Memory.

Proceedings of the Structural Information and Communication Complexity, 2016

Time and Space Optimal Counting in Population Protocols.

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

2015

Spreading Alerts Quietly and the Subgroup Escape Problem.

J. Cryptology, 2015

Network construction with subgraph connectivity constraints.

J. Comb. Optim., 2015

Limited-Use Atomic Snapshots with Polylogarithmic Step Complexity.

J. ACM, 2015

Counting with Population Protocols.

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

2014

Tight Bounds for Adopt-Commit Objects.

Theory Comput. Syst., 2014

Tight Bounds for Asynchronous Renaming.

J. ACM, 2014

Effective storage capacity of labeled graphs.

Inf. Comput., 2014

Communication-Efficient Randomized Consensus.

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

Dynamic Task Allocation in Asynchronous Shared Memory.

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

2013

On the learnability of shuffle ideals.

J. Mach. Learn. Res., 2013

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

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

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

2012

Polylogarithmic concurrent data structures from monotone circuits.

J. ACM, 2012

Randomized load balancing by joining and splitting bins.

Inf. Process. Lett., 2012

Lower bounds for restricted-use objects: extended abstract.

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

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

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

Faster randomized consensus with an oblivious adversary.

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

On the Learnability of Shuffle Ideals.

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

2011

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

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

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

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

Tight bounds for anonymous adopt-commit objects.

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.

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

Mutation Systems.

Proceedings of the Language and Automata Theory and Applications, 2011

The Complexity of Renaming.

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

2010

Combining shared-coin algorithms.

J. Parallel Distrib. Comput., 2010

Storage Capacity of Labeled Graphs.

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

Low-contention data structures.

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

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

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

Inferring Social Networks from Outbreaks.

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

k

^{ + }Decision Trees - (Extended Abstract).
Proceedings of the Algorithms for Sensor Systems, 2010

2009

Approximate shared-memory counting despite a strong adversary.

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

Max registers, counters, and monotone circuits.

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

An Introduction to Population Protocols.

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

2008

Ranged hash functions and the price of churn.

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

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

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

Learning Acyclic Probabilistic Circuits Using Test Paths.

Proceedings of the 21st Annual Conference on Learning Theory, 2008

Optimally Learning Social Networks with Activations and Suppressions.

Proceedings of the Algorithmic Learning Theory, 19th International Conference, 2008

2007

Towards a theory of data entanglement.

Theor. Comput. Sci., 2007

An Introduction to Population Protocols.

Bulletin of the EATCS, 2007

Editorial.

Distributed Computing, 2007

The computational power of population protocols.

Distributed Computing, 2007

A Simple Population Protocol for Fast Robust Approximate Majority.

Proceedings of the Distributed Computing, 21st International Symposium, 2007

Path-independent load balancing with unreliable machines.

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

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

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?.

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

Learning Large-Alphabet and Analog Circuits with Value Injection Queries.

Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

2006

A Theory of Network Localization.

IEEE Trans. Mob. Comput., 2006

Eight Open Problems in Distributed Computing.

Bulletin of the EATCS, 2006

Fast Computation by Population Protocols with a Leader.

Proceedings of the Distributed Computing, 20th International Symposium, 2006

Learning a circuit by injecting values.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Stably computable predicates are semilinear.

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

2005

Compositional competitiveness for distributed algorithms.

J. Algorithms, 2005

The expansion and mixing time of skip graphs with applications.

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

Fast construction of overlay networks.

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

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

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

Self-stabilizing Population Protocols.

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

On the Power of Anonymous One-Way Communication.

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

Skip B-Trees.

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

Stably Computable Properties of Network Graphs.

Proceedings of the Distributed Computing in Sensor Systems, 2005

Spreading Alerts Quietly and the Subgroup Escape Problem.

Proceedings of the Advances in Cryptology, 2005

Distributed Data Structures for Peer-to-Peer Systems.

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

2004

Relationships Between Broadcast and Shared Memory in Reliable Anonymous Distributed Systems.

Proceedings of the Distributed Computing, 18th International Conference, 2004

Load balancing and locality in range-queriable data structures.

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

Computation in networks of passively mobile finite-state sensors.

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

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

Proceedings of the Computer Security, 2004

On the Computational Complexity of Sensor Network Localization.

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

2003

Randomized protocols for asynchronous consensus.

Distributed Computing, 2003

Skip graphs.

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

2002

Wait-free consensus with infinite arrivals.

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

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

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.

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

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

Proceedings of the Algorithms and Computation, 12th International Symposium, 2001

2000

Fast deterministic consensus in a noisy environment.

Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

1998

Spreading Rumors Rapidly Despite an Adversary.

J. Algorithms, 1998

Fairness in Scheduling

J. Algorithms, 1998

1997

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

J. ACM, 1997

Lower Bounds for Distributed Coin-Flipping and Randomized Consensus.

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

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

SIAM J. Comput., 1996

Modular Competitiveness for Distributed Algorithms.

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

Spreading Rumors Rapidly Despite and Adversary.

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

Competitive Analysis of Distributed Algorithms.

Proceedings of the Online Algorithms, 1996

1995

Fairness in Scheduling.

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

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

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

1994

Counting Networks.

J. ACM, 1994

The Expressive Power of Voting Polynomials.

Combinatorica, 1994

Competitiveness in Distributed Algorithms.

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

A Theory of Competitive Analysis for Distributed Algorithms

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

1993

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

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

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

1991

Counting Networks and Multi-Processor Coordination

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

The Expressive Power of Voting Polynomials

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

1990

Fast Randomized Consensus Using Shared Memory.

J. Algorithms, 1990

Wait-Free Data Structures in the Asynchronous PRAM Model.

Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990

Time- and Space-Efficient Randomized Consensus.

Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing, 1990

1988

A Theory of Timestamp-Based Concurrency Control for Nested Transactions.

Proceedings of the Fourteenth International Conference on Very Large Data Bases, August 29, 1988