Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > KONSTANTIN GOLUBEV:
All reports by Author Konstantin Golubev:

TR19-139 | 8th October 2019
Irit Dinur, Konstantin Golubev

Direct sum testing - the general case


A function f:[n_1] x ... x [n_d]-->F is a direct sum if it is of the form f(a_1,...,a_d) = f_1(a_1) + ... + f_d (a_d) (mod 2) for some d functions f_i:[n_i]-->F_i for all i=1,...,d. We present a 4-query test which distinguishes between direct sums and functions that are ... more >>>




ISSN 1433-8092 | Imprint