caa a22 4500 445805242 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111101xx s 000 0 eng 10.1007/s00453-010-9426-9 doi (NATIONALLICENCE)springer-10.1007/s00453-010-9426-9 Efficiently Testing Sparse GF (2) Polynomials [Elektronische Daten] [Ilias Diakonikolas, Homin Lee, Kevin Matulef, Rocco Servedio, Andrew Wan] 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 in1/ε. Our approach significantly extends the "testing by implicit learning” methodology of Diakonikolas et al. (Proceedings of the 48th Annual Symposium on Foundations of Computer Science, FOCS, pp.549-558, 2007). The learning component of that earlier work was a brute-force exhaustive search over a concept class to find a hypothesis consistent with a sample of random examples. In this work, the learning component is a sophisticated exact learning algorithm for sparse GF(2) polynomials due to Schapire and Sellie (J. Comput. Syst. Sci. 52(2):201-213, 1996). A crucial element of this work, which enables us to simulate the membership queries required by Schapire and Sellie (J. Comput. Syst. Sci. 52(2):201-213, 1996), is an analysis establishing new properties of how sparse GF(2) polynomials simplify under certain restrictions of "low-influence” sets of variables. Springer Science+Business Media, LLC, 2010 Property testing nationallicence GF (2) polynomials nationallicence Sparse polynomials nationallicence Randomized algorithms nationallicence Diakonikolas Ilias Columbia University, New York, NY, USA aut Lee Homin University of Texas, Austin, TX, USA aut Matulef Kevin Tsinghua University, Beijing, China aut Servedio Rocco Columbia University, New York, NY, USA aut Wan Andrew Columbia University, New York, NY, USA aut Algorithmica Springer-Verlag 61/3(2011-11-01), 580-605 0178-4617 61:3<580 2011 61 453 https://doi.org/10.1007/s00453-010-9426-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9426-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Diakonikolas Ilias Columbia University, New York, NY, USA aut NATIONALLICENCE 700 1- Lee Homin University of Texas, Austin, TX, USA aut NATIONALLICENCE 700 1- Matulef Kevin Tsinghua University, Beijing, China aut NATIONALLICENCE 700 1- Servedio Rocco Columbia University, New York, NY, USA aut NATIONALLICENCE 700 1- Wan Andrew Columbia University, New York, NY, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/3(2011-11-01), 580-605 0178-4617 61:3<580 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer