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.