Random permutations in computational complexity
From MaRDI portal
Cites work
- A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem
- A method for obtaining digital signatures and public-key cryptosystems
- Almost everywhere high nonuniform complexity
- An observation on probability versus randomness with applications to complexity classes
- Bi-immune sets for complexity classes
- Circuit size relative to pseudorandom oracles
- Exact learning algorithms, betting games, and circuit lower bounds
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hard languages in NP \(\cap\) coNP and NIZK proofs from unstructured hardness
- Hardness vs randomness
- scientific article; zbMATH DE number 1261804 (Why is no real title available?)
- scientific article; zbMATH DE number 1048036 (Why is no real title available?)
- scientific article; zbMATH DE number 3034028 (Why is no real title available?)
- Kolmogorov-Loveland randomness and stochasticity
- Mathematical metaphysics of randomness
- New directions in cryptography
- Polynomial-time random oracles and separating complexity classes
- Query complexity, or why is it difficult to separate NP^ A coNP^ A from P^ A by random oracles A?
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Strengths and Weaknesses of Quantum Computing
- The definition of random sequences
- The zero-one law holds for BPP
- Why computational complexity requires stricter martingales
This page was built for publication: Random permutations in computational complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7310233)
