2023/03/29 by Edward Pyne, Pyne, Edward, Ran Raz +3
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2303.16413
openalex publication_date 2023/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let L be a language that can be decided in linear space and let ε>0 be any constant. Let A be the exponential hardness assumption that for every n, membership in L 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 A is false'', followed by a (provenly correct) circuit of size smaller than 2εn' for membership in L for inputs of length~n', for some n' = Θ(log n); that is, a circuit that refutes A. 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 CR ⋅ log n (where CR 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 CR ⋅ (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.