An optimal tester for k-linear

DOI10.1007/978-3-030-96731-4_17MaRDI QIDQ2154097zbMATH OpenOpenAlexFDO

Authors Nader H. Bshouty

Publication date 13 July 2022

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A brief introduction to property testing
• Algorithmic and analysis techniques in property testing
• Almost optimal distribution-free junta testing
• Distribution-Free Property-Testing
• scientific article; zbMATH DE number 6292744 (Why is no real title available?)
• Improved Bounds for Testing Juntas
• Introduction to Property Testing
• On testing computability by small width OBDDs
• Property testing and its connection to learning and approximation
• Property testing lower bounds via communication complexity
• Property testing. A learning theory perspective
• Robust Characterizations of Polynomials with Applications to Program Testing
• Self-testing/correcting with applications to numerical problems
• Sublinear time algorithms
• Testing juntas
• Testing juntas nearly optimally
• Tight bounds for testing k-linearity

Cited in

(2)

• On Linear Time Minor Tests with Depth-First Search
• Lower bounds for linear degeneracy testing

This page was built for publication: An optimal tester for \(k\)-linear

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