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.