DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2017.40

Cube vs. Cube Low Degree Test

Authors: Amey Bhangale, Irit Dinur, and Inbal Livni Navon

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract

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.

Cite as

Amey Bhangale, Irit Dinur, and Inbal Livni Navon. Cube vs. Cube Low Degree Test. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 40:1-40:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bhangale_et_al:LIPIcs.ITCS.2017.40,
  author =	{Bhangale, Amey and Dinur, Irit and Livni Navon, Inbal},
  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 =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.40},
  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}
}

Document

DOI: 10.4230/LIPIcs.CCC.2017.29

Exponentially Small Soundness for the Direct Product Z-Test

Authors: Irit Dinur and Inbal Livni Navon

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract

Given a function f:[N]^k->[M]^k, the Z-test is a three query test for checking if a function f is a direct product, namely if there are functions g_1,...g_k:[N]->[M] such that f(x_1,...,x_k)=(g_1(x_1),...,g_k(x_k)) for every input x in [N]^k. This test was introduced by Impagliazzo et. al. (SICOMP 2012), who showed that if the test passes with probability epsilon > exp(-sqrt k) then f is Omega(epsilon) close to a direct product function in some precise sense. It remained an open question whether the soundness of this test can be pushed all the way down to exp(-k) (which would be optimal). This is our main result: we show that whenever f passes the Z test with probability epsilon > exp(-k), there must be a global reason for this: namely, f must be close to a product function on some Omega(epsilon) fraction of its domain. Towards proving our result we analyze the related (two-query) V-test, and prove a "restricted global structure" theorem for it. Such theorems were also proven in previous works on direct product testing in the small soundness regime. The most recent work, by Dinur and Steurer (CCC 2014), analyzed the V test in the exponentially small soundness regime. We strengthen their conclusion of that theorem by moving from an "in expectation" statement to a stronger "concentration of measure" type of statement, which we prove using hyper-contractivity. This stronger statement allows us to proceed to analyze the Z test. We analyze two variants of direct product tests. One for functions on ordered tuples, as above, and another for functions on sets of size k. The work of Impagliazzo et al. was actually focused only on functions of the latter type, i.e. on sets. We prove exponentially small soundness for the Z-test for both variants. Although the two appear very similar, the analysis for tuples is more tricky and requires some additional ideas.

Cite as

Irit Dinur and Inbal Livni Navon. Exponentially Small Soundness for the Direct Product Z-Test. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 29:1-29:50, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dinur_et_al:LIPIcs.CCC.2017.29,
  author =	{Dinur, Irit and Livni Navon, Inbal},
  title =	{{Exponentially Small Soundness for the Direct Product Z-Test}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{29:1--29:50},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.29},
  URN =		{urn:nbn:de:0030-drops-75336},
  doi =		{10.4230/LIPIcs.CCC.2017.29},
  annote =	{Keywords: Direct Product Testing, Property Testing, Agreement}
}

Search Results

Documents authored by Livni Navon, Inbal

Cube vs. Cube Low Degree Test

Abstract

Cite as

Exponentially Small Soundness for the Direct Product Z-Test

Abstract

Cite as

Thanks for your feedback!

Could not send message