Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

Revisions: 1

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