We investigate one of the most basic problems in streaming algorithms: approximating the number of elements in the stream. Famously, [Mor78] gave a randomized algorithm achieving a constant-factor approximation error for streams of length at most N in space $O(\log\log N)$. We investigate the pseudo-deterministic complexity of the problem and prove a tight $\Omega(\log N)$ lower bound, thus resolving a problem of [GGMW20].

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed. We show that in this setting, it is sub-optimal to use standard error correction. We consider a model where there is a set of "valid messages" which the sender may send that may not be efficiently compressible, but where it is possible for the receiver to recognize valid messages. In this model, we construct a (probabilistic) encoding procedure that achieves better tradeoffs between data rates and error-resilience (compared to just applying a standard error correcting code). Additionally, our techniques yield improved efficiently decodable (probabilistic) codes for fully compressed messages (the standard setting where the set of valid messages is all binary strings) in the high-rate regime.

In many combinatorial games, one can prove that the first player wins under best play using a simple but non-constructive argument called strategy-stealing. This work is about the complexity behind these proofs: how hard is it to actually find a winning move in a game, when you know by strategy-stealing that one exists? We prove that this problem is PSPACE-Complete already for Minimum Poset Games and Symmetric Maker-Maker Games, which are simple classes of games that capture two of the main types of strategy-stealing arguments in the current literature.

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.

By far the most fruitful technique for showing lower bounds for the CONGEST model is reductions to two-party communication complexity. This technique has yielded nearly tight results for various fundamental problems such as distance computations, minimum spanning tree, minimum vertex cover, and more.

We study the problem of approximating the diameter D of an unweighted and undirected n-node graph in the congest model. Through a connection to extremal combinatorics, we show that a (6/11 + ε)-approximation requires Ω(n^{1/6}/log n) rounds, a (4/7 + ε)-approximation requires Ω(n^{1/4}/log n) rounds, and a (3/5 + ε)-approximation requires Ω(n^{1/3}/log n) rounds. These lower bounds are robust in the sense that they hold even against algorithms that are allowed to return an additional small additive error. Prior to our work, only lower bounds for (2/3 + ε)-approximation were known [Frischknecht et al. SODA 2012, Abboud et al. DISC 2016]. Furthermore, we prove that distinguishing graphs of diameter 3 from graphs of diameter 5 requires Ω(n/log n) rounds. This stands in sharp contrast to previous work: while there is an algorithm that returns an estimate ⌊ 2/3D ⌋ ≤ D̃ ≤ D in Õ(√n+D) rounds [Holzer et al. DISC 2014], our lower bound implies that any algorithm for returning an estimate 2/3D ≤ D̃ ≤ D requires ̃Ω(n) rounds.

We develop techniques to prove lower bounds for the BCAST(log n) Broadcast Congested Clique model (a distributed message passing model where in each round, each processor can broadcast an O(log n)-sized message to all other processors). Our techniques are built to prove bounds for natural input distributions. So far, all lower bounds for problems in the model relied on constructing specifically tailored graph families for the specific problem at hand, resulting in lower bounds for artificially constructed inputs, instead of natural input distributions.

A curious property of randomized log-space search algorithms is that their outputs are often longer than their workspace. This leads to the question: how can we reproduce the results of a randomized log space computation without storing the output or randomness verbatim? Running the algorithm again with new random bits may result in a new (and potentially different) output. We show that every problem in search-RL has a randomized log-space algorithm where the output can be reproduced. Specifically, we show that for every problem in search-RL, there are a pair of log-space randomized algorithms A and B where for every input x, A will output some string tx of size O(log n), such that B when running on (x, tx) will be pseudo-deterministic: that is, running B multiple times on the same input (x, tx) will result in the same output on all executions with high probability. Thus, by storing only O(log n) bits in memory, it is possible to reproduce the output of a randomized log-space algorithm. An algorithm is reproducible without storing any bits in memory (i.e., |tx| = 0) if and only if it is pseudo-deterministic. We show pseudo-deterministic algorithms for finding paths in undirected graphs and Eulerian graphs using logarithmic space. Our algorithms are substantially faster than the best known deterministic algorithms for finding paths in such graphs in log-space. The algorithm for search-RL has the additional property that its output, when viewed as a random variable depending on the randomness used by the algorithm, has entropy O(log n).

The noisy broadcast model was first studied by [Gallager, 1988] where an n-character input is distributed among n processors, so that each processor receives one input bit. Computation proceeds in rounds, where in each round each processor broadcasts a single character, and each reception is corrupted independently at random with some probability p. [Gallager, 1988] gave an algorithm for all processors to learn the input in O(log log n) rounds with high probability. Later, a matching lower bound of Omega(log log n) was given by [Goyal et al., 2008]. We study a relaxed version of this model where each reception is erased and replaced with a `?' independently with probability p, so the processors have knowledge of whether a bit has been corrupted. In this relaxed model, we break past the lower bound of [Goyal et al., 2008] and obtain an O(log^* n)-round algorithm for all processors to learn the input with high probability. We also show an O(1)-round algorithm for the same problem when the alphabet size is Omega(poly(n)).

We introduce pseudo-deterministic interactive proofs (psdIP): interactive proof systems for search problems where the verifier is guaranteed with high probability to output the same output on different executions. As in the case with classical interactive proofs, the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover. We view pseudo-deterministic interactive proofs as an extension of the study of pseudo-deterministic randomized polynomial time algorithms: the goal of the latter is to find canonical solutions to search problems whereas the goal of the former is to prove that a solution to a search problem is canonical to a probabilistic polynomial time verifier. Alternatively, one may think of the powerful prover as aiding the probabilistic polynomial time verifier to find canonical solutions to search problems, with high probability over the randomness of the verifier. The challenge is that pseudo-determinism should hold not only with respect to the randomness, but also with respect to the prover: a malicious prover should not be able to cause the verifier to output a solution other than the unique canonical one. The IP=PSPACE characterization implies that psdIP = IP. The challenge is to find constant round pseudo-deterministic interactive proofs for hard search problems. We show a constant round pseudo-deterministic interactive proof for the graph isomorphism problem: on any input pair of isomorphic graphs (G_0,G_1), there exist a unique isomorphism phi from G_0 to G_1 (although many isomorphism many exist) which will be output by the verifier with high probability, regardless of any dishonest prover strategy. In contrast, we show that it is unlikely that psdIP proofs with constant rounds exist for NP-complete problems by showing that if any NP-complete problem has a constant round psdIP protocol, then the polynomial hierarchy collapses.

We present a pseudo-deterministic NC algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses poly(n) processors, poly(log n) depth, poly(log n) random bits, and outputs for each bipartite input graph a unique perfect matching with high probability. That is, on the same graph it returns the same matching for almost all choices of randomness. As an immediate consequence we also find a pseudo-deterministic NC algorithm for constructing a depth first search (DFS) tree. We introduce a method for computing the union of all min-weight perfect matchings of a weighted graph in RNC and a novel set of weight assignments which in combination enable isolating a unique matching in a graph. We then show a way to use pseudo-deterministic algorithms to reduce the number of random bits used by general randomized algorithms. The main idea is that random bits can be reused by successive invocations of pseudo-deterministic randomized algorithms. We use the technique to show an RNC algorithm for constructing a depth first search (DFS) tree using only O(log^2 n) bits whereas the previous best randomized algorithm used O(log^7 n), and a new sequential randomized algorithm for the set-maxima problem which uses fewer random bits than the previous state of the art. Furthermore, we prove that resolving the decision question NC = RNC, would imply an NC algorithm for finding a bipartite perfect matching and finding a DFS tree in NC. This is not implied by previous randomized NC search algorithms for finding bipartite perfect matching, but is implied by the existence of a pseudo-deterministic NC search algorithm.

Graph spanners are fundamental graph structures with a wide range of applications in distributed networks. We consider a standard synchronous message passing model where in each round O(log n) bits can be transmitted over every edge (the CONGEST model). The state of the art of deterministic distributed spanner constructions suffers from large messages. The only exception is the work of Derbel et al., which computes an optimal-sized (2k-1)-spanner but uses O(n^(1-1/k)) rounds. In this paper, we significantly improve this bound. We present a deterministic distributed algorithm that given an unweighted n-vertex graph G = (V,E) and a parameter k > 2, constructs a (2k-1)-spanner with O(k n^(1+1/k)) edges within O(2^k n^(1/2 - 1/k)) rounds for every even k. For odd k, the number of rounds is O(2^k n^(1/2 - 1/(2k))). For the weighted case, we provide the first deterministic construction of a 3-spanner with O(n^(3/2)) edges that uses O(log n)-size messages and ~O(1) rounds. If the vertices have IDs in [1,Theta(n)], the spanner is computed in only 2 rounds!

We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (nonuniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm and hence a slowdown, our techniques produce algorithms with similar run-time to the original randomized algorithms. The amplification technique applies when there is a quick, probabilistic test of the randomness. In this case, we show how to efficiently find one randomness string for the algorithm that works with very high probability and apply the algorithm only on that randomness (in contrast, standard approaches suggest a number of possible randomness strings and run the algorithm on all of them). The search of good randomness turns out to be a natural stochastic multiarmed bandit problem, which we define (``the biased coin problem'') and analyze. The derandomization technique applies when there is a verifier that can test the randomness of the algorithm while only inspecting a sublinear size sketch of the input (the sketch may be hard to compute; the verifier may be inefficient and is allowed to reject a small portion of the good randomness strings). In this case, we show how to apply Adleman's derandomization (from the proof of $BPP\subseteq P/poly$) more efficiently. We demonstrate the techniques by showing applications for dense max-cut, approximate clique, free games, and going from list decoding to unique decoding for Reed--Muller codes.