Linearity Testing Over the Biased Cube
Explore a comprehensive lecture on linearity testing over the biased cube, presented by Amey Bhangale from The Weizmann Institute of Science at the Simons Institute. Delve into the problem of linearity testing introduced by Blum, Luby, and Rubinfeld, and its applications in constructing efficient probabilistically checkable proofs. Examine the challenges of linearity testing in the p-biased setting compared to the uniform setting. Learn about a novel 4-query p-biased linearity test for p between 1/2 and 2/3, featuring perfect completeness and optimal soundness of 1/2. Understand the analysis of this test, including the structural result for functions correlated to linear functions under random restrictions and a direct product test. Gain insights from this joint work with Subhash Khot and Dor Minzer, which contributes to the broader "Beyond the Boolean Cube" research area.