All reports by Author Inbal Livni Navon:

__
TR18-136
| 1st August 2018
__

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma#### List Decoding with Double Samplers

Revisions: 1

__
TR17-096
| 30th May 2017
__

Irit Dinur, Inbal Livni Navon#### Exponentially Small Soundness for the Direct Product Z-test

__
TR16-205
| 22nd December 2016
__

Amey Bhangale, Irit Dinur, Inbal Livni Navon#### Cube vs. Cube Low Degree Test

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma

We develop the notion of double samplers, first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders.

We show how double samplers give a generic way of amplifying distance in a way that enables ... more >>>

Irit Dinur, Inbal Livni Navon

Given a function $f:[N]^k\rightarrow[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,\dots g_k:[N]\to[M]$ such that $f(x_1,\ldots,x_k)=(g_1(x_1),\dots g_k(x_k))$ for every input $x\in [N]^k$.

This test was introduced by Impagliazzo et. al. (SICOMP 2012), who ...
more >>>

Amey Bhangale, Irit Dinur, Inbal Livni Navon

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 ... more >>>