License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.40
URN: urn:nbn:de:0030-drops-81748
Go to the corresponding LIPIcs Volume Portal

Bhangale, Amey ; Dinur, Irit ; Livni Navon, Inbal

Cube vs. Cube Low Degree Test

LIPIcs-ITCS-2017-40.pdf (0.6 MB)


We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. In this test the tester has access to a "cubes table" which assigns to every cube a low degree polynomial. The tester randomly selects two cubes (affine sub-spaces of dimension 3) that intersect on a point x in F^m, and checks that the assignments to the cubes agree with each other on the point x. Our main result is a new combinatorial proof for a low degree test that comes closer to the soundness limit, as it works for all epsilon >= poly(d)/{|F|}^{1/2}, where d is the degree. This should be compared to the previously best soundness value of epsilon >= poly(m, d)/|F|^{1/8}. Our soundness limit improves upon the dependence on the field size and does not depend on the dimension of the ambient space.

Our proof is combinatorial and direct: unlike the Raz-Safra proof, it proceeds in one shot and does not require induction on the dimension of the ambient space. The ideas in our proof come from works on direct product testing which are even simpler in the current setting thanks to the low degree.

Along the way we also prove a somewhat surprising fact about connection between different agreement tests: it does not matter if the tester chooses the cubes to intersect on points or on lines: for every given table, its success probability in either test is nearly the same.

BibTeX - Entry

  author =	{Amey Bhangale and Irit Dinur and Inbal Livni Navon},
  title =	{{Cube vs. Cube Low Degree Test}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{40:1--40:31},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-81748},
  doi =		{10.4230/LIPIcs.ITCS.2017.40},
  annote =	{Keywords: Low Degree Test, Probabilistically Checkable Proofs, Locally Testable Codes}

Keywords: Low Degree Test, Probabilistically Checkable Proofs, Locally Testable Codes
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI