# Anindya De: Junta correlation is testable.

#### Speaker

Anindya De

#### Host

Ankur Moitra

Abstract: A Boolean function f on the n-dimensional hypercube is said

to be a k-junta if it is dependent only on some k coordinates of the

input. These functions have been widely studied in the context of

PCPs, learning theory and property testing. In particular, a flagship

result in property testing is that k-juntas can be tested with

\tilde{O}(k) queries -- i.e., there is an algorithm which when given

a black box to f, makes only \tilde{O}(k) queries and decides between

the following two cases:

1. f is a k-junta.

2. f is at least 0.01 far from every k-junta g in Hamming distance.

Surprisingly, the query complexity is completely independent of the

ambient dimension n. In this work, we achieve the same qualitative

guarantee for the noise tolerant version of this problem. In

particular, we give a 2^k query algorithm to distinguish between the

following two cases.

1. f is 0.48-close to some k-junta.

2. f is at least 0.49 far from every k-junta.

The algorithm and its proof of correctness are simple and modular

employing some classical tools like "random restrictions" with

elementary properties of the noise operator on the cube.

Joint work with Elchanan Mossel and Joe Neeman.

to be a k-junta if it is dependent only on some k coordinates of the

input. These functions have been widely studied in the context of

PCPs, learning theory and property testing. In particular, a flagship

result in property testing is that k-juntas can be tested with

\tilde{O}(k) queries -- i.e., there is an algorithm which when given

a black box to f, makes only \tilde{O}(k) queries and decides between

the following two cases:

1. f is a k-junta.

2. f is at least 0.01 far from every k-junta g in Hamming distance.

Surprisingly, the query complexity is completely independent of the

ambient dimension n. In this work, we achieve the same qualitative

guarantee for the noise tolerant version of this problem. In

particular, we give a 2^k query algorithm to distinguish between the

following two cases.

1. f is 0.48-close to some k-junta.

2. f is at least 0.49 far from every k-junta.

The algorithm and its proof of correctness are simple and modular

employing some classical tools like "random restrictions" with

elementary properties of the noise operator on the cube.

Joint work with Elchanan Mossel and Joe Neeman.