David Eppstein - Publications

Publications with Andrew Winslow

• 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)