The isomorphism conjecture fails relative to a random oracle

DOI10.1145/201019.201030MaRDI QIDQ4369869zbMATH OpenOpenAlexWikidataFDO

Authors Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Publication date 2 February 1998

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://surface.syr.edu/eecs/37

zbMATH Keywords

annihilating functionsscrambling functions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The isomorphism conjecture for NP
• The isomorphism conjecture holds and one-way functions exist relative to an oracle
• One-way functions and the isomorphism conjecture

Cited in

(27)

• A survey of one-way functions in complexity theory
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• The random oracle hypothesis is false
• The lazy adversary conjecture fails
• DSPACE(\(n\)) \(\overset {?} =\) NSPACE(\(n\)): A degree theoretic characterization
• Polynomial-time axioms of choice and polynomial-time cardinality
• Non-uniform reductions
• An oracle builder's toolkit
• The Isomorphism Conjecture Holds Relative to an Oracle
• Collapsing degrees via strong computation
• Reductions to sets of low information content (extended abstract)
• On one-way functions and polynomial-time isomorphisms
• Circuit size relative to pseudorandom oracles
• One-way functions and the isomorphism conjecture
• The degree structure of 1-L reductions
• Relativized worlds with an infinite hierarchy
• A hierarchy based on output multiplicity
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• Structural complexity theory: Recent surprises
• The isomorphism conjecture holds and one-way functions exist relative to an oracle
• Inverting onto functions.
• On P-immunity of exponential time complete sets
• One-way functions and the nonisomorphism of NP-complete sets
• The isomorphism conjecture for constant depth reductions
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• On the topological size of p-m-complete degrees
• Relativized isomorphisms of NP-complete sets

This page was built for publication: The isomorphism conjecture fails relative to a random oracle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4369869)