Pure-circuit: strong inapproximability for PPAD

The current state-of-the-art methods for showing inapproximability in PPAD arise from the ε-Generalized-Circuit (ε-GCircuit) problem. Rubinstein (2018) showed that there exists a small unknown constant ε for which ε-GCircuit is PPAD-hard, and subsequent work has shown hardness results for other prob...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awduron: Deligkas, A, Fearnley, J, Hollender, A, Melissourgos, T
Fformat: Conference item
Iaith:English
Cyhoeddwyd: IEEE 2022