Buchumschlag

Separations in Proof Complexity and TFNP

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Göös, Mika, Hollender, Alexandros, Jain, Siddhartha, Maystre, Gilbert, Pires, William, Robere, Robert, Tao, Ran
Format:	Preprint
Veröffentlicht:	2022
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On Pigeonhole Principles and Ramsey in TFNP
von: Jain, Siddhartha, et al.
Veröffentlicht: (2024)

Quantum Communication Advantage in TFNP
von: Göös, Mika, et al.
Veröffentlicht: (2024)

Direct Sums for Parity Decision Trees
von: Besselman, Tyler, et al.
Veröffentlicht: (2024)

Supercritical Tradeoffs for Monotone Circuits
von: Göös, Mika, et al.
Veröffentlicht: (2024)

The Complexity of Symmetric Bimatrix Games with Common Payoffs
von: Ghosh, Abheek, et al.
Veröffentlicht: (2024)

The Computational Complexity of Finding Stationary Points in Non-Convex Optimization
von: Hollender, Alexandros, et al.
Veröffentlicht: (2023)

Separations above TFNP from Sherali-Adams Lower Bounds
von: Fleming, Noah, et al.
Veröffentlicht: (2026)

Envy-Free Cake-Cutting for Four Agents
von: Hollender, Alexandros, et al.
Veröffentlicht: (2023)

The Complexity of Two-Team Polymatrix Games with Independent Adversaries
von: Hollender, Alexandros, et al.
Veröffentlicht: (2024)

The Complexity of Computing KKT Solutions of Quadratic Programs
von: Fearnley, John, et al.
Veröffentlicht: (2023)

Equality is Far Weaker than Constant-Cost Communication
von: Göös, Mika, et al.
Veröffentlicht: (2025)

Tight Inapproximability of Nash Equilibria in Public Goods Games
von: Dinh, Jérémi Do, et al.
Veröffentlicht: (2024)

Monotone Circuit Complexity of Matching
von: Cavalar, Bruno, et al.
Veröffentlicht: (2025)

Pseudodeterministic Communication Complexity
von: Göös, Mika, et al.
Veröffentlicht: (2025)

Hierarchies within TFNP: building blocks and collapses
von: Ghentiyala, Surendra, et al.
Veröffentlicht: (2025)

Lower Bounds for Approximate Sign Rank
von: Bindua, Riju, et al.
Veröffentlicht: (2026)

Top-Down Lower Bounds for Depth-Four Circuits
von: Göös, Mika, et al.
Veröffentlicht: (2023)

Constant-Cost Communication is not Reducible to k-Hamming Distance
von: Fang, Yuting, et al.
Veröffentlicht: (2024)

How to fit large complexity classes into TFNP
von: Thapen, Neil
Veröffentlicht: (2024)

Constant Inapproximability for PPA
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2022)

Pure-Circuit: Tight Inapproximability for PPAD
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2022)

Constant Inapproximability for Fisher Markets
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2026)

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2026)

KRW Composition Theorems via Lifting
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2020)

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
von: Aldi, Marco, et al.
Veröffentlicht: (2024)

On the Computation of Equilibria in Discrete First-Price Auctions
von: Filos-Ratsikas, Aris, et al.
Veröffentlicht: (2024)

Equilibrium Computation in First-Price Auctions with Correlated Priors
von: Filos-Ratsikas, Aris, et al.
Veröffentlicht: (2025)

Computing Equilibrium Points of Electrostatic Potentials
von: Ghosh, Abheek, et al.
Veröffentlicht: (2025)

Sampling Permutations with Cell Probes is Hard
von: Alekseev, Yaroslav, et al.
Veröffentlicht: (2025)

Efficient Equilibrium Computation in Symmetric First-Price Auctions
von: Filos-Ratsikas, Aris, et al.
Veröffentlicht: (2026)

Certificate Games and Consequences for the Classical Adversary Bound
von: Chakraborty, Sourav, et al.
Veröffentlicht: (2022)

Sign-Rank of $k$-Hamming Distance is Constant
von: Göös, Mika, et al.
Veröffentlicht: (2025)

Min-Max Optimization Requires Exponentially Many Queries
von: Bernasconi, Martino, et al.
Veröffentlicht: (2026)

From Proof Complexity to Circuit Complexity via Interactive Protocols
von: Arteche, Noel, et al.
Veröffentlicht: (2024)

Proof Complexity and Feasible Interpolation
von: Tabatabai, Amirhossein Akbar
Veröffentlicht: (2025)

Optimal Proof Systems for Complex Sets are Hard to Find
von: Egidy, Fabian, et al.
Veröffentlicht: (2024)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2026)

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
von: Iyer, Vishnu, et al.
Veröffentlicht: (2026)

Proof Complexity of Linear Logics
von: Tabatabai, Amirhossein Akbar, et al.
Veröffentlicht: (2026)

No Constant-Cost Protocol for Point--Line Incidence
von: Göös, Mika, et al.
Veröffentlicht: (2026)