SU\G(𝔸)/K·U

Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence

Mohsen Ghaffari, Christoph Grunau, Václav Rozhoň

Type: Preprint

Publication Date: 2023-01-01

Citations: 0

DOI: https://doi.org/10.48550/arxiv.2311.13764

Locations

  • arXiv (Cornell University) - View - PDF
  • DataCite API - View

Similar Works

Action Title Year Authors
+ PDF Chat Work-Efficient Parallel Derandomization I: Chernoff-like Concentrations via Pairwise Independence 2023 Mohsen Ghaffari
Christoph Grunau
Václav Rozhoň
+ Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping 2023 Mohsen Ghaffari
Christoph Grunau
+ Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping 2024 Mohsen Ghaffari
Christoph Grunau
+ Derandomizing Chernoff Bound with Union Bound with an Application to $k$-wise Independent Sets 2016 Nader H. Bshouty
+ Derandomizing Chernoff Bound with Union Bound with an Application to $k$-wise Independent Sets. 2016 Nader H. Bshouty
+ Theorems about space-bounded Kolmogorov complexity obtained by "naive" derandomization 2010 Daniil Musatov
+ Derandomization by exploiting redundancy and mutual independence 1990 Yijie Han
Yoshihide Igarashi
+ PDF Chat Amplification and Derandomization without Slowdown 2016 Ofer Grossman
Dana Moshkovitz
+ PDF Chat Pairwise Independence and Derandomization 2005 Michael Luby
Avi Wigderson
+ Amplification and Derandomization Without Slowdown 2015 Ofer Grossman
Dana Moshkovitz
+ Amplification and Derandomization Without Slowdown 2015 Ofer Grossman
Dana Moshkovitz
+ Derandomization via small sample spaces 1996 Noga Alon
+ A New Approach to Multi-Party Peer-to-Peer Communication Complexity 2019 Adi Rosén
Florent Urrutia
+ Parameterized Derandomization 2008 Moritz Müller
+ PDF Chat Derandomized concentration bounds for polynomials, and hypergraph maximal independent set 2018 David G. Harris
+ A New Approach to Multi-Party Peer-to-Peer Communication Complexity 2019 Adi Rosén
Florent Urrutia
+ Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization 2010 Daniil Musatov
+ PDF Chat A mathematical theory of randomized computation, I 1988 Shinichi Yamada
+ Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization 2010 Daniil Musatov
+ Derandomization: A Brief Overview 2002 Valentine Kabanets

Works That Cite This (0)

Action Title Year Authors

Works Cited by This (0)

Action Title Year Authors