David Eisenstat’s Curriculum Vitae

Education

• 2009–present: Ph.D. student (candidate 2011–present), Computer Science, Brown University. Advisor: Claire Mathieu
• 2011: Sc.M., Computer Science, Brown University
• 2006: B.S. (Honors), Computer Science, B.A., Mathematics, University of Rochester (summa cum laude)

Honors

• Best Student Paper, SSS 2010
• Best Student Paper, DISC 2007
• National Defense Science and Engineering Graduate (NDSEG) Fellow, 2006–2007
• NSF Graduate Research Fellowship Program, Honorable Mention
• Computing Research Association Outstanding Undergraduate Award, 2006
• Phi Beta Kappa, 2005 (elected as a junior)

Papers

• David Eisenstat, Philip N. Klein and Claire Mathieu: An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. SODA 2012, the Twenty-Third Annual ACM–SIAM Symposium on Discrete Algorithms (January 2012).
• David Eisenstat and Philip N. Klein: A dynamic-tree product line. October 2011. Submitted.
• David Eisenstat: Random road networks: the quadtree model. ANALCO 2011, the Eighth Workshop on Analytic Algorithmics and Combinatorics: 76–84 (January 2011).
• Dana Angluin, David Eisenstat, Leonid (Aryeh) Kontorovich and Lev Reyzin: Lower bounds on learning random structures with statistical queries. ALT 2010, the Twenty-First International Conference on Algorithmic Learning Theory: 194–208 (October 2010).
• Dana Angluin, James Aspnes, Rida A. Bazzi, Jiang Chen, David Eisenstat and Goran Konjevod: Storage capacity of labeled graphs. SSS 2010, the Twelfth International Symposium on Stabilization, Safety, and Security of Distributed Systems: 573–587 (September 2010). Best Student Paper.
• James Aspnes, David Eisenstat and Yitong Yin: Low-contention data structures. SPAA 2010, the Twenty-Second ACM Symposium on Parallelism in Algorithms and Architectures: 345–354 (June 2010).
• David Eisenstat: k-fold unions of low-dimensional concept classes. Information Processing Letters 109(23–24): 1232–1234 (November 2009).
• 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). Extended abstract appeared at COLT 2008.
• David Eisenstat: Two-enqueuer queue in Common2. April 2009.
• Dana Angluin, James Aspnes and David Eisenstat: Fast computation by population protocols with a leader. Distributed Computing 21(3): 183–199 (September 2008). Extended abstract appeared at DISC 2006.
• Dana Angluin, James Aspnes, Jiang Chen, David Eisenstat and Lev Reyzin: Learning acyclic probabilistic circuits using test paths. COLT 2008, the Twenty-First Annual Conference on Learning Theory: 169–180 (July 2008).
• Dana Angluin, James Aspnes and David Eisenstat: A simple population protocol for fast robust approximate majority. Distributed Computing 21(2): 87–102 (July 2008). Extended abstract appeared at DISC 2007.
• David Eisenstat, Gary Gordon and Amanda Redlich: Combinatorial properties of a rooted graph polynomial. SIAM Journal on Discrete Mathematics 22(2): 776–785 (April 2008).
• David Eisenstat, Jennifer Feder, Gregory Francos, Gary Gordon and Amanda Redlich: Expected rank and randomness in rooted graphs. Discrete Applied Mathematics 156(5): 746–756 (March 2008).
• Dana Angluin, James Aspnes, David Eisenstat and Eric Ruppert: The computational power of population protocols. Distributed Computing 20(4): 279–304 (November 2007). Extended abstracts appeared at OPODIS 2005 and PODC 2006.
• Dana Angluin, James Aspnes and David Eisenstat: A simple population protocol for fast robust approximate majority. DISC 2007, the Twenty-First International Symposium on Distributed Computing: 20–32 (September 2007). Best Student Paper, invited to a special issue.
• Stephen Soltesz, Soner Sevinc, David Eisenstat, Marc Fiuczynski and Larry Peterson: On the design and evolution of an architecture for federation. ROADS 2007, the Second International Workshop on Real Overlays and Distributed Systems (July 2007).
• David Eisenstat and Dana Angluin: The VC dimension of k-fold union. Information Processing Letters 101(5): 181–184 (March 2007).
• Dana Angluin, James Aspnes and David Eisenstat: Fast computation by population protocols with a leader. DISC 2006, the Twentieth International Symposium on Distributed Computing: 61–75 (September 2006).
• Dana Angluin, James Aspnes and David Eisenstat: Stably computable predicates are semilinear. PODC 2006, the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing: 292–299 (July 2006). Invited to a special issue. Full version incorporated into “The computational power of population protocols”.
• 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. TRANSACT 2006, the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (June 2006). In conjunction with PLDI 2006. A previous, expanded version is available as TR 893, Computer Science Department, University of Rochester.
• 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. TRANSACT 2006, the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing (June 2006). In conjunction with PLDI 2006. A previous, expanded version is available as TR 887, Computer Science Department, University of Rochester.
• David Eisenstat and Gary Gordon: Non-isomorphic caterpillars with identical subtree data. Discrete Mathematics 306(8–9): 827–830 (May 2006).
• Dana Angluin, James Aspnes, David Eisenstat and Eric Ruppert: On the power of anonymous one-way communication. OPODIS 2005, the Ninth International Conference on Principles of Distributed Systems: 396–411 (December 2005). Full version incorporated into “The computational power of population protocols”.
• David Eisenstat: Simpler proofs of the power of one query to a p-selective set. TR-2005-883, Computer Science Department, University of Rochester (October 2005).

Teaching

• Computer Science Department, Brown University, Providence, RI: Fall 2011. I am the TA for Approximation Algorithms (CSCI2510).
• Computer Science Department, Brown University, Providence, RI: Spring 2011. I was the TA for Introduction to Computational Geometry (CSCI1950-J).
• Computer Science Department, Princeton University, Princeton, NJ: Fall 2007. I was a TA for Operating Systems (COS 318).

Graduate-level coursework

• Brown: Introduction to Combinatorial Optimization (CSCI1490), Approximation Algorithms (CSCI2510), Solving Hard Problems in Combinatorial Optimization (CSCI2580), Planar Graph Algorithms (CSCI2950-R), Online Algorithms (CSCI2950-W), Multiplicative-Weights/Packing-Covering Method for Approximating Linear and Semidefinite Programs (CSCI2956-R), Recent Applications of Probability and Statistics (APMA2610), Computational Linear Algebra (APMA2821-F).
• Princeton: Advanced Algorithm Design (COS 521), Computational Complexity (COS 522), Advanced Computer Networks (COS 561).
• Rochester: Markov Chains (CSC 574), Algebra I (MTH 436), Algebra II (MTH 437), Theory of Analytic Functions I (MTH 467), Algebraic Geometry I (MTH 538).