James Aspnes

Work address

Yale University
Department of Computer Science
51 Prospect Street
P.O. Box 208285
New Haven, CT 06520-8285
+1 203 432 1232
email: aspnes@cs.yale.edu

Home address

39 Willow Rd
Guilford, CT 06437-1723
+1 203 458 3023

Degrees

• PhD (CS) 1992, Carnegie-Mellon University.
• SM (EECS) 1987, Massachusetts Institute of Technology.
• SB (Math) 1987, Massachusetts Institute of Technology.

Experience

• Yale University. Assistant Professor of Computer Science, 1993–1998; Associate Professor of Computer Science (term), 1998–2001; Associate Professor of Computer Science (tenured), 2001–2005; Professor of Computer Science, 2005–.
• IBM Almaden Research Center. Visiting Scientist, 1992–1993.

Honors

• The Dylan Hixon '88 Prize for Teaching Excellence in the Natural Sciences. Awarded by Yale College, 2000.
• IBM Graduate Fellowship, 1991–1992.
• NSF Graduate Fellowship, 1987–1990.
• Phi Beta Kappa, 1987.

Grants

• NSF award CNS-0435201, 2004–2008. (Co-PI, $349,987.)
• NSF award CNS-0305258, 2003–2006. (PI, $300,000.)
• NSF award CCR-0098078, 2001–2004. (PI, $200,940.)
• NSF award CCR-9820888, 1999–2002. (PI, $131,264.)
• NSF award CCR-9415410, 1995–1997. (Co-PI, $122,318.)
• NSF award CCR-9410228, 1994–1998. (PI, $78,568.)

Professional activities

• Editorial board member: Algorithmica, 2004–; Distributed Computing, 2008–2011.
• Program committee chair: PODC 2005, DCOSS 2007.
• Program committee vice chair: DCOSS 2006 (Algorithms track).
• Program committee member: PODC 1996, PODC 1997, PODC 1999, FOCS 1999, FOCS 2001, PODC 2003, PODC 2004, DCOSS 2005, MPPS 2005, PODC 2005, DCOSS 2006, SSS 2006, IPTPS 2007, ICALP 2007, DCOSS 2007, DISC 2007, SSS 2007, STOC 2008, DCOSS 2008, IPDPS 2009, COCOON 2009, DCOSS 2009, DISC 2009, ALGOSENSORS 2009.
• Steering committee member: PODC, 2004–2007.

Memberships

• Association for Computing Machinery, SIGACT.

Publications

Also available as a BibTex file.

• Randomized load balancing by joining and splitting bins, with Yitong Yin. In preparation. [PDF]
• Approximate shared-memory counting despite a strong adversary, with Keren Censor. To appear, SODA 2009. [PDF]
• Collisions lead to shallower decision trees, with Murat Demirbas, Ryan O'Donnell, Atri Rudra, and Steve Uurtamo. In preparation. [PDF]
• Optimally learning social networks with activations and suppressions, with Dana Angluin and Lev Reyzin. Nineteenth International Conference on Algorithmic Learning Theory, Lecture Notes in Computer Science 5254, Springer-Verlag, October 2008, pp. 272–286. [PDF]
• Randomized consensus in expected O(n log n) individual work, with Hagit Attiya and Keren Censor. In Twenty-Seventh annual ACM Symposium on Principles of Distributed Computing, August 2008, pp. 325–334. [PDF]
• Learning acyclic probabilistic circuits using test paths, with Dana Angluin, Jiang Chen, David Eisenstat, and Lev Reyzin. Twenty-First International Conference on Learning Theory (COLT), July 2008, pp. 169–179. [PDF]
• Ranged hash functions and the price of churn, with Muli Safra and Yitong Yin. Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2008, pp. 1066–1075. [PDF]
• O(log n)-time overlay network construction from graphs with out-degree 1, with Yinghua Wu. Principles of Distributed Systems; 11th International Conference, OPODIS 2007, Gaudaloupe, French West Indies, December 17–20, 2007, Proceedings. Lecture Notes in Computer Science 4878. Springer-Verlag, December 2007, pp. 286–300. [PDF]
• Worm versus alert: Who wins in a battle for control of a large-scale network? , with Navin Rustagi and Jared Saia. Principles of Distributed Systems; 11th International Conference, OPODIS 2007, Gaudaloupe, French West Indies, December 17–20, 2007, Proceedings. Lecture Notes in Computer Science 4878. Springer-Verlag, December 2007, pp. 443–456. [PDF]
• The computational power of population protocols, with Dana Angluin, David Eisenstat, and Eric Ruppert. Distributed Computing 20(4):279–304, November 2007. (PODC 2006 special issue.) Incorporates material previously appearing in OPODIS 2005 and PODC 2006. Available as arXiv:cs.CC/0608084. [PDF]
• An introduction to population protocols, with Eric Ruppert. Bulletin of the European Association for Theoretical Computer Science, Distributed Computing Column, 93:98–117, October 2007. [PDF]
• A simple population protocol for fast robust approximate majority, with Dana Angluin and David Eisenstat. Distributed Computing 21(2):87–102, July 2008 (DISC 2007 special issue). An earlier version appeared in Distributed Computing, 21st International Symposium, DISC 2007, Lemesos, Cyprus, September 24–26, 2007, Proceedings, pp. 20–32. [PDF]
• Learning large-alphabet and analog circuits with value injection queries, with Dana Angluin, Jiang Chen, and Lev Reyzin. Machine Learning 72(1–2):113–138, August 2008 (COLT 2007 special issue). An earlier version appeared in Twentieth Annual Conference on Learning Theory, June 2007, pp. 51–65 (Winner, Best Student Paper award). [PDF]
• Path-independent load balancing with unreliable machines, with Yang Richard Yang and Yitong Yin. Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2007, pp. 814–823. Available as arXiv:cs.DS/0607026. [PDF]
• A theory of network localization, with T. Eren, D. K. Goldenberg, A. S. Morse, W. Whiteley, Y. R. Yang, B. D. O. Anderson, and P. N. Belhumeur. IEEE Transactions on Mobile Computing, 12(5):1663–1678, December 2006. [PDF]
• Eight open problems in distributed computing, with Costas Busch, Shlomi Dolev, Panagiota Fatourou, Chryssis Georgiou, Alex Shvartsman, Paul Spirakis, and Roger Wattenhofer. Bulletin of the European Association for Theoretical Computer Science, Distributed Computing Column, 90:109–126, October 2006. [PDF]
• Fast computation by population protocols with a leader, with Dana Angluin and David Eisenstat. Distributed Computing 21(2):87–102, July 2008 (DISC 2007 special issue). An earlier version appeared in Distributed Computing, 20th International Symposium, DISC 2006, pp. 61–75. Available as YALEU/DCS/TR-1332, May 2006. [PDF]
• Stably computable predicates are semilinear, with Dana Angluin and David Eisenstat. Twenty-Fifth ACM Symposium on Principles of Distributed Computing, July 2006, pp. 292–299. [PDF]
• Learning a circuit by injecting values, with Dana Angluin, Jiang Chen, and Yinghua Wu. Thirty-Eighth Annual ACM Symposium on Theory of Computing, May 2006, pp. 584–593. To appear, Journal of Computing and System Sciences, Special Issue on Learning Theory. [PDF]
• On the power of anonymous one-way communication, with Dana Angluin, David Eisenstat, and Eric Ruppert. Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, December 2005, pp. 396–411. [PDF]
• Self-stabilizing population protocols, with Dana Angluin, Michael J. Fischer, and Hong Jiang. Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, December 2005, pp. 103–117. To appear, ACM Transactions on Autonomous and Adaptive Systems, Special Issue on Stabilization, Safety, and Security of Distributed Systems. [PDF]
• Skip B-trees, with Ittai Abraham and Jian Yuan. Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, December 2005, pp. 366–380. [PDF]
• Spreading alerts quietly and the subgroup escape problem, with Zoë Diamadi, Kristian Gjøsteen, René Peralta, and Aleksandr Yampolskiy. Advances in Cryptology — ASIACRYPT 2005: 11th International Conference on the Theory and Application of Cryptology and Information Security, Chennai, India, December 4–8, 2005. Proceedings. Lecture Notes in Computer Science 3788, Springer-Verlag, December 2005, pp. 253–272. Available as YALEU/DCS/TR-1326, December 2005. Submitted to Journal of Cryptology, February 2006. [PDF]
• Distributed data structures for P2P systems, with Gauri Shah. In Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wireless and Peer-to-Peer Networks, Jie Wu, editor, CRC Press, 2005, pages 685–700.
• Exposing computationally-challenged Byzantine impostors, with Collin Jackson and Arvind Krishnamurthy. Available as YALEU/DCS/TR-1332, July 2005. [PDF]
• Fast construction of overlay networks, with Dana Angluin, Jiang Chen, Yinghua Wu, and Yitong Yin. Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, July 2005, pages 145–154. [PDF]
• The expansion and mixing time of skip graphs with applications, with Udi Wieder. Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, July 2005, pages 126–134. To appear, Distributed Computing. [PDF]
• Stably computable properties of network graphs, with Dana Angluin, Melody Chan, Michael J. Fischer, Hong Jiang, and René Peralta. In Distributed Computing in Sensor Systems: First IEEE International Conference, DCOSS 2005, Marina del Rey, CA, USE, June/July, 2005, Proceedings, Lecture Notes in Computer Science, volume 3560, Springer-Verlag, June 2005, pp. 63–74. [PDF]
• Inoculation strategies for victims of viruses and the sum-of-squares partition problem, with Kevin Chang and Aleksandr Yampolskiy. Journal of Computer and System Sciences, 72(6):1077–1093, September 2006. An ealier version appeared in Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2005, pp. 43–52. Available as YALEU/DCS/TR-1295, July 2004. [PS]
• Relationships between broadcast and shared memory in reliable anonymous distributed systems, with Faith Ellen Fich and Eric Ruppert. Distributed Computing 18(3):209–219, February 2006. (DISC 2004 special issue.) An earlier version appeared in Proceedings of the Eighteenth International Symposium on Distributed Computing (DISC 2004), October 2004, pp. 260–274. [PDF]
• Towards a theory of data entanglement, with Joan Feigenbaum, Aleksandr Yampolskiy, and Sheng Zhong. Theoretical Computer Science 389(1–2):26–43, December 2007. An earlier version appeared in Ninth European Symposium on Research in Computer Security, Lecture Notes in Computer Science 3192, Springer-Verlag, September 2004, pp. 177–192. [PDF]
• Computation in networks of passively mobile finite-state sensors, with Dana Angluin, Zoë Diamadi, Michael J. Fischer, and René Peralta. Distributed Computing 18(4):235–253, March 2006. (PODC 2004 special issue.) An earlier version appeared in Twenty-Third Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, July 2004, pp. 290–299. [PDF]
• Load balancing and locality in range-queriable data structures, with Jonathan Kirsch and Arvind Krishnamurthy. Twenty-Third ACM Symposium on Principles of Distributed Computing, July 2004, pp. 115–124. [PDF]
• On the computational complexity of sensor network localization, with David Goldenberg and Yang Richard Yang. Algorithmic Aspects of Wireless Sensor Networks: First International Workshop, ALGOSENSORS 2004, Turku, Finland, July 16, 2004. Proceedings. Lecture Notes in Computer Science 3121, Springer-Verlag, 2004, pp. 32–44. Available as YALEU/DCS/TR-1282, April 2004. [PDF]
• Urn automata, with Dana Angluin, Zoë Diamadi, Michael J. Fischer, and René Peralta. Available as YALEU/DCS/TR-1280, November 2003. [PDF]
• Randomized protocols for asynchronous consensus. Invited survey paper for Distributed Computing PODC 20th anniversary issue, 16:(2–3):165–175, September 2003. Available as arXiv:cs.DS/0209014. [PDF]
• Towards better definitions and measures of Internet security, with Joan Feigenbaum, Michael Mitzenmacher, and David C. Parkes. Workshop on Large-Scale-Network Security and Deployment Obstacles, Landsdowne VA, March 2003. [PDF]
• Skip graphs, with Gauri Shah. ACM Transactions on Algorithms, 3(4):37, November 2007. An earlier version appeared in Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2003, pp. 384–393. Available as arXiv:cs.DS/0306043. [PDF]
• Fault-tolerant routing in peer-to-peer systems, with Zoë Diamadi and Gauri Shah. Twenty-First ACM Symposium on Principles of Distributed Computing, July 2002, pp. 223–232. Submitted to Distributed Computing. Available as arXiv:cs.DS/0302022. [PDF]
• Wait-free consensus with infinite arrivals, with Gauri Shah and Jatin Shah. Thirty-Fourth Annual ACM Symposium on Theory of Computing, May 2002, pp. 524–533. [PDF]
• Opportunity-cost algorithms for combinatorial auctions, with Karhan Akcoglu, Bhaskar DasGupta, and Ming-Yang Kao. In E. J. Kontoghiorghes, B. Rustem, and S. Siokos, eds., Applied Optimization 74: Computational Methods in Decision-Making, Economics and Finance, Kluwer Academic Publishers, 2002, pp. 455–479. An earlier version is available as DIMACS technical report 2000-27 and as arXiv:cs.CE/0010031. [PDF]
• A combinatorial toolbox for protein sequence design and landscape analysis in the Grand Canonical model, with Julia Hartling, Ming-Yang Kao, Junhyong Kim, and Gauri Shah. Journal of Computational Biology, 9(5):721–741, October, 2002. An earlier version appeared in Twelfth Annual International Symposium on Algorithms and Computation, December 2001, pp. 403–415. Available as arXiv:cs.CE/0101015. [PDF]
• Towards understanding the predictability of stock markets from the perspective of computational complexity, with David F. Fischer, Michael J. Fischer, Ming-Yang Kao, and Alok Kumar. Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2001, pp. 745–754. Available as arXiv:cs.CE/0010021. [PDF]
• Fast deterministic consensus in a noisy environment. Journal of Algorithms, 45(1):16–39, October, 2002. An earlier version appeared in Nineteenth Annual ACM Symposium on Principles of Distributed Computing, July 2000, pp. 299–309. Available as arXiv:cs.DS/0206012. [PDF]
• Lower bounds for distributed coin-flipping and randomized consensus. Journal of the Association for Computing Machinery 45(3):415–450, May 1998. An earlier version appeared in Twenty-Ninth Annual ACM Symposium on Theory of Computing, May 1997, pp. 559–568. [PDF]
• Competitive analysis of distributed algorithms. Invited survey paper, Dagstuhl-Seminar on On-line Algorithms, Schloss Dagstuhl, June 23–28, 1996. In Amos Fiat, Gerhard Woeginger, eds., Online Algorithms: The State of the Art, Lecture Notes in Computer Science 1442, Springer-Verlag, 1998, pp. 118–146.
• Compositional competitiveness for distributed algorithms, with Orli Waarts. Journal of Algorithms 54(2):127–151, February 2005. Available as arXiv:cs.DS/0306044. An earlier version appeared in Twenty-Eighth Annual ACM Symposium on Theory of Computing, May 1996, pp. 237–246, under the title ``Modular competitiveness for distributed algorithms.'' A brief announcement of this work appeared in Fourteenth Annual ACM Symposium on Principles of Distributed Computing, August 1995, p. 252, under the title ``A modular measure of competitive performance for distributed algorithms.'' [PDF]
• Spreading rumors rapidly despite an adversary, with William Hurwood. Journal of Algorithms 26(2):386–411, February 1998. An earlier version appeared in Fifteenth Annual ACM Symposium on Principles of Distributed Computing, May 1996, pp. 143–151. [PDF]
• Fairness in scheduling, with Miklos Ajtai, Moni Naor, Yuval Rabani, Leonard J. Schulman, and Orli Waarts. Journal of Algorithms 29(2):306–357, November, 1998. (SODA 1995 special issue.) An earlier version appeared in Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, January 1995, pp. 477–485. [PDF]
• A theory of competitive analysis for distributed algorithms, with Miklos Ajtai, Cynthia Dwork, and Orli Waarts. Thirty-Fifth IEEE Symposium on Foundations of Computer Science, November 1994, pp. 401–411. A brief announcement of this work appeared in Thirteenth ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 1994, under the title ``Competitive analysis for distributed algorithms.'' [PDF]
• On-line routing of virtual circuits with applications to load balancing and machine scheduling, with Yossi Azar, Amos Fiat, Serge Plotkin, and Orli Waarts. Journal of the Association for Computing Machinery 44(3):486–504, May 1997. An earlier version appeared in Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 1993, pp. 623–631, under the title ``On-line load balancing with applications to machine scheduling and virtual circuit routing.'' [PDF]
• Randomized consensus in O(n log² n) operations per processor, with Orli Waarts. SIAM Journal on Computing 25(5):1024–1044, October 1996. An earlier version appeared in Thirty-Third IEEE Symposium on Foundations of Computer Science, October 1992, pp. 137–146. [PDF]
• Wait-Free Consensus. PhD thesis, Carnegie-Mellon University, 1992. Available as CMU-CS-TR-92-164. [PDF]
• Counting networks, with Maurice Herlihy and Nir Shavit. Journal of the Association for Computing Machinery 41(5):1020–1048, September 1994. An earlier version appeared under the title ``Counting networks and multiprocessor coordination,'' in Twenty-Third Annual ACM Symposium on Theory of Computing, May 1991, pp. 348–358. [PS]
• The expressive power of voting polynomials, with Richard Beigel, Merrick Furst, and Steven Rudich. Combinatorica 14(2):1–14, 1994. An earlier version appeared in Twenty-Third Annual ACM Symposium on Theory of Computing, May 1991, pp. 402–409. [PDF]
• Fast randomized consensus using shared memory, with Maurice Herlihy. Journal of Algorithms 11(3):441–461, September 1990. [PDF]
• Time- and space-efficient randomized consensus. Journal of Algorithms 14(3):414–431, May 1993. An earlier version appeared in Ninth ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, August 1990, pp. 325–331. [PDF]
• Wait-free data structures in the asynchronous PRAM model, with Maurice Herlihy. Second Annual ACM Symposium on Parallel Algorithms and Architectures, July 1990, pp. 340–349. [PDF]
• A theory of timestamp-based concurrency control for nested transactions, with Alan Fekete, Nancy Lynch, Michael Merritt, and William Weihl. Fourteenth International Conference on Very Large Databases, August 1988, pp. 431–444. [PDF]

Last updated November 17th, 2008