David Eisenstat's Curriculum Vitae

Education

• 2009–present, Ph.D. student, Computer Science, Brown University. Advisor: Claire Mathieu
• 2006–2007, Ph.D. student, Computer Science, Princeton University. Advisor: Larry Peterson
• 2002–2006, B.S. (Honors), Computer Science, B.A., Mathematics, University of Rochester (summa cum laude, GPA 3.98/4.0)

Honors

• Best Student Paper, DISC 2007 (21st International Symposium on Distributed Computing)
• Computing Research Association Outstanding Undergraduate Award, 2006
• National Defense Science and Engineering Graduate (NDSEG) Fellow, 2006–2007
• Gordon Y. S. Wu Fellow, Princeton University, 2006–2007
• NSF Graduate Research Fellowship Program, Honorable Mention
• Phi Beta Kappa, 2005 (elected as a junior)

Papers

• DBLP
• 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 (October 2010). To appear.
• 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 (September 2010). To appear.
• David Eisenstat: Random road networks: the quadtree model. http://arxiv.org/abs/1008.4916 (August 2010).
• James Aspnes, David Eisenstat and Yitong Yin: Low-contention data structures. SPAA 2010, the Twenty-Second Annual ACM Symposium on Parallel 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. http://arxiv.org/abs/0805.0444 (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–179 (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, 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).
• 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).
• 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, David Eisenstat, Marc Fiuczynski and Larry Peterson: On the design and evolution of an architecture for testbed 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.
• 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).
• 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).

Research, employment, and workshops

• Computer Science Department, Brown University, Providence, RI: September 2009–. Advised by Professor Claire Mathieu, I am investigating random planar graphs that resemble road networks.
• December 2007–August 2009. I worked on various problems in computational learning theory and the theory of distributed computing.
• Computer Science Department, Princeton University, Princeton, NJ: July 2006–November 2007. Advised by Professor Larry Peterson, I designed a framework for expressing transitive resource-sharing agreements between autonomous systems and a method for verifying the feasibility of these agreements without central coordination. I also rewrote the PlanetLab Node Manager, which allocates resources to network experiments at hundreds of sites around the world.
• Undergraduate Honors Project, Computer Science Department, University of Rochester, Rochester, NY: September 2005–May 2006. Advised by Professor Michael Scott, I designed much of the original Rochester Software Transactional Memory API. In my honors thesis, I proposed language extensions to facilitate programming with RSTM.
• NSF Research Experience for Undergraduates Program, Mathematics Department, Iowa State University, Ames, IA: Summer 2005. My group, advised by Professor Sung-Yell Song, studied strongly regular graphs with parameters (64, 28, 12, 12).
• NSF Research Experience for Undergraduates Program, Mathematics Department, Lafayette College, Easton, PA: Summer 2004. My group, advised by Professor Gary Gordon, studied the combinatorial and analytic properties of graph polynomials inspired by network failures.
• Programmer, Computer Science Department, Yale University, New Haven, CT: Summers 2001–2003. Supervised by research scientist Dr. John Peterson, I wrote a Haskell-like interpreter for Pan#, an image transformation system designed to introduce high-school students to functional programming.
• First Workshop in Algorithmic Computer Music (WACM), University of California Santa Cruz, Santa Cruz, CA: June 23–July 11, 2003. This three-week workshop was led by Professor David Cope.

Graduate-level coursework

• Brown: Approximation Algorithms (CSCI2510, in progress), Introduction to Combinatorial Optimization (CSCI1490), Solving Hard Problems in Combinatorial Optimization (CSCI2580), Planar Graph Algorithms (CSCI2950-R), Online Algorithms (CSCI2950-W), 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).