Lower time bounds for randomized computation

DOI10.1007/3-540-60084-1_73zbMath1412.68063OpenAlexW4205776748MaRDI QIDQ4645177

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

Kolmogorov complexityTuring machineprobabilistic machineinput tapeinput word

Mathematics Subject Classification ID

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• On randomized versus deterministic computation
• Information Transfer under Different Sets of Protocols
• Lower space bounds for randomized computation

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