Fetching the paper…
Reading the bibliography…
For any real numbers $B \ge 1$ and $\delta \in (0, 1)$ and function $f: [0, B] \rightarrow \mathbb{R}$, let $d_{B; \delta} (f) \in \mathbb{Z}_{> 0}$ denote the minimum degree of a polynomial $p(x)$ satisfying $\sup_{x \in [0, B]} \big| p(x) - f(x) \big| < \delta$.
An iteration method for the solution of the eigenvalue problem of linear differential and integral operators
Cornelius Lanczos · 1950
Earlier work this paper cites.
Theory of approximation of functions of a real variable
A. F. Timan · 1963
Earlier work this paper cites.
On the maximum errors of polynomial approximations defined by interpolation and by least squares criteria
Michael JD Powell · 1967
Earlier work this paper cites.
A fast algorithm for particle simulations
Leslie Greengard and Vladimir Rokhlin · 1987
Earlier work this paper cites.
On the degree of boolean functions as real polynomials
Noam Nisan and Mario Szegedy · 1994
Earlier work this paper cites.
On krylov subspace approximations to the matrix exponential operator
Marlis Hochbruck and Christian Lubich · 1997
Earlier work this paper cites.
Approximating linear restrictions of boolean functions
Yaoyun Shi · 2002
Earlier work this paper cites.
Chebyshev polynomials
J. C. Mason and D. C. Handscomb · 2003
Earlier work this paper cites.
Improved fast gauss transform and efficient kernel density estimation
Changjiang Yang, Ramani Duraiswami, Nail A Gumerov, and Larry Davis · 2003
Earlier work this paper cites.
Quantum lower bounds for the collision and the element distinctness problems
Scott Aaronson and Yaoyun Shi · 2004
Earlier work this paper cites.
Geometric approximation via coresets
Pankaj K Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et al · 2005
Earlier work this paper cites.
Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range
Andris Ambainis · 2005
Cited alongside, same era.
Approximating the exponential, the lanczos method and an o (m)-time spectral algorithm for balanced separator
Lorenzo Orecchia, Sushant Sachdeva, and Nisheeth K Vishnoi · 2012
Cited alongside, same era.
ε \varepsilon -samples for kernels
Jeff M Phillips · 2013
Cited alongside, same era.
Approximation theory and approximation practice
Lloyd N. Trefethen · 2013
Cited alongside, same era.
More applications of the polynomial method to algorithm design
Amir Abboud, Ryan Williams, and Huacheng Yu · 2014
Cited alongside, same era.
Hardware implementation of the exponential function using taylor series
Peter Nilsson, Ateeq Ur Rahman Shaik, Rakesh Gangarajaiah, and Erik Hertz · 2014
Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky
Timothy M Chan and Ryan Williams · 2016
Later among the works it cites.
On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks
Arturs Backurs, Piotr Indyk, and Ludwig Schmidt · 2017
Later among the works it cites.
Hashing-based-estimators for kernel density in high dimensions
Moses Charikar and Paris Siminelakis · 2017
Later among the works it cites.
Efficient softmax approximation for gpus
Armand Joulin, Moustapha Cissé, David Grangier, Hervé Jégou, et al · 2017
Later among the works it cites.
Stability of the lanczos method for matrix function approximation
Cameron Musco, Christopher Musco, and Aaron Sidford · 2018
Later among the works it cites.
Hardness of approximate nearest neighbor search
Aviad Rubinstein · 2018
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Faster algorithms via approximation theory
Sushant Sachdeva and Nisheeth K Vishnoi · 2014
Cited alongside, same era.
Probabilistic polynomials and hamming nearest neighbors
Josh Alman and Ryan Williams · 2015
Cited alongside, same era.
Dual lower bounds for approximate degree and markov–bernstein inequalities
Mark Bun and Justin Thaler · 2015
Cited alongside, same era.
Strategies for training large vocabulary neural language models
Welin Chen, David Grangier, and Michael Auli · 2015
Cited alongside, same era.
Polynomial representations of threshold functions and algorithmic applications
Josh Alman, Timothy M Chan, and Ryan Williams · 2016
Cited alongside, same era.
Later among the works it cites.
Finding the mode of a kernel density estimate
Jasper CH Lee, Jerry Li, Christopher Musco, Jeff M Phillips, and Wai Ming Tai · 2019
Later among the works it cites.
Fast Kernel Evaluation in High Dimensions: Importance Sampling and near Neighbor Search
Paraskevas Syminelakis · 2019
Later among the works it cites.
Algorithms and hardness for linear algebra on geometric graphs
Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song · 2020
Later among the works it cites.
Oblivious sketching of high-degree polynomial kernels
Thomas D Ahle, Michael Kapralov, Jakob BT Knudsen, Rasmus Pagh, Ameya Velingker, David P Woodruff, and Amir Zandieh · 2020
Later among the works it cites.
Guest column: Approximate degree in classical and quantum computing
Mark Bun and Justin Thaler · 2021
Later among the works it cites.