Further collapses in TFNP

DOI10.4230/LIPICS.CCC.2022.33MaRDI QIDQ6568376zbMATH OpenFDO

Authors Mika Göös, Alexandros Hollender, Siddhartha Jain, William Pires, Robert Robere, Ran Tao

Publication date 5 July 2024

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2022.33

zbMATH Keywords

EOPLPLSPPADTFNP

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited in

(11)

• The complexity of gradient descent: CLS = PPAD pls
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Note on constrained long choice with multiple beginning elements
• Algorithms and complexity for computing Nash equilibria in adversarial team games
• Smoothed analysis of deterministic discounted and Mean-payoff games
• Total NP search problems with abundant solutions
• Intersection classes in TFNP and proof complexity
• TFNP intersections through the Lens of feasible disjunction
• On the complexity of some restricted variants of \textsc{Quotient Pigeon} and a weak variant of \textsc{Kőnig}
• Separations in proof complexity and TFNP
• An oracle with no up-complete sets, but NP = PSPACE

This page was built for publication: Further collapses in TFNP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6568376)