Total search problems in ZPP
From MaRDI portal
Cites work
- A combinatorial characterization of resolution width
- A complexity gap for tree resolution
- Adventures in monotone complexity and TFNP
- Almost-everywhere circuit lower bounds from non-trivial derandomization
- Approximate counting and NP search problems
- Approximate counting in bounded arithmetic
- Certified hardness vs. randomness for log-space
- Colourful TFNP and propositional proofs
- Computing with a full memory: catalytic space
- Constructive separations and their consequences
- Derandomization from time-space tradeoffs
- Derandomization vs refutation: a unified framework for characterizing derandomization
- Derandomizing logspace with a small shared hard drive
- Distinguishing, predicting, and certifying: on the long reach of partial notions of pseudorandomness
- Dual weak pigeonhole principle, Boolean complexity, and derandomization
- Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
- Explicit lower bounds against (n)-rounds of sum-of-squares
- Extremal combinatorics, iterated pigeonhole arguments and generalizations of PPP
- Fragments of approximate counting
- Further collapses in \(\mathsf{TFNP}\)
- Graph colouring is hard on average for polynomial calculus and Nullstellensatz
- Hardness vs randomness
- How easy is local search?
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- Integer factoring and modular square roots
- Intersection classes in TFNP and proof complexity
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Notes on resolution over linear equations
- On average-case hardness in \textsf{TFNP} from one-way functions
- On Independence of Variants of the Weak Pigeonhole Principle
- 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 range avoidance problem for circuits
- One-way functions vs. TFNP: Simpler and improved
- Optimality of size-width tradeoffs for resolution
- PRIMES is in P
- Propositional proofs and reductions between NP search problems
- Provability of the pigeonhole principle and the existence of infinitely many primes
- Provably total functions in the polynomial hierarchy
- Pseudo-random generators for all hardnesses
- Random resolution refutations
- Range avoidance and the complexity of explicit constructions
- Range avoidance for constant depth circuits: hardness and algorithms
- Range avoidance for low-depth circuits and connections to pseudorandomness
- Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
- Reusing space: techniques and open problems
- Reverse mathematics of complexity lower bounds
- Semialgebraic Proofs and Efficient Algorithm Design
- Separations in proof complexity and TFNP
- Settling the complexity of two-player Nash equilibrium
- Short proofs for tricky formulas
- Strong vs. weak range avoidance and the linear ordering principle
- Sum of squares bounds for the ordering principle
- TFNP characterizations of proof systems and monotone circuits
- TFNP intersections through the Lens of feasible disjunction
- The classical decision problem.
- The complexity of computing a Nash equilibrium
- The complexity of gradient descent: CLS = PPAD pls
- The hardest explicit construction
- The more the merrier! On total coding and lattice problems and the complexity of finding multicollisions
- The ordering principle in a fragment of approximate counting
- The relative complexity of NP search problems
- Total functions in the polynomial hierarchy
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Witnessing functions in bounded arithmetic and search problems
This page was built for publication: Total search problems in ZPP
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7445583)