2022/09/30 by Argyrios Deligkas, John Fearnley, Alexandros Hollender +1 · 1 voice · 3 citations
Computer Science · Engineering · Mathematics · #Advancements in Semiconductor Devices and Circuit Design #Combinatorics #Computer science #Discrete mathematics #Low-power high-performance VLSI design #Mathematics #Physics #Quantum Computing Algorithms and Architecture #cs.CC #cs.GT
paper · pdf · doi:10.1145/3678166
published in Journal of the ACM 71(5), 1-48 (Association for Computing Machinery)
arxiv published 2022/09/30 · openalex publication_date 2024/07/15 · arxiv updated 2024/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
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 problems in PPAD by using ɛ- GCircuit as an intermediate problem. We introduce Pure-Circuit , a new intermediate problem for PPAD , which can be thought of as ɛ- GCircuit pushed to the limit as ɛ → 1, and we show that the problem is PPAD -complete. We then prove that ɛ- GCircuit is PPAD -hard for all ɛ < 1/10 by a reduction from Pure-Circuit , and thus strengthen all prior work that has used GCircuit as an intermediate problem from the existential-constant regime to the large-constant regime. We show that stronger inapproximability results can be derived by reducing directly from Pure-Circuit . In particular, we prove tight inapproximability results for computing approximate Nash equilibria and approximate well-supported Nash equilibria in graphical games, for finding approximate well-supported Nash equilibria in polymatrix games, and for finding approximate equilibria in threshold games.