# Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimation

arXiv: https://arxiv.org/abs/2205.06249 · HTML: https://mlsanity.com/paper/2205.06249/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 May 2022.

## Built on by (most cited first, 19 of 19)

- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models](https://mlsanity.com/paper/2406.03136/) (2024)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [Training Tensor Attention Efficiently: From Cubic to Almost Linear Time](https://mlsanity.com/paper/2405.16411/) (2024)
- [Bypass Exponential Time Preprocessing: Fast Neural Network Training via Weight-Data Correlation Preprocessing](https://mlsanity.com/paper/2211.14227/) (2022)
- [Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time](https://mlsanity.com/paper/2408.13233/) (2024)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [Streaming Kernel PCA Algorithm With Small Space](https://mlsanity.com/paper/2303.04555/) (2023)
- [Subquadratic Algorithms and Hardness for Attention with Any Temperature](https://mlsanity.com/paper/2505.14840/) (2025)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)
- [On the Fine-Grained Hardness of Inverting Generative Models](https://mlsanity.com/paper/2309.05795/) (2023)
- [Tracking High-order Evolutions via Cascading Low-rank Fitting](https://mlsanity.com/paper/2604.10980/) (2026)
- [Approaching I/O-optimality for Approximate Attention](https://mlsanity.com/paper/2605.23751/) (2026)

## Abstract (arXiv)

For any real numbers B ≥ 1 and δ ∈ (0, 1) and function f: [0, B] rightarrow ℝ, let dB; δ (f) ∈ mathbbZ> 0 denote the minimum degree of a polynomial p(x) satisfying supx ∈ [0, B] big| p(x) - f(x) big| < δ. In this paper, we provide precise asymptotics for dB; δ (e-x) and dB; δ (ex) in terms of both B and δ, improving both the previously known upper bounds and lower bounds. In particular, we show dB; δ (e-x) = Thetaleft( max left √B log(δ-1), fraclog(δ-1)  log(B-1 log(δ-1)) rightright),  and dB; δ (ex) = Thetaleft( max left B, fraclog(δ-1)  log(B-1 log(δ-1)) rightright). Polynomial approximations for e-x and ex have applications to the design of algorithms for many problems, and our degree bounds show both the power and limitations of these algorithms. We focus in particular on the Batch Gaussian Kernel Density Estimation problem for n sample points in Theta(log n) dimensions with error δ = n-Theta(1). We show that the running time one can achieve depends on the square of the diameter of the point set, B, with a transition at B = Theta(log n) mirroring the corresponding transition in dB; δ (e-x): - When B=o(log n), we give the first algorithm running in time n1 + o(1). - When B = kappa log n for a small constant kappa>0, we give an algorithm running in time n^1 + O(log log kappa-1 /log kappa-1). The log log kappa-1 /log kappa-1 term in the exponent comes from analyzing the behavior of the leading constant in our computation of dB; δ (e-x). - When B = ω(log n), we show that time n2 - o(1) is necessary assuming SETH.