Goldwasser, Shafi ;
Grossman, Ofer ;
Mohanty, Sidhanth ;
Woodruff, David P.
PseudoDeterministic Streaming
Abstract
A pseudodeterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Classic streaming algorithms, such as those for finding heavy hitters, approximate counting, 𝓁_2 approximation, finding a nonzero entry in a vector (for turnstile algorithms) are not pseudodeterministic. For example, in the instance of finding a nonzero entry in a vector, for any known lowspace algorithm A, there exists a stream x so that running A twice on x (using different randomness) would with high probability result in two different entries as the output.
In this work, we study whether it is inherent that these algorithms output different values on different executions. That is, we ask whether these problems have lowmemory pseudodeterministic algorithms. For instance, we show that there is no lowmemory pseudodeterministic algorithm for finding a nonzero entry in a vector (given in a turnstile fashion), and also that there is no lowdimensional pseudodeterministic sketching algorithm for 𝓁_2 norm estimation. We also exhibit problems which do have low memory pseudodeterministic algorithms but no low memory deterministic algorithm, such as outputting a nonzero row of a matrix, or outputting a basis for the rowspan of a matrix.
We also investigate multipseudodeterministic algorithms: algorithms which with high probability output one of a few options. We show the first lower bounds for such algorithms. This implies that there are streaming problems such that every low space algorithm for the problem must have inputs where there are many valid outputs, all with a significant probability of being outputted.
BibTeX  Entry
@InProceedings{goldwasser_et_al:LIPIcs:2020:11764,
author = {Shafi Goldwasser and Ofer Grossman and Sidhanth Mohanty and David P. Woodruff},
title = {{PseudoDeterministic Streaming}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {79:179:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11764},
URN = {urn:nbn:de:0030drops117644},
doi = {10.4230/LIPIcs.ITCS.2020.79},
annote = {Keywords: streaming, pseudodeterministic}
}
06.01.2020
Keywords: 

streaming, pseudodeterministic 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Issue date: 

2020 
Date of publication: 

06.01.2020 