EUVIMEDEUVIMED entdecken
Crossref

Guest Column: New ways of studying the BPP = P conjecture

Lijie Chen, Roei Tell

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →