Cheng, Kuan ;
Hoza, William M.
Hitting Sets Give TwoSided Derandomization of Small Space
Abstract
A hitting set is a "onesided" variant of a pseudorandom generator (PRG), naturally suited to derandomizing algorithms that have onesided error. We study the problem of using a given hitting set to derandomize algorithms that have twosided error, focusing on spacebounded algorithms. For our first result, we show that if there is a logspace hitting set for polynomialwidth readonce branching programs (ROBPs), then not only does š = šš, but š = ššš as well. This answers a question raised by Hoza and Zuckerman [William M. Hoza and David Zuckerman, 2018].
Next, we consider constantwidth ROBPs. We show that if there are logspace hitting sets for constantwidth ROBPs, then given blackbox access to a constantwidth ROBP f, it is possible to deterministically estimate š¼[f] to within Ā± Īµ in space O(log(n/Īµ)). Unconditionally, we give a deterministic algorithm for this problem with space complexity O(logĀ² n + log(1/Īµ)), slightly improving over previous work.
Finally, we investigate the limits of this line of work. Perhaps the strongest reduction along these lines one could hope for would say that for every explicit hitting set, there is an explicit PRG with similar parameters. In the setting of constantwidth ROBPs over a large alphabet, we prove that establishing such a strong reduction is at least as difficult as constructing a good PRG outright. Quantitatively, we prove that if the strong reduction holds, then for every constant Ī± > 0, there is an explicit PRG for constantwidth ROBPs with seed length O(log^{1 + Ī±} n). Along the way, unconditionally, we construct an improved hitting set for ROBPs over a large alphabet.
BibTeX  Entry
@InProceedings{cheng_et_al:LIPIcs:2020:12562,
author = {Kuan Cheng and William M. Hoza},
title = {{Hitting Sets Give TwoSided Derandomization of Small Space}},
booktitle = {35th Computational Complexity Conference (CCC 2020)},
pages = {10:110:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771566},
ISSN = {18688969},
year = {2020},
volume = {169},
editor = {Shubhangi Saraf},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12562},
URN = {urn:nbn:de:0030drops125625},
doi = {10.4230/LIPIcs.CCC.2020.10},
annote = {Keywords: hitting sets, derandomization, readonce branching programs}
}
17.07.2020
Keywords: 

hitting sets, derandomization, readonce branching programs 
Seminar: 

35th Computational Complexity Conference (CCC 2020)

Issue date: 

2020 
Date of publication: 

17.07.2020 