# Pure-Circuit: Tight Inapproximability for PPAD

arXiv: https://arxiv.org/abs/2209.15149 · HTML: https://mlsanity.com/paper/2209.15149/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Sep 2022.

## Built on by (most cited first, 7 of 7)

- [On the Computational Complexity of Performative Prediction](https://mlsanity.com/paper/2601.20180/) (2026)
- [Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models](https://mlsanity.com/paper/2508.11874/) (2025)
- [Min-Max Optimization Requires Exponentially Many Queries](https://mlsanity.com/paper/2605.13806/) (2026)
- [The Complexity of Min-Max Optimization for Quadratic Polynomials](https://mlsanity.com/paper/2606.17000/) (2026)
- [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026)
- [Normal-Form Correlation in Markov Games](https://mlsanity.com/paper/2610.03621/) (2026)
- [PPAD-Completeness of Contiguous Envy-Free Cake Cutting with Additive Valuations](https://mlsanity.com/paper/2610.19690/) (2026)

## Abstract (arXiv)

The current state-of-the-art methods for showing inapproximability in PPAD arise from the varepsilon-Generalized-Circuit (varepsilon-GCircuit) problem. Rubinstein (2018) showed that there exists a small unknown constant varepsilon for which varepsilon-GCircuit is PPAD-hard, and subsequent work has shown hardness results for other problems in PPAD by using varepsilon-GCircuit as an intermediate problem. We introduce Pure-Circuit, a new intermediate problem for PPAD, which can be thought of as varepsilon-GCircuit pushed to the limit as varepsilon rightarrow 1, and we show that the problem is PPAD-complete. We then prove that varepsilon-GCircuit is PPAD-hard for all varepsilon < 0.1 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.