Further collapses in \(\mathsf{TFNP}\)
type: Item
instance of: scholarly article
title: Further collapses in \(\mathsf{TFNP}\)
author: Mika Göös
author: Alexandros Hollender
author: Siddhartha Jain
author: Q6115372
author: William Pires
author: Robert Robere
author: Ran Tao
published in: SIAM Journal on Computing
publication date: 2024-05-24T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 7852674
zbMATH Keywords: \textsf{TFNP}
zbMATH Keywords: \textsf{PLS}
zbMATH Keywords: \textsf{PPAD}
zbMATH Keywords: \textsf{EOPL}
MaRDI profile type: Publication
cites work: The relative complexity of NP search problems
cites work: The Complexity of Computing a Nash Equilibrium
cites work: Q5365081
cites work: ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP
cites work: Q5875712
cites work: The complexity of gradient descent: CLS = PPAD ∩ PLS
cites work: Unique end of potential line
cites work: ARRIVAL: Next Stop in CLS
cites work: The Hairy Ball problem is PPAD-complete
cites work: Adventures in monotone complexity and TFNP
cites work: Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
cites work: The complexity of the parity argument with potential
cites work: How easy is local search?
cites work: On total functions, existence theorems and computational complexity
cites work: The Rainbow at the End of the Line — A PPAD Formulation of the Colorful Carathéodory Theorem with Applications
cites work: On the complexity of the parity argument and other inefficient proofs of existence
cites work: Q6187794
DOI: 10.1137/22M1498346
description: scientific article; zbMATH DE number 7852674