Guest Column: New ways of studying the BPP = P conjecture
ACM SIGACT News · 13.06.2023 · 54 (2) · 44-69
DOI: 10.1145/3604943.3604950 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM SIGACT News, online erschienen am 14.06.2023. Verfasst von Lijie Chen und 1 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 80 Literaturangaben.
Abstract (Originalsprache)
What's new in the world of derandomization? Questions about pseudorandomness and derandomization have been driving progress in complexity theory for many decades. In this survey we will describe new approaches to the BPP = P conjecture from recent years, as well as new questions, algorithmic approaches, and ways of thinking. For example: Do we really need pseudorandom generators for derandomization, or can we get away with weaker objects? Can we prove free lunch theorems, eliminating randomness with zero computational overhead? What hardness assumptions are necessary and sufficient for derandomization? And how do new advances in this area interact with progress in cryptography and in interactive proof systems?
Zitieren
APA
Chen, L., & Tell, R. (2023). Guest Column: New ways of studying the BPP = P conjecture. ACM SIGACT News, 54(2), 44-69. https://doi.org/10.1145/3604943.3604950
Vancouver
Chen L, Tell R. Guest Column: New ways of studying the BPP = P conjecture. ACM SIGACT News. 2023;54(2):44-69. doi:10.1145/3604943.3604950
BibTeX
@article{Chen2023,
author = {Chen, Lijie and Tell, Roei},
title = {Guest Column: New ways of studying the BPP = P conjecture},
journal = {ACM SIGACT News},
year = {2023},
volume = {54},
number = {2},
pages = {44--69},
doi = {10.1145/3604943.3604950}
}
EUVIMED