Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > FUNCTION PARTITIONABILITY:
Reports tagged with function partitionability:
TR20-164 | 9th November 2020
Andrej Bogdanov, Gautam Prakriya

#### Direct Sum and Partitionability Testing over General Groups

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

ISSN 1433-8092 | Imprint