SUM-INDEX 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.68024Sun, Xiaoming 2003 Cited by 1 Author 1 Sun, Xiaoming Cited in 1 Serial 1 Algorithmica Cited in 1 Field 1 Computer science (68-XX) Citations by Year