Certified Hardness vs. Randomness for Log-Space
share
Let ℒ be a language that can be decided in linear space and let ϵ >0 be any constant. Let 𝒜 be the exponential hardness assumption that for every n, membership in ℒ for inputs of length n cannot be decided by circuits of size smaller than 2^ϵ n. We prove that for every function f :{0,1}^* →{0,1}, computable by a randomized logspace algorithm R, there exists a deterministic logspace algorithm D (attempting to compute f), such that on every input x of length n, the algorithm D outputs one of the following: 1: The correct value f(x). 2: The string: “I am unable to compute f(x) because the hardness assumption 𝒜 is false”, followed by a (provenly correct) circuit of size smaller than 2^ϵ n' for membership in ℒ for inputs of length n', for some n' = Θ (log n); that is, a circuit that refutes 𝒜. Our next result is a universal derandomizer for BPL: We give a deterministic algorithm U that takes as an input a randomized logspace algorithm R and an input x and simulates the computation of R on x, deteriministically. Under the widely believed assumption BPL=L, the space used by U is at most C_R ·log n (where C_R is a constant depending on R). Moreover, for every constant c ≥ 1, if BPL⊆ SPACE[(log(n))^c] then the space used by U is at most C_R · (log(n))^c. Finally, we prove that if optimal hitting sets for ordered branching programs exist then there is a deterministic logspace algorithm that, given a black-box access to an ordered branching program B of size n, estimates the probability that B accepts on a uniformly random input. This extends the result of (Cheng and Hoza CCC 2020), who proved that an optimal hitting set implies a white-box two-sided derandomization.
READ FULL TEXT