Skip navigation
Please use this identifier to cite or link to this item:
Title: Interactive Information Complexity and Applications
Authors: Weinstein, Omri
Advisors: Braverman, Mark
Contributors: Computer Science Department
Keywords: Circuit Complexity
Communication Complexity
Information Theory
Subjects: Computer science
Issue Date: 2015
Publisher: Princeton, NJ : Princeton University
Abstract: With applications in nearly every field of computer science, Communication Complexity constitutes one of the most useful methods for proving unconditional lower bounds - the holy grail of complexity theory. Developing tools in communication complexity is a promising approach for making progress in other computational models such as streaming, property testing, distributed computing, circuit complexity and data structures. One striking example of such tool is Shannon's information theory, introduced in the late 1940's in the context of the one way data transmission problem. While revealing the intimate connection between information and communication, Shannon's work and its classical extensions do not readily convert to interactive setups such as the communication complexity model, where two parties must engage in a multi-round conversation to accomplish some desirable interactive task. The research presented in this monograph aspires to extend Shannon's theory, develop the right tools, and understand how information behaves in interactive setups. The main measure if interest is the Interactive Information Complexity of a function, which informally captures the least amount of information the parties need to disclose each other about their inputs in order to solve the underlying task. We develop information-theoretic tools with applications to some of the most fundamental questions in communication complexity, including the limits of parallel computation, interactive compression, and the KRW conjecture. We then demonstrate the power of information complexity beyond communication complexity, with applications to various theoretical models, including data streaming, circuit lower bounds, privacy and economics. Lurking beneath these results is the fascinating question about the role of interaction and information in obtaining efficient outcomes, where efficiency may be measured in terms of social welfare, space, privacy or communication, depending on the model and context.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Computer Science

Files in This Item:
File Description SizeFormat 
Weinstein_princeton_0181D_11259.pdf911.32 kBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.