David Eppstein - Publications

Miscellaneous

• A heuristic approach to program inversion.
  D. Eppstein.
  9th Int. Joint Conf. Artificial Intelligence, Los Angeles, 1985, pp. 219–221.

  Program transformation. Given a (lisp) program for an invertible function, how do we automatically find a program for the inverse function? Considers more general simultaneous inverses of multiple functions. The heuristic part involves type inference for finding conditionals to use in certain if statements.

  (MacLISP source code – Kawabe's Common Lisp port)

• Reset sequences for monotonic automata.
  D. Eppstein.
  15th Int. Coll. Automata, Languages and Programming, Tampere, Finland, 1988.
  Springer, Lecture Notes in Comp. Sci. 317, 1988, pp. 230–238.
  SIAM J. Computing 19 (3): 500–510, 1990.

  Automata theory. A reset sequence for a DFA is an input such that, no matter which state the DFA starts in, it ends up after the input in a known state. These have been used by Natarajan and Goldberg for certain robot motion planning problems (in fact the conference version of this paper used the title "Reset sequences for finite automata with application to design of parts orienters"), and also in coding theory where they arise in the design of self-synchronizing codes. This paper considers DFAs in which the transition functions respect a given cyclic ordering of the states, and shows that their shortest reset sequences can be found quickly. It also considers parallel algorithms for the problem. There remains open a gap between n² and n³ in the maximum length of reset sequences for general automata.

• Simultaneous strong separations of probabilistic and unambiguous complexity classes.
  D. Eppstein, L. Hemachandra, J. Tisdall, and B. Yener.
  Int. Conf. Computing and Information, Toronto, North-Holland, 1989, pp. 65–70.
  Tech. Rep. 335, Dept. Comp. Sci., U. Rochester, 1990.
  Mathematical Systems Theory 25 (1): 23–36, 1992.

  Structural complexity theory. Constructs oracles in which \(\mathsf{BPP}\) (a probabilistic complexity class) and \(\mathsf{UP}\) (the class of problems with a unique "witness") contain languages that in a very strong sense are not contained in the other class. The conference version used the title "Probabilistic and unambiguous computation are incomparable".

• Persistence, offline algorithms, and space compaction.
  D. Eppstein.
  Tech. Rep. 91-54, ICS, UCI, 1991.

  Considers persistence for a naive form of dynamic algorithm in which each update rebuilds a static solution. The space bounds for this can often be reduced by maintaining an offline solution over a sequence of updates constructed from an Euler tour of the persistent update history tree.

• Minimum range balanced cuts via dynamic subset sums.
  D. Eppstein.
  Tech. Rep. 95-10, ICS, UCI, 1995.
  J. Algorithms 23: 375–385, 1997.

  Describes data structures for maintaining the solution of a dynamically changing subset sum problem, and uses them to find a cut in a graph minimizing the difference between the heaviest and lightest cut edge.

• Choosing subsets with maximum weighted average.
  D. Eppstein and D. S. Hirschberg.
  Tech. Rep. 95-12, ICS, UCI, 1995.
  5th MSI Worksh. on Computational Geometry, 1995, pp. 7–8.
  J. Algorithms 24: 177–193, 1997.

  Uses geometric optimization techniques to find, among n weighted values, the k to drop so as to maximize the weighted average of the remaining values. The feasibility test for the corresponding decision problem involves k-sets in a dual line arrangement.

  (Full paper)

• Guest editor's forward to special issue of papers from the 34th Annual Symposium on Foundations of Computer Science.
  D. Eppstein.
  J. Comp. Sys. Sci. 54:263, 1997.
  
• Reference caching using unit distance redundant codes for activity reduction on address buses.
  D. Eppstein and T. Givargis.
  Worksh. Embedded System Codesign (ESCODES'02), San Jose, 2002, pp. 43–48.
  J. Microprocessors & Microsystems 29 (4): 145–153, 2005.

  We study the problem of minimizing transitions in address signals on a bus. The UDRC part of the title refers to an algorithm for coding signals with at most one transition per signal (using an increased number of wires); we combine this with a scheme for caching previously coded addresses and use trace data to compare our technique with previous approaches.

• Improved combinatorial group testing for real-world problem sizes.
  D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
  9th Worksh. Algorithms and Data Structures, Waterloo, 2005.
  Springer, Lecture Notes in Comp. Sci. 3608, 2005, pp. 86–98.
  arXiv:cs.DS/0505048.
  SIAM J. Computing 36 (5): 1360–1375, 2007.

  We study practically efficient methods for finding few flawed items among large sets of items, by testing whether there exist flaws in each of a small number of batches of items.

  (Mike's WADS talk slides)

• On the approximability of geometric and geographic generalization and the min-max bin covering problem.
  W. Du, D. Eppstein, M. T. Goodrich, G. Lueker.
  arXiv:0904.3756.
  Algorithms and Data Structures Symposium (WADS), Banff, Canada.
  Springer, Lecture Notes in Comp. Sci. 5664, 2009, pp. 242–253.

  We investigate several simplified models for k-anonymization in databases, show them to be hard to solve exactly, and provide approximation algorithms for them.

  The min-max bin covering problem is closely related to one of our models. An input to this problem consists of a collection of items with sizes and a threshold size. The items must be grouped into bins such that the total size within each bin is at least the threshold, while keeping the maximum bin size as small as possible.

  (Slides)

• Questions answered. In theory.
  Clarke, Eppstein, Ghasemloo, Reyzin, Salamon, Shor, Sterling, and Venkatasubramanian.
  ACM SIGACT News 41 (4), 2010.

  An overview of the Theoretical Computer Science question and answer exchange web site.

• Privacy-enhanced methods for comparing compressed DNA sequences.
  D. Eppstein, M. T. Goodrich, and P. Baldi.
  arXiv:1107.3593.
  
• Combinatorial pair testing: distinguishing workers from slackers.
  D. Eppstein, M. T. Goodrich, and D. S. Hirschberg.
  arXiv:1305.0110.
  13th Int. Symp. Algorithms and Data Structures (WADS 2013), London, Ontario.
  Springer, Lecture Notes in Comp. Sci. 8037, 2013, pp. 316–327.
  

  We study the problem of distinguishing workers (people who complete their assigned tasks) from slackers (people who do not contribute towards the completion of their tasks) by grouping people in pairs and assigning a task to each group.

• Wear minimization for cuckoo hashing: how not to throw a lot of eggs into one basket.
  D. Eppstein, M. T. Goodrich, M .Mitzenmacher, and P. Pszona.
  arXiv:1404.0286.
  Proc. 13th International Symposium on Experimental Algorithms (SEA 2014), Copenhagen, Denmark, 2014.
  Springer, Lecture Notes in Comp. Sci. 8504, pp. 162–173, 2014.

  We study cuckoo hashing data structures in a model of flash memory in which each memory cell has a limited number of times it can be changed, so the goal is to prevent hot spots that change many times.

• Linear-time algorithms for proportional apportionment.
  Z. Cheng and D. Eppstein.
  arXiv:1409.2603.
  Proc. 25th Int. Symp. Algorithms and Computation (ISAAC 2014), Jeonju, Korea, 2014.
  Springer, Lecture Notes in Comp. Sci. 8889, 2014, pp. 581–592.
  

  We consider a broad class of highest averages methods for proportional allocation (the problems of allocating seats to parties after a parliamentary election, or of allocating congressmen to states based on total population). We show that these methods can be simulated by an algorithm whose running time is proportional only to the number of parties or states, independent of the number of seats allocated or the number of voters.

  (Slides)

• From discrepancy to majority.
  D. Eppstein and D. S. Hirschberg.
  arXiv:1512.06488.
  Proc. 12th Latin American Theoretical Informatics Symposium (LATIN 2016), Ensenada, Mexico.
  Springer, Lecture Notes in Comp. Sci. 9644 (2016), pp. 390–402.
  Algorithmica 80 (4): 1278–1297, 2018.

  We provide upper and lower bounds on the query complexity of a problem in which the input is a collection of two-colored items, and the problem is to either find an item of the majority color or to determine that there is no majority, by performing queries that determine the discrepancy of fixed-size subsets of the items.

  (Slides)

• Cuckoo filter: simplification and analysis.
  D. Eppstein.
  arXiv:1604.06067.
  Proc. 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016), Reykjavik, Iceland.
  Leibniz International Proceedings in Informatics (LIPIcs) 53, pp. 8.1–8.12.

  A cuckoo filter is an approximate set data structure that can be used in place of a Bloom filter, but with several practical advantages: it uses less space, has better locality of reference, and can handle element deletions. We provide the first theoretical analysis of a simplified variation of cuckoo filters, showing that these advantages can be guaranteed to hold theoretically and not just experimentally.

  (Slides)

• Scheduling autonomous vehicle platoons through an unregulated intersection.
  J. Besa, W. E. Devanny, D. Eppstein, and M. T. Goodrich.
  Proc. 16th Worksh. Algorithmic Approaches for Transportation Modelling, Optimization and Systems (ATMOS 2016), Aarhus, Denmark, 2016.
  OpenAccess Series in Informatics (OASIcs) 54, Schloss Dagstuhl (2016), pp. 5:1–5.16.
  arXiv:1609.04512.
  

  We consider a model of vehicle scheduling in which vehicles arrive at an intersection in indivisible platoons (or individual vehicles of variable length) and the goal is to find a schedule for them to all cross the intersection without collisions, minimizing the maximimum delay incurred by any platoon. We show that for many types of intersections, an optimal schedule can be found in polynomial time by a combination of dynamic programming and parametric search.

• Using multi-level parallelism and 2-3 cuckoo filters for faster set intersection queries and sparse boolean matrix multiplication.
  D. Eppstein and M. T. Goodrich.
  Brief announcement, Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Washington, DC, 2017, pp. 137–139.
  

  We provide parallel versions of our bit-parallel algorithms from PODS 2017 for sparse set intersection.

• Quadratic time algorithms appear to be optimal for sorting evolving data.
  J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
  Proc. Algorithm Engineering & Experiments (ALENEX 2018), New Orleans, 2018, pp. 87–96.
  arXiv:1805.05443.

  We experiment with sorting algorithms in the evolving data model, in which, at the same time as the algorithm compares pairs of elements and possibly chooses a new ordering based on the results of the comparison, an adversary randomly chooses two adjacent elements in the sorted order and swaps them. As we show, bubble sort and its variants appear to maintain an order that is within inversion distance of optimal.

• Optimally sorting evolving data.
  J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson.
  arXiv:1805.03350
  Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague.
  Leibniz International Proceedings in Informatics (LIPIcs) 107, pp. 81:1–81:13.
  

  Suppose that a collection of objects has a linear order that is evolving by swaps of randomly chosen consecutive elements. We would like to maintain an approximation to this order using an algorithm that performs one comparison per swap. We show that repeated insertion sort can maintain linear inversion distance from the underlying order, the best possible.

• Reconfiguration of satisfying assignments and subset sums: Easy to find, hard to connect.
  J. Cardinal, E. Demaine, D. Eppstein, R. Hearn, and A. Winslow.
  arXiv:1805.04055
  Proc. 24th International Computing and Combinatorics Conference (COCOON 2018), Qingdao, China.
  Springer, Lecture Notes in Comp. Sci. 10976 (2018), pp. 365–377.
  Theor. Comput. Sci. 806: 332–343, 2020.

  For several problems with polynomial-time solutions, we show that finding a sequence of steps that converts one solution into another (maintaining a valid solution at each step) is hard. These include planar monotone not-all-equal 3-sat, subset sum on integers of polynomial magnitude, and 0-1 integer programming with a constant number of linear inequality constraints.

  (Slides)

• Which women mathematicians get written about on Wikipedia, and why.
  D. Eppstein.
  AWM Newsletter 48 (4): 12–14, July–August 2018.

  This short opinion piece explains Wikipedia's guidelines for inclusion of articles on academics, and outlines steps to help improve Wikipedia's coverage of women in mathematics.

• The complexity of iterated reversible computation.
  D. Eppstein.
  arXiv:2112.11607.
  Invited talk at 15th Latin American Theoretical Informatics Symposium, Guanajuato, Mexico, November 2022.
  TheoretiCS 2: A10:1–A10:41, 2023.
  

  We study a class of problems involving computing a value \(f^{(n)}(x)\), the \(n\)th iterate of a function \(f\), for polynomial time bijections. We prove that these problems are complete for \(\mathsf{P}^{\mathsf{PSPACE}}\), and include hard problems in circuit complexity, graph algorithms, the simulation of one- and two-dimensional automata, and dynamical systems. We also provide a polynomial time algorithm for the special case where the bijection is an interval exchange transformation.

• Fast Schulze voting using quickselect.
  A. Arora, D. Eppstein, and R. L. Huynh.
  arXiv:2411.18790.

  We show how to determine the outcome of a Schulze method election, from an input consisting of an \(m\times m\) array of pairwise margins of victory, in time \(O(m^2\log m)\). The algorithm uses random pivoting like that of quickselect.

• Princ-wiki-a mathematica: Wikipedia editing and mathematics.
  D. Eppstein, J. B. Lewis, R. Woodroofe, and X. Easter.
  arXiv:2412.20419.
  Notices of the AMS 72 (1): 65–73, 2025.
  

  We describe the experience of editing mathematics articles on Wikipedia, with the aim of providing helpful advice for new editors and encouraging mathematicians to become Wikipedia editors.

• Zip-tries: simple dynamic data structures for strings.
  D. Eppstein, O. Gila, M. T. Goodrich, and R. Kitagawa.
  SIAM Conference on Applied and Computational Discrete Algorithms (ACDA25), Montreal, Canada, 2025, pp. 130–143.
  arXiv:2505.04953.
  

  We provide fast parallel and bit-parallel data structures for string search in a dynamic set of strings, with few bits of metadata per node.