Abstract
We introduce a streaming model that uses both catalytic and regular memory. In this model, we show how to exactly compute the frequency moments using a logarithmic number of bits of regular memory and a polynomial number of bits of catalytic memory. More generally, we show how to compute arbitrary polynomials of the item frequencies exactly within the same space bounds. As an application, we obtain catalytic streaming algorithms that exactly compute the number of distinct elements in a stream, count the number of triangles (or any other small subgraph) in a graph whose edges arrive in a stream, and identify heavy hitters.
Our algorithms for frequency moments perform a constant number of passes over the stream, and for polynomial evaluation, we require one more pass than the degree of the polynomial. By relating our catalytic streaming model to the catalytic communication model introduced in [1], we show that catalytic memory is not useful for any one-pass streaming algorithm. For lower bounds on multipass streaming algorithms, the impossibility results of [1] are not strong enough. However, using a different technique, we show that under certain natural restrictions, no catalytic streaming algorithm can compute the second frequency moment in fewer than three passes.
This definition of the restricted class of two-pass algorithms then guides us in the design of a two-pass algorithm for computing the second moment exactly that circumvents these restrictions and breaks the three-pass barrier.
1 Introduction↩︎
Catalytic computation was introduced by Buhrman, Cleve, Koucký, Loff, and Speelman [2] as a theoretical model for understanding the computational power of a “full hard drive” (i.e.,memory which can be used but has to be restored at the end to its original content). Since then, catalytic memory has attracted significant attention and has led to several interesting results in complexity theory. In particular, researchers have explored the power of non-determinism [3] and randomness [4] in this model, as well as non-uniform [5]–[7] and quantum [8] versions of it. Furthermore, interesting space-efficient algorithms using catalytic memory have been developed. Notable examples include the work of Henzinger, Pyne, and Ragavan [9], who improved upon Cook and Mertz’s [10] results by solving the Tree Evaluation Problem using subpolynomial catalytic memory and logarithmic regular memory. Additionally, Chmel et al. [11] provided deterministic solutions for directed connectivity and sequence alignment.
A Catalytic Turing machine has a working tape as of a standard Turing machine and in addition it has a catalytic tape initialized arbitrarily that has to be restored to its original content by the end of the computation.2 The class Catalytic Logspace, denoted by \(\mathsf{CL}\), contains all problems computable by a catalytic Turing machine with a regular tape of size logarithmic in the input length and a polynomial-size catalytic tape. Surprisingly, Buhrman et al. [2] proved that \(\mathsf{TC}^1 \subseteq \mathsf{CL},\)3 showing that catalytic memory can be exploited to solve problems not known to lie in \(\mathsf{L}\).4
Recently, Pyne, Sheffield, and Wang [1] introduced a catalytic communication model, in which Alice and Bob communicate by exchanging messages using a small clean memory and a large catalytic memory. They show that this model is substantially stronger than the standard one as it enables them to solve certain problems such as set equality or inner product over \(GF(2)\), exactly, using only one bit of clean memory.
Streaming algorithms typically have memory which is only logarithmic in the input size (so they cannot store their inputs). They traverse their inputs one by one in a single or multiple passes, maintain some information in their small memory and compute the result. Streaming algorithms have been intensively studied for many problems, starting from the seminal work of Alon, Matias, and Szegedy on the frequency moment [12], for a survey see [13]–[15].
1.1 The Catalytic Streaming model↩︎
In the standard multi-pass streaming model [16] (see also the surveys cited above) a sequence of \(m\) elements \(\boldsymbol{\sigma}=x_1, x_2, \ldots, x_m\) is given sequentially as input. The algorithm is then allowed to make \(p\) passes over \(\sigma\) while maintaining \(s\) (sublinear in \(m\)) bits of memory.
In the catalytic streaming model in addition to the \(s\) bits of regular memory, the algorithm has access to a large catalytic memory of \(c\) bits. Initially, the catalytic memory contains an arbitrary string \(\boldsymbol{\mathcal{T}}\) of \(c\) bits. The algorithm can use this catalytic memory however it wants, with the constraint that it must be restored to contain exactly \(\boldsymbol{\mathcal{T}}\) when the algorithm ends. Its formal definition is as follows.
Definition 1 (Catalytic Streaming).
= -1 A catalytic streaming algorithm \(A\) has a read-only input tape, a read-only stream tape (storing the current stream element), a read-write regular memory, and a read-write catalytic memory. \(A\) gets \(n,m\in \mathbb{N}\) as input, possibly additional inputs on its input tape, and a stream \(\boldsymbol{\sigma}= x_1,x_2,\ldots,x_m\) of elements from a domain \(D\) of size \(n\).5
Let \(p \in \mathbb{N}\). We say that \(A\) makes \(p\) passes if it scans its input stream \(\sigma\) sequentially from \(x_1\) to \(x_m\), \(p\) times. Thus, during each pass, at time step \(j\), the symbol \(x_j\) appears on the stream tape and is processed by \(A\).
Suppose that initially the catalytic memory contains an arbitrary string \(\boldsymbol{\mathcal{T}}\). We say that \(A\) computes the function \(F\) from \(D^m\) to some output range \(\mathcal{O}\) in \(p\) passes if, for every stream \(\boldsymbol{\sigma}= x_1,x_2,\ldots,x_m\), after the \(p\)-th pass of \(A\) on input \(\boldsymbol{\sigma}\):
The value \(F(x_1,x_2,\dots,x_m)\) appears in memory, and
The catalytic memory is restored to contain exactly the string \(\boldsymbol{\mathcal{T}}\).
We say that \(A\) uses \(s\) bits of regular memory and \(c\) bits of catalytic memory if, at every point during its execution, it uses at most \(s\) bits on the regular memory and at most \(c\) bits on the catalytic memory. \(\lozenge\)
Remark 1. Unless stated otherwise, the stream elements in this paper are drawn from \([n]\mathrel{\vcenter{:}}=\{1,2,\ldots,n\}\). Although our complexity measure is in bits, we describe our algorithms in terms of registers storing integers. We perform our computations over a ring of integers modulo some \(q \in \mathbb{N}\), which we denote by \(Z_q\). Whenever additional assumptions on the ring are needed, we will state them explicitly.
Basic catalytic algorithms rely on a symmetric execution—computing forward, copying the output, and uncomputing backward to restore the memory. This often necessitates reading the input in reverse order during the uncomputation phase. In the streaming model, however, data arrives sequentially and can only be accessed in the forward direction. This restriction breaks the standard uncomputation strategy, making the design of catalytic streaming algorithms a significant challenge even with multiple passes.
1.2 Our contributions↩︎
We introduce the catalytic streaming model (1), describe algorithms for classical streaming problems in this model, and prove lower bounds as follows.
Frequency Moments
We show that a straightforward generalization of the catalytic exponentiation algorithm given in [2] can be used to compute \(F_k(\boldsymbol{\sigma})=\sum_{i\in [n]}f_k^k\) exactly, using four passes over \(\sigma\) for any \(k\ge 2\). Here \(f_i \mathrel{\vcenter{:}}= \bigl|\{j \in [m] : x_j = i\}\bigr|\) is the number of occurrences of item \(i\) in \(\sigma\). Computing frequency moments is maybe the most classical and well-studied streaming problem. This result sets a clear separation between the model of catalytic streaming and the standard streaming model, since it’s well-known that any moment other than \(F_1\) cannot be computed exactly in sublinear space using a constant number of passes. Classical results give randomized sublinear algorithms for approximating the frequency moments [12].
Using a different technique, we also show how to compute the second frequency moment exactly in two passes, improving upon the four-pass algorithm for general frequencies.
Polynomial Evaluation
We give a new, simple, catalytic streaming algorithm that evaluates \(P(f_1,\ldots,f_n)\) in \(k+1\) passes where \(P\) is a multivariate polynomial of degree \(k\). We can evaluate this polynomial over any ring \(Z_q\) (the integers modulo \(q\)) as long as this ring contains multiplicative inverses to \(2,3,\ldots,k\). We can do so by using \(O(1)\) regular registers and \(n\) catalytic registers of \(O(\log q)\) bits each. Since the evaluation of \(P(f_1,f_2,\ldots,f_n)\) over the integers is \(O(m^k)\),6, by choosing \(q\) of this magnitude, we in fact compute \(P(f_1,\ldots,f_n)\) over the integers.
Lower Bounds
We were intrigued by the question of whether we can compute \(F_2\) in the catalytic streaming model in less than three passes. Using results in the recently introduced catalytic communication complexity model [1], and a well-known reduction from the Set-Disjointness problem in communication complexity to streaming algorithms for frequency moments, we are able to easily show that one cannot compute \(F_k\) for any \(k\ge 2\) using a one-pass catalytic streaming algorithm and only sublinear regular memory. However, in the catalytic arena this approach fails for two passes since, as we show, there is a catalytic communication protocol with small regular memory for Set-Disjointness in three rounds.
This led us to characterize a class of two-pass catalytic streaming algorithms for which computing the second frequency moment using sublinear regular memory is impossible. The understanding of the limitations of this class enabled us to develop a two-pass algorithm for \(F_2\) that avoids them and overcomes the three-pass barrier. We believe that our restricted family is still of interest as a natural extension of this family to algorithms with more than two passes includes all algorithms presented here, the only exception is the 2-pass algorithm we mentioned above.
Applications: \(F_0\), Counting Subgraphs, and Heavy Hitters
Finally, we apply our algorithms for moments and polynomial evaluation to obtain space efficient catalytic streaming algorithms for several other well-studied streaming problems. In particular, we get a four-pass algorithm to compute the exact number of distinct items in a stream. We show how to count triangles (or any other small subgraph) in a multigraph whose edges arrive as a stream. We also show that we can compute the exact set of \(F_k\) heavy hitters in \(O(\log n)\) passes.7
1.3 Roadmap↩︎
We follow the notation of 1. 2 shows how to compute moments in four passes. 3 gives our polynomial evaluation algorithm. We prove lower bounds in 4. 6 shows how to apply our algorithm to compute the number of distinct elements in a stream (so called \(F_0\)), count small subgraphs in a graph stream, and compute heavy hitters.
2 Computing Exact Moments Using 4 Passes and Logarithmic Space↩︎
In this section, we study the classic problem of computing the \(k\)-th frequency moment of a stream and prove the following theorem.
Theorem 2. Let \(\boldsymbol{\sigma}=x_1,x_2,\dots,x_m\) be a stream over \([n]\), and let \(f_1,f_2,\dots,f_n\) denote the corresponding frequencies. Then there exists a catalytic streaming algorithm that evaluates \(F_k(\boldsymbol{\sigma}) \mathrel{\vcenter{:}}= \sum_{i=1}^n f_i^k\) in \(4\) passes, using \(O(1)\) regular registers and \(n \cdot (k+1)\) catalytic registers. This algorithm works over any ring \(Z_q\). To compute \(F_k\) over the integers it is enough to take \(q = O(m^k)\).
A key lemma in the proof of the above theorem is a result proved in [2] called the powering lemma. We formulated it here in a suitable way for our task.
Lemma 1 ([2]). Let \(k \in \mathbb{N}\). Let \(r\) and \(r_1,r_2,\ldots,r_k\) be catalytic registers, initialized with arbitrary values \(\tau\), \(\tau_1, \tau_2, \ldots, \tau_k\) respectively, and let \(r_o\) be a regular register. There are programs \(I_1\), \(I_2\), and \(I_3\) that only use the registers \(\{r_i\}_{i \in [k]}\) and \(r_o\) such that for every input \(f \in [n]\) the program \[I_1,\; r\leftarrow r+f,\; I_2,\; r\leftarrow r-f,\; I_3\] computes \(r_o \leftarrow f^k.\) Moreover, the values of the other registers are as follows \[r=\tau, \quad \text{and for every i\in [k],} \quad r_i=\tau_i-(\tau+f)^{k-i}.\] They can be restored by executing the program in reverse.
For convenience, we give in 8 the algorithm used in [2] to prove 1.
Proof of 2. Let \(r_1,r_2,\ldots,r_n\) and \(\{r_{i,j}\}_{i \in [n],\, j \in [k]}\) be catalytic registers, and let \(r_o\) be a regular output register. Given 1, computing \(F_k(\boldsymbol{\sigma})\) is straightforward. We simply run the algorithm of 1 in parallel for each item \(i \in [n]\), using the frequency \(f_i\) in place of the value \(f\) appearing in that lemma.
All of these parallel executions share the same output register \(r_o\), so their contributions accumulate to \(\sum_{i=1}^n f_i^k = F_k(\boldsymbol{\sigma}).\) On the other hand, each execution uses its own catalytic registers, i.e. for the computation corresponding to \(f_i\), we use \(r_i\) in the role of the register \(r\), and \(r_{i,1},r_{i,2},\ldots,r_{i,k}\) in the roles of the registers \(r_1,r_2,\ldots,r_k\). Denote by \(\tau_i\) the initial value of \(r_i\) and \(\tau_{i,j}\) the initial value of \(r_{i,j}\).
The resulting algorithm is given in 1. There, for \(t\in \{1,2,3\}\), \(I_t^i\) denotes the program \(I_t\) applied to the registers dedicated to \(f_i\). Observe that before the two additional passes mentioned in line [line:f95k32comp32two32more32pass32line] the values of the registers \(r_1,r_2,\ldots,r_n\) are restored, but each register \(r_{i,j}\) still contains \(\tau_{i,j} - (\tau_i + f_i)^{k-j}\), thus two more passes are needed. ◻
Polynomial Evaluation by Powering
Alekseev et al.[17] show how to evaluate a multivariate polynomial of degree \(k\) over \(n\) variables by representing it as a linear combination of powers (\(\le k\)) of linear functions of the variables (so called Waring representation [18]). However, due to the large number of coefficients required for this representation, their program is designed for a specific polynomial. It does not receive a representation of the polynomial as input. Their implementation requires catalytic memory of size exponential in \(k\). Similarly to our catalytic streaming implementation of the computation of \(F_k\), we can implement this polynomial evaluation scheme in \(4\) passes in our model. We will get a streaming algorithm for a specific multivariate polynomial \(P\) that, given a stream, evaluates \(P(f_1,f_2,\ldots,f_n)\) (it cannot get a polynomial as input). Furthermore, it requires exponential in \(k\) catalytic memory.
3 Polynomial of Degree \(k\) Using \(k+1\) Passes↩︎
In this section we show how to evaluate polynomials over the frequencies of items in a stream. We assume we get the polynomial’s coefficients in our input tape, like we get \(m\) and \(n\). The following is this section’s main result.
Theorem 3. Let \(\boldsymbol{\sigma}=x_1,x_2,\dots,x_m\) be a stream over \([n]\), and let \(f_1,f_2,\dots,f_n\) denote the corresponding frequencies. Then there exists a catalytic streaming algorithm that for every multivariate polynomial \(P \in \mathbb{F}[y_1,y_2,\dots,y_n]\) of total degree \(k\),8 evaluates \(P(f_1,f_2,\dots,f_n)\) in \(k+1\) passes. This algorithm uses \(O(1)\) regular registers and \(n\) catalytic registers. It works over any ring \(Z_q\) that contains inverses to \(2,3,\dots,k\), to evaluate \(P(f_1,f_2,\ldots,f_n)\) over the integers it is enough to take \(q = O(\alpha \cdot m^k)\) where \(\alpha \in \mathbb{Z}\) is the largest coefficient of any monomial.
3.1 Warm Up: Degree 2 Polynomials↩︎
To warm up, we first show how to evaluate degree \(2\) polynomials.
Let \(\boldsymbol{\sigma}= x_1, x_2, \dots, x_m\) be a stream of elements from the set \([n]\) with frequencies \(f_1, f_2,\ldots f_n\) and let \(P \in \mathbb{F}[y_1,y_2,\dots,y_n]\) be a multivariate polynomial of degree \(2\). Let \[P(f_1, f_2,\ldots, f_n) = \sum_{1\leq i\leq j \leq n} a_{i,j}f_i f_j \, ,\] for some \(\{a_{i,j}\} \subseteq \mathbb{F}\), i.e. we assume \(P\) only contains degree \(2\) monomials. Solving the problem with respect to such polynomials is easily generalized, since adding degree-1 monomials and constants is trivial using \(O(\log m)\) bits of regular memory.
We allocate registers \(r_1, r_2,\ldots, r_n\) in the catalytic memory, each of size \(2\log m\) bits. We denote the initial values inside these registers by \(\tau_1, \tau_2, \ldots, \tau_n\). In addition, we allocate \(2 \log m\) bits of regular memory as our output. We give this register a name, \(r_o\), and think of it as the output register. The algorithm goes as follows.
Set \(r_o \leftarrow P(r_1, r_2,\ldots, r_n)\).
During the first pass of the stream, for every item \(x_j\) received, increment the register \(r_{x_j}\) by one. After this pass, \(r_i\) holds \(\tau_i + f_i\).
Set \(r_o \leftarrow r_o - 2 P(r_1, \ldots, r_n)\).
During the second pass, we repeat Step [item:d232poly32alg32first32pass]. At the end of this pass, \(r_i\) holds \(\tau_i + 2f_i\).
Set \(r_o \leftarrow r_o + P(r_1, \ldots, r_n)\).
During the third pass, we reverse our previous operations, i.e. for every \(x_j\) received, we subtract \(2\) from its corresponding register.
Return \(r_o /2\).
To establish correctness, we follow the contents of \(r_o\) along the execution of these steps. We use the following definitions. \[\begin{align} J &= \sum_{1\leq i\leq j \leq n} a_{ij} \tau_i \tau_j &&(\text{the junk term})\, , \\ C &= \sum_{1\leq i\leq j \leq n} a_{ij} (\tau_i f_j + f_i \tau_j) &&(\text{the cross term}) \, , \text{and} \\ V &= \sum_{1\leq i\leq j \leq n} a_{ij} f_i f_j &&(\text{the target term}). \end{align}\] We assume that the regular memory is initialized to \(\boldsymbol{0} =0^s\), hence initially \(r_o = 0\). Following Step [item:d232poly32alg32first32set], \[r_o = P(\tau_1, \tau_2, \ldots, \tau_n) = \sum_{1\leq i\leq j \leq n} a_{i,j}\tau_i \tau_j = J \, .\] Following Step [item:d232poly32alg32second32set], \[\begin{align} r_o &= J - 2P(r_1, r_2, \ldots, r_n )= J - 2P(\tau_1 + f_1, \tau_2 + f_2, \ldots, \tau_n + f_n ) \\ & = J - 2\sum_{1\leq i\leq j \leq n} a_{i,j}(\tau_i + f_i)( \tau_j + f_j)=J -2(J+C+V) \, . \end{align}\] Following Step [item:d232poly32alg32third32set], \[\begin{align} r_o & = J - 2(J+C+V) +\sum_{1\leq i\leq j \leq n} a_{i,j}(\tau_i + 2f_i)( \tau_j + 2f_j)\\ & = J-2(J+C+V) + (J+ 2C+4V) = 2V \end{align}\] It follows that when Step [item:d232poly32alg32third32set] ends, \(r_o = 2V = 2P(f_1,f_2,\ldots,f_n)\). Hence \(r_o/2\) is exactly \(P(f_1, f_2,\ldots, f_n)\), which is the desired output.
3.2 Proof of 3↩︎
In order to prove the theorem, we first handle the case of evaluating a single monomial.
Lemma 2. Let \(\boldsymbol{\sigma}=x_1,x_2,\dots,x_m\) be a stream over \([n]\), and let \(f_1,f_2,\dots,f_n\) denote the corresponding frequencies. There exists a catalytic streaming algorithm that given any monomial \(M \in \mathbb{F}[y_1,y_2,\dots,y_n]\) of total degree \(k\), evaluates \(M(f_1,f_2,\ldots,f_n)\) in \(k+1\) passes. The algorithm uses \(O(1)\) regular registers and \(n\) catalytic registers. This algorithm works over any ring \(Z_q\) that contains inverses to \(2,3,\dots,k\). To evaluate \(M(f_1, \ldots, f_n)\) over the integers, it is enough to take \(q = O(m^k)\).
Proof. Let \(r_1, r_2,\ldots, r_n\) be the catalytic registers, where each \(r_i\) initially contains the value \(\tau_i\), and let \(r_o\) be the regular register. Evaluating \(M\) on \((f_1,f_2,\ldots,f_n)\) goes as follows ([alg:monomial]):
Observe, that for every \(1 \leq i \leq k\) and \(j \in [n]\), after the \(i\)-th pass, the value in register \(r_j\) is \(\tau_j + i \cdot f_j\). Thus, by summing the values added to \(r_o\) in every pass, we get \[\label{stirling} \begin{align} r_o &= (-1)^k M(\tau_1, \ldots, \tau_n) + \sum_{i=1}^k (-1)^{k-i} \binom{k}{i} M(\tau_1 + if_1, \ldots, \tau_n + i f_n) \\ &=\sum_{i=0}^k (-1)^{k-i} \binom{k}{i} M(\tau_1 + i f_1, \ldots, \tau_n + if_n) \, . \end{align}\tag{1}\] Since the exact degree of \(M\) is \(k\), we can choose \(\{i_\alpha\}_{\alpha \in [k]} \subseteq [n]\) (these indices are not necessary distinct) such that \(M(y_1,y_2,\ldots,y_n) = \prod_{\alpha = 1}^k y_{i_{\alpha}}\). Therefore, by expanding \(M\) in Equation 1 in that way we get \[r_o = \sum_{i=0}^k (-1)^{k-i} \binom{k}{i} \prod_{\alpha=1}^k (\tau_{i_\alpha} + i f_{i_\alpha}) = \sum_{i=0}^k (-1)^{k-i} \binom{k}{i}\sum_{\ell = 0}^k i^{k-\ell}\text{Cross}_\ell(\boldsymbol{\mathcal{T}},\boldsymbol{f})\] where \(\boldsymbol{\mathcal{T}}=\tau_1,\tau_2,\ldots,\tau_n\), \(\boldsymbol{f}=f_1, f_2,\ldots,f_n\), and \[\text{Cross}_\ell(\boldsymbol{\mathcal{T}}, \mathbf{f}) = \sum_{\substack{\beta =\{\beta_1, \ldots \beta_\ell\} \subseteq [k] \\ \gamma_1, \ldots, \gamma_{k-\ell = [k]\setminus \beta} }} \tau_{\beta_1}\cdots\tau_{\beta_\ell}\cdot f_{\gamma_1}\cdots f_{\gamma_{k-\ell}}\] where the sum is over all partitions of \(\{i_\alpha\}_{\alpha \in [k]}\) into two sets, \(\{\beta_j\}_{j \in [\ell]}\) and \(\{\gamma_t\}_{t \in [k -\ell]}\).
By changing the order of summation we get that
\[\label{eq:reorder} r_o = \sum_{\ell = 0}^k\text{Cross}_\ell(\boldsymbol{\mathcal{T}}, \boldsymbol{f})\sum_{i=0}^k (-1)^{k-i} \binom{k}{i} i^{k-\ell} \, .\tag{2}\]
Recall the definition of Stirling numbers of the second kind: \[S(n, k) = \frac{1}{k!} \sum_{i=0}^k (-1)^{k-i} \binom{k}{i} i^n \, .\] A key property is that \(S(n, k) = 0\) whenever \(n < k\), and \(S(k, k) = 1\). Using these identities to rewrite Equation 2 we get \[r_o = \sum_{\ell=0}^k \text{Cross}_{\ell}(\boldsymbol{\mathcal{T}},\boldsymbol{f}) \cdot k!\cdot S(k-\ell,k) = k! \cdot \text{Cross}_0(\boldsymbol{\mathcal{T}},\boldsymbol{f}) = k! \cdot \prod_{\alpha=1}^k f_{i_\alpha} = k! \cdot M(f_1,f_2,\ldots,f_n) \, .\] Therefore \(\frac{r_o}{k!} = M(f_1,f_2,\ldots,f_n)\) and the returned value is correct. ◻
We are now ready to prove 3.
Proof of 3. Denote the set of monomials with nonzero coefficient in \(P(\boldsymbol{y})\) by \(\text{Mon}(P)\) and let \(a_M \in Z_q\) be the coefficient of the monomial \(M(\boldsymbol{y})\) in \(P(\boldsymbol{y})\). Moreover, let \(r_1,r_2,\ldots,r_n\) be catalytic registers and \(r_o\) a regular register. Algorithm \(3\) shows how to evaluate \(P\) on \(f_1,f_2,\ldots,f_n\).
The idea is to evaluate in parallel all monomials of \(P\) using the same set of registers. Since summation is commutative different monomials do not interfere with one another. The correctness of 3 essentially follows as in the proof of 2. ◻
3.3 Polynomial Evaluation over a Field Using Primitives Roots of Unity↩︎
In Cook and Mertz [10], the authors show how to evaluate any multivariate polynomial \(P(y_1,\ldots,y_n)\) of degree \(k\) over a finite field \(\mathbb{F}_q\) under the assumption that \(k +1 < q\). Their algorithm requires a primitive root of unity of order \(e \ge k+1\). Note that the smallest \(e\) for which such a root exists is the smallest divisor of \(q-1\) which is larger than \(k\). Their algorithm reads each input variable \(e\) times, and uses \(\log q\) bits of regular memory together with \(n\log q\) bits of catalytic memory. As we did for \(F_k\) we can modify this algorithm to a catalytic streaming algorithm that evaluates \(P(f_1,\ldots, f_n)\) in \(e\ge k+1\) passes over the stream. To evaluate \(P(f_1,\ldots, f_n)\) over the integers we have to use a field of characteristic \(\Omega(m^k)\). Note that it is not clear how to find a field of characteristic \(O(m^k)\) that contains a primitive root of unity of order \(k+1\). Hence this algorithm may require more than \(k+1\) passes. The algorithm presented in this section, which is arguably simpler, always evaluates \(P\) in exactly \(k+1\) passes and requires only milder assumptions on the underlying ring.
Goldreich [19] simplified the Cook-Mertz procedure. He observed that Cook and Mertz in fact interpolate the univariate polynomial \(f(x)=P(x\cdot \tau_1+f_1,\ldots,x\cdot\tau_n + f_n)\) at powers of a primitive root of unity, but one can also interpolate at other points. (Since we only need to extract \(f(0)\) at the end.) This removes the need for a primitive root of unity, however, when we attempt to implement it in the catalytic streaming model it would require twice as many passes. This happens since to evaluate at arbitrary values of \(x\) requires two passes per value (we need to subtract away the frequencies \(f_i\), multiply the “noise” by a different value of \(x\) and then add back the frequencies). But powers of a primitive root of unity allow to get away with one pass per value of \(x\).
Remark 4. Using this method we get a \(3\)-pass algorithm computing \(F_2\) using \(O(\log m)\) bits of regular memory.
Remark 5. In this section we have evaluated polynomials over the frequencies of the elements in the stream. Note that this can be easily generalized to evaluating \(\ell\)-variate polynomials over every set of functions of the steam elements \(\{g_1(\boldsymbol{\sigma}), \ldots, g_\ell(\boldsymbol{\sigma})\}\), such that we can compute \(r_i\leftarrow g_i(\boldsymbol{\sigma})\) for every \(i\) in one pass and within our space bounds.
4 Lower Bounds↩︎
Standard streaming lower bounds are typically proved via reductions from communication complexity. In this section, we apply this approach to the catalytic setting. Specifically, in 4.1, we leverage the recently introduced framework of catalytic communication complexity [1] to establish lower bounds for the catalytic streaming model.
However, catalytic communication results cannot establish lower bounds for multi-pass catalytic streaming. As we show below, this is because a modified inner product protocol from [1] actually solves Set-Disjointness. Using alternative techniques, we instead prove that our 3-pass algorithm for \(F_2\) is pass-optimal among a family of “natural” algorithms.
4.1 Implication of Catalytic Communication↩︎
In this section, we use results from [1] to establish a lower bound for one-pass catalytic streaming algorithms. We then adapt their method for computing inner product over \(\text{GF}_2\) to obtain a catalytic communication protocol for Set-Disjointness in three rounds of communication that uses only \(O(\log n)\) bits of regular memory. This latter result shows that the typical approach to prove streaming lower bounds via reductions from Set-Disjointness cannot yield lower bounds in our new model for algorithms with more than one pass.
Briefly, the communication model of [1] is as follows (for the exact definition, see [1]). Alice, holding an input \(\boldsymbol{x}\in \{0,1\}^n\), and Bob, holding an input \(\boldsymbol{y}\in \{0,1\}^n\) communicate to compute a function \(f(\boldsymbol{x},\boldsymbol{y})\). They exchange messages on \(c\) bits of catalytic memory (arbitrarily initialized) and \(s\) bits of regular memory (initialized to \(\boldsymbol{0}\)), note that the message size in every round is fixed. In their protocol the last player sending a message should send/restore the original contents of the catalytic memory. The player that gets this message should output \(f(\boldsymbol{x},\boldsymbol{y})\).
A lower bound on the amount of regular memory required by a catalytic streaming algorithm for computing the frequency moment \(F_k\) follows from the following three facts: (1) We observe that the standard reduction from the Set-Disjointness problem in communication complexity to the streaming problem of computing the frequency moment also works in the catalytic setting. The Set-Disjointness problem in communication complexity asks how many bits of communication Alice, holding \(x\in \{0,1\}^n\), and Bob, holding \(y\in \{0,1\}^n\), have to exchange in order to compute the function \[\text{Disj}_{n}(x,y) = \begin{cases} 1\forall i \in [n]: x_i =1 \Rightarrow y_i = 0 \\ 0\text{otherwise} \end{cases} \; .\]
Specifically, our lower bound relies on three facts: (1) A \(p\)-pass catalytic streaming algorithm for a frequency moment \(F_k\) yields a \(2p\)-round catalytic communication protocol for Set-Disjointness (\(\text{Disj}_n\)) with the same catalytic memory and \(O(\log n)\) regular memory (a standard reduction provided in 9). (2) Any catalytic communication protocol with fewer than three rounds can be simulated without catalytic memory at a similar regular communication cost [1]. (3) Computing \(\text{Disj}_n\) strictly requires \(\Omega(n)\) standard communication [12], [20], [21]. Combining these, we immediately obtain the following:
Proposition 6. There is no one-pass catalytic streaming algorithm for frequency moments with sublinear regular memory.
Proof. Assume there exists a 1-pass catalytic streaming algorithm with sublinear regular memory. By Fact (1), this yields a 2-round catalytic protocol for \(\text{Disj}_n\) with sublinear regular communication. By Fact (2), this implies a standard 2-round protocol for \(\text{Disj}_n\) with sublinear communication, which contradicts Fact (3). ◻
While similar reductions can rule out other one-pass catalytic streaming algorithms, this approach fails for multiple passes (which induce protocols with more than two rounds). This barrier is inherent: in 10, we show that a simple modification of the \(\text{GF}_2\) inner-product protocol from [1] yields a 3-round catalytic protocol for \(\text{Disj}_n\). Thus, multi-pass lower bounds cannot be obtained via this route.
4.2 A Restricted Lower Bound for Moments in Two Passes↩︎
In this section, we characterize a set of properties of catalytic streaming algorithms, which seem natural, such that every algorithm that have these properties cannot calculate \(F_k\), for \(k \ge 2\), in two passes.
Assumption 1 (Restricted two-pass Catalytic Streaming Algorithm). We denote by \(C\) the catalytic memory, \(r_i\) is a catalytic register associated with item \(i\), and \(M\) is the regular memory. A restricted two-pass catalytic streaming algorithm obeys the following structure:
Initial Update (Before we see the stream): \(M \leftarrow M + W_s(\boldsymbol{C})\), where \(W_s\) is some function of the entire catalytic memory \(\boldsymbol{C}\). It returns a vector that we use in order to update the clean memory \(M\) additively.
Pass 1 (Forward): For each item \(x_j\) in the stream, if \(x_j=i\) then we set \(r_{i} \leftarrow U_{i}(r_i)\), and then \(M \leftarrow M + P_i(r_{i})\). Here \(U_i\) is an item-specific bijection \(U_i : \Sigma \rightarrow \Sigma\). We require that \(r_i \not= r_j\) for \(i\not= j\). \(P_i\) is also an item specific function that updates \(M\) additively after the change to \(r_i\).
Intermediate Update (End of Pass 1): \(M \leftarrow M + W_m(\boldsymbol{C})\). \(W_m\) is a function of the entire catalytic memory \(\boldsymbol{C}\) that we use to update the clean memory between the two passes.
Pass 2 (Backward): To restore the catalytic memory, if \(x_j=i\), we set \(r_{i} \leftarrow U_i^{-1}(r_{i})\), then \(M \leftarrow M + Q_i(r_{i})\). \(Q_i\) is an item specific function that updates \(M\) additively after the update to \(r_i\).
Final Update (End of Pass 2): \(M \leftarrow M + W_e(\boldsymbol{C})\). \(W_e\) is a function of the entire catalytic memory \(\boldsymbol{C}\) that we use to update the clean memory between following the two passes.
Remark 7. 1 can be generalized to apply to \(p\)-pass streaming algorithms. If \(U_{i,j}\) is the function applied to \(r_i\) in pass \(j\) when we see item \(i\), then we should have \(U_{i,p}^\ell(\cdots (U_{i,2}^\ell(U_{i,1}^\ell(\tau_i))))=\tau_i\) for every \(\ell \leq m\). Further generalizations of this assumption allocate a set of registers to every element instead of only one register and allow to apply some function \(g_{i,j}\) to each \(r_i\) after pass \(j\) such that \(g_{i,p}(U_{i,p}^\ell(\cdots (g_{i,2}(U_{i,2}^\ell (g_{i,1}(U_{i,1}^\ell(g_{i,0}(\tau_i))))))))=\tau_i\) for every \(\ell \leq m\). All our algorithms obey this generalized assumption.
Now we show that no program that satisfies 1 can compute \(F_2\) exactly using only two passes. The proof for \(F_k\), \(k> 2\) is analogous. The intuition is that the catalytic tape behaves as a one time pad with respect to the items frequencies, so, in one pass it is impossible to extract information about them from the catalytic memory. Formally, we prove this by analyzing the discrete derivative of the output as a function of \(f_i\).
4.2.1 The Discrete Derivative Argument↩︎
Let \(\boldsymbol{C} = \boldsymbol{\mathcal{T}}\) and in particular let \(r_i = \tau_i\) initially for all \(i\in [n]\). For every \(i \in [n]\) and \(j \in [f_i]\) we denote by \(U_i^j\) the bijective function \(U_i\) applied \(j\) times. We analyze the state of \(M\) at the end of the algorithm, denoted by \(M_e(\boldsymbol{\mathcal{T}},\boldsymbol{f})\). \[M_e(\boldsymbol{\mathcal{T}},\boldsymbol{f}) = W_s(\boldsymbol{\mathcal{T}})+ \sum_{i=1}^n \sum_{j=1}^{f_i} P_i\big(U_i^j(\tau_i)\big) + W_m\big(\boldsymbol{U^{f}(\boldsymbol{\mathcal{T}})}\big) + \sum_{i=1}^n\sum_{j=0}^{f_i-1} Q_i\big(U_i^j(\tau_i)\big) + W_e(\boldsymbol{\mathcal{T}})\]
where \(\boldsymbol{U^{f}(\boldsymbol{\mathcal{T}})} = \left(U^{f_1}_1(\tau_1),\ldots, U_n^{f_n}(\tau_n)\right)\). The second term from the right comes from the fact that in the second pass (see Item [item:232pass32lb32assump32backward32pass]) after seeing item \(i\) for the \(j\)-th time, the value of the register \(r_i\) is \(U_i^{f_i-j}(\tau_i)\).
For simplicity, for the rest of the proof we denote \[E_i(\tau_i,f_i) = \sum_{j=1}^{f_i} P_i\big(U_i^j(\tau_i)\big) + \sum_{j=0}^{f_i-1} Q_i\big(U_i^j(\tau_i)\big)\]
Theorem 8. There is no algorithm satisfying 1 for which \(M_e(\boldsymbol{\mathcal{T}},\boldsymbol{f}) = \sum_{i=1}^n f_i^2\).9
Proof. Assume, by way of contradiction, that for every initial state \(\boldsymbol{\mathcal{T}}\) of the catalytic tape and for every set of \(f_i\)’s we have an algorithm such that \[\label{master} M_e(\boldsymbol{\mathcal{T}},\boldsymbol{f}) = \sum_{i=1}^n E_i(\tau_i,f_i) + W_s(\boldsymbol{\mathcal{T}})+ W_m\big(\boldsymbol{U^{f}(\boldsymbol{\mathcal{T}})}\big) + W_e(\boldsymbol{\mathcal{T}})= \sum_{i=1}^n f_i^2\tag{3}\]
We take the discrete partial derivative of \(M_e\) with respect to \(f_i\), which in our case is defined as \(\Delta_{f_i}(g) \mathrel{\vcenter{:}}= g(f_1,\ldots,f_i + 1, \ldots,f_n) - g(\boldsymbol{f})\), of both sides of Equation 3 . On the right hand side we get:
\[\Delta_{f_i} \left( \sum_{j=1}^n f_j^2 \right) = (f_i + 1)^2 - f_i^2 = 2f_i + 1 \, .\]
For the left hand side first observe that \[\Delta_{f_i} \left(\sum_{i=1}^n E_i(\tau_i,f_i)\right) = P_i\big(U_i^{f_i+1}(\tau_i) \big) + Q_i\big(U_i^{f_i}(\tau_i) \big) = P_i\big(U_i(y) \big) + Q_i\big(y\big) \;,\] where \(y = U_i^{f_i}(\tau_i)\) is the state of register \(r_i\) at the end of the forward pass. Note that \(\Delta_{f_i}\big(W_s(\boldsymbol{\mathcal{T}})\big)=\Delta_{f_i}\big(W_e(\boldsymbol{\mathcal{T}})\big) = 0\). Overall, we get
\[\begin{align} \Delta_{f_i}\big(&M_e(\boldsymbol{\mathcal{T}},\boldsymbol{f})\big) = P_i\big(U_i(y) \big) + Q_i\big(y\big) + \\ &W_m\left(U^{f_1}_1(\tau_1),\ldots,\boldsymbol{U_i(y)},\ldots, U_n^{f_n}(\tau_n)\right) - W_m\left(U^{f_1}_1(\tau_1),\ldots,\boldsymbol{y},\ldots, U_n^{f_n}(\tau_n)\right) \;. \end{align}\] We argue that \(\Delta_{f_i}\big(M_e(\boldsymbol{\mathcal{T}},\boldsymbol{f})\big) = 2f_i + 1\) is not possib which would give a contradiction.
We fix \(f_j\) and \(\tau_j\) for \(j \neq i\), and think of \(\Delta_{f_i}\big(M_e(\boldsymbol{\mathcal{T}},\boldsymbol{f})\big)\) as a function of \(y = U_i^{f_i}(\tau_i)\), which we denote by \(H_i(y)\). Note that the dependency of \(\Delta_{f_i}\big(M_e(\boldsymbol{\mathcal{T}},\boldsymbol{f})\big)\) on \(f_i\) is only through \(y = U_i^{f_i}(\tau_i)\). Let \(\tau_i\) and \(f_i\) be random variables, each distributed uniformly over its set of possible values. The intuition is as follows. Since \(\tau_i\) is a uniform random variable and \(U_i\) is a bijection it follows that \(y\) is also distributed uniformly at random and independent of \(f_i\). Therefore it cannot hold any information about \(f_i\). This is formalized in the following claim.
Claim 9. Let \(f_i\) and \(\tau_i\) be independent random variables over the uniform distribution and let \(I(\cdot,\cdot)\) be the mutual information function. Then \(I(f_i,y) = 0\).
Proof. By 1, \(U_i\) is a bijection, thus it holds that \(\forall f_i, \; U_i^{f_i}: \Sigma\rightarrow \Sigma\) is also a bijection. Therefore we have that \(y\) is a random variable that is distributed uniformly over \(\Sigma\). In particularly he have \[\text{Pr}_{\tau_i\sim U_{\Sigma}}\left[y = \sigma \mid f_i = k\right] = \text{Pr}_{\tau_i\sim U_{\Sigma}}\left[U^k(\tau_i)=\sigma\right]= \frac{1}{|\Sigma|}\] Where the last equality follows from the fact that \(U_i^k(\cdot)\) is a bijection. Since the conditional probability of \(y\) is completely independent of the choice of \(f_i\) we have that \(I(f_i,y) = 0\). ◻
Since \(H_i(y)\) is a deterministic function of \(y\) we have that \(I(f_i,H_i(y))\le I(f_i,y) = 0\) by the data processing inequality and 9. We have assumed the algorithm always computes \(F_2\) exactly, therefore \(H_i(y) = 2f_i +1\), which implies that \(I\big(f_i,H(y)\big) = 1\) in contradiction. ◻
The last proof works with small changes for every \(F_k\) with \(k \geq 2\).
In 11 we show where the proof fails for \(3\) passes.
5 Computing \(F_2\) in two passes↩︎
Having identified the limitations of the family of algorithms considered in section 4.2 we took a different approach and construct in this section a two-pass algorithm with the following properties.
Theorem 10 (Two-pass catalytic computation of \(F_2\)). Let \(\boldsymbol{\sigma}=x_1,\ldots,x_m\) be a stream over \([n]\), and let \(f_i=\left|\{t\in[m]:x_t=i\}\right|\) be the frequency of item \(i\). There is a two-pass catalytic streaming algorithm that computes \(F_2(\boldsymbol{\sigma})=\sum_{i=1}^n f_i^2\) exactly using \(O(1)\) regular registers and \(O(nm)\) catalytic registers over the ring \(Z_q\) with \(q = \Theta(m^2)\), and hence uses \(O(nm\log m)\) bits of catalytic memory and \(O(\log(nm))\) bits of regular memory.
Proof. For simplicity, we assume \(m\) is a power of \(2\); the algorithm easily generalizes to any value of \(m\).
We first describe the algorithm. Consider the complete binary tree \(T\) with \(m\) leaves, where the \(t\)-th leaf from the left is identified with the stream element \(x_t\) at position \(t\). For every internal node \(v\) of \(T\), and every item \(i\in[n]\), we allocate one catalytic register \(r_{v,i} \in Z_q\). We denote the arbitrary initial value of \(r_{v,i}\) by \(\tau_{v,i}\). The algorithm also maintains one regular output register \(r_o\), initialized to \(0\).
The idea is that each internal node \(v\) counts the number of pairs of equal stream elements \(x_s=x_t=i\), for \(s < t\), such that \(x_s\) is in the left subtree of \(v\) and \(x_t\) is in the right subtree of \(v\). Each such pair of equal stream elements has a unique lowest common ancestor in \(T\). Summing these contributions over all internal nodes counts every pair of equal stream elements exactly once.
The algorithm proceeds as follows.
Pass 1 (Forward): When \(x_t = i\) arrives, we scan all ancestors \(v\) of the leaf corresponding to \(t\), and for each we do the following:
If we arrived from the left child of \(v\), we set \(r_{v,i}\gets r_{v,i}+1\).
If we arrived from the right child of \(v\), we set \(r_o\gets r_o+r_{v,i}\).
Pass 2 (Backward): Again, when \(x_t = i\) arrives, we scan all ancestors \(v\) of the leaf corresponding to \(t\), and for each we do the following:
If we arrived from the left child of \(v\), we set \(r_{v,i}\gets r_{v,i}-1\).
If we arrived from the right child of \(v\), we set \(r_o\gets r_o-r_{v,i}\).
At the end of the second pass, the algorithm outputs \(m+2r_o \pmod q\). We give pseudo-code in 4.
We solve the case where \(m\) is not a power of \(2\) by adding “dummy” leaves to the tree up to the next power of \(2\).
We now prove correctness. Fix an internal node \(v\) with a left child \(v_\ell\) and a right child \(v_r\). Let \(f_i(v_\ell)\) and \(f_i(v_r)\) be the number of occurrences of item \(i\) in the subtrees of \(v_\ell\) and \(v_r\), respectively. Because the stream is processed chronologically from left to right, all leaves in \(v_\ell\) are processed before any leaves in \(v_r\).
Assume first that the initial state is \(\tau_{v,i}=0\) for all catalytic registers \(r_{v,i}\). During Pass 1, when we process the left subtree \(v_\ell\), we increment \(r_{v,i}\) exactly \(f_i(v_\ell)\) times. Thus, when we begin processing the right subtree \(v_r\), the register contains \(r_{v,i} = f_i(v_\ell)\). Each time we encounter \(i\) in \(v_r\) (which happens \(f_i(v_r)\) times), we add \(r_{v,i}\) to \(r_o\). Therefore, while processing the stream underneath \(v\), we add exactly \(f_i(v_\ell)f_i(v_r)\) to \(r_o\). This is exactly the number of pairs of \(i\)’s where one occurs in \(v_\ell\) and the other in \(v_r\). Since each pair of equal stream elements \(x_s=x_t=i\) (with \(s < t\)) has a unique lowest common ancestor, it contributes exactly once to the sum in \(r_o\).
Since this holds for every item \(i\in [n]\), at the end of the first pass we get: \[r_o = \sum_{i=1}^n \binom{f_i}{2}.\]
The algorithm outputs \[m+2r_o = \sum_{i=1}^n f_i + 2\sum_{i=1}^n \frac{f_i^2-f_i}{2} = \sum_{i=1}^nf_i^2 = F_2(\boldsymbol{\sigma}).\]
Because \(q = \Theta(m^2)\) is chosen such that \(q>m^2\) and \(F_2(\boldsymbol{\sigma})\le m^2\), this equality over \(Z_q\) determines the exact integer value of \(F_2(\boldsymbol{\sigma})\).
Now we argue that we get the exact same result even when the initial values \(\tau_{v,i}\) are arbitrary (i.e., there is initial “garbage” in the registers). During the first pass, when processing the left subtree \(v_\ell\), we again increment \(r_{v,i}\) exactly \(f_i(v_\ell)\) times. Thus, when we process the right subtree \(v_r\), the register \(r_{v,i}\) contains \(\tau_{v,i} + f_i(v_\ell)\). We add this value to \(r_o\) exactly \(f_i(v_r)\) times, contributing \(f_i(v_r)(\tau_{v,i} + f_i(v_\ell))\) to \(r_o\).
Crucially, the second pass also processes the stream in the forward chronological direction. When processing the left subtree \(v_\ell\) in the second pass, we decrement \(r_{v,i}\) exactly \(f_i(v_\ell)\) times. Therefore, by the time we begin processing the right subtree \(v_r\) in the second pass, \(r_{v,i}\) has been perfectly restored to its initial value \(\tau_{v,i}\). Thus, during the processing of the right subtree \(v_r\) in the second pass, we subtract \(\tau_{v,i}\) from \(r_o\) exactly \(f_i(v_r)\) times.
The arbitrary value \(\tau_{v,i}\) perfectly cancels out across the two passes: \[f_i(v_r)(\tau_{v,i} + f_i(v_\ell)) - f_i(v_r)\tau_{v,i} = f_i(v_\ell)f_i(v_r).\] This leaves a net addition of \(f_i(v_\ell)f_i(v_r)\) to \(r_o\), exactly as in the zero-initialized case. Furthermore, since we increment \(r_{v,i}\) in the first pass and decrement it under the exact same conditions in the second pass, every catalytic register is restored to its initial value \(\tau_{v,i}\) by the end of the computation.
Finally, we analyze the complexity of the algorithm. The complete binary tree has \(m-1=O(m)\) internal nodes. For each internal node \(v\) and item \(i\in[n]\), we use one catalytic register over \(Z_q\), so we have \(O(nm)\) registers in total. They consist of \(n(m-1)\lceil\log q\rceil=O(nm\log q)\) bits. Substituting \(q= \Theta(m^2)\), we get a total of \(O(nm\log m)\) catalytic bits.
We need one regular register of \(O(\log m)\) bits for \(r_o\), and we also use regular memory to address the catalytic registers (to navigate between nodes of \(T\)). Addressing \(O(nm)\) catalytic registers requires \(O(\log(nm))\) bits.
To process each stream position, the algorithm loops over the \(O(\log m)\) ancestors of the corresponding leaf, so the total running time is \(O(m\log m)\) arithmetic operations per pass. The algorithm uses exactly two passes over the stream. ◻
6 Applications↩︎
In this section, we apply our polynomial evaluation algorithm to design multi-pass streaming algorithms for the exact computation of quantities that are notoriously difficult to evaluate exactly in the standard streaming model. Specifically, we present algorithms for counting distinct elements, counting occurrences of small subgraphs in an edge stream, and identifying the exact set of frequent elements.
6.1 \(F_0\) Using Powering↩︎
The zero moment of a stream \(\boldsymbol{\sigma}= x_1, x_2, \ldots, x_m\) over \([n]\), is \(F_0(\boldsymbol{\sigma}) := \sum_{i=1}^n \boldsymbol{1}_{f_i >0}\); that is the number of distinct items that appear in \(\sigma\). Computing \(F_0\) in the standard streaming model using a constant number of passes is known to be hard. In particular, [12] show that any \(p\)-pass algorithm requires \(\Omega(min\{m,n\}/p)\) bits of memory. In contrast, in the catalytic streaming model we have the following Lemma.
Lemma 3 (\(F_0\) Computation). Let \(\boldsymbol{\sigma}=x_1,x_2,\dots,x_m\) be a stream over \([n]\). There exists a catalytic streaming algorithm that evaluates \(F_0(\boldsymbol{\sigma})\) in \(4\) passes, using one regular register and \(n\) catalytic registers. This algorithm works over the field \(\mathbb{F}_p\) for every prime \(p > m\) .
Proof. By Fermat’s little theorem we have \(f_i^{p-1} \equiv 1 \pmod p\) for every \(f_i \not \equiv 0 \pmod p\), and \(0\) whenever \(f_i \equiv 0 \pmod p\). Therefore, evaluating the \(p-1\)-th moment of \(\boldsymbol{\sigma}\) over the field \(\mathbb{F}_p\) gives us \(F_0(\boldsymbol{\sigma})\). ◻
Remark 11. Note that by Bertrand’s postulate there exists a prime \(m < p \le 2m\), so the registers used require at most \(\log (m) + 1\) bits.
6.2 Finding Subgraphs in a Stream Using Polynomials↩︎
Consider a multigraph \(G = (V, E)\) with \(|V| = n\) and \(|E| = m\). In the graph streaming model, \(G\) is revealed sequentially as a stream of edges \(e_1, e_2, \ldots, e_m\). A fundamental problem in this setting is computing the number of occurrences of a small target subgraph \(H\) (e.g., a triangle or four cycle) within \(G\), or simply detecting its presence. This task is difficult because local structural information is fragmented across the stream. In fact, exact counting, or even detecting a single instance of a simple subgraph like a triangle, requires \(\Omega(m/p)\) bits of memory in the worst case for any \(p\)-pass streaming algorithm [22]–[24].
Lemma 4 (Subgraph Counting). Let \(H = (V_H, E_H)\) be a fixed target multigraph. There exists an algorithm that, given an edge stream of length \(m\) over a vertex set \(V\) of size \(n\), computes the exact number of occurrences of \(H\) in the underlying graph \(G\). The algorithm requires \(|E_H|+1\) passes over the stream, uses \(O(|E_H| + |V_H|)\) regular registers and \(n^2\) catalytic registers, and works over \(Z_q\) with \(q = O\big(\max\{m^{|E_H|}, n\}\big)\) .
Proof. For simplicity, consider first the case where \(H\) is a triangle.
Observation 12. Denote by \(x_{u,v}\) the number of occurrences of the edge \((u,v)\) in \(G\). The exact number of triangles in \(G\) is therefore given by the polynomial: \[P(\{x_{u,v} \mid (u,v)\in E\} )= \sum_{u < v < w \in V} x_{u,v} \cdot x_{v,w} \cdot x_{u,w} \, .\]
Given this observation, we can compute the number of triangles by evaluating \(P\) over the stream using 3 for cubic polynomials.
We generate these coefficients of the polynomial \(P(\{x_{u,v} \mid (u,v)\in E\})\) on the fly. To do so, we allocate \(3\) registers in our regular memory, to index the vertices \(u\), \(v\), and \(w\). By incrementally updating these registers, we iterate through all triplets \((u, v, w)\) such that \(u < v < w\). For each such triplet, the corresponding monomial \(x_{u,v} \cdot x_{v,w} \cdot x_{u,w}\) appears in \(P\) with coefficient \(1\).
Generalization to Arbitrary Subgraphs
To generalize this approach to an arbitrary subgraph \(H = (V_H, E_H)\), we define a polynomial of degree \(k = |E_H|\). For every set of \(|V_H|\) vertices and assignment of labels to the vertices we generate a monomial. This generates each monomial as many times as the number of automorphisms of \(H\). So we divide the result by the cardinality of the automorphism group of \(H\). This number should either be given as input or if \(H\) is small it can be computed in (regular) memory polynomial in the size of \(H\), by checking all permutations of the vertices in \(H\) lexicographically. We evaluate this polynomial over the frequencies of edges using 3. As for triangles we do not store the polynomial but traverse the monomials using \(|V_H|\) registers of size \(\log n\) each. Applying 3, this takes \(|E_H|+1\) passes, and calculations are over some ring which requires registers of size at most \(2 \Big( \frac{m}{|E_H|}\Big)^{|E_H|}\) bits since \(\Big( \frac{m}{|E_H|}\Big)^{|E_H|}\) is an upper bound on the number of occurrences of \(H\) in a multigraph with \(m\) edges. ◻
6.3 \(F_2\) Heavy Hitters↩︎
We use our two-pass algorithm for \(F_2\) to compute \(\epsilon F_2\)-heavy hitters. We say that an element \(i\) is \(\epsilon F_2\)-heavy hitter if \(f_i^2 \ge \epsilon F_2\). We do it in logarithmic number of passes and with \(O(1/\epsilon)\) registers of clean memory. This is about the same amount of memory required by the classical state of the art (one-pass) streaming algorithm for \(F_2\)-heavy hitters [25], just that we identify them exactly rather than approximately using a simple divide an conquer scheme.10 Specifically we show the following.
Lemma 5. There is an algorithm that given a stream \(\boldsymbol{\sigma}= x_1, x_2, \ldots, x_m\), returns the exact set of \(\epsilon F_2\)-heavy hitters of \(\boldsymbol{\sigma}\) in \(2+2\log \epsilon n\) passes using \(O(1/\epsilon)\) registers of regular memory and \(O(nm)\) registers of catalytic memory, over a ring of size \(Z_q\) where \(q = O(m^2)\) .
Proof. The formal description of the algorithm is given in Algorithm 5. In short we maintain a set \(\mathcal{B}\) of at most \(1/\epsilon\) buckets, each is an interval of consecutive elements from \([n]\), containing the heavy hitters. In each iteration we partition each bucket into two buckets. Then we estimate the contribution to \(F_2\) of the elements in each bucket simultaneously by running a copy of 4 separately on the elements of each bucket. There could be at most \(1/\epsilon\) buckets whose contribution is more than \(\epsilon F_2\), we continue with them to the next iteration and discard the rest. We need two passes to compute \(F_2\) initially and then two passes in each iteration to compute the \(F_2\) contributions of the buckets. The number of iterations is at most \(\log \epsilon n\), as the initial size of the buckets is \(\epsilon n\). We keep in the regular memory the boundaries of the buckets in \(\mathcal{B}\) and the \(F_2\) values of the elements in each of at most \(2/\epsilon\) buckets. Thus we need \(O(1/\epsilon)\) registers over \(Z_q\) for \(q = O(m^2)\).
The catalytic memory we need is the same as required by 4. In order to evaluate the \(F_2\) of the elements of every bucket we use a tree that needs at most \(O(\epsilon n m \log m)\) bits of catalytic memory. At every iteration we evaluate \(1/\epsilon\) such buckets. Therefore the total number of bits in the catalytic memory the algorithm requires is \(O(nm \log m)\). ◻
Extension to \(F_k\)-heavy hitters. Notice we can use the same idea in order to compute \(\epsilon F_k-\)Heavy Hitters using Algorithm 1. In this case we would need \(4 + 4\log \epsilon n\) passes and \(O(kn)\) catalytic registers over the ring \(Z_q\) with \(q = O(nm^k)\).
7 Concluding Remarks↩︎
In this paper, we introduced the catalytic streaming model, which equips algorithms with a large auxiliary memory that must be restored to its initial state by the end of the computation. The central question of this model is identifying which streaming problems inherently benefit from this restricted memory.
While recent results in catalytic communication [1] imply that catalytic memory offers no advantage for one-pass algorithms, we demonstrated that it is remarkably powerful given multiple passes. Specifically, we showed how to exactly evaluate multivariate polynomials of stream frequencies using \(O(1)\) regular memory of logarithmically many bits.
We characterize a broad family of algorithms for which computing \(F_2\) in two passes is impossible, and show that this barrier can be overcome by designing an algorithm outside this family. Since all our other algorithms satisfy these restriction (or extensions of them to more passes) we believe that this family may still be of interest.
We believe the catalytic streaming model opens a rich landscape for future work. Several compelling open problems remain:
Higher-degree pass optimality: Our current lower bound technique is limited to two passes and puts restrictions on the algorithms that it applies to. Can one prove more general lower bounds that relate the number of required passes to the degree of the evaluated polynomial?
Exact Heavy Hitters: Can heavy hitters be computed exactly using a constant number of passes in the catalytic model?
Further catalytic separations: Which other fundamental streaming problems admit catalytic algorithms that require substantially less regular memory than their standard streaming counterparts?
8 Powering32Lemma↩︎
We give here the powering algorithm of 1. We denote \(c_i \mathrel{\vcenter{:}}= (-1)^i {k\choose i}\).
![Figure 6: Powering Algorithm (Lemma 10) [Modified]](/article/2607.09475/_pdflatex/bxdmcsal.png "fig:")
After the execution of line [item:powering32algo32line321], the output register satisfies \[r_o=\sum_{i=1}^k (-1)^i \binom{k}{i}\tau_i \tau^i.\]
After the execution of line [item:powering32algo32line323], we have \[\forall i\in [k], \qquad r_i=\tau_i-(\tau+f)^{k-i}.\]
After the execution of line [item:powering32algo32line324], the output register satisfies \[r_o=(\tau+f)^k+\sum_{i=1}^k (-1)^i \binom{k}{i}\tau_i \tau^i.\]
Hence, after the execution of line [item:powering32algo32line326], we obtain \[\begin{align} r_o &= (\tau+f)^k+\sum_{i=1}^k (-1)^i \binom{k}{i}\tau_i \tau^i -\sum_{i=1}^k (-1)^i \binom{k}{i}\bigl(\tau_i-(\tau+f)^{k-i}\bigr)\tau^i \\ &= (\tau+f)^k+\sum_{i=1}^k (-1)^i \binom{k}{i}\tau^i(\tau+f)^{k-i} \\ &= f^k, \end{align}\] where the last equality follows from the binomial theorem.
Therefore, at the end of the computation, the registers contain \[r=\tau, \qquad r_o=f^k, \quad \text{and for every i\in [k],} \quad r_i=\tau_i-(\tau+f)^{k-i}.\]
9 Set-Disjointness↩︎
Proposition 13. Suppose there exists a catalytic streaming algorithm \(A\) that computes \(F_2\) in \(p\) passes using \(s\) bits of regular memory. Then there exists a catalytic communication protocol for \(\text{Disj}_n\) with \(2p\) rounds that uses \(s + \log (n) + c_0\) bits of regular memory, where \(c_0\) is some absolute constant.
Proof. Let \(\boldsymbol{x}\) be Alice’s input and \(\boldsymbol{y}\) be Bob’s input. To compute \(\text{Disj}_n(\boldsymbol{x},\boldsymbol{y})\), Alice and Bob simulate the streaming algorithm \(A\) on an appropriate stream, while using the shared memory exactly as \(A\) would.
First, Alice inserts into the stream every item \(i \in [n]\) such that \(x_i = 1\). She then passes the inner state of \(A\) plus it’s memory configuration to Bob.
Bob then inserts in a similar way \(\boldsymbol{y}\) into the stream. Moreover, he calculates \(\lVert\boldsymbol{y}\rVert_0\)11 and passes both \(A\) and \(\lVert\boldsymbol{y}\rVert_0\) to Alice.
They continue in this way, alternately simulating the execution of \(A\) and passing it’s inner state together with it’s current configuration, until the execution of \(A\) is complete.
Let \(a\) denote the output of \(A\) on the simulated stream. Alice accepts if and only if \[a = \|\boldsymbol{x}\|_0 + \|\boldsymbol{y}\|_0.\] Note that \(\|\boldsymbol{x}\|_0 + \|\boldsymbol{y}\|_0\) is exactly the length of the simulated stream.
Claim 14. Alice accepts if and only if \(\text{Disj}_n(\boldsymbol{x},\boldsymbol{y})=1\).
Proof. Suppose first that \(\text{Disj}_n(\boldsymbol{x},\boldsymbol{y})=1\). Then the supports of \(\boldsymbol{x}\) and \(\boldsymbol{y}\) are disjoint, so each item \(i \in [n]\) appears in the stream at most once. Hence, for every \(i \in [n]\), we have \(f_i \in \{0,1\},\) and therefore \(f_i^2 = f_i.\) It follows that \[F_2=\sum_{i=1}^n f_i^2 = \sum_{i=1}^n f_i = \|\boldsymbol{x}\|_0+\|\boldsymbol{y}\|_0.\] Since \(A\) computes \(F_2\), we have \(a=\|\boldsymbol{x}\|_0+\|\boldsymbol{y}\|_0\), and so Alice accepts.
Conversely, suppose that \(\text{Disj}_n(\boldsymbol{x},\boldsymbol{y})=0\). Then there exists some \(i \in [n]\) such that \(x_i=y_i=1\), and hence \(f_i=2\). More generally, there is at least one index \(i\) for which \(f_i>1\). Since for every \(t \in \mathbb{Z}_{\ge 0}\), \(t^2 \ge t,\)with strict inequality whenever \(t>1\), we obtain \[F_2=\sum_{i=1}^n f_i^2 > \sum_{i=1}^n f_i = \|\boldsymbol{x}\|_0+\|\boldsymbol{y}\|_0.\] Thus \(a > \|\boldsymbol{x}\|_0+\|\boldsymbol{y}\|_0\), and Alice rejects. ◻
The claim about the number of rounds is trivial. Each time the simulation is passed from one player to the other, the players need to communicate the current configuration of \(A\), which contributes \(s + c_0\) bits of regular memory, \(s\) bits for the memory size of \(A\) and \(c_0\) for description of it’s inner state. In addition, Bob communicates the value \(\|\boldsymbol{y}\|_0\) to Alice, which requires at most \(\log n\) bits of regular memory. ◻
Remark 15. Observe that the last reduction works for algorithm \(A\) which computes any moment other than \(F_1\), not just \(F_2\).
10 A Three-Round Catalytic Communication Protocol for Set-Disjointness↩︎
In [1], it is shown that the inner product of two vectors over \(\text{GF}_2\) can be computed by a three-round catalytic communication protocol using only \(1\) bit of regular memory and \(n\) bits of catalytic memory. We observe that essentially the same construction, with a minor modification, yields a protocol for \(\text{Disj}_n\). For completeness, we include the proof here, following their argument with the necessary changes.
Proposition 16. There exists a catalytic communication protocol for \(\text{Disj}_n\) that uses \(\log n + 1\) bits of regular memory, \(n(\log n + 1)\) bits of catalytic memory, and requires \(3\) rounds.
Proof. Let \(\boldsymbol{x}\in \{0,1\}^n\) be Alice’s input and let \(\boldsymbol{y}\in \{0,1\}^n\) be Bob’s input.
Partition the catalytic tape into \(n\) registers \[r_1,r_2,\dots,r_n,\] each of size \(\log (n) + 1\) bits. For each \(i \in [n]\), let \(\tau_i\) denote the initial contents of register \(r_i\). The regular memory consists of \(\log (n) + 1\) bits, so throughout the protocol all arithmetic operations are performed modulo \(2n\). Alice and Bob exchange the clean abd catalytic memory in three rounds as follows.
Alice increments \(r_i\) for every \(i\in [n]\) such that \(x_i =1\).
Bob adds \(r_i\) to regular memory for every \(i\in [n]\) such that \(y_i=1\).
Following this round, the regular memory contains \[\label{eq:disj32protocol32second32pass32memory32eq} \sum_{i:\, y_i=1} r_i \pmod{2n} = \sum_{i:\, y_i=1} \bigl(\tau_i + \mathbf{1}[x_i=1]\bigr) \pmod{2n},\tag{4}\] where \(\mathbf{1}[x_i=1]\) is the indicator of the event \(x_i=1\).
Alice decrements \(r_i\) for every \(i\in [n]\) such that \(x_i=1\).
Following this step, every catalytic register is restored to its initial value. .
Finally, once Bob gets the second message from Alice, he Bob subtracts \(r_i\) from the value in the regular memory for every \(i\) such that \(y_i = 1\). After doing so, using Equation 4 , the value Bob obtains is \[\label{eq:disj32protocol32reg32memory32output} \sum_{i \, : \, y_i=1} \mathbf{1}[x_i=1] \pmod{2n} \, .\tag{5}\] Bob outputs \(1\) if this value is \(0\), and outputs \(0\) otherwise.
The space bounds are immediate from the construction, the catalytic memory contains \(n\) registers of \(\log n+1\) bits each, for a total of \(n(\log n+1)\) bits, while the regular memory uses exactly \(\log n+1\) bits.
To prove correctness, observe that \[\sum_{i:\, y_i=1} \mathbf{1}[x_i=1] = |\{i \in [n] : x_i=y_i=1\}|,\] namely, the number of coordinates in which both \(\boldsymbol{x}\) and \(\boldsymbol{y}\) contain a \(1\). Therefore, \[\text{Disj}_n(\boldsymbol{x},\boldsymbol{y})=1 \quad\Longleftrightarrow\quad \sum_{i:\, y_i=1} \mathbf{1}[x_i=1]=0.\] Moreover, this sum is always at most \(n\), and hence is strictly smaller than \(2n\). Thus its value modulo \(2n\) is zero if and only if the sum itself is zero. ◻
11 Why the Discrete Derivative Argument Breaks in Three Passes↩︎
The impossibility result strictly relies on the two-pass constraint (one to hold some information about the input and one to clean the catalytic tape). We claim that if the algorithm is permitted a third pass, the information-theoretic contradiction vanishes. In a three-pass model, we have three bijection matrices \(U_{i,1}\), \(U_{i,2}\), \(U_{i,3}\), one for each pass such thatfor every \(f_i\), and every \(\tau_i\), applying \((U_{i,3})^{f_i}\Big((U_{i,2})^{f_i}\big((U_{i,1})^{f_i}(\tau_i)\big)\Big) = \tau_i\). If we apply the same proof technique then the derivative we get in this case will depend on \(y_1 = (U_{i,1})^{f_i}(\tau_1)\) and \(y_2 = (U_{i,2})^{f_i}\big((U_{i,1})^{f_i}(\tau_i)\big)\). So, we will have some deterministic function \(H_i(\cdot,\cdot)\) that satisfies \(H_i(y_1,y_2) = 2f_i + 1\). Crucially, while \(y_1\) and \(y_2\) are individually uniformly distributed and independent of \(f_i\), they jointly can determine \(f_i\). In particular they indeed determine \(f_i\) if there is a unique \(k\) for which \(y_2 = (U_{i,2})^k(y_1)\).
References↩︎
An extended abstract of this paper appears in ESA 2026.↩︎
The terminology comes from chemistry: a catalyst enables a reaction to proceed without being consumed or permanently altered.↩︎
\(\mathsf{TC}^1\) denotes the class of decision problems solvable by a family of polynomial-size, logarithmic-depth Boolean circuits with unbounded fan-in AND, OR, and MAJORITY (aka threshold) gates.↩︎
\(L\) is the class of problems computable with memory of size logarithmic in the input length.↩︎
We assume in this paper that \(n\leq m\). Since the number of catalytic registers which we use depends on \(n\), then when \(n>m\), we need \(\log n\) (rather than \(\log m)\) regular bits to address the catalytic registers.↩︎
The hidden constant depends on the largest coefficient of a monomial.↩︎
All items \(i\) such that \(f_i^k\ge \epsilon F_k\).↩︎
\(\mathbb{F}[y_1,y_2,\dots,y_n]\) is the ring of polynomials over the field \(\mathbb{F}\) with the variables \(y_1,y_2,\ldots,y_n\). The coefficients of \(P\) are given to the algorithm on the input tape.↩︎
We assume w.l.o.g.that in the end of the algorithm we only have \(F_2\) on our regular memory.↩︎
Maybe a more common notion is \(\epsilon\) \(\ell_2\)-heavy hitter, defined to be any item \(i\) such that \(f_i\ge \epsilon \sqrt{F_2}\). These notions are the same up to squaring \(\epsilon\).↩︎
The \(L_0\) norm of \(\boldsymbol{y}\), i.e. the number of \(1\) bits in \(\boldsymbol{y}\)↩︎