| Publication | Date of Publication | Type |
|---|
| Approximate majority with catalytic inputs | 2026-03-31 | Paper |
Privacy in population protocols with probabilistic scheduling
Theoretical Computer Science | 2024-12-12 | Paper |
Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
| Message complexity of population protocols | 2023-11-02 | Paper |
Why Extension-Based Proofs Fail
SIAM Journal on Computing | 2023-08-10 | Paper |
| Consensus with max registers | 2023-02-03 | Paper |
| Allocate-on-use space complexity of shared-memory algorithms | 2022-07-21 | Paper |
Communication-efficient randomized consensus
Distributed Computing | 2022-02-15 | Paper |
Clocked population protocols
Journal of Computer and System Sciences | 2021-07-06 | Paper |
Brief Announcement: Why Extension-Based Proofs Fail
Proceedings of the 39th Symposium on Principles of Distributed Computing | 2021-03-15 | Paper |
Randomized protocols for asynchronous consensus
Distributed Computing | 2020-12-04 | Paper |
Why extension-based proofs fail
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Dynamic Task Allocation in Asynchronous Shared Memory
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
| Approximate shared-memory counting despite a strong adversary | 2019-05-06 | Paper |
Erratum to: ``Limited-use atomic snapshots with polylogarithmic step complexity''
Journal of the ACM | 2019-02-25 | Paper |
Skip graphs
ACM Transactions on Algorithms | 2018-11-05 | Paper |
| Depth of a random binary search tree with concurrent insertions | 2018-08-16 | Paper |
Time and space optimal counting in population protocols
(available as arXiv preprint) | 2018-07-18 | Paper |
Time-space trade-offs in population protocols
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| scientific article; zbMATH DE number 6850453 (Why is no real title available?) | 2018-03-15 | Paper |
scientific article; zbMATH DE number 6850453 (Why is no real title available?)
(available as arXiv preprint) | 2018-03-15 | Paper |
Clocked population protocols
Proceedings of the ACM Symposium on Principles of Distributed Computing | 2017-10-11 | Paper |
Brief Announcement
Proceedings of the ACM Symposium on Principles of Distributed Computing | 2017-10-11 | Paper |
Concurrent use of write-once memory
Structural Information and Communication Complexity | 2016-12-01 | Paper |
Lower bounds for restricted-use objects
SIAM Journal on Computing | 2016-06-16 | Paper |
Spreading alerts quietly and the subgroup escape problem
Journal of Cryptology | 2016-01-11 | Paper |
Optimal-time adaptive strong renaming, with applications to counting
Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing | 2015-09-11 | Paper |
Spreading rumors rapidly despite an adversary
Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing - PODC '96 | 2015-09-11 | Paper |
Limited-use atomic snapshots with polylogarithmic step complexity
Journal of the ACM | 2015-08-14 | Paper |
Computation in networks of passively mobile finite-state sensors
Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing | 2015-08-03 | Paper |
Load balancing and locality in range-queriable data structures
Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing | 2015-08-03 | Paper |
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 - STOC '93 | 2015-05-07 | Paper |
Faster randomized consensus with an oblivious adversary
Distributed Computing | 2015-03-25 | Paper |
Stably computable predicates are semilinear
Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing | 2015-03-10 | Paper |
Fast deterministic consensus in a noisy environment
Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing | 2015-03-03 | Paper |
A modular approach to shared-memory consensus, with applications to the probabilistic-write model
Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing | 2015-03-02 | Paper |
Randomized loose renaming in \(O(\log \log n)\) time
Proceedings of the 2013 ACM symposium on Principles of distributed computing | 2015-03-02 | Paper |
Network construction with subgraph connectivity constraints
Journal of Combinatorial Optimization | 2015-02-16 | Paper |
Tight bounds for adopt-commit objects
Theory of Computing Systems | 2015-01-19 | Paper |
| Path-independent load balancing with unreliable machines | 2014-12-18 | Paper |
Randomized consensus in expected O(n n) individual work
Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing | 2014-12-12 | Paper |
| On the learnability of shuffle ideals | 2014-12-08 | Paper |
Faster randomized consensus with an oblivious adversary
Proceedings of the 2012 ACM symposium on Principles of distributed computing | 2014-12-05 | Paper |
Faster than optimal snapshots (for a while), preliminary version
Proceedings of the 2012 ACM symposium on Principles of distributed computing | 2014-12-05 | Paper |
Learning a circuit by injecting values
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
Approximate shared-memory counting despite a strong adversary
ACM Transactions on Algorithms | 2014-11-18 | Paper |
| Inoculation strategies for victims of viruses and the sum-of-squares partition problem | 2014-10-13 | Paper |
Tight bounds for asynchronous renaming
Journal of the ACM | 2014-09-12 | Paper |
The Complexity of Renaming
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Fault-tolerant routing in peer-to-peer systems
Proceedings of the twenty-first annual symposium on Principles of distributed computing | 2014-07-25 | Paper |
MAX registers, counters, and monotone circuits
Proceedings of the 28th ACM symposium on Principles of distributed computing | 2014-07-23 | Paper |
Polylogarithmic concurrent data structures from monotone circuits
Journal of the ACM | 2014-02-17 | Paper |
Effective storage capacity of labeled graphs
Information and Computation | 2014-02-11 | Paper |
Mutation systems
International Journal of Computer Mathematics | 2013-10-22 | Paper |
A simple population protocol for fast robust approximate majority
Distributed Computing | 2013-07-04 | Paper |
Fast computation by population protocols with a leader
Distributed Computing | 2013-06-28 | Paper |
The expansion and mixing time of skip graphs with applications
Distributed Computing | 2013-06-28 | Paper |
The computational power of population protocols
Distributed Computing | 2013-06-20 | Paper |
Computation in networks of passively mobile finite-state sensors
Distributed Computing | 2013-06-13 | Paper |
Relationships between broadcast and shared memory in reliable anonymous distributed systems
Distributed Computing | 2013-06-07 | Paper |
A modular approach to shared-memory consensus, with applications to the probabilistic-write model
Distributed Computing | 2013-02-04 | Paper |
On the learnability of shuffle ideals
Lecture Notes in Computer Science | 2012-10-16 | Paper |
Randomized load balancing by joining and splitting bins
Information Processing Letters | 2012-07-20 | Paper |
Low-contention data structures
Journal of Parallel and Distributed Computing | 2012-07-13 | Paper |
Learning acyclic probabilistic circuits using test paths
Journal of Machine Learning Research (JMLR) | 2012-04-17 | Paper |
Combining shared-coin algorithms
Journal of Parallel and Distributed Computing | 2012-03-07 | Paper |
Randomized consensus in expected \(O(n ^{2})\) total work using single-writer registers
Lecture Notes in Computer Science | 2011-10-28 | Paper |
Sublogarithmic test-and-set against a weak adversary
Lecture Notes in Computer Science | 2011-10-28 | Paper |
Mutation Systems
Language and Automata Theory and Applications | 2011-06-03 | Paper |
Inferring Social Networks from Outbreaks
Lecture Notes in Computer Science | 2010-10-01 | Paper |
| scientific article; zbMATH DE number 5764834 (Why is no real title available?) | 2010-08-06 | Paper |
Wait-free consensus with infinite arrivals
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Optimally learning social networks with activations and suppressions
Theoretical Computer Science | 2010-07-07 | Paper |
| scientific article; zbMATH DE number 5605125 (Why is no real title available?) | 2009-09-19 | Paper |
| scientific article; zbMATH DE number 5605099 (Why is no real title available?) | 2009-09-19 | Paper |
Learning large-alphabet and analog circuits with value injection queries
Machine Learning | 2009-03-31 | Paper |
Learning a circuit by injecting values
Journal of Computer and System Sciences | 2009-01-09 | Paper |
Optimally Learning Social Networks with Activations and Suppressions
Lecture Notes in Computer Science | 2008-10-14 | Paper |
Fast Computation by Population Protocols with a Leader
Lecture Notes in Computer Science | 2008-09-09 | Paper |
A Simple Population Protocol for Fast Robust Approximate Majority
Lecture Notes in Computer Science | 2008-09-02 | Paper |
Spreading Alerts Quietly and the Subgroup Escape Problem
Lecture Notes in Computer Science | 2008-03-18 | Paper |
Towards a theory of data entanglement
Theoretical Computer Science | 2008-01-07 | Paper |
Learning Large-Alphabet and Analog Circuits with Value Injection Queries
Learning Theory | 2008-01-03 | Paper |
| Towards understanding the predictability of stock markets from the perspective of computational complexity | 2006-01-23 | Paper |
Algorithmic Aspects of Wireless Sensor Networks
Lecture Notes in Computer Science | 2005-08-25 | Paper |
Relationships Between Broadcast and Shared Memory in Reliable Anonymous Distributed Systems
Lecture Notes in Computer Science | 2005-08-17 | Paper |
Compositional competitiveness for distributed algorithms
Journal of Algorithms | 2005-02-22 | Paper |
Lower bounds for distributed coin-flipping and randomized consensus
Journal of the ACM | 2005-01-25 | Paper |
| scientific article; zbMATH DE number 2081008 (Why is no real title available?) | 2004-08-04 | Paper |
| scientific article; zbMATH DE number 2079362 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2065154 (Why is no real title available?) | 2004-05-18 | Paper |
Fast deterministic consensus in a noisy environment
Journal of Algorithms | 2003-05-14 | Paper |
| Towards understanding the predictability of stock markets from the perspective of computational complexity | 2002-07-22 | Paper |
| scientific article; zbMATH DE number 1559571 (Why is no real title available?) | 2001-02-28 | Paper |
| scientific article; zbMATH DE number 1256740 (Why is no real title available?) | 1999-10-04 | Paper |
| scientific article; zbMATH DE number 1256649 (Why is no real title available?) | 1999-04-22 | Paper |
Fairness in Scheduling
Journal of Algorithms | 1999-01-17 | Paper |
Spreading Rumors Rapidly Despite an Adversary
Journal of Algorithms | 1998-08-30 | Paper |
On-line routing of virtual circuits with applications to load balancing and machine scheduling
Journal of the ACM | 1998-02-17 | Paper |
Randomized Consensus in Expected O(N\log ^2 N) Operations Per Processor
SIAM Journal on Computing | 1997-05-11 | Paper |
| scientific article; zbMATH DE number 910905 (Why is no real title available?) | 1996-07-28 | Paper |
Counting networks
Journal of the ACM | 1995-02-20 | Paper |
The expressive power of voting polynomials
Combinatorica | 1994-08-11 | Paper |
Time- and Space-Efficient Randomized Consensus
Journal of Algorithms | 1993-06-29 | Paper |
Fast randomized consensus using shared memory
Journal of Algorithms | 1990-01-01 | Paper |
