Lower time bounds for randomized computation

DOI10.1007/3-540-60084-1_73MaRDI QIDQ4645177zbMATH OpenOpenAlexFDO

Authors Rūsiņš Freivalds, Marek Karpinski

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_73

zbMATH Keywords

input tapeinput wordKolmogorov complexityprobabilistic machineTuring machine

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Lower space bounds for randomized computation
• Time-space trade-off lower bounds for randomized computation of decision problems
• Automata, Languages and Programming
• scientific article; zbMATH DE number 1072535
• Separating sublinear time computations by approximate diameter

Cites work

• scientific article; zbMATH DE number 3887666 (Why is no real title available?)
• scientific article; zbMATH DE number 3858415 (Why is no real title available?)
• scientific article; zbMATH DE number 3700210 (Why is no real title available?)
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• scientific article; zbMATH DE number 18635 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 3540744 (Why is no real title available?)
• scientific article; zbMATH DE number 3573787 (Why is no real title available?)
• scientific article; zbMATH DE number 3316587 (Why is no real title available?)
• Information Transfer under Different Sets of Protocols
• Lower space bounds for randomized computation
• On randomized versus deterministic computation
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes

Cited in

(9)

• Lower Bounds for Coin-Weighing Problems
• Time-space trade-off lower bounds for randomized computation of decision problems
• scientific article; zbMATH DE number 3938347 (Why is no real title available?)
• The Random Adversary: A Lower-Bound Technique for Randomized Parallel Algorithms
• Lower space bounds for randomized computation
• On lower bounds for the time of computation
• Theory of Cryptography
• A lower bound for randomized list update algorithms
• Separating sublinear time computations by approximate diameter

This page was built for publication: Lower time bounds for randomized computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645177)