Faster algorithms via approximation theory

DOI10.1561/0400000065MaRDI QIDQ5167553zbMATH OpenOpenAlexFDO

Authors Sushant Sachdeva, Nisheeth K. Vishnoi

Publication date 10 July 2014

Published in Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.4882, https://semanticscholar.org/paper/abd66255d179e1baa829846cc70392519084f9ae

zbMATH Keywords

combinatoricsgraph theoryspectral methodsdesign and analysis of algorithms

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Analysis of algorithms (68W40) Approximation algorithms (68W25) Approximation by polynomials (41A10) Approximation by rational functions (41A20)

Abstract: We survey key techniques and results from approximation theory in the context of uniform approximations to real functions such as e^{-x}, 1/x, and x^k. We then present a selection of results demonstrating how such approximations can be used to speed up primitives crucial for the design of fast algorithms for problems such as simulating random walks, graph partitioning, solving linear system of equations, computing eigenvalues and combinatorial approaches to solve semi-definite programs.

Recommendations

• Polynomial approximation of functions of matrices and applications
• scientific article; zbMATH DE number 4176354
• Publication:3033207
• Decay bounds and \(O(n)\) algorithms for approximating functions of sparse matrices
• Hierarchical matrices: algorithms and analysis

Cited in

(21)

• Faster exact algorithms for hard problems: A parameterized point of view
• Optimal near-optimality bounds for the Lanczos method for matrix functions
• Query lower bounds for log-concave sampling
• Quantum differential equation solvers: limitations and fast-forwarding
• Faster algorithms for computing Hong's bound on absolute positiveness
• Fast approximate PCPs
• An optimal speedup algorithm for the measure problem
• Pressure-improved Scott-Vogelius type elements
• Fast envelope algorithms
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• A tighter bound for FFd algorithm
• A general method to speed up fixed-parameter-tractable algorithms
• Dynamic study of Schröder's families of first and second kind
• Efficient quantum algorithms for state measurement and linear algebra applications
• scientific article; zbMATH DE number 5050108 (Why is no real title available?)
• Solving sparse linear systems faster than matrix multiplication
• Graph powering and spectral robustness
• scientific article; zbMATH DE number 1929930 (Why is no real title available?)
• Faster algorithms for Schatten-p low rank approximation
• The approximating capability of fast forms
• Approximate Degree, Secret Sharing, and Concentration Phenomena

This page was built for publication: Faster algorithms via approximation theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5167553)