×

A 3-party simultaneous protocol for SUM-INDEX. (English) Zbl 1045.68024

Summary: We show that the SUM-INDEX function can be computed by a 3-party simultaneous protocol in which one player sends only \(O(n^\varepsilon)\) bits and the other sends \(O(n^{1-C(\varepsilon)})\) bits (\(0<C(\varepsilon)<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.

MSC:

68M12 Network protocols

Software:

SUM-INDEX
Full Text: DOI