Title: New Lower Bounds in Complexity via Information Theory
Advisor: Anup Rao
Supervisory Committee: Anup Rao (Chair), Sreeram Kannan (GSR, EE), Paul W. Beame, and Dan Suciu
Abstract: In recent years, tools in information theory have been used extensively to solve some long-
standing open problems in complexity theory. In this proposal, we apply information-theoretic
tools to prove new lower bounds in different computational models:
1. We initiate the study of direct-sum questions in the model of streaming algorithms and prove
some initial results in this direction.
2. We introduce a new communication lower bound method which gives a simpler proof of the
recent result of Ganor, Kol and Raz (STOC '15) proving an exponential separation between
information complexity and communication complexity.
3. We propose to prove lower bounds on the size of approximate linear programming formulations
for some well-known optimization problems. In this direction, we discuss our efforts towards
proving a tight lower bound for approximate extended formulations for the matching polytope
by showing connections to lopsided unique disjointness.