Tight Bounds for Testing k-Linearity
From MaRDI portal
Publication:3167415
DOI10.1007/978-3-642-32512-0_37zbMath1372.68111OpenAlexW970692799MaRDI QIDQ3167415
Publication date: 2 November 2012
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-32512-0_37
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items (10)
An adaptivity hierarchy theorem for property testing ⋮ An optimal tester for \(k\)-linear ⋮ An optimal tester for \(k\)-Linear ⋮ On Active and Passive Testing ⋮ The complexity of computing (almost) orthogonal matrices with \(\varepsilon\)-copies of the Fourier transform ⋮ Almost Optimal Testers for Concise Representations. ⋮ Property testing lower bounds via a generalization of randomized parity decision trees ⋮ Property testing lower bounds via communication complexity ⋮ Almost optimal distribution-free junta testing ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable
This page was built for publication: Tight Bounds for Testing k-Linearity
