Abstract
The problem of linearity testing was introduced by Blum, Luby and Rubinfeld. In linearity testing, given a query access to a Boolean function f : {0,1}^n-> {0,1}, we need to decide if f is a linear function or if f is far from every linear function. These tests are useful in constructing efficient probabilistically checkable proofs.
While we have efficient linearity tests in the uniform setting (where each query is uniformly distributed), the situation in the p-biased setting (where each query is distributed according to the p-biased measure for a fixed p\in (0,1)) is not fully understood. In this talk, I will discuss a 4-query p-biased linearity test where p\in (1/2, 2/3). The test has perfect completeness and optimal soundness of 1/2.
The analysis of the test uses a structural result for functions that are correlated to linear functions under random restrictions, as well as a certain direct product test which will be of independent interest.
Based on joint work with Subhash Khot and Dor Minzer.