Abstract | ||
---|---|---|
The problem of tolerant junta testing is a natural and challenging problem which asks if the property of a function having some specified correlation with a k-Junta is testable. In this paper we give an affirmative answer to this question: There is an algorithm which given distance parameters c, d, and oracle access to a Boolean function f on the hypercube, has query complexity exp(k).poly(1/(cd)) and distinguishes between the following cases: 1) The distance of f from any k-junta is at least c; 2) There is a k-junta g which has distance at most d from f. This is the first non-trivial tester (i.e., query complexity is independent of the ambient dimension n) which works for all c and d (bounded by 0.5). The best previously known results by Blais et al., required c to be at least 16d. In fact, with the same query complexity, we accomplish the stronger goal of identifying the most correlated k-junta, up to permutations of the coordinates. We can further improve the query complexity to poly(k/(c-d)) for the (weaker) task of distinguishing between the following cases: 1) The distance of f from any k'-junta is at least c. 2) There is a k-junta g which is at a distance at most d from f. Here k'=poly(k/(c-d)). Our main tools are Fourier analysis based algorithms that simulate oracle access to influential coordinates of functions. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1109/FOCS.2019.00090 | 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | Field | DocType |
Junta testing,Noise operator,Random restrictions | Discrete mathematics,Combinatorics,Permutation,Mathematics | Journal |
Volume | ISSN | ISBN |
abs/1904.04216 | 1523-8288 | 978-1-7281-4953-0 |
Citations | PageRank | References |
0 | 0.34 | 11 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Anindya De | 1 | 239 | 24.77 |
Elchanan Mossel | 2 | 1725 | 145.16 |
Joe Neeman | 3 | 0 | 1.01 |