Faster algorithms via approximation theory

DOI10.1561/0400000065zbMATH Open1333.68296arXiv1309.4882OpenAlexW2064769982MaRDI QIDQ5167553FDOQ5167553

Sushant Sachdeva, Nisheeth K. Vishnoi

Publication date: 10 July 2014

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

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.

Full work available at URL: https://arxiv.org/abs/1309.4882

Recommendations

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

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)

Cited In (15)

• Faster algorithms for computing Hong's bound on absolute positiveness
• Fast approximate PCPs
• An optimal speedup algorithm for the measure problem
• Fast envelope algorithms
• Graph Powering and Spectral Robustness
• 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
• Title not available (Why is that?)
• Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision
• Title not available (Why is that?)
• The approximating capability of fast forms
• Approximate Degree, Secret Sharing, and Concentration Phenomena
• Faster exact algorithms for hard problems: A parameterized point of view

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)