Communication Complexity, Proof Complexity, and Approximation

University Of Washington, Seattle WA

Investigators

Abstract

This proposal encompasses three main subjects of research within the general field of computational complexity. They consider (1) communication complexity: the measure of the amount of information required by computationally unbounded entities in a distributed environment to compute shared functions of inputs that are not available to all entities, and (2) proof complexity: the complexity of expressing proofs of propositional logic tautologies (and unsatisfiable formulas) as a function of the size of these tautologies. Approximation plays a role in the research in both of these areas. Intellectual Merits Tradeoffs between the time and space used to solve computational problems are fundamental in computational complexity. In many instances one can save space by employing more time to recompute intermediate results rather than storing them. Moreover, the relationship between time and space is one of the major open questions in computational complexity. One of the most important is whether or not every efficiently-solvable problem can be solved using small space. Computational complexity is the key to the best methods of analysis for time-space tradeoffs but more powerful models of computational complexity are required to analyze comptutation at a finer-grained level. Massive data sets have become ubiquitous and are growing faster than random access memories. To handle these massive data sets efficiently, algorithms must use the fact that data can typically be transferred more quickly sequentially. Moreover, as in the internet context, the data can be evanescent. These features have led to the study of streaming algorithms which compute properties of datasets based on a single sweep through the unordered data. To keep the space requirements of these algorithms small and feasible, the answers produced are necessarily approximations. Analysis of communication complexity has been the major tool for studying streaming algorithms but existing results on approximation problems are very limited. By Cook's theorem, the existence of proof systems whose proofs are polynomially-bounded in the sizes of the input formulas is equivalent to NP = coNP. Although such an understanding is the ultimate goal of proof complexity, proof complexity also has many applications in the design of inference systems that are useful in practice and important for understanding the complexity of NP-hard problems. Research Topics The proposed research encompasses all three of these areas: (1) research on new models of communication complexity with the goal of obtaining stronger time-space tradeoff lower bounds. (2) research on a systematic study of approximation problems in communication complexity with the goal of obtaining bounds for a wider variety of problems using streaming (and related) algorithms. (3) research on proof complexity including the use of proof complexity in analyzing approximation algorithms, connections to communication complexity, search algorithms on satisfiable instances (including random instances), and more powerful inferencing algorithms. Broader Impact The proposed research on proof complexity has direct relevance to algorithms for satisfiability search and general automated inference, tasks which are major tools in AI and formal verification. Researchers in statistical physics and AI have suggested a strong connection between the properties of phase transitions in random problems and their associated computational complexity. Recent research on proof complexity by the PI and others has shed light on the connections between these areas. The PI has a record of interactions with researchers in statistical physics and AI. The proposed research will continue work on briding the gap between the methodologies of statistical physics, combinatorics and theoretical computer science and will encourage the cross-fertilization of ideas. Communication complexity is so fundamental that it necessarily impacts a broad range of topics within computer science. The list of impacts of the known techniques already encompasses applications ranging from properties of OBDDs used in formal verification to the efficiency of VLSI layout to streaming algorithms in database systems. The proposed research on the communication complexity of approximation problems will yield a body of results for application to streaming algorithms and will permit the extension of these notions to graphics pipelines as well.