Private Continual Counting of Unbounded Streams

arXiv:2506.15018 · cs.CR, cs.DS, cs.LG · Submitted 2025-06-17 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: We're looking at the paper: "Private Continual Counting of Unbounded Streams".

Elias: Here's the gist of the paper. Private continual counting of unbounded streams studies the problem of differentially private continual counting in an unbounded setting where the input size n is not known in advance The resulting algorithm has smooth error, and for any α > 0 and t ≤ n it is able to privately estimate the sum of the first t data points with O(log2+2α(t)) variance It requires O(t) space and amortized O(log t) time per round, compared to O(n log n) pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al.

27: Empirically, we find that our algorithm’s performance is also comparable to theirs in absolute terms: our variance is less than 1.5× theirs for t as large as 2 4 Problem Statement and Motivation Differentially private counting under continual observation refers to the problem of maintaining accurate running totals over streams of sensitive data It has attracted a great deal of attention in recent years for its wide-ranging applications in optimization, online learning and the private analysis of streaming data more broadly One challenge when applying matrix-based algorithms to streaming settings is that they largely assume access to the input size n as a parameter Simple solutions to this problem all carry fundamental tradeoffs Algorithm Design and Matrix Factorization The main contribution in this paper is a matrix-based algorithm that overcomes this trilemma: to the best of our knowledge, it is the first private counting algorithm that is simultaneously smooth and unbounded with almost-optimal asymptotic error The resulting algorithm has smooth error, and for any α > 0 and t ≤ n it is able to privately estimate the sum of the first t data points with O(log2+2α(t)) variance The matrix decompositions we consider are of the form L = LTToep(f(z; −γ, −δ)), R = LTToep(f(z; γ, δ)), where f1(z):= 1/√1−z, f2(z; γ):= 1/z ln 1/(1−z) γ, and f3(z; δ):= 2/z ln 1/(z ln 1−zδ) Theoretical Guarantees Theorem 1 states that for all α > 0, there exists an infinite lower-triangular Toeplitz matrix factorization L, R ∈ R∞×∞ with the following properties: Joint Validity: For all n ∈ Z+,

L: n

R: n =

Mcount: n Bounded Sensitivity: limn→∞∥

R: n∥1→2 = C < ∞ for some computable constant C Near-Optimal Asymptotic Error: ∥

L: n∥2→∞ = O(log1+α(n)) Corollary 1 states that for all ε, δpriv, α > 0 there exists an unbounded streaming algorithm for continual counting, described in Algorithm 1, which has the same complexity as in Theorem 1 and satisfies (ε, δpriv)-DP in the continual release model Implementation Details and Extensions Algorithm 1 requires computing next t coefficients of L = LTToep(f(z; −γ, −δ)) in O(tlog t) time with an FFT The total cost over the entire input is 12P⌈log2 n⌉ k=1 M(2k) ∼ 12P⌈log2 n⌉ k=1 2−k+1M(n) ≤ 24M(n), which can be cut down to 17.5M(n) if δ = −γ, or 13M(n) when δ = 0 Algorithm 2 introduces an order K approximation to improve running time by switching from exact computations to order K approximations once the relative error of the approximation falls below some threshold η We have shown for the first time that the classic matrix factorization method

33: can be efficiently extended to online settings with unknown input size without the use of doubling tricks The only algorithms we are aware of that exactly achieve asymptotically optimal O(log2 t) variance in the unbounded setting rely on some form of doubling trick Open Question 1 asks whether there exist LTToep matrices L, R such that

L: n

R: n =

Mcount: n, limn→∞∥

R: n∥1→2 < ∞, and ∥

L: n∥2→∞ = Θ(log2 n)?

Elias: Technical Details for Computing Sensitivity To actually compute the sensitivity, we make use of Parseval’s theorem, which gives us: X∞ m=0 (

z m: fR)2 = 1/2π Z 2π 0 fR(e iθ)2 dθ = 2(2δ/4) Z π/3 0 I1(ω) −1 I2(ω) −1/2−α (I3(ω) + I4(ω)) squared δ dω + Z π/2 π/3 I1(ω) −1 I2(ω) −1/2−α (I3(ω) + (I4(ω) − π) 2) δ dω The integrands are sufficiently smooth to be numerically integrated to high precision Empirical Findings We have also shown empirically that it enjoys excellent constants when its parameters are set correctly, with variance that is uniformly less than 1.5× that of Henzinger et al.

27: for inputs as large as n = 224 The Hybrid mechanism using Algorithm 1 for the unbounded component outperforms the variant using independent noise as in Chan et al.

Paper summary: Nadia: So we’re looking at this paper, "Private Continual Counting of Unbounded Streams." It tackles differentially private continual counting when you don't even know the total size of the stream in advance.

Elias: Right. The core idea they’re pushing is that current methods that rely on knowing the input size n just don't work in this unbounded setting because their privacy guarantees only hold when you tune those parameters to n.

Priya: So what's the main claim here about how they solve this? What are they actually proposing instead of just using some noise trick?

Nadia: They introduce a new matrix-based algorithm that aims to be both smooth and unbounded at the same time with almost optimal asymptotic error. It’s a matrix factorization approach based on logarithmic perturbations of the function root one over one minus z, which they studied in prior work.

Elias: And what’s the specific performance metric they claim for this new method? They say that for any alpha greater than zero and any t less than or equal to n, you can privately estimate the sum of the first t data points with an error variance of two plus alpha t over log two plus two alpha t.

Priya: That sounds like a specific bound. So, what’s the cost? Because when you're dealing with streaming data, space and time complexity are huge concerns for real-world deployment.

Nadia: They say it requires space proportional to t, which is O of t space, and the time per round is amortized O of log t time. This is significantly better than the nearly optimal bounded-input algorithm by Henzinger et al., which takes O of n log n pre-processing time.

Elias: They also note that they have smooth error, which means the variance is a smooth function of t. That smoothness, combined with being unbounded, is what they call their main contribution over simpler methods like just adding independent noise to each data point.

Priya: But the paper mentions that this approach isn't truly unbounded in a strict sense; it's still linked to n in some way, and they admit that it might not be satisfying for practical use. That’s a caveat we should keep in mind.

Paper summary: Nadia: Exactly. They also compare their performance empirically to the Henzinger et al. work, saying their variance is less than one point five times theirs when t is as large as two to the power of four.

Elias: It sounds like they’re trying to solve a trilemma: getting smoothness, staying unbounded, and achieving almost optimal asymptotic error all at once. They found a way around that trade-off using these specific matrix factorizations L and R.

Priya: If we look at the complexity again, they mention that computing the next t coefficients of L requires FFT time which is O of t log t. So, if you’re processing a stream, that means each step costs about t log t operations.

Nadia: That’s the computational trade-off for getting this performance level. They also mention an order K approximation in Algorithm two to try and speed things up by switching to approximations once the relative error of that approximation drops below some threshold eta <ref:2506.15018#pg1>.

Elias: And that leads us into a question about what they’re trying to achieve with these matrix decompositions L and R. They define them using functions f1, f2, and f3 involving logarithms of one over one minus z, which are related to prior work in the area.

Priya: I wonder if we can simplify what this means for someone who just needs a running total estimate for their data stream without knowing its final size. It suggests a way to get good privacy guarantees even when the data never ends.

Nadia: It really does. The whole point of the paper, "Private Continual Counting of Unbounded Streams," is that it provides a matrix-based solution that overcomes the limitations of previous algorithms in this area regarding smoothness and unboundedness simultaneously.

Elias: And looking at the conclusion, they aren't claiming a perfect solution yet because they acknowledge that their specific matrix factorization isn't truly unbounded and might not be practical in every scenario.

Priya: So, what’s the big picture implication here for applications? Is this something we can actually rely on for sensitive data streams?

Nadia: It shows that a method exists with a very low variance bound, O of log two plus two alpha t, compared to the previous logarithmic variance bounds. It's a significant step forward in achieving better privacy guarantees in online learning and streaming data analysis.

Paper summary: Elias: They’ve also shown that their hybrid mechanism outperforms variants using independent noise for the unbounded component, but they admit both variants can have very erratic performance when t is close to a power of two. That’s a practical warning about implementation choices.

Priya: So, while the theoretical bounds look good, we still have to worry about those practical performance dips based on how t relates to powers of two. It’s not just smooth math; it has real-world quirks.

Nadia: Precisely. The paper gives us a concrete algorithm that's much more powerful than just adding independent noise, but we need to be careful with the tuning parameters like delta and gamma they use in their functions f1, f2, and f3.

Elias: And if you want to know what they’re really asking for in terms of future work, there’s an open question about whether there exist LTToep matrices L and R such that their product relates to the count matrix in a way that keeps the norm of R bounded while the norm of L stays logarithmically bounded by n.

Priya: That open question points toward understanding if we can find a factorization that maintains both the required privacy bound and truly unbounded behavior without needing those doubling tricks they mentioned earlier.

Nadia: It’s a good direction for future research, pushing towards a more robust mathematical structure for these private counting problems in the unbounded setting.

Elias: So, to wrap up this discussion on "Private Continual Counting of Unbounded Streams," the paper presents a matrix-based algorithm that offers smooth error and almost optimal asymptotic error variance O of log two plus two alpha t, which is better than previous methods.

Priya: It’s a step in the right direction for privacy research, but we still need to see how robust these solutions are when you move from theoretical bounds to actual deployment on real data streams.

Nadia: The key thing is that they’ve provided a concrete mechanism that addresses the trilemma of smoothness, unboundedness, and error bound simultaneously in a way that’s practically implementable with O of t space and time.

Conclusion: Nadia: So we're wrapping up this look at "Private Continual Counting of Unbounded Streams." Basically, they’ve developed a way to keep running totals private even when you don't know how big the total stream is.

Elias: Exactly. They use some specific matrix math—logarithms and Toeplitz matrices—to handle that unknown size problem without needing to pre-know the whole thing in advance.

Priya: From a privacy standpoint, what does that actually mean for someone tracking sensitive data over time? Does it offer a real improvement over just adding random noise to every single piece of data?

Nadia: It offers a different kind of bound. They show that you can estimate the sum of the first t items with an error variance tied to log two plus alpha times t. That means for a fixed privacy level, the error gets much smaller as you look at more items, which is pretty good for long-term tracking.

Elias: But there's a catch in their math. They admit that this approach isn't perfectly unbounded in the strictest sense of the problem they set up initially, so it’s not a magic solution for every single streaming scenario.

Priya: I see what you mean about the catch. So we’re looking at a method that performs really well asymptotically, but maybe it breaks down when you hit certain thresholds with t?

Nadia: That's right. They did show empirically that their performance is comparable to other methods, better than some by a factor of one point five times for large inputs. It’s solid work for the theoretical foundation.

Elias: The authors are asking a big question about whether we can ever find these perfect Toeplitz matrices where the norm stays bounded while still getting that optimal logarithmic error scaling with n.

Priya: That's a tough ask, Elias. If they can nail that, it would mean we could have truly robust continual counting systems for anything from online learning to monitoring public data streams without those tricky limitations.

Ben Jacobsen, Kassem Fawaz

University of Wisconsin — Madison

cs.CR, cs.DS, cs.LG

Submitted: 2025-06-17

Updated: 2026-11-08

Comments: Corrects a numerical integration error from the version published at NeurIPS 2025. We ask that future papers cite this updated version

Code: https://github.com/ben-jacobsen/central-dpolo

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 74/100

The gist: Private continual counting of unbounded streams studies the problem of differentially private continual counting in an unbounded setting where the input size n is not known in advance The resulting…

Key concepts

Differentially Private Continual Counting
This is the problem of keeping track of running totals from an endless stream while ensuring privacy. The algorithm must provide accurate counts while preventing attackers from learning sensitive information about individual data points in the stream.
Matrix Factorization (LTToep)
The core technique involves using specific types of infinite lower-triangular Toeplitz matrices to model the counting process. These matrices are constructed using functions like $f_1(z)$ and $f_2(z)$, which help manage the structure of the stream data in a way that allows for privacy guarantees.
Smooth Error
The resulting algorithm has smooth error, meaning its estimation accuracy changes gradually rather than jumping abruptly. This is a desirable property for streaming applications where continuous, predictable performance is needed over time.

Terminology

Summary

Private continual counting of unbounded streams studies the problem of differentially private continual counting in an unbounded setting where the input size n is not known in advance The resulting algorithm has smooth error, and for any α > 0 and t ≤ n it is able to privately estimate the sum of the first t data points with O(log2+2α(t)) variance It requires O(t) space and amortized O(log t) time per round, compared to O(n log n) pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al. p. 0

Where the paper says it

The resulting algorithm has smooth error, and for any α > 0 and t ≤ n it is able to privately estimate the sum of the first t data points with O(log2+2α (t)) variance. It requires O(t) space and amortized O(log t) time per round, compared to O(log(n) log(t)) variance, O(n) space and O(n log n) pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al.

[27] Empirically, we find that our algorithm’s performance is also comparable to theirs in absolute terms: our variance is less than 1. p. 0
Where the paper says it

It requires O(t) space and amortized O(log t) time per round, compared to O(log(n) log(t)) variance, O(n) space and O(n log n) pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al. Empirically, we find that our algorithm’s performance is also comparable to theirs in absolute terms: our variance is less than 1.

5× theirs for t as large as 2 4

Problem Statement and Motivation

Differentially private counting under continual observation refers to the problem of maintaining accurate running totals over streams of sensitive data It has attracted a great deal of attention in recent years for its wide-ranging applications in optimization, online learning and the private analysis of streaming data more broadly One challenge when applying matrix-based algorithms to streaming settings is that they largely assume access to the input size n as a parameter Simple solutions to this problem all carry fundamental tradeoffs

Algorithm Design and Matrix Factorization

The main contribution in this paper is a matrix-based algorithm that overcomes this trilemma: to the best of our knowledge, it is the first private counting algorithm that is simultaneously smooth and unbounded with almost-optimal asymptotic error The resulting algorithm has smooth error, and for any α > 0 and t ≤ n it is able to privately estimate the sum of the first t data points with O(log2+2α(t)) variance The matrix decompositions we consider are of the form L = LTToep(f(z; −γ, −δ)), R = LTToep(f(z; γ, δ)), where f1(z):= 1/√1−z, f2(z; γ):= 1/z ln 1/(1−z) γ, and f3(z; δ):= 2/z ln 1/(z ln 1−zδ)

Theoretical Guarantees

Theorem 1 states that for all α > 0, there exists an infinite lower-triangular Toeplitz matrix factorization L, R ∈ R∞×∞ with the following properties: Joint Validity: For all n ∈ Z+, [L]n[R]n = [Mcount]n Bounded Sensitivity: limn→∞∥[R]n∥1→2 = C < ∞ for some computable constant C Near-Optimal Asymptotic Error: ∥[L]n∥2→∞ = O(log1+α(n)) Corollary 1 states that for all ε, δpriv, α > 0 there exists an unbounded streaming algorithm for continual counting, described in Algorithm 1, which has the same complexity as in Theorem 1 and satisfies (ε, δpriv)-DP in the continual release model

Implementation Details and Extensions

Algorithm 1 requires computing next t coefficients of L = LTToep(f(z; −γ, −δ)) in O(tlog t) time with an FFT The total cost over the entire input is 12P⌈log2 n⌉ k=1 M(2k) ∼ 12P⌈log2 n⌉ k=1 2−k+1M(n) ≤ 24M(n), which can be cut down to 17.5M(n) if δ = −γ, or 13M(n) when δ = 0 Algorithm 2 introduces an order K approximation to improve running time by switching from exact computations to order K approximations once the relative error of the approximation falls below some threshold η

Conclusion and Open Questions

We have shown for the first time that the classic matrix factorization method [33] can be efficiently extended to online settings with unknown input size without the use of doubling tricks The only algorithms we are aware of that exactly achieve asymptotically optimal O(log2 t) variance in the unbounded setting rely on some form of doubling trick Open Question 1 asks whether there exist LTToep matrices L, R such that [L]n[R]n = [Mcount]n, limn→∞∥[R]n∥1→2 < ∞, and ∥[L]n∥2→∞ = Θ(log2 n)?

Technical Details for Computing Sensitivity

To actually compute the sensitivity, we make use of Parseval’s theorem, which gives us: X∞ m=0 ([z m]fR)2 = 1/2π Z 2π 0 fR(e iθ)2 dθ = 2(2δ/4) Z π/3 0 I1(ω) −1 I2(ω) −1/2−α (I3(ω) + I4(ω)) squared δ dω + Z π/2 π/3 I1(ω) −1 I2(ω) −1/2−α (I3(ω) + (I4(ω) − π) 2) δ dω The integrands are sufficiently smooth to be numerically integrated to high precision

Empirical Findings

We have also shown empirically that it enjoys excellent constants when its parameters are set correctly, with variance that is uniformly less than 1.5× that of Henzinger et al. p. 0

Where the paper says it

The resulting algorithm has smooth error, and for any α > 0 and t ≤ n it is able to privately estimate the sum of the first t data points with O(log2+2α (t)) variance. It requires O(t) space and amortized O(log t) time per round, compared to O(log(n) log(t)) variance, O(n) space and O(n log n) pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al.

[27] for inputs as large as n = 224 The Hybrid mechanism using Algorithm 1 for the unbounded component outperforms the variant using independent noise as in Chan et al. p. 8
Where the paper says it

Contrast with asymptotics in Table 1. The Hybrid mechanism using Algorithm 1 for the unbounded component outperforms the variant using independent noise as in Chan et al.

[11], but both variants exhibit very erratic performance when t is close to a power of 2 For Algorithm 1, the parameters δ = −γ and δ = −6γ/5 give similar performance, but the latter is slightly better once t > 2 20, and both outperform δ = 0 when t > 2 10 The choice δ = -6γ/5 produces lines that are as close as possible to that of M 1/2count without crossing it, which we hypothesize explains its good performance The original hybrid mechanism used a simple unbounded algorithm that adds independent noise to each input (corresponding to the matrix decomposition L = Mcount, R = I) Our work enables a more powerful instantiation using Algorithm 1 as the unbounded algorithm instead (‘Hybrid Matrix’ in Table 1), which we compare against the original We improve on the original presentation by using M 1/2count for the bounded algorithm and allocating 75% of the privacy budget to the bounded learner, which reduces the constant of the leading O(log2 t) term The performance of Algorithm 2 with δ = 0 is visually indistinguishable from that of Algorithm 1

Code Availability

Our code is available at https://github.com/ben-jacobsen/centraldpolo/ The paper does not use any existing data or models, and the primary package we use is mpmath, which we cite in Appendix A Our work is largely theoretical and defensive in nature, and does not involve any human subjects or sensitive datasets The paper does not release new assets The authors do not use LLMs in the core methods of this research

Broader Impacts

The work is largely theoretical and not tied to any concrete application, and we do not anticipate any particular negative societal impacts We do not release any data or models The paper does not involve crowdsourcing nor research with human subjects The paper does not describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse Our work is largely theoretical and defensive in nature, and does not involve any human subjects or sensitive datasets

Experimental Setting

We only conduct two small experiments, which are described in Figure 1 and Figure 2 We provide all parameters for our own algorithm, and explicitly describe the construction of the hybrid mechanisms All of them were carried out in python using a single commercial CPU in a few seconds or minutes The paper does not include experiments requiring code The answer NA means that the paper does not include experiments.

Statistical Significance

Our experiments are all exact and involve no randomness

Computational Resources

There are no special computational resources required to reproduce our experiments All of them were carried out in python using a single commercial CPU in a few seconds or minutes The paper does not include experiments requiring code

Licenses for Existing Assets

We do not use any existing data or models, and the primary package we use is mpmath, which we cite in Appendix A The name of the license (e.g., CC-BY 4.0) should be included for each asset

New Assets

The paper does not release new assets Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates The paper does not use LLMs in the core methods of this research

Crowdsourcing and Human Subjects

The paper does not involve crowdsourcing nor research with human subjects The paper does not involve crowdsourcing nor research with human subjects The paper does not involve crowdsourcing nor research with human subjects The paper does not involve crowdsourcing nor research with human subjects

IRB Approvals

The paper does not involve humans and therefore no IRB approval is required

LLM Usage Declaration

This paper did not use LLMs The core method development in this research does not involve LLMs as any important, original, or non-standard components The paper did not use LLMs

Safeguards

Our paper does not release any data or models

Open Access to Data and Code

We have released our code as open-source software, including scripts to reproduce all figures in the paper The instructions should contain the exact command and environment needed to run to reproduce the results

Data and Code Instructions

The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc. The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines

Experimental Setting/Details

The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them The full details can be provided either with the code, in appendix, or as supplemental material

The answer NA means that the paper does not include experiments

Compute Resources

There are no special computational resources required to reproduce our experiments The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage

Code of Ethics

Our work is largely theoretical and defensive in nature, and does not involve any human subjects or sensitive datasets

The work is largely theoretical and not tied to any concrete application We do not anticipate any particular negative societal impacts The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology

Our paper does not release any data or models We recognize that providing effective safeguards is challenging, and many papers do not require this The answer NA means that the paper poses no such risks.

Crowdsourcing and Research with Human Subjects

The paper does not involve crowdsourcing nor research with human subjects The paper does not involve crowdsourcing nor research with human subjects The paper does not involve crowdsourcing nor research with human subjects The paper does not involve crowdsourcing nor research with human subjects

IRB Approvals or Equivalent

The paper does not involve humans and therefore no IRB approval is required

Declaration of LLM Usage

This paper did not use LLMs The core method development in this research does not involve LLMs as any important, original, or non-standard components This paper did not use LLMs

We do not use any existing data or models, and the primary package we use is mpmath, which we cite in Appendix A The name of the license (e.g., CC-BY 4.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Privacy-preserving continual counting in unbounded settings can be achieved using a matrix-based algorithm that is simultaneously smooth and unbounded with almost-optimal asymptotic error. This allows AI systems to maintain accurate running totals over streams of sensitive data without needing prior knowledge of the input size n, overcoming the limitations of doubling tricks.

  2. The proposed algorithm achieves a variance bounded by O(log2+2alpha(t)) for estimating the sum of the first t data points, which is comparable to existing state-of-the-art algorithms in absolute terms, providing a strong utility/privacy tradeoff.

  3. AI systems can be deployed to estimate partial sums with O(t) space and amortized O(log t) time per round, offering a practical implementation complexity similar to foundational algorithms like Henzinger et al. [27].

  4. The algorithm's performance is robust for realistic input sizes, empirically showing variance less than 1.5 times that of the nearly-optimal bounded-input algorithm when t is as large as 2 24.

Abstract

We study the problem of differentially private continual counting in the unbounded setting where the input size n is not known in advance. Current state-of-the-art algorithms based on optimal instantiations of the matrix mechanism cannot be directly applied here because their privacy guarantees only hold when key parameters are tuned to n. Using the common `doubling trick' avoids knowledge of n but leads to suboptimal and non-smooth error. We solve this problem by introducing novel matrix factorizations based on logarithmic perturbations of the function 1 over sqrt 1-z studied in prior works, which may be of independent interest. The resulting algorithm has smooth error, and for any α> 0 and t at most n, it is able to privately estimate the sum of the first t data points with O(squared(t)(t) 1+2α) variance. It requires O(t) space and amortized O(t) time per round, compared to O((n) (t)) variance, O(n) space and O(n n) pre-processing time for the nearly-optimal bounded-input algorithm of Henzinger et al. Empirically, we find that our algorithm's performance is also comparable to theirs in absolute terms: with optimized parameters, our variance is less than 2 times theirs for t as large as 2 32.

Sources

Related papers