swMATH ID: 2935
Software Authors: Sun, Xiaoming
Description: 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.
Homepage: http://link.springer.com/article/10.1007/s00453-002-1007-0
Keywords: Communication complexity; SUM-INDEX function; Communication protocol; Simultaneous model; Circuit lower bound
Related Software:
Cited in: 1 Document

Standard Articles

1 Publication describing the Software, including 1 Publication in zbMATH Year
A 3-party simultaneous protocol for SUM-INDEX. Zbl 1045.68024
Sun, Xiaoming

Cited by 1 Author

1 Sun, Xiaoming

Cited in 1 Serial

1 Algorithmica

Citations by Year