License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.32
URN: urn:nbn:de:0030-drops-183022
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18302/
Liu, Yanyi ;
Pass, Rafael
Leakage-Resilient Hardness vs Randomness
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 Blum-Micali (SIAM JoC’84), Yao (FOCS’84) and Nisan-Wigderson (JCSS’94) presents hardness assumptions under which e.g., prBPP = prP (so-called "high-end derandomization), or prBPP ⊆ prSUBEXP (so-called "low-end 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 "almost-all-input" hardness of a function f (i.e., hardness of computing f on more than a finite number of inputs), we consider "almost-all-input" leakage-resilient 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 leakage-resilient hardness characterizes derandomization of prBPP (i.e., gives a both necessary and sufficient condition for derandomization), both in the high-end and in the low-end 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 almost-all-input leakage-resilient hard with respect to n^c-time probabilistic algorithms. As far as we know, this is the first assumption that characterizes derandomization in both the low-end and the high-end regime.
Additionally, our characterization naturally extends also to derandomization of prMA, and also to average-case derandomization, by appropriately weakening the requirements on the function f. In particular, for the case of average-case (a.k.a. "effective") derandomization, we no longer require the function to be almost-all-input hard, but simply satisfy the more standard notion of average-case leakage-resilient hardness (w.r.t., every samplable distribution), whereas for derandomization of prMA, we instead consider leakage-resilience for relations.
BibTeX - Entry
@InProceedings{liu_et_al:LIPIcs.CCC.2023.32,
author = {Liu, Yanyi and Pass, Rafael},
title = {{Leakage-Resilient Hardness vs Randomness}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {32:1--32:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-282-2},
ISSN = {1868-8969},
year = {2023},
volume = {264},
editor = {Ta-Shma, Amnon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18302},
URN = {urn:nbn:de:0030-drops-183022},
doi = {10.4230/LIPIcs.CCC.2023.32},
annote = {Keywords: Derandomization, Leakage-Resilient Hardness}
}
|
Keywords: |
|
Derandomization, Leakage-Resilient Hardness |
|
Collection: |
|
38th Computational Complexity Conference (CCC 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
10.07.2023 |
