  In the task of differentially private (DP) continual counting, we receive a
stream of increments and our goal is to output an approximate running total of
these increments, without revealing too much about any specific increment.
Despite its simplicity, differentially private continual counting has attracted
significant attention both in theory and in practice. Existing algorithms for
differentially private continual counting are either inefficient in terms of
their space usage or add an excessive amount of noise, inducing suboptimal
utility.
  The most practical DP continual counting algorithms add carefully correlated
Gaussian noise to the values. The task of choosing the covariance for this
noise can be expressed in terms of factoring the lower-triangular matrix of
ones (which computes prefix sums). We present two approaches from this class
(for different parameter regimes) that achieve near-optimal utility for DP
continual counting and only require logarithmic or polylogarithmic space (and
time).
  Our first approach is based on a space-efficient streaming matrix
multiplication algorithm for a class of Toeplitz matrices. We show that to
instantiate this algorithm for DP continual counting, it is sufficient to find
a low-degree rational function that approximates the square root on a circle in
the complex plane. We then apply and extend tools from approximation theory to
achieve this. We also derive efficient closed-forms for the objective function
for arbitrarily many steps, and show direct numerical optimization yields a
highly practical solution to the problem. Our second approach combines our
first approach with a recursive construction similar to the binary tree
mechanism.
