The Taub Faculty of Computer Science Events and Talks

Axis-parallel tests are variants of low-degree tests where the input function can only be examined via its restrictions to axis-parallel lines or hyperplanes. In this talk, we present two new results on axis-parallel tests.

(1) We prove the first analogue of the Bivariate Low-Degree Testing Theorem of Polishchuk and Spielman (1994) that works for arbitrarily small agreement. Unlike previous works, our proof techniques are combinatorial, not algebraic.
(2) We improve on the analysis of the axis-parallel hyperplane test previously studied by Viderman (2012) and Ben-Sasson Sudan (2006). Our proof is simpler than previous work.

Joint work with Alessandro Chiesa (UC Berkeley) and Igor Shinkar (UC Berkeley).