2023/12/21 by Shalunov, Yakov
#68Q15 (Primary) 68Q25 #68Q87 (Secondary) #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #G.3
paper · doi:10.48550/arxiv.2312.14023
Efficient derandomization has long been a goal in complexity theory, and a major recent result by Yanyi Liu and Rafael Pass identifies a new class of hardness assumption under which it is possible to perform time-bounded derandomization efficiently: that of ''leakage-resilient hardness.'' They identify a specific form of this assumption which is equivalent to prP = prBPP. In this paper, we pursue an equivalence to derandomization of \mathsfprBP⋅L (logspace promise problems with two-way randomness) through techniques analogous to Liu and Pass. We are able to obtain an equivalence between a similar ''leakage-resilient hardness'' assumption and a slightly stronger statement than derandomization of \mathsfprBP⋅L, that of finding ''non-no'' instances of ''promise search problems.''