Efficiently Testing Sparse <Emphasis Type="Italic">GF</Emphasis>(2) Polynomials |
| |
Authors: | Ilias Diakonikolas Homin K Lee Kevin Matulef Rocco A Servedio Andrew Wan |
| |
Affiliation: | (2) Ben-Gurion University, Beer Sheva, Israel;(3) University of Torino, Torino, Italy;(4) Technion, Haifa, Israel;(5) Department of Computer Science, University of Roma, Rome, Italy |
| |
Abstract: | We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function f:{0,1}
n
→{−1,1} is an s-sparse GF(2) polynomial versus ε-far from every such polynomial. Our algorithm makes poly(s,1/ε) black-box queries to f and runs in time n⋅poly(s,1/ε). The only previous algorithm for this testing problem (Diakonikolas et al. in Proceedings of the 48th Annual Symposium on
Foundations of Computer Science, FOCS, pp. 549–558, 2007) used poly(s,1/ε) queries, but had running time exponential in s and super-polynomial in 1/ε. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|