Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization

We establish an equivalence between two algorithmic tasks: derandomization, the deterministic simulation of probabilistic algorithms; and refutation, the deterministic construction of inputs on which a given probabilistic algorithm fails to compute a certain hard function. We prove that refuting low-space probabilistic streaming algorithms which attempt to compute functions $f \in \mathcal{F P}$ is equivalent to proving that $\operatorname{pr} \mathcal{B P} \mathcal{P}=\operatorname{pr} \mathcal{P}$, even in cases where a lower bound for f against such streaming algorithms (without a refuter) is already unconditionally known. We also demonstrate the generality of our connection between refutation and derandomization, by establishing connections between refuting classes of constant-depth circuits of sublinear size and derandomizing constant-depth circuits of polynomial size with threshold gates (i. e. , $\mathcal{T C}^{0}$). Our connection generalizes and strengthens recent work on the characterization of derandomization. In particular, the refuter framework allows to directly compare several recent works to each other and to our work, as well as to chart a path for further progress. Along the way, we also improve the targeted hitting-set generator of Chen and Tell (FOCS 2021), showing that its translation of hardness to pseudorandomness scales down to $\mathcal{T C}^{0}$.

Authors

• Lijie Chen 0001
• Roei Tell
• R. Ryan Williams

Keywords

• Computer science
• Logic gates
• Probabilistic logic
• Generators
• Task analysis
• Classical Circuit
• Time And Space
• Lower Bound
• Decoding
• Classification Algorithms
• Reconstruction Algorithm
• Reconstructive
• Decision Problem
• Universal Constant
• Codeword
• Forward Error Correction
• Constant Depth
• Turing Machine
• Entry In Row
• Deterministic Time
• Small Circuit
• Output Length
• Output Bits
• Original Proof
• Probabilistic Polynomial Time
• Multiple Bits
• Multiple Outputs
• Input Length
• Search Problem
• Line Of Work
• Alphabet
• Complex Communication
• Functional Class
• Refuters
• derandomization
• streaming algorithms
• threshold circuits