Publications with Robert A. Hearn
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.
New results in sona drawing: hardness and TSP separation.
M.-W. Chiu, E. Demaine, M. Demaine, D. Eppstein, R. Hearn, A. Hesterberg, M. Korman, I. Parada, and M. Rudoy.
arXiv:2007.15784.
Proc. 32nd Canadian Conference on Computational Geometry, 2020, pp. 63–72.A sona drawing is a self-crossing curve in the plane that separates each of a given system of points into its own region. We show that it is hard to find the shortest such curve, and we explore how much shorter than the TSP it can be.