ECCC-Report TR24-020https://eccc.weizmann.ac.il/report/2024/020Comments and Revisions published for TR24-020en-usWed, 07 Feb 2024 17:58:47 +0200
Revision 1
| Constant Degree Direct Product Testers with Small Soundness |
Mitali Bafna,
Noam Lifshitz,
Dor Minzer
https://eccc.weizmann.ac.il/report/2024/020#revision1Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k))$ for each $k$-face $\sigma$. In an effort to simplify components of the PCP theorem, Goldreich and Safra introduced the problem of direct product testing, which asks whether one can test if $F\colon X(k)\to \{0,1\}^k$ is correlated with a direct product function by querying $F$ on only $2$ inputs. Dinur and Kaufman conjectured that there exist bounded degree complexes with a direct product test in the small soundness regime. We resolve their conjecture by showing that for all $\delta>0$, there exists a family of high-dimensional expanders with degree
$O_{\delta}(1)$ and a $2$-query direct product tester with soundness $\delta$.
We use the characterization given by Bafna and Minzer and independently by Dikstein and Dinur, who showed that some form of non-Abelian coboundary expansion (which they called ``Unique-Games coboundary expansion'') is a necessary and sufficient condition for a complex to admit such direct product testers. Our main technical contribution is a general technique for showing coboundary expansion of complexes with coefficients in a non-Abelian group. This allows us to prove that the high dimensional expanders constructed by Chapman and Lubotzky satisfies the conditions of Bafna and Minzer, thus admitting a 2-query direct product tester with small soundness.
Wed, 07 Feb 2024 17:58:47 +0200https://eccc.weizmann.ac.il/report/2024/020#revision1
Paper TR24-020
| Constant Degree Direct Product Testers with Small Soundness |
Mitali Bafna,
Noam Lifshitz,
Dor Minzer
https://eccc.weizmann.ac.il/report/2024/020Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k))$ for each $k$-face $\sigma$. In an effort to simplify components of the PCP theorem, Goldreich and Safra introduced the problem of direct product testing, which asks whether one can test if $F\colon X(k)\to \{0,1\}^k$ is correlated with a direct product function by querying $F$ on only $2$ inputs. Dinur and Kaufman conjectured that there exist bounded degree complexes with a direct product test in the small soundness regime. We resolve their conjecture by showing that for all $\delta>0$, there exists a family of high-dimensional expanders with degree
$O_{\delta}(1)$ and a $2$-query direct product tester with soundness $\delta$.
We use the characterization given by Bafna and Minzer and independently by Dikstein and Dinur, who showed that some form of non-Abelian coboundary expansion (which they called ``Unique-Games coboundary expansion'') is a necessary and sufficient condition for a complex to admit such direct product testers. Our main technical contribution is a general technique for showing coboundary expansion of complexes with coefficients in a non-Abelian group. This allows us to prove that the high dimensional expanders constructed by Chapman and Lubotzky satisfies the conditions of Bafna and Minzer, thus admitting a 2-query direct product tester with small soundness.
Fri, 02 Feb 2024 03:29:41 +0200https://eccc.weizmann.ac.il/report/2024/020