Junta Correlation is Testable

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.

Authors

• Anindya De
• Elchanan Mossel
• Joe Neeman

Keywords

• Complexity theory
• Testing
• Correlation
• Standards
• Boolean functions
• Task analysis
• Computer science
• Test Problems
• Distance Parameter
• Boolean Function
• Markov Chain
• Authoritarian
• Random Walk
• Correction Algorithm
• Fourier Series
• Probability 1
• Error Correlation
• Fourier Coefficients
• Loop Iteration
• Average Procedure
• Setting Of Theorem
• Confidence Parameter
• Junta testing
• Noise operator
• Random restrictions