דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: On Axis-Parallel Tests for Tensor Product Codes
event speaker icon
פיטר מנוהאר (אונ' ברקלי)
event date icon
יום רביעי, 12.7.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).
[בחזרה לאינדקס האירועים]