Checking approximate computations over the reals

DOI10.1145/167088.167288MaRDI QIDQ5248550zbMATH OpenOpenAlexFDO

Authors Sigal Ar, Bruno Codenotti, Peter S. Gemmell, Manuel Blum

Publication date 7 May 2015

Published in Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/167088.167288

Mathematics Subject Classification ID

Numerical linear algebra (65Fxx) Roundoff error (65G50) Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Checking approximate computations of polynomials and functional equations
• Self-testing/correcting with applications to numerical problems
• Approximate testing with error relative to input size.
• Checking properties of polynomials
• Approximate testing with relative error

Cited in

(12)

• Self-testing/correcting with applications to numerical problems
• Approximate testing with error relative to input size.
• Spot-checkers
• Bootstrapping the operator norm in high dimensions: error estimation for covariance matrices and sketching
• Checking approximate computations of polynomials and functional equations
• Checking properties of polynomials
• Program result checking: a new approach to making programs more reliable
• A bootstrap method for error estimation in randomized matrix multiplication
• Self-correcting for function fields of finite transcendental degree
• On black-box verifiable outsourcing
• Sum-check protocol for approximate computations
• A fast randomized algorithm for the approximation of matrices

This page was built for publication: Checking approximate computations over the reals

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