License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.79
URN: urn:nbn:de:0030-drops-117644
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11764/
Go to the corresponding LIPIcs Volume Portal

Goldwasser, Shafi ; Grossman, Ofer ; Mohanty, Sidhanth ; Woodruff, David P.

Pseudo-Deterministic Streaming

pdf-format:
LIPIcs-ITCS-2020-79.pdf (0.6 MB)

Abstract

A pseudo-deterministic 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 pseudo-deterministic. For example, in the instance of finding a nonzero entry in a vector, for any known low-space 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 low-memory pseudo-deterministic algorithms. For instance, we show that there is no low-memory pseudo-deterministic algorithm for finding a nonzero entry in a vector (given in a turnstile fashion), and also that there is no low-dimensional pseudo-deterministic sketching algorithm for ?_2 norm estimation. We also exhibit problems which do have low memory pseudo-deterministic algorithms but no low memory deterministic algorithm, such as outputting a nonzero row of a matrix, or outputting a basis for the row-span of a matrix.
We also investigate multi-pseudo-deterministic 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 =	{{Pseudo-Deterministic Streaming}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{79:1--79:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Thomas Vidick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11764},
  URN =		{urn:nbn:de:0030-drops-117644},
  doi =		{10.4230/LIPIcs.ITCS.2020.79},
  annote =	{Keywords: streaming, pseudo-deterministic}
}

Keywords: streaming, pseudo-deterministic
Collection: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Issue Date: 2020
Date of publication: 06.01.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI