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

combinatoricsdesign and analysis of algorithmsgraph theoryspectral methods

Mathematics Subject Classification ID

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

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)

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

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)