Theory Group

James Aspnes and Eric Ruppert. An introduction to population protocols. In Middleware for Network Eccentric and Mobile Applications, pages 97-120, Springer, 2009.

Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela and Kirk Pruhs. Nonclairvoyant speed scaling for flow and energy. In Proc. 26th International Symposium on Theoretical Aspects of Computer Science, 2009.

Jeff Edmonds, N. Bansal, H. L. Chan, and K. Pruhs, Speed scaling of processes with arbitrary speedup curves on a multiprocessor, In SPAA, ACM Symp. of Parallelism in Algorithms and Architectures, 2009.

Jeff Edmonds and Kirk Pruhs. Scalably scheduling processes with arbitrary speedup curves. In Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, pages 685-692, 2009.

Rachid Guerraoui and Eric Ruppert. Names trump malice: Tiny mobile agents can tolerate Byzantine failures. In Proc. 36th International Colloquium on Automata, Languages and Programming, volume 2, pages 484-495, 2009.

Niloufar Shafiei. Non-blocking array-based algorithm for stack and queue. In Proc. 10th International Conference on Distributed Computing and Networking, pages 55-66, 2009.

Hagit Attiya, Rachid Guerraoui and Eric Ruppert. Partial snapshot objects. In Proc. 20th ACM Symposium on parallelism in Algorithms and Architectures, pages 336-343, 2008.

Franck van Breugel, Babita Sharma and James Worrell. Approximating a behavioural pseudometric without discount. Logical Methods in Computer Science, 4(2:2), 2008.

Jeff Edmonds. How to Think About Algorithms. Cambridge University Press, 2008.

Jeff Edmonds, Kirk Pruhs and Jaisingh Solanki. Confidently cutting a cake into approximately fair pieces. In Proc. Conference on Algorithmic Aspects in Information and Management, 2008.

Faith Ellen, Panagiota Fatourou and Eric Ruppert. The space complexity of unbounded timestamps. Distributed Computing, 21(2), pages 103-115, 2008.

Stuart MacLean and Suprakash Datta. A lower bound on range-free node localization algorithms. In Proc. IEEE International Symposium on Wireless Communication Systems, pages 628-632, 2008.

George Tourlakis. Mathematical Logic, Wiley-Interscience, 2008.

Jeff Edmonds. Embedding into l^2_infinity is easy; Embedding into l^3_infinity is NP-complete. In Discrete and Computational Geometry, pages 747-765 2008.

Jeff Edmonds. Scheduling with Equipartition; in Encyclopedia of Algorithms, Springer, Editor Ming-Yang Kao, 2008.

Dana Angluin, James Aspnes, David Eisenstat and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4), pages 279-304, 2007.

Franck van Breugel, Claudio Hermida, Michael Makkai and James Worrell. Recursively defined metric spaces without contraction. Theoretical Computer Science, 380(1-2), pages 143-163, 2007.

Masoomeh Rudafshani and Suprakash Datta. In Proc. 6th International Conference on Information Processing in Sensor Networks, pages 51-60, 2007.

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui and Eric Ruppert. Secretive birds: Privacy in population protocols. In Proc. 11th International Conference on Principles of Distributed Systems, pages 329-342, 2007.

Jeff Edmonds. Embedding into l^2_infinity is easy; Embedding into l^3_infinity is NP-complete. In Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, pages 522-531, 2007.

Faith Ellen, Panagiota Fatourou and Eric Ruppert. Time lower bounds for implementations of multi-writer snapshots. Journal of the ACM, 54(6), article 30, 2007.

Rachid Guerraoui and Eric Ruppert. Anonymous and fault-tolerant shared-memory computing. Distributed Computing, 20(3), pages 165-177, 2007.

Eric Ruppert. The anonymous consensus hierarchy and naming problems. In Proc. 11th International Conference on Principles of Distributed Systems, pages 386-400, 2007.

James Aspnes, Faith Ellen Fich and Eric Ruppert. Relationships between broadcast and shared memory in reliable anonymous distributed systems. Distributed Computing, 18(3), pages 209-219, 2006.

Franck van Breugel and James Worrell. Approximating and computing behavioural distances in probabilistic transition systems. Theoretical Computer Science, 360(1-3), pages 373-385, 2006.

Sashka Davis, Jeff Edmonds and Russell Impagliazzo. Online algorithms to minimize resource reallocations and network communication. In Proc. 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pages 104-115, 2006.

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui and Eric Ruppert. When birds die: Making population protocols fault-tolerant. In Proc. IEEE International Conference on Distributed Computing in Sensor Systems, pages 51-66, 2006.

Jeff Edmonds and Kirk Pruhs. Balanced allocations of cake. In Proc. 47th IEEE Symposium on Foundations of Computer Science, pages 623-634, 2006.

Jeff Edmonds and Kirk Pruhs. Cake cutting really is not a piece of cake. In Proc. 17th ACM-SIAM Symposium on Discrete Algorithms, pages 271-278, 2006.

Panagiota Fatourou, Faith Ellen Fich and Eric Ruppert. Time-space tradeoffs for implementations of snapshots. In Proc. 38th ACM Symposium on Theory of Computing, pages 169-178, 2006.

Francisco Kibedi and George Tourlakis. A modal extension of weak generalisation predicate logic. Logic Journal of the IGPL, 14(4), pages 591-621, 2006.