Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EXTREMAL GRAPH THEORY:
Reports tagged with extremal graph theory:
TR17-110 | 22nd June 2017
Alessandro Chiesa, Peter Manohar, Igor Shinkar

On Axis-Parallel Tests for Tensor Product Codes

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests.

In this paper we study a test introduced by Ben-Sasson and Sudan in 2006 that ... more >>>




ISSN 1433-8092 | Imprint