Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > GAUTAM PRAKRIYA:
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

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