PaperfootJoin free
arXiv

Proof finds the exact boundary for solving generalized circuits

A proof established an exact threshold of 1/6, closing the gap between previously known bounds of 1/10 for hardness and 1/2 for polynomial-time solvability.

Paper by Panagiotis Kanellopoulos, Themistoklis Melissourgos
Preprint: theory

Edited by Boris Djordjevic · Paperfoot

Paper

In a theory preprint, researchers proved a tight threshold for finding approximate solutions in generalized circuits, a framework used to classify the difficulty of equilibrium problems. For every fixed positive error tolerance below 1/6, they proved the problem is complete for Polynomial Parity Arguments on Directed graphs (PPAD), a class of search problems with guaranteed solutions. This means it belongs to that class and is as hard as any problem in it. The result held even with just four gate types. For every fixed error tolerance of 1/6 or more, they proved the problem is solvable in polynomial time, a standard measure of efficiency. This closed the gap between an earlier hardness bound of 1/10 and a solvability bound of 1/2. They also applied their positive results to game-theory problems, including financial networks and public goods games, obtaining improved approximation guarantees.

Why it matters

The proof settles the approximation threshold for generalized circuits, a tool for classifying equilibrium problems. The applications yield improved approximation guarantees for the game-theory problems considered, not a single threshold for approximating equilibria generally.

Caveats

The hardness classification does not unconditionally rule out polynomial-time algorithms; the results are theoretical, not measurements of deployed systems. The work is a preprint and has not yet been peer-reviewed.

In this paper

complexity of finding approximate solutions to generalized circuits

Methods
Algorithm 1 (this paper)

What it shows

ε-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.

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.

Abstract

(ε,δ)-GCircuit is polynomial-time solvable for every constant ε>0 and δ>1/5, and fan-out-one formulations of δ-Pure-Circuit are polynomial-time solvable for every constant δ>1/8.

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.

Abstract

At tolerance 1/6, the propagation algorithm solves 1/6-GCircuit in polynomial time.

\tfrac{1}{6} -GCircuit can be solved in polynomial time.

Theorem 4.5.

The PCP-for-PPAD conjecture cannot be true for the established values of ε and δ unless PPAD = P.

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.

Abstract

Quoted word for word from the full text on arXiv.

The paper

Tight Inapproximability for Generalized Circuits

Panagiotis Kanellopoulos, Themistoklis Melissourgos

arXiv, Oct 19, 2026, Open access, Preprint, not peer-reviewed

doi.org/10.48550/arxiv.2610.26772

arXiv:2610.26772v1 in cs.GT, also cs.CC

AbstractPDFHTML

Cite as BibTeX
@misc{kanellopoulos2026tight,
  title = {Tight Inapproximability for Generalized Circuits},
  author = {Kanellopoulos, Panagiotis and Melissourgos, Themistoklis},
  year = {2026},
  eprint = {2610.26772},
  archivePrefix = {arXiv},
  primaryClass = {cs.GT},
  doi = {10.48550/arxiv.2610.26772},
  url = {https://arxiv.org/abs/2610.26772}
}

Related