Skip navigation
Please use this identifier to cite or link to this item:
Title: Information Theoretic Relaxations in Complexity Theory
Authors: Garg, Ankit
Advisors: Braverman, Mark
Contributors: Computer Science Department
Keywords: Communication Complexity
Complexity Theory
Information Complexity
Subjects: Computer science
Issue Date: 2016
Publisher: Princeton, NJ : Princeton University
Abstract: Since Shannon’s “A Mathematical Theory of Communication”, information theory has found applicability in a wide range of scientific disciplines. Over the past two decades, information theory has reemerged in theoretical computer science as a mathematical tool with applications to streaming algorithms, data structures, communication complexity etc. Properties of mutual information such as additivity and chain rule play an important role in these applications. In this thesis, we apply information theoretic tools to study various problems in complexity theory. These include the study of information complexity and com- munication complexity, hardness amplification of 2-prover games, applications of quantum information complexity to the study of quantum communication complexity of disjointness and the use of strong data process- ing inequalities to analyze communication complexity of distributed statistical estimation. Along the way, we also develop several information theoretic tools such as correlated sampling theorems, subadditivity properties of information and quantum information cost etc. which could be of independent interest.
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 
Garg_princeton_0181D_11856.pdf1.03 MBAdobe PDFView/Download

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