arXiv · Oct 19, 2026
Tight Inapproximability for Generalized Circuits
By Panagiotis Kanellopoulos, Themistoklis Melissourgos
Generalized circuits are a fundamental tool for establishing PPAD-hardness and membership of approximate equilibrium problems. Despite their importance, the complexity of finding approximate solutions has remained unresolved for a wide range of approximation parameters. We settle this question by establishing a tight threshold at ε=1/6. Specifically, we prove that ε-GCircuit is PPAD-complete for every constant 0<ε<1/6, even when restricted to four gate types, and polynomial-time solvable for every constant ε≥1/6. This closes the gap between the previously known hardness bound of 1/10 and the polynomial-time solvability bound of 1/2. We further investigate the relaxation in which a fraction δ of the gates may be violated. We establish polynomial-time solvability of (ε,δ)-GCircuit for every constant ε>0 and δ>1/5, and of the fan-out-one formulations of δ-Pure-Circuit for every constant δ>1/8. These results follow from a decomposition theorem for directed graphs of maximum in-degree two and establish that the PCP-for-PPAD conjecture cannot be true for the aforementioned values of ε and δ, unless PPAD = P. To showcase the contribution of our positive results, we apply them to a variety of problems in algorithmic game theory, including public goods games, financial networks, Bayesian, polymatrix, and graphical games, and obtain improved approximation guarantees.