David Eppstein

Home * People * David Eppstein

[ David Eppstein [1] David A. Eppstein,

an American mathematician and computer scientist. He is professor in the Computer Science Department, Donald Bren School of Information and Computer Sciences, University of California, Irvine. He received a B.Sc. in mathematics from Stanford University in 1984, and M.Sc. and Ph.D. degrees in computer science from Columbia University in 1985 and 1989 respectively. His research interests covers algorithms and data structures, complexity theory, graph theory, such as minimum spanning tree, shortest path, and graph coloring as well as game theory and finite element methods. He teaches strategy and board game programming and tried his own hands on Fanorona [2], a traditional board game from Madagascar.

Selected Publications#

[3] [4] [5]

1985 …#

• David Eppstein (1985). A Heuristic Approach to Program Inversion. IJCAI 1985
• David Eppstein, Zvi Galil, Raffaele Giancarlo (1988). Speeding up Dynamic Programming. FOCS 1988
• David Eppstein, Zvi Galil (1988). Parallel Algorithmic Techniques for Combinatorial Computation. ICALP 1989, pdf
• David Eppstein (1989). Efficient Algorithms for Sequence Analysis with Concave and Convex Gap Costs. Ph.D. thesis, Columbia University, advisor Zvi Galil

1900 …#

• David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano (1990). Sparse Dynamic Programming. SODA 1990, pdf
• David Eppstein (1990). Sequence Comparison with Mixed Convex and Concave Costs. Journal of Algorithms, Vol. 11, No. 1, pdf
• David Eppstein (1992). Finding the k Smallest Spanning Trees. BIT, Vol. 32
• David Eppstein, Zvi Galil, Raffaele Giancarlo, Giuseppe F. Italiano (1993). Efficient Algorithms for Sequence Analysis. Sequences II, Springer, pdf
• David Eppstein (1994). Finding the k Shortest Paths. Tech. Report 94-26, 35th FOCS 1994, TR-94-26.pdf

1995 …#

• Marshall Bern, David Eppstein (1995). Mesh Generation and Optimal Triangulation. Computing in Euclidean Geometry (2nd ed), pdf [6]
• David Eppstein (1997). Dynamic Connectivity in Digital Images. Information Processing Letters, Vol. 62, No. 3, TR-96-13.pdf
• David Eppstein (1998). Finding the k Shortest Paths. SIAM Journal on Computing, Vol. 28, No. 2, pdf
• David Eppstein (1999). Setting Parameters by Example. arXiv:cs/9907001

2000 …#

• David Eppstein (2000). Searching for Spaceships. arXiv:cs/0004003
• Erik D. Demaine, Martin L. Demaine, David Eppstein (2000). Phutball Endgames are Hard. arXiv:cs/0008025 [7]
• Cristopher Moore, David Eppstein (2000). One-Dimensional Peg Solitaire. arXiv:math/0006067 [8]
• Cristopher Moore, David Eppstein (2000). One-Dimensional Peg Solitaire, and Duotaire. arXiv:math/0008172
• David Eppstein, S. Muthukrishnan (2000). Internet Packet Filter Management and Rectangle Geometry. arXiv:cs/0010018
• David Eppstein, Jean-Claude Falmagne (2002). Algorithms for Media. arXiv:cs/0206033
• David Eppstein (2004). Algorithms for Drawing Media. arXiv:cs/0406020
• David Eppstein (2004). Quasiconvex Programming. arXiv:cs/0412046

2005 …#

• David Eppstein, Michael T. Goodrich, Jonathan Z. Sun (2005). The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data. https://arxiv.org/abs/cs/050704
• David Eppstein (2005). Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku. arXiv:cs/0507053
• David Eppstein (2008). Learning Sequences. arXiv:0803.4030
• David Eppstein, Jean-Claude Falmagne, Sergei Ovchinnikov (2008). Media Theory - interdisciplinary applied mathematics. Springer
• David Eppstein (2009). Growth and Decay in Life-Like Cellular Automata. arXiv:0911.2890

2010 …#

• Michael J. Bannister, David Eppstein (2011). Randomized Speedup of the Bellman-Ford Algorithm. arXiv:1111.5414 [9]
• David Eppstein (2012). Solving Single-digit Sudoku Subproblems. arXiv:1202.5074
• David Eppstein, Michael T. Goodrich, Michael Mitzenmacher, Paweł Pszona (2014). Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket. arXiv:1404.0286
• Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, Yushi Uno (2014). Folding a Paper Strip to Minimize Thickness. arXiv:1411.6371

2015 …#

• David Eppstein (2016). Cuckoo Filter: Simplification and Analysis. arXiv:1604.06067 [10]
• David Eppstein, Vijay V. Vazirani (2018). NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs. arXiv:1802.00084 [11]
• David Eppstein (2018). Faster Evaluation of Subtraction Games. arXiv:1804.06515
• David Eppstein (2018). Making Change in 2048. arXiv:1804.07396
• David Eppstein (2018). Forbidden Configurations in Discrete Geometry. Cambridge University Press
• Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, Yushi Uno (2019). Reconfiguring Undirected Paths. arXiv:1905.00518

Forum Posts#

• “Suspicious move” extension by David Eppstein, CCC, November 20, 1997 » Extensions
• Using too-shallow mate scores from the hash table by David Eppstein, CCC, July 05, 1998 » Transposition Table

Re: Using too-shallow mate scores from the hash table by David Eppstein, CCC, July 06, 1998

• Re: UCI (=universal chess interface) by David Eppstein, CCC, November 29, 2000 » UCI
• Why does a Wikipedia administrator, David Eppstein, aggressively move against new machine learning technologies? by David Bowie, Quora, July 2019

Blog Posts#

• 11011110, David Eppstein’s blog

Analyzing Algorithm X in honor of Knuth’s 70th birthday, by David Eppstein, January 2008 Chessboards and colorings, by David Eppstein, August 30, 2010 External Links

• David Eppstein from Wikipedia
• The Mathematics Genealogy Project - David Eppstein
• Fano Experimental Web Server (Archive)

ICS.UCI.EDU#

• David Eppstein’s homepage
• Computational Complexity of Games and Puzzles by David Eppstein » Games
• David Eppstein’s Research Projects
• David Eppstein’s Photo Galleries
• Lecture notes for April 8, 1997 Board Representations
• Lecture notes for April 22, 1997 Alpha-Beta Search
• ICS 180, Winter 1999 - Strategy and board game programming

References#

1. ↑ David Eppstein in Limerick, Ireland, for the 13th International Symposium on Graph Drawing, September 15, 2005, Image by Elena Mumford, David Eppstein from Wikipedia, Wikimedia Commons
2. ↑ Fanorona by David Eppstein
3. ↑ David Eppstein - Publication
4. ↑ dblp: David Eppstein
5. ↑ David Eppstein - Google Scholar Citations
6. ↑ Mesh generation from Wikipedia
7. ↑ Phutball from Wikipedia
8. ↑ Peg solitaire from Wikipedia
9. ↑ Bellman–Ford algorithm from Wikipedia
10. ↑ Cuckoo filter from Wikipedia
11. ↑ NC (complexity) from Wikipedia

Up one level