scientific article; zbMATH DE number 1789922
From MaRDI portal
Publication:4549233
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)
Recommendations
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)
