The isomorphism conjecture fails relative to a random oracle

DOI10.1145/201019.201030zbMATH Open0886.68068OpenAlexW2090039082WikidataQ56610697 ScholiaQ56610697MaRDI QIDQ4369869FDOQ4369869

Stephen R. Mahaney, Stuart A. Kurtz, 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)

Cited In (26)

• Reductions to sets of low information content
• 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
• 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
• Structural complexity theory: Recent surprises
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• 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

   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 👍 👎

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)