scientific article; zbMATH DE number 1789922
zbMATH Open1012.68080MaRDI QIDQ4549233FDOQ4549233
Authors: Russell Impagliazzo 
Publication date: 27 August 2002
Title of this publication is not available (Why is that?)
Recommendations
complexity classesderandomizationcircuit complexityprobabilistic algorithmspseudo-randomnessprobabilistic complexity classesalgebraic circuit complexity
Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (14)
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Random oracles and non-uniformity
- List-Decoding with Double Samplers
- Computational Randomness from Generalized Hardcore Sets
- Easiness assumptions and hardness tests: Trading time for zero error
- (Nondeterministic) hardness vs. non-malleability
- Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- Pairwise independence and derandomization.
- Hardness hypotheses, derandomization, and circuit complexity
- Randomisation and derandomisation in descriptive complexity theory
- Randomisation and derandomisation in descriptive complexity theory
- Can every randomized algorithm be derandomized?
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4549233)
