An oracle builder's toolkit
From MaRDI portal
Publication:1398366
Recommendations
Cites work
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 3652325 (Why is no real title available?)
- scientific article; zbMATH DE number 3715539 (Why is no real title available?)
- scientific article; zbMATH DE number 46423 (Why is no real title available?)
- scientific article; zbMATH DE number 107774 (Why is no real title available?)
- scientific article; zbMATH DE number 192916 (Why is no real title available?)
- scientific article; zbMATH DE number 1072530 (Why is no real title available?)
- scientific article; zbMATH DE number 1555957 (Why is no real title available?)
- scientific article; zbMATH DE number 1775405 (Why is no real title available?)
- scientific article; zbMATH DE number 1796836 (Why is no real title available?)
- scientific article; zbMATH DE number 841081 (Why is no real title available?)
- scientific article; zbMATH DE number 845841 (Why is no real title available?)
- scientific article; zbMATH DE number 3358471 (Why is no real title available?)
- scientific article; zbMATH DE number 3092555 (Why is no real title available?)
- A model of set-theory in which every set of reals is Lebesgue measurable
- Almost everywhere high nonuniform complexity
- An oracle builder's toolkit
- Classical recursion theory. The theory of functions and sets of natural numbers
- Complexity Measures for Public-Key Cryptosystems
- Complexity limitations on quantum computation
- Complexity of Presburger arithmetic with fixed quantifier dimension
- Definability in the Turing degrees
- Definability in the enumeration degrees
- Forcing and reducibilities
- Gap-definable counting classes
- Generic separations
- Graph Isomorphism is in SPP
- Graph isomorphism is low for PP
- On Isomorphisms and Density of NP and Other Complete Sets
- On degrees of recursive unsolvability
- On the degree of Boolean functions as real polynomials
- One-way functions and the nonisomorphism of NP-complete sets
- Oracles for structural properties: The isomorphism problem and public-key cryptography
- PP-lowness and a simple definition of AWPP
- Quantum Complexity Theory
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Set theory. An introduction to independence proofs
- Some applications of the notions of forcing and generic sets
- Strengths and Weaknesses of Quantum Computing
- THE INDEPENDENCE OF THE CONTINUUM HYPOTHESIS
- The Isomorphism Conjecture Holds Relative to an Oracle
- The complexity of computing the permanent
- The isomorphism conjecture fails relative to a random oracle
- The isomorphism conjecture holds and one-way functions exist relative to an oracle
- The upper semi-lattice of degrees of recursive unsolvability
- Two queries
Cited in
(24)- Complexity classes of equivalence problems revisited
- Complexity limitations on quantum computation
- Partially definable forcing and bounded arithmetic
- Relativized generic classes P and NP
- An oracle builder's toolkit
- The robustness of LWPP and WPP, with an application to graph reconstruction
- A tight relationship between generic oracles and type-2 complexity theory
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Quantum and classical complexity classes: Separations, collapses, and closure properties
- LWPP and WPP are not uniformly gap-definable
- A general method to construct oracles realizing given relationships between complexity classes
- Error-bounded probabilistic computations between MA and AM
- Relativized worlds with an infinite hierarchy
- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- A hierarchy based on output multiplicity
- One complexity theorist's view of quantum computing
- NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
- The isomorphism conjecture holds and one-way functions exist relative to an oracle
- Strong self-reducibility precludes strong immunity
- Complexity measures and decision tree complexity: a survey.
- The generic oracle hypothesis is false
- Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
- Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\)
- Graph Isomorphism is in SPP
This page was built for publication: An oracle builder's toolkit
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1398366)
