2 papers
cs.CC2025
Monotone Contractions
Eleni Batziou, John Fearnley, Spencer Gordon +2
We study functions that are both monotone and contracting, and we consider the problem of finding an -approximate fixed point of $f…
cs.CC2024
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…