Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents

Michaela Borzechowski, John Fearnley, Spencer Gordon +3

We provide polynomial-time reductions between three search problems from three distinct areas: the P-matrix linear complementarity problem (P-LCP), finding the sink of a unique sin…