Patrick Schnider

activity

20242026

collaborators

Showing cs.CCShow all

2 papers · 1 filter

cs.CC2025

Query-Efficient Fixpoints of $ℓ_{p}$ -Contractions

Sebastian Haslebacher, Jonas Lill, Patrick Schnider +1

We prove that an $ε$ -approximate fixpoint of a map $f : [0, 1]^{d} \to [0, 1]^{d}$ can be found with $O (d^{2} (lo g \frac{1}{ε} + lo g \frac{1}{1 - λ}))$ queries to $f$ if $f$ is $…

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…

Query-Efficient Fixpoints of ℓp​-Contractions

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

Query-Efficient Fixpoints of $ℓ_{p}$ -Contractions