Abstract
A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. The celebrated "hardness v.s. randomness” paradigm pioneered by BlumMicali (SIAM JoC’84), Yao (FOCS’84) and NisanWigderson (JCSS’94) presents hardness assumptions under which e.g., prBPP = prP (socalled "highend derandomization), or prBPP ⊆ prSUBEXP (socalled "lowend derandomization), and more generally, under which prBPP ⊆ prDTIME(?) where ? is a "nice" class (closed under composition with a polynomial), but these hardness assumptions are not known to also be necessary for such derandomization.
In this work, following the recent work by Chen and Tell (FOCS’21) that considers "almostallinput" hardness of a function f (i.e., hardness of computing f on more than a finite number of inputs), we consider "almostallinput" leakageresilient hardness of a function f  that is, hardness of computing f(x) even given, say, √x bits of leakage of f(x). We show that leakageresilient hardness characterizes derandomization of prBPP (i.e., gives a both necessary and sufficient condition for derandomization), both in the highend and in the lowend setting.
In more detail, we show that there exists a constant c such that for every function T, the following are equivalent:
 prBPP ⊆ prDTIME(poly(T(poly(n))));
 Existence of a poly(T(poly(n)))time computable function f :{0,1}ⁿ → {0,1}ⁿ that is almostallinput leakageresilient hard with respect to n^ctime probabilistic algorithms. As far as we know, this is the first assumption that characterizes derandomization in both the lowend and the highend regime.
Additionally, our characterization naturally extends also to derandomization of prMA, and also to averagecase derandomization, by appropriately weakening the requirements on the function f. In particular, for the case of averagecase (a.k.a. "effective") derandomization, we no longer require the function to be almostallinput hard, but simply satisfy the more standard notion of averagecase leakageresilient hardness (w.r.t., every samplable distribution), whereas for derandomization of prMA, we instead consider leakageresilience for relations.
BibTeX  Entry
@InProceedings{liu_et_al:LIPIcs.CCC.2023.32,
author = {Liu, Yanyi and Pass, Rafael},
title = {{LeakageResilient Hardness vs Randomness}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {32:132:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772822},
ISSN = {18688969},
year = {2023},
volume = {264},
editor = {TaShma, Amnon},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18302},
URN = {urn:nbn:de:0030drops183022},
doi = {10.4230/LIPIcs.CCC.2023.32},
annote = {Keywords: Derandomization, LeakageResilient Hardness}
}
Keywords: 

Derandomization, LeakageResilient Hardness 
Collection: 

38th Computational Complexity Conference (CCC 2023) 
Issue Date: 

2023 
Date of publication: 

10.07.2023 