----------------------- REVIEW 1 --------------------- PAPER: 10 TITLE: Multiparty Equality Function Computation in Networks with Point-to-Point Links AUTHORS: Guanfeng Liang and Nitin Vaidya OVERALL RATING: 3 (strong accept) The notion of communication complexity (CC) was introduced by Yao in 1979 [3]. He investigated the problem involving two parties (Alice and Bob) that want to mutually compute a Boolean function that is defined on pairs of inputs. CC became since then an important research area. The notion of CC has been generalized to a multiparty setting, i.e., when the number of parties > 2, where the communication is performed by a broadcast mechanism. In this paper, the authors consider a point-to-point communication model, in which nodes communicate over private point-to-point links. They argue that this model makes the problem significantly different from the ones with the broadcast communication model. They study the CC complexity of the MEQ problem under the point-to-point communication model, where the parties have to detect if their inputs are different or equal. The paper proposes an interesting research line, offering some initial interesting results, although not particularly difficult but well written. My main concern is the discussion of related work. CC is a mature research area, where many papers have been published. The paper cites only three references. Even in SIROCCO a related paper has appeared before, its journal version is: Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum: Exact communication costs for consensus and leader in a tree. J. Discrete Algorithms 1(2): 167-183 (2003) ----------------------- REVIEW 2 --------------------- PAPER: 10 TITLE: Multiparty Equality Function Computation in Networks with Point-to-Point Links AUTHORS: Guanfeng Liang and Nitin Vaidya OVERALL RATING: 2 (accept) The result is neat and I like it, although it is somewhat narrow in terms of applicability. I am very looking forward to a general result. A serious drawback of this paper is that it does not contain a survey of related works and a description how the authors place its work in the context of SIROCCO. If the paper is accepted and the authors have a chance to revise it, I strongly suggest them to create a subsection for them. ----------------------- REVIEW 3 --------------------- PAPER: 10 TITLE: Multiparty Equality Function Computation in Networks with Point-to-Point Links AUTHORS: Guanfeng Liang and Nitin Vaidya OVERALL RATING: 0 (borderline paper) In this paper, the authors study the communication complexity of a problem that they call Multiparty Equality Function Computation (MEQ). Each node of a network starts with one value from a set of initial values and the goal is to determine if all of the initial values are the same by sending information over the links of the network. Communication complexity in this paper is not the same as the usual broadcast model because a message transmitted over a link is only received by the node at the other end of the link. I like this paper. The technique that involves flipping the directions of links in section 4 is very interesting and so are the constructions in later sections. The paper is nicely organized and quite readable. The results are non-trivial and fit well into the scope of SIROCCO. Unfortunately, there is a major problem with this paper. The authors have provided almost no context for their work. The only references are two old papers (1979 and 1983) that are not very closely related to the subject of the paper, and a textbook on computational complexity. The MEQ problem is the same as the Set Disjointness problem which has been studied in several recent papers and it is very similar to versions of the Consensus problem which have been widely studied. Neither of these problems is mentioned in the paper. I am not an expert on communication complexity, so I am not confident that I can judge the novelty or significance of this work in the absence of any context. However, it seems pretty clear that the bibliography and survey of related work are inadequate. The addition of a section discussing related work and placing this paper in context should be a condition of any decision to accept this paper to SIROCCO. ----------------------- REVIEW 4 --------------------- PAPER: 10 TITLE: Multiparty Equality Function Computation in Networks with Point-to-Point Links AUTHORS: Guanfeng Liang and Nitin Vaidya OVERALL RATING: -1 (weak reject) This paper studies the communication complexity of the problem of determining by $n$ parties whether the input values of all the parties (integers from the range $[1,K]$) are identical, under a point-to-point model of communication. Whereas this is a potentially interesting topic, I believe the paper in its present form requires substantial modifications before it is fit for publication at SIROCCO: * The authors do not set their work in any context, not mentioning any of the related work in the area (in different communication models) which has appeared in the last 30 years. The paper has exactly 3 references, two of which are 3 decades old, and one of which is a handbook. Apart from this (and less importantly), no effort is made to describe the problem in a way which would be of interest to a distributed computing audience. The authors should mention secure/cryptographic approaches to multiparty equality computation, as well as links to the consensus problem, the [Socialist] Millionaires' Problem, and the like. * The contribution appears to be very limited, with no results explicitly stated for general values of $n$ -- the results only concern the case of $n=3$. The result probably generalizes to larger values of $n$ with some small gain on communication complexity; the authors should comment on this. * The fact that the improved complexity holds for all $K$ should be highlighted in the abstract and introduction. * Some discussion of potential lower bounds in the area would make the paper more valuable (is the result tight?) If the paper is accepted for presentation SIROCCO, the authors should definitely set the result in its scientific context more firmly, taking into account all of the above comments.