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

(15)

• Dynamic study of Schröder's families of first and second kind
• scientific article; zbMATH DE number 5050108 (Why is no real title available?)
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• An optimal speedup algorithm for the measure problem
• Graph powering and spectral robustness
• Efficient quantum algorithms for state measurement and linear algebra applications
• Fast approximate PCPs
• Faster exact algorithms for hard problems: A parameterized point of view
• The approximating capability of fast forms
• Faster algorithms for computing Hong's bound on absolute positiveness
• scientific article; zbMATH DE number 1929930 (Why is no real title available?)
• Fast envelope algorithms
• Approximate Degree, Secret Sharing, and Concentration Phenomena
• A tighter bound for FFd algorithm
• A general method to speed up fixed-parameter-tractable algorithms

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)