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

DOI10.1007/S00224-015-9639-ZzbMATH Open1350.68284arXiv1412.5484OpenAlexW2131697455MaRDI QIDQ315532FDOQ315532

Authors: Sheela Devadas, Ronitt Rubinfeld 

Publication date: 21 September 2016

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

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.

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

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

zbMATH Keywords

property testinglinearity testing

Mathematics Subject Classification ID

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

Cites Work

• Faster integer multiplication
• Property testing and its connection to learning and approximation
• Self-testing/correcting with applications to numerical problems
• Linearity testing in characteristic two
• Robust Characterizations of Polynomials with Applications to Program Testing
• Non-deterministic exponential time has two-prover interactive protocols
• Designing programs that check their work
• Gowers uniformity, influence of variables, and PCPs
• 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
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Simple analysis of graph tests for linearity and PCP
• Efficient probabilistically checkable proofs and applications to approximations
• Multi-linearity self-testing with relative error

Cited In (5)

• Linear-consistency testing.
• Title not available (Why is that?)
• Batch checking with applications to linear functions
• Title not available (Why is that?)
• Title not available (Why is that?)

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)