In this work, we introduce clean, purely information theoretic space-bounded com- munication complexity models. In our new general space-bounded communication model, unlike in classical communication complexity models, the players only have limited space to compress previous communication history. The players remain all- powerful when performing local computation, the same as in classical models. We also introduce restricted variants of this general model, in particular the limited-memory communication model and the memoryless communication model. In these models the communication is one-way and the players are constrained in the way they utilize their limited memory. We show several basic properties about these new models, in particular that the limited-memory communication model can simulate the general space-bounded two-way communication model with moderate overhead. We introduce a new combinatorial concept called rectangle overlay, which nat- urally generalizes the rectangle partition and rectangle cover concepts in classical communication complexity. This concept fully characterizes our memoryless commu- nication model.
Our new space-bounded communication models provide several new characteriza- tions and new lower bound techniques for the study of the communication complexity polynomial hierarchy [7]. This communication analog of the Turing machine poly- nomial hierarchy has recently attracted a lot of attention because of its newly found technical connection with its Turing machine counterpart [2, 18]. In particular, our rectangle overlay concept fully characterizes ${P^{NP}}^{cc}$, the communication analog of the oracle Turing machine complexity class P^NP . It is the first combinatorial charac- terization of ${P^{NP}}^{cc}$ and it properly conceptualizes and strengthens previously known separation results concerning ${P^{NP}}^{cc}$ . We also provide the first characterization of the $PSPACE^{cc}$ complexity class, the communication analog of $PSPACE$, in terms of a natural space notion.
We show equivalences and separations to other models (e.g. the garden-hose model [16], bounded-width branching programs, etc.), unify and extend techniques appeared in [28] and [10] regarding previously proposed space-bounded communica- tion models, all under the same models we introduce.
Table of Contents
Notations and Symbols
1 Introduction
1.1 Philosophy: the “Information-Theoretic” Approach
1.2 Conceptual Contributions: Space-Bounded Communication Models
1.2.1 The General Model
1.2.2 The Restricted Variants: Main Contribution
1.3 Technical Contributions
1.3.1 Applications: New Tools and New Paradigms
1.3.2 One-Way Communication versus Two-Way Communication
1.3.3 More Lower Bounds and Protocols
2 Overview of Standard Models of Computation
2.1 Classical Communication Complexity
2.1.1 The Deterministic Model
2.1.2 The Nondeterministic Model
2.1.3 The Randomized Model
2.1.4 Communication Matrices
2.2 The Communication Complexity Polynomial Hierarchy
2.3 Boolean Circuits
2.4 Branching Programs
3 The General Space-Bounded Communication Model
3.1 Model Definition
3.2 Connections to Space-Bounded Turing Machines
3.3 Connections to the Garden-Hose Model
3.4 Connections to Communicating Branching Programs
3.5 Space Lower Bound Results
3.5.1 The Boolean Case
3.5.2 The Non-Boolean Case
4 Overlays and the Memoryless Communication Model
4.1 Definitions
4.1.1 The Memoryless Model
4.1.2 Rectangle Overlay
4.2 Memory Hierarchy Theorems
4.3 Overlay and the Memoryless Model
4.4 ${P^{NP}}^{cc}$ and the Memoryless Model
4.5 Overlay Lower Bounds
4.5.1 Combinatorial Lower Bound Technique
4.5.2 Applications of the Lower Bound Technique
4.5.3 Proof of Lemma 4.12
4.6 Protocol Composition
5 The Limited-Memory Communication Model
5.1 Definitions
5.1.1 Alternative Definition in Terms of Semi-Oblivious Space
5.1.2 Randomized Variants
5.2 Techniques for Constructing Efficient Protocols
5.2.1 Proof of Lemma 5.3
5.3 Comparison with Bounded-Width Branching Programs
5.4 Comparison with the General Two-way Model
5.5 Connections to the Communication Complexity Polynomial Hierarchy
5.5.1 3 Memory States and $PH^{cc}$
5.5.2 5 Memory States and $PSPACE^{cc}$
6 Some Remarks on Randomized Memoryless Lower Bound
6.1 Prerequisites: Fourier Analysis for Boolean Functions
6.2 Lower Bounds in Restricted Cases
6.3 Going Forward
6.3.1 $P_{3}$-Protocols: Repertoire Containing All Parity Functions
6.3.2 $P_{4}$-protocols: Repertoire Containing an Arbitrary Fourier Basis
6.3.3 $P_{5}$-protocols: Arbitrary Repertoire
Bibliography