A 3-party simultaneous protocol for SUM-INDEX. We show that the SUM-INDEX function can be computed by a 3-party simultaneous protocol in which one player sends only O(nɛ) bits and the other sends O(n1-C(ɛ)) bits (0<C(ɛ)<1 ). This implies that, in the Valiant—Nisan—Wigderson approach for proving circuit lower bounds, the SUM-INDEX function is not suitable as a target function.
Keywords for this software
References in zbMATH (referenced in 1 article , 1 standard article )
Showing result 1 of 1.