Shadows to Seeds: Importing Classical-Shadow Derandomization into Algorithm Design

Translate derandomized measurement schemes from classical-shadow tomography to classical randomized algorithms by designing deterministic or near-deterministic “seed sets” whose averages mimic expectations over random choices for families of objectives or tests. These seed sets act like epsilon-approximations but are tuned to algorithmic primitives such as randomized rounding, isolation, or reconstruction. This approach focuses on minimizing measurement/sample complexity under specific observable families and systematically characterizes when such “shadow seed sets” can derandomize computations without time overhead. It builds on expander-walk PRG ideas and identifies regimes where shadow-style constructions outperform generic expanders in sample complexity and runtime. The project also explores time–space tradeoffs where shadow seeds beat standard derandomization. The impact includes practical, drop-in deterministic replacements for widely used randomized steps with provable guarantees and no runtime penalty in targeted settings.

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. Derandomization from time-space tradeoffs. Oliver Korten (2022). Cybersecurity and Cyberforensics Conference.
4. Measurement optimization of variational quantum simulation by classical shadow and derandomization. Kouhei Nakaji, Suguru Endo, Y. Matsuzaki, H. Hakoshima (2022). Quantum.