M.Sc Thesis

M.Sc StudentAharoni Eldar
SubjectDirect Sum Related Problems in Communication Complexity
DepartmentDepartment of Computer Science
Supervisor PROF. Eyal Kushilevitz
Full Thesis textFull thesis text - English Version


We study the direct-sum problem and relaxations of it, in different models of communication complexity. We show positive results for the direct-sum problem for k-party “Number On the Forehead” (NOF) deterministic communication complexity, showing that the complexity of computing a function f  in this model, on l instances, may be significantly cheaper than l times the complexity of computing  f on a single instance. Quite surprisingly, we show that this is the case for “most” (boolean, k-argument) functions.

We generalize the NOF model in a new model, NOFG, which offers a more general notion of which input is seen by which parties. We formalize sufficient conditions on a NOFG protocol Q, for a single instance, which guarantees some communication complexity savings when appropriately extending Q to work on l instances, in the NOF model. We give specific examples to the uses of this method. We also perform a similar task on the one way-myopic NOF model. In all cases, the tool that we use is “multiplexing”: we combine messages sent in parallel executions of protocols for a single instance, into a single message for the multi-instance (direct-sum) case, by xoring them with each other.

Next, we define a relaxation of direct-sum, termed APP operator, which requires solving l instances of a function, with at most d mistakes. We study this operator within different models of communication complexity (both two-party and multi-party), and give upper and lower bounds on the communication complexity of specific and general functions.

Finally, we revisit the previously studied operator CHOOSE, and consider a variant of it, in the NOF model.