On total functions, existence theorems and computational complexity
From MaRDI portal
Recommendations
- Towards a unified complexity theory of total functions
- On the complexity of the parity argument and other inefficient proofs of existence
- Computational complexity of fixed points and intersection points
- Towards a Unified Complexity Theory of Total Functions
- On the Complexity of Nash Equilibria and Other Fixed Points
Cites work
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 192986 (Why is no real title available?)
- A Partition Theorem for Euclidean n-Space
- An interior point potential reduction algorithm for the linear complementarity problem
- Bimatrix Equilibrium Points and Mathematical Programming
- Complementary pivot theory of mathematical programming
- Every Prime Has a Succinct Certificate
- Homotopy Continuation Methods for Nonlinear Complementarity Problems
- How easy is local search?
- Nash and correlated equilibria: Some complexity considerations
- Relative complexity of checking and evaluating
- The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem
Cited in
(89)- The complexity of computational problems about Nash equilibria in symmetric win-lose games
- Equilibria for games with combined qualitative and quantitative objectives
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- Incremental delay enumeration: space and time
- Characterising the intersection of QMA and coQMA
- An oracle separating conjectures about incompleteness in the finite domain
- Towards a unified complexity theory of total functions
- Hardness of continuous local search: query complexity and cryptographic lower bounds
- Nested PLS
- The Hairy Ball Problem is PPAD-Complete.
- On the Complexity of Equilibrium Computation in First-Price Auctions
- Efficient approximation algorithms for the subset-sums equality problem.
- The structure and complexity of Nash equilibria for a selfish routing game
- scientific article; zbMATH DE number 7561747 (Why is no real title available?)
- Reductions in \textbf{PPP}
- On the complexity of finding a Caristi's fixed point
- scientific article; zbMATH DE number 5885061 (Why is no real title available?)
- The complexity of gradient descent: CLS = PPAD \(\cap\) pls
- The fibre of P-matrices: the recursive construction of all matrices with positive principal minors
- On the black-box complexity of Sperner's Lemma
- Quantum and classical query complexities of local search are polynomially related
- Nash equilibria: complexity, symmetries, and approximation
- Mortality of Iterated Piecewise Affine Functions over the Integers: Decidability and Complexity (extended abstract)
- Time hierarchies for cryptographic function inversion with advice
- On the complexity of stable fractional hypergraph matching
- Total functions in QMA
- Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation
- Constant rank two-player games are PPAD-hard
- Discrete versions of the KKM lemma and their PPAD-completeness
- The Veblen functions for computability theorists
- Fixed-Parameter Algorithms for the Kneser and Schrijver Problems
- PPAD-complete pure approximate Nash equilibria in Lipschitz games
- A Sperner lemma complete for PPA
- A finite set of functions with an EXPTIME-complete composition problem
- Propositional proofs and reductions between NP search problems
- Approximate counting and NP search problems
- An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
- The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham Sandwich
- On the upper bounds for complexities of discrete functions
- The classes PPA-\(k\): existence from arguments modulo \(k\)
- A Mihalisin-Klee theorem for fans
- Hardness results for consensus-halving
- On the complexity of the parity argument and other inefficient proofs of existence
- Consensus-Halving: Does It Ever Get Easier?
- Unique End of Potential Line
- Does the polynomial hierarchy collapse if onto functions are invertible?
- The complexity of the parity argument with potential
- Recent development in computational complexity characterization of Nash equilibrium
- The journey from NP to TFNP hardness
- Continuous verifiable delay functions
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
- The parameterized complexity of welfare guarantees in Schelling segregation
- Unique end of potential line
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Eisenberg-Gale markets: algorithms and game-theoretic properties
- Good hidden \(P\)-matrix sandwiches
- Revisiting the Cryptographic Hardness of Finding a Nash Equilibrium
- Simple search methods for finding a Nash equilibrium
- Satisfactory graph partition, variants, and generalizations
- The computational content of Walras' existence theorem
- PPAD is as hard as LWE and iterated squaring
- On the complexity of collision resistant hash functions: new and old black-box separations
- Mean-payoff games with \(\omega\)-regular specifications
- Towards a Unified Complexity Theory of Total Functions
- Structure versus hardness through the obfuscation lens
- Combinatorial nullstellensatz modulo prime powers and the parity argument
- TFNP: an update
- Computational aspects of the colorful Carathéodory theorem
- Relativization of Gurevich’s Conjectures
- Computational tameness of classical non-causal models
- PPAD-complete approximate pure Nash equilibria in Lipschitz games
- On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$
- The Complexity of Public-Key Cryptography
- Note on constrained long choice with multiple beginning elements
- Simple complexity from imitation games
- A CSP-Based Approach for Solving Parity Game
- Did the train reach its destination: the complexity of finding a witness
- scientific article; zbMATH DE number 3999295 (Why is no real title available?)
- Adventures in monotone complexity and TFNP
- Computable total functions on metric algebras, universal algebraic specifications and dynamical systems
- Computing equilibria: a computational complexity perspective
- On functional complexity and superpositions of functions
- The complexity of finding fair independent sets in cycles
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Type 2 computational complexity of functions on Cantor's space
- The Hairy Ball problem is PPAD-complete
- Two's company, three's a crowd: consensus-halving for a constant number of agents
- Further collapses in \(\mathsf{TFNP}\)
- The frontier of intractability for EFX with two agents
This page was built for publication: On total functions, existence theorems and computational complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q808245)
