Name
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 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 $xin mathbf{F}^m$, and checks that the assignments to the cubes agree with each other on the point $x$. 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 ge poly(d)/{mathbf{F}}^{1/2}$, where $d$ is the degree. This should be compared to the previously best soundness value of $epsilon ge poly(m, d)/mathbf{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. 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. |
Year | Venue | DocType |
|---|---|---|
2016 | ITCS | Journal |
Citations | PageRank | References |
1 | 0.37 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amey Bhangale | 1 | 10 | 6.71 |
| Irit Dinur | 2 | 1187 | 85.67 |
| Inbal Livni Navon | 3 | 1 | 0.37 |