All reports by Author Gautam Prakriya:

__
TR20-164
| 9th November 2020
__

Andrej Bogdanov, Gautam Prakriya#### Direct Sum and Partitionability Testing over General Groups

Revisions: 1

Andrej Bogdanov, Gautam Prakriya

A function $f(x_1, \dots, x_n)$ from a product domain $\mathcal{D}_1 \times \cdots \times \mathcal{D}_n$ to an abelian group $\mathcal{G}$ is a direct sum if it is of the form $f_1(x_1) + \cdots + f_n(x_n)$. We present a new 4-query direct sum test with optimal (up to constant factors) soundness error. ... more >>>