Is Untrusted Randomness Helpful?
summary
Defines a model where an algorithm gets many adversarial untrusted random bits plus k truly random bits and may output 0,1 or "I don't know", formalized as RPP_k. Shows equivalence to a prover–verifier proof object and proves for log-space that RPL_log n collapses to BPL using only O(log n) trusted bits by a streaming proof that verifies distributions via linear tests. Also gives an unconditional query separation: a one-query promise problem solvable with k trusted + n untrusted bits but requiring exponentially many queries for any BPP or ZPP algorithm.
AI-written summary · about