The Price of Correlation: Quantifying and Derandomizing Shared Randomness in Local Distributed Algorithms

Develop a general complexity measure for the “price of correlation” in local distributed algorithms and design algorithmic primitives—network PRGs—that use sparse communication and small memory to simulate or approximate shared randomness from private randomness. This builds on results showing shared randomness can drastically reduce complexity in LCL problems. The project aims to establish a systematic tradeoff framework quantifying how much shared correlation is needed for a given speedup and to construct protocols that realize these tradeoffs. It draws on expander walks for correlation seeding, derandomization frameworks in LOCAL models, and lossy beacon constructions for broadcasting short seeds. This research bridges the gap between existential separations and constructive methods, potentially yielding practical protocols for distributed systems (including quantum variants) that minimize global randomness sources without sacrificing speed. The impact includes a unified theory and toolkit for trading communication, memory, and shared randomness, clarifying when “free derandomization” is impossible and offering near-optimal approximations when costly.

References:

1. Pseudorandomness of expander random walks for symmetric functions and permutation branching programs. Louis Golowich, S. Vadhan (2022). Electron. Colloquium Comput. Complex..
2. Derandomization with Minimal Memory Footprint. Dean Doron, R. Tell (2023). Electron. Colloquium Comput. Complex..
3. Shared Randomness Helps with Local Distributed Problems. Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikael Rabie, J. Suomela, Jara Uitto (2024). International Colloquium on Automata, Languages and Programming.
4. Shared Randomness Helps with Local Distributed Problems. Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mikael Rabie, J. Suomela, Jara Uitto (2024). International Colloquium on Automata, Languages and Programming.
5. CS265/CME309: Randomized Algorithms and Probabilistic Analysis Lecture #18: A taste of pseudorandomness: extractors and expanders. Mary Wootters (2020).