Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: On Axis-Parallel Tests for Tensor Product Codes
event speaker icon
Peter Manohar (Berkeley University)
event date icon
Wednesday, 12.07.2017, 12:30
event location icon
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).