Approximate testing with error relative to input size.

DOI10.1016/S0022-0000(03)00004-7MaRDI QIDQ1400577zbMATH OpenOpenAlexFDO

Authors Frédéric Magniez, Miklos Santha, Marcos Kiwi

Publication date 13 August 2003

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0022-0000(03)00004-7

zbMATH Keywords

Program verificationApproximation errorRobustness and stability of functional equationsSelf-testing programs

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Approximate testing with relative error
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Sub-constant error low degree test of almost-linear size
• On the Complexity of Estimating the Size of a Test Set
• Approximate testing and its relationship to learning
• A testing approach to estimation
• Approximate testing equivalence based on time, probability, and observed behavior
• Improving on exact tests by approximate conditioning

Cites work

• scientific article; zbMATH DE number 4191094 (Why is no real title available?)
• scientific article; zbMATH DE number 4213418 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 599025 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1500524 (Why is no real title available?)
• scientific article; zbMATH DE number 742944 (Why is no real title available?)
• A representation theorem for $(X_1-1)(X_2-1)...(X_n-1)$ and its applications
• Approximate homomorphisms
• Checking approximate computations over the reals
• Designing programs that check their work
• Functions with bounded nth differences
• Hyers-Ulam stability of functional equations in several variables
• Local stability of the functional equation characterizing polynomial functions
• On the Behavior of Mappings which do not Satisfy Hyers-Ulam Stability
• On the Robustness of Functional Equations
• On the Stability of the Linear Functional Equation
• On the Stability of the Linear Mapping in Banach Spaces
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems

Cited in

(6)

• Approximate testing with relative error
• Checking approximate computations over the reals
• Checking approximate computations of polynomials and functional equations
• The complexity of error metrics
• Input-Thrifty Extrema Testing
• Approximate testing and its relationship to learning

This page was built for publication: Approximate testing with error relative to input size.

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