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

Anything in here will be replaced on browsers that support the canvas element

References in zbMATH (referenced in 1 article , 1 standard article )

Showing result 1 of 1.
Sorted by year (citations)

  1. Sun, Xiaoming: A 3-party simultaneous protocol for SUM-INDEX (2003)