scientific article; zbMATH DE number 1789922
From MaRDI portal
Publication:4549233
algebraic circuit complexitycircuit complexitycomplexity classesderandomizationprobabilistic algorithmsprobabilistic complexity classespseudo-randomness
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Recommendations
Cited in
(16)- Random oracles and non-uniformity
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science
- Can every randomized algorithm be derandomized?
- Computational Randomness from Generalized Hardcore Sets
- Pairwise independence and derandomization.
- scientific article; zbMATH DE number 1156868 (Why is no real title available?)
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- Quantified Derandomization: How to Find Water in the Ocean
- List-Decoding with Double Samplers
- Randomisation and derandomisation in descriptive complexity theory
- Randomisation and derandomisation in descriptive complexity theory
- Easiness assumptions and hardness tests: Trading time for zero error
- (Nondeterministic) hardness vs. non-malleability
- Hardness hypotheses, derandomization, and circuit complexity
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)
