Post

Thomas Steinke
@stein.ke

The square root can be uniformly approximated to error ε by a rational function of degree O(log²(1/ε)). This surprising, since a polynomial approximation (e.g. Taylor series) requires degree Ω(1/ε), so rational functions are exponentially better than polynomials.

Thomas Steinke
@stein.ke

This approximation result was originally shown by Newman in 1964 (using a different construction and proof). Approximating the square root function on [0,1] is equivalent to approximating the absolute value function on [-1,1]. doi.org/10.1307/mmj/...

0 reposts2 likes

Thomas Steinke
@stein.ke

This approximation turns out to be useful for designing algorithms! Rational functions have Taylor series whose coefficients satisfy a linear recurrence. And we used that structure to make efficient streaming algorithms. Here's my paper, which appeared at FOCS 2024: arxiv.org/abs/2404.16706

arxiv.orgEfficient and Near-Optimal Noise Generation for Streaming Differential PrivacyIn 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 ...