Total NP search problems with abundant solutions
From MaRDI portal
Cites work
- Adventures in monotone complexity and TFNP
- Can PPAD hardness be based on standard cryptographic assumptions?
- Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
- Extremal combinatorics, iterated pigeonhole arguments and generalizations of PPP
- Fragments of approximate counting
- Further collapses in TFNP
- Hardness of continuous local search: query complexity and cryptographic lower bounds
- How easy is local search?
- scientific article; zbMATH DE number 1263206 (Why is no real title available?)
- scientific article; zbMATH DE number 1303133 (Why is no real title available?)
- scientific article; zbMATH DE number 6783433 (Why is no real title available?)
- Integer factoring and modular square roots
- Lower Bounds for Local Search by Quantum Arguments
- Matching algorithmic bounds for finding a Brouwer fixed point
- Near-optimal communication lower bounds for approximate Nash equilibria
- On average-case hardness in \textsf{TFNP} from one-way functions
- On the complexity of finding falsifying assignments for Herbrand disjunctions
- On the complexity of the parity argument and other inefficient proofs of existence
- On the possibilities and limitations of pseudodeterministic algorithms
- On total functions, existence theorems and computational complexity
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- PPP-completeness with connections to cryptography
- Pseudorandomness
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum separation of local search and fixed point computation
- Reducing Tarski to unique Tarski (In the Black-Box model)
- Separations in proof complexity and TFNP
- Settling the complexity of computing two-player Nash equilibria
- The complexity of computing a Nash equilibrium
- The complexity of constrained min-max optimization
- The complexity of gradient descent: CLS = PPAD pls
- The complexity of splitting necklaces and bisecting ham sandwiches
- Tight bounds for randomized and quantum local search
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Unique end of potential line
- Verifiable quantum advantage without structure
This page was built for publication: Total NP search problems with abundant solutions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6906352)
