Realizability Makes a Difference: A Complexity Gap for Sink-Finding in USOs

Simon Weber, Joel Widmer

Algorithms for finding the sink in Unique Sink Orientations (USOs) of the hypercube can be used to solve many algebraic and geometric problems, most importantly including the P-Mat…