A self-tester for linear functions over the integers with an elementary proof of correctness

DOI10.1007/S00224-015-9639-ZMaRDI QIDQ315532zbMATH OpenOpenAlexFDO

Authors Sheela Devadas, Ronitt Rubinfeld

Publication date 21 September 2016

Published in Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

property testinglinearity testing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Abstract: We present simple, self-contained proofs of correctness for algorithms for linearity testing and program checking of linear functions on finite subsets of integers represented as n-bit numbers. In addition we explore a generalization of self-testing to homomorphisms on a multidimensional vector space. We show that our self-testing algorithm for the univariate case can be directly generalized to vector space domains. The number of queries made by our algorithms is independent of domain size.

Recommendations

• scientific article; zbMATH DE number 1263217
• scientific article; zbMATH DE number 1500524
• scientific article; zbMATH DE number 742944
• On self-testing without the generator bottleneck
• Self-Testing without the Generator Bottleneck

Cites work

• scientific article; zbMATH DE number 1775415 (Why is no real title available?)
• scientific article; zbMATH DE number 742944 (Why is no real title available?)
• A PCP characterization of NP with optimal amortized query complexity
• Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
• Derandomizing homomorphism testing in general groups
• Designing programs that check their work
• Efficient probabilistically checkable proofs and applications to approximations
• Faster integer multiplication
• Gowers uniformity, influence of variables, and PCPs
• Linearity testing in characteristic two
• Multi-linearity self-testing with relative error
• Non-deterministic exponential time has two-prover interactive protocols
• Property testing and its connection to learning and approximation
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Simple analysis of graph tests for linearity and PCP

Cited in

(6)

• scientific article; zbMATH DE number 2086425 (Why is no real title available?)
• scientific article; zbMATH DE number 1418270 (Why is no real title available?)
• Batch checking with applications to linear functions
• On self-testing without the generator bottleneck
• Linear-consistency testing.
• scientific article; zbMATH DE number 742944 (Why is no real title available?)

This page was built for publication: A self-tester for linear functions over the integers with an elementary proof of correctness

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