Carboni Oliveira, Igor ;
Santhanam, Rahul
PseudoDerandomizing Learning and Approximation
Abstract
We continue the study of pseudodeterministic algorithms initiated by Gat and Goldwasser [Eran Gat and Shafi Goldwasser, 2011]. A pseudodeterministic algorithm is a probabilistic algorithm which produces a fixed output with high probability. We explore pseudodeterminism in the settings of learning and approximation. Our goal is to simulate known randomized algorithms in these settings by pseudodeterministic algorithms in a generic fashion  a goal we succinctly term pseudoderandomization. Learning. In the setting of learning with membership queries, we first show that randomized learning algorithms can be derandomized (resp. pseudoderandomized) under the standard hardness assumption that E (resp. BPE) requires large Boolean circuits. Thus, despite the fact that learning is an algorithmic task that requires interaction with an oracle, standard hardness assumptions suffice to (pseudo)derandomize it. We also unconditionally pseudoderandomize any {quasipolynomial} time learning algorithm for polynomial size circuits on infinitely many input lengths in subexponential time.
Next, we establish a generic connection between learning and derandomization in the reverse direction, by showing that deterministic (resp. pseudodeterministic) learning algorithms for a concept class C imply hitting sets against C that are computable deterministically (resp. pseudodeterministically). In particular, this suggests a new approach to constructing hitting set generators against AC^0[p] circuits by giving a deterministic learning algorithm for AC^0[p]. Approximation. Turning to approximation, we unconditionally pseudoderandomize any polytime randomized approximation scheme for integervalued functions infinitely often in subexponential time over any samplable distribution on inputs. As a corollary, we get that the (0,1)Permanent has a fully pseudodeterministic approximation scheme running in subexponential time infinitely often over any samplable distribution on inputs.
Finally, we {investigate} the notion of approximate canonization of Boolean circuits. We use a connection between pseudodeterministic learning and approximate canonization to show that if BPE does not have subexponential size circuits infinitely often, then there is a pseudodeterministic approximate canonizer for AC^0[p] computable in quasipolynomial time.
BibTeX  Entry
@InProceedings{carbonioliveira_et_al:LIPIcs:2018:9459,
author = {Igor Carboni Oliveira and Rahul Santhanam},
title = {{PseudoDerandomizing Learning and Approximation}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {55:155:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770859},
ISSN = {18688969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9459},
URN = {urn:nbn:de:0030drops94598},
doi = {10.4230/LIPIcs.APPROXRANDOM.2018.55},
annote = {Keywords: derandomization, learning, approximation, boolean circuits}
}
13.08.2018
Keywords: 

derandomization, learning, approximation, boolean circuits 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Issue date: 

2018 
Date of publication: 

13.08.2018 