Curriculum vitæ

The latest version of this document is available at https://www.davideisenstat.com/cv/.

Publications

• [BibTeX]  Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest.  Time-space trade-offs in population protocols.  arXiv:1602.08032v7 [cs.DC], April 2017.

• [BibTeX]  Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest.  Time-space trade-offs in population protocols.  In Proceedings of the Twenty-Eighth Symposium on Discrete Algorithms (SODA), pages 2560–2579, January 2017.

• [BibTeX]  David Eisenstat, Claire Mathieu, and Nicolas Schabanel.  Facility location in evolving metrics.  In Proceedings of the Forty-First International Colloquium on Automata, Languages, and Programming (ICALP), Part II, pages 459–470, July 2014.

• [BibTeX]  David Eisenstat.  Toward practical planar graph algorithms.  PhD thesis, Computer Science Department, Brown University, May 2014.

• [BibTeX]  Dana Angluin, James Aspnes, Rida A. Bazzi, Jiang Chen, David Eisenstat, and Goran Konjevod.  Effective storage capacity of labeled graphs.  Information and Computation, 234:44–56, February 2014.

• [BibTeX]  David Eisenstat, Philip N. Klein, and Claire Mathieu.  Approximating k-center in planar graphs.  In Proceedings of the Twenty-Fifth Symposium on Discrete Algorithms (SODA), pages 617–627, January 2014.

• [BibTeX]  David Eisenstat and Philip N. Klein.  Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs.  In Proceedings of the Forty-Fifth Symposium on Theory of Computing (STOC), pages 735–744, June 2013.

• [BibTeX]  James Aspnes, David Eisenstat, and Yitong Yin.  Low-contention data structures.  Journal of Parallel and Distributed Computing, 72(5):705–715, May 2012.

• [BibTeX]  David Eisenstat, Philip N. Klein, and Claire Mathieu.  An efficient polynomial-time approximation scheme for Steiner forest in planar graphs.  arXiv:1110.1320v2 [cs.DS], October 2011.

• [BibTeX]  David Eisenstat, Philip N. Klein, and Claire Mathieu.  An efficient polynomial-time approximation scheme for Steiner forest in planar graphs.  In Proceedings of the Twenty-Third Symposium on Discrete Algorithms (SODA), pages 626–638, January 2012.

• [BibTeX]  David Eisenstat.  Random road networks: the quadtree model.  In Proceedings of the Eighth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pages 76–84, January 2011.

• [BibTeX]  Dana Angluin, David Eisenstat, Leonid (Aryeh) Kontorovich, and Lev Reyzin.  Lower bounds on learning random structures with statistical queries.  In Proceedings of the Twenty-First International Conference on Algorithmic Learning Theory (ALT), pages 194–208, October 2010.

• [BibTeX]  Dana Angluin, James Aspnes, Rida A. Bazzi, Jiang Chen, David Eisenstat, and Goran Konjevod.  Storage capacity of labeled graphs.  In Proceedings of the Twelfth International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 573–587, September 2010.  Journal article: Effective storage capacity of labeled graphs.

• [BibTeX]  James Aspnes, David Eisenstat, and Yitong Yin.  Low-contention data structures.  In Proceedings of the Twenty-Second Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 345–354, June 2010.

• [BibTeX]  David Eisenstat.  k-fold unions of low-dimensional concept classes.  Information Processing Letters, 109(23-24):1232–1234, November 2009.

• [BibTeX]  Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, and Lev Reyzin.  Learning acyclic probabilistic circuits using test paths.  Journal of Machine Learning Research, 10(Aug):1881–1911, August 2009.

• [BibTeX]  David Eisenstat.  Two-enqueuer queue in Common2.  arXiv:0805.0444v2 [cs.DC], April 2009.

• [BibTeX]  Dana Angluin, James Aspnes, and David Eisenstat.  Fast computation by population protocols with a leader.  Distributed Computing, 21(3):183–199, September 2008.

• [BibTeX]  Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat, and Lev Reyzin.  Learning acyclic probabilistic circuits using test paths.  In Proceedings of the Twenty-First Conference on Learning Theory (COLT), pages 169–180, July 2008.

• [BibTeX]  Dana Angluin, James Aspnes, and David Eisenstat.  A simple population protocol for fast robust approximate majority.  Distributed Computing, 21(2):87–102, July 2008.

• [BibTeX]  David Eisenstat, Jennifer Feder, Greg Francos, Gary Gordon, and Amanda Redlich.  Expected rank and randomness in rooted graphs.  Discrete Applied Mathematics, 156(5):746–756, March 2008.

• [BibTeX]  David Eisenstat, Gary Gordon, and Amanda Redlich.  Combinatorial properties of a rooted graph polynomial.  SIAM Journal on Discrete Mathematics, 22(2):776–785, March 2008.

• [BibTeX]  Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert.  The computational power of population protocols.  Distributed Computing, 20(4):279–304, November 2007.

• [BibTeX]  Dana Angluin, James Aspnes, and David Eisenstat.  A simple population protocol for fast robust approximate majority.  In Proceedings of the Twenty-First International Symposium on Distributed Computing (DISC), pages 20–32, September 2007.

• [BibTeX]  Stephen Soltesz, Soner Sevinc, David Eisenstat, Marc Fiuczynski, and Larry Peterson.  On the design and evolution of an architecture for federation.  In Proceedings of the Second International Workshop on Real Overlays and Distributed Systems (ROADS), July 2007.

• [BibTeX]  David Eisenstat and Dana Angluin.  The VC dimension of k-fold union.  Information Processing Letters, 101(5):181–184, March 2007.

• [BibTeX]  Dana Angluin, James Aspnes, and David Eisenstat.  Fast computation by population protocols with a leader.  In Proceedings of the Twentieth International Symposium on Distributed Computing (DISC), pages 61–75, September 2006.

• [BibTeX]  Dana Angluin, James Aspnes, and David Eisenstat.  Stably computable predicates are semilinear.  In Proceedings of the Twenty-Fifth Symposium on Principles of Distributed Computing (PODC), pages 292–299, July 2006.  Journal article: The computational power of population protocols.

• [BibTeX]  Virendra J. Marathe, Michael F. Spear, Christopher Heriot, Athul Acharya, David Eisenstat, William N. Scherer III, and Michael L. Scott.  Lowering the overhead of nonblocking software transactional memory.  In Proceedings of the First Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT), June 2006.

• [BibTeX]  Arrvindh Shriraman, Virendra J. Marathe, Sandhya Dwarkadas, Michael L. Scott, David Eisenstat, Christopher Heriot, William N. Scherer III, and Michael F. Spear.  Hardware acceleration of software transactional memory.  In Proceedings of the First Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (TRANSACT), June 2006.

• [BibTeX]  Virendra J. Marathe, Michael F. Spear, Christopher Heriot, Athul Acharya, David Eisenstat, William N. Scherer III, and Michael L. Scott.  Lowering the overhead of nonblocking software transactional memory.  Technical Report 893, Computer Science Department, University of Rochester, May 2006.

• [BibTeX]  David Eisenstat and Gary Gordon.  Non-isomorphic caterpillars with identical subtree data.  Discrete Mathematics, 306(8-9):827–830, May 2006.

• [BibTeX]  Arrvindh Shriraman, Virendra J. Marathe, Sandhya Dwarkadas, Michael L. Scott, David Eisenstat, Christopher Heriot, William N. Scherer III, and Michael F. Spear.  Hardware acceleration of software transactional memory.  Technical Report 887, Computer Science Department, University of Rochester, March 2006.

• [BibTeX]  Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert.  On the power of anonymous one-way communication.  In Proceedings of the Ninth International Conference on Principles of Distributed Systems (OPODIS), pages 396–411, December 2005.  Journal article: The computational power of population protocols.

• [BibTeX]  David Eisenstat.  Simpler proofs of the power of one query to a p-selective set.  Technical Report 883, Computer Science Department, University of Rochester, October 2005.

Education

• PhD 2014, Computer Science, Brown University.
• ScM 2011, Computer Science, Brown University.
• Graduate studies 2006–2007, Computer Science, Princeton University.
• BS 2006, Computer Science, University of Rochester (summa cum laude, highest distinction and highest honors in research in Computer Science).
• BA 2006, Mathematics, University of Rochester (summa cum laude, highest distinction in Mathematics).

Awards and honors

• van Dam Fellow, Computer Science Department, Brown University, Summer 2011.
• Best Student Paper, SSS 2010.
• Honorable Mention, National Science Foundation (NSF) Graduate Research Fellowship Program (GRFP), 2006 and 2010.
• Best Student Paper, DISC 2007.
• National Defense Science and Engineering Graduate (NDSEG) Fellow, 2006–2007.
• Gordon Y.S. Wu Fellow, School of Engineering and Applied Science (SEAS), Princeton University, 2006–2007.
• Outstanding Undergraduate Award, Computing Research Association (CRA), 2006.
• Phi Beta Kappa (ΦΒΚ), University of Rochester, 2005 (junior year).
• Stoddard Prize, Mathematics Department, University of Rochester, 2004.

Teaching experience

• TA, Coding the Matrix: Linear Algebra through Computer Science Applications, Brown University, Fall 2012.
• TA, Approximation Algorithms (CSCI2510), Brown University, Fall 2011.
• TA, Introduction to Computational Geometry (CSCI1950J), Brown University, Spring 2011.
• TA, Operating Systems (COS 318), Princeton University, Fall 2007.