One-Way Communication Complexity and Formula Size

Title: One-Way Communication Complexity and Formula Size

Abstract: This research investigates the relationship between one-way communication complexity and the size of formulae in various scenarios, including probabilistic, nondeterministic, and quantum formulae. The study uses the Neˇciporuk method, a technique for proving lower bounds on the size of Boolean formulae, and applies it to the context of one-way communication complexity. The main results include polynomial size gaps between probabilistic/quantum and deterministic formulae, near-quadratic size gaps for nondeterministic formulae with limited access to nondeterministic bits, and near-quadratic lower bounds on quantum formula size. The research also presents optimal separations between one-way and two-way protocols for limited nondeterminism and quantum communication, and shows that zero-error quantum one-way communication complexity asymptotically equals deterministic one-way communication complexity for total functions.

Research Question: Can we use one-way communication complexity to provide lower bounds on the size of formulae in various scenarios, including probabilistic, nondeterministic, and quantum formulae?

Methodology: The study uses the Neˇciporuk method, a technique for proving lower bounds on the size of Boolean formulae, and applies it to the context of one-way communication complexity. The research considers formulae with arbitrary gates of fan-in two and applies the technique to randomized, nondeterministic, and quantum formulae.

Results: The study presents the following key results:

1. Polynomial size gaps between probabilistic/quantum and deterministic formulae. 2. Near-quadratic size gaps for nondeterministic formulae with limited access to nondeterministic bits. 3. Near-quadratic lower bounds on quantum formula size. 4. Polynomial separation between the sizes of quantum formulae with and without multiple read random inputs. 5. Optimal separations between one-way and two-way protocols for limited nondeterminism and quantum communication. 6. Zero-error quantum one-way communication complexity asymptotically equals deterministic one-way communication complexity for total functions.

Implications: The research has significant implications for the field of complexity theory, as it provides new methods for proving lower bounds on the size of formulae in various scenarios, including probabilistic, nondeterministic, and quantum formulae. The study also contributes to the understanding of one-way communication complexity and its applications in the context of formula size.

Link to Article: https://arxiv.org/abs/0111062v2 Authors: arXiv ID: 0111062v2