Communication Complexity and Circuit Complexity

University Of Texas At Austin, Austin TX

Investigators

Abstract

A major challenge in complexity theory is to prove lower bounds on the number of steps necessary to compute a given function in general computational models. It would be important to have techniques that help to find out what is the most efficient solution we can hope to achieve for specific problems. There are methods for proving strong lower bounds for restricted versions of some important models of computation. However, there are no known techniques powerful enough to prove strong lower bounds on the intrinsic complexity of specific computational problems. The long term objective of the proposed research is finding new methods for proving complexity lower bounds and identifying mathematical properties of Boolean functions that determine their computational complexity. The specific plan of research outlined in the proposal involves the analysis of problems in various computational models, such as the cell probe model, branching programs, span programs, and multiparty communication protocols. All the models considered in the proposal are related to some important computational resource. Thus proving strong lower bounds on the complexity of specific Boolean functions in the unrestricted versions of any of these models would represent significant progress towards better understanding the inherent complexity of computational tasks. Because of the connections of these models to the Boolean circuit model, several of the problems and approaches considered may potentially provide new techniques to attack fundamental open problems in complexity theory. The problems considered in the proposal are also interesting on their own right from the point of view of various applications, including cryptographic applications such as secret sharing schemes, private multiparty computation, and data structures. A common theme of the problems considered in the proposal is their connection to communication complexity. Several of the known lower bound techniques in different models are based on techniques related to communication complexity. The proposed research plans to explore these connections further.