Pure-Circuit: tight inapproximability for PPAD

Pure-Circuit: tight inapproximability for PPAD

<p>The current state-of-the-art methods for showing inapproximability in <span data-="">PPAD</span> arise from the ε-Generalized-Circuit (ε-<span data-="">GCircuit</span>) problem. Rubinstein (2018) showed th...

Full description

Bibliographic Details
Main Authors:	Deligkas, A, Fearnley, J, Hollender, A, Melissourgos, T
Format:	Journal article
Language:	English
Published:	Association for Computing Machinery 2024

Similar Items

Pure-circuit: strong inapproximability for PPAD
by: Deligkas, A, et al.
Published: (2022)

Constant inapproximability for PPA
by: Deligkas, A, et al.
Published: (2022)

Constant inapproximability for Fisher markets
by: Deligkas, A, et al.
Published: (2024)

Tight inapproximability of Nash equilibria in public goods games
by: Do Dinh, J, et al.
Published: (2024)

The complexity of gradient descent: CLS = PPAD ∩ PLS
by: Fearnley, J, et al.
Published: (2021)

The complexity of gradient descent: CLS = PPAD∩PLS
by: Fearnley, J, et al.
Published: (2022)

The Hairy Ball problem is PPAD-complete
by: Goldberg, PW, et al.
Published: (2021)

The Hairy Ball problem is PPAD-complete
by: Goldberg, P, et al.
Published: (2019)

PPAD-complete approximate pure Nash equilibria in Lipschitz Games
by: Goldberg, P, et al.
Published: (2023)

PPAD-membership for problems with exact rational solutions: a general approach via convex optimization
by: Filos-Ratsikas, A, et al.
Published: (2024)

Inapproximability of counting hypergraph colourings
by: Galanis, A, et al.
Published: (2022)

Cautionary Tales of Inapproximability
by: Budden, David, et al.
Published: (2017)

Delegation with Updatable Unambiguous Proofs and PPAD-Hardness
by: Yang, Lisa L.
Published: (2022)

The inapproximability for the $(0,1)$-additive number
by: Arash Ahadi, et al.
Published: (2016-06-01)

Inapproximability of the independent set polynomial in the complex plane
by: Bezáková, I, et al.
Published: (2020)

Inapproximability of the independent set polynomial in the complex plane
by: Bezakova, I, et al.
Published: (2018)

Inapproximability of the independent set polynomial below the Shearer threshold
by: Galanis, A, et al.
Published: (2017)

Inapproximability for antiferromagnetic spin systems in the tree nonuniqueness region
by: Galanis, A, et al.
Published: (2015)

Fiat-Shamir for Repeated Squaring with Applications to PPAD-Hardness and VDFs
by: Lombardi, Alex, et al.
Published: (2021)

Approximation algorithms and inapproximability of partition functions of spin systems
by: Yang, K
Published: (2019)

Approximation and inapproximability results on balanced connected partitions of graphs
by: Frédéric Chataigner, et al.
Published: (2007-01-01)

Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs
by: Demaine, Erik D, et al.
Published: (2019)

Approximation and Inapproximability Results on Balanced Connected Partitions of Graphs
by: Yoshiko Wakabayashi, et al.
Published: (2007-01-01)

Inapproximability of the partition function for the antiferromagnetic ising and hard-core models
by: Galanis, A, et al.
Published: (2016)

Two's company, three's a crowd: consensus-halving for a constant number of agents
by: Deligkas, A, et al.
Published: (2022)

Lyapunov Exponent of Rank One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution
by: Altschuler, Jason M, et al.
Published: (2021)

Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution
by: Altschuler, Jason M, et al.
Published: (2022)

On the Inapproximability of the Shortest Vector in a Lattice Within Some Constant Factor
by: Micciancio, Danielle
Published: (2023)

Max 2SAT-3, Net, Euclidea: Techniques and Results in Computational Inapproximability
by: Luo, Victor
Published: (2024)

The Interaction Effect of Anti-RgpA and Anti-PPAD Antibody Titers: An Indicator for Rheumatoid Arthritis Diagnosis
by: Diana Marcela Castillo, et al.
Published: (2023-04-01)

<i>Porphyromonas gingivalis</i> Peptidyl Arginine Deiminase (PPAD) in the Context of the Feed-Forward Loop of Inflammation in Periodontitis
by: Zsombor Prucsi, et al.
Published: (2023-08-01)

The complexity of computing KKT solutions of quadratic programs
by: Fearnley, J, et al.
Published: (2024)

Tight Bounds on the Convergence of Noisy Random Circuits to the Uniform Distribution
by: Abhinav Deshpande, et al.
Published: (2022-12-01)

Variational tight-binding method for simulating large superconducting circuits
by: D. K. Weiss, et al.
Published: (2021-09-01)

Adversarial quantum circuit learning for pure state approximation
by: Marcello Benedetti, et al.
Published: (2019-01-01)

VIRUS DELIVERED, BRAIN CIRCUIT TARGETABLE, TIGHTLY-CONTROLLED INDUCIBLE GENE EXPRESSION SYSTEM
by: Gorka Kortabarria, et al.
Published: (2023-10-01)

Tight bag
by: S Parthasarathy, et al.
Published: (2010-01-01)

Time is tight
by: Gerhard Konrad Seeberger
Published: (2013-01-01)

Tight junctions /
by: Gonzalez-Mariscal, Lorenza
Published: (2006)

Genes and sepsis: how tight is the fit?
by: Gordon, A, et al.
Published: (2008)