One-Way Communication Complexity and Lower Bounds on Formula Size

Title: One-Way Communication Complexity and Lower Bounds on Formula Size

Abstract: This research investigates the scenarios of probabilistic, nondeterministic, and quantum formulae using one-way communication complexity. It presents a reformulation of the Neˇciporuk method for proving lower bounds on formula size in terms of one-way communication complexity. The main results include:

1. A polynomial size gap between probabilistic/quantum and deterministic formulae. 2. A near-quadratic size gap between nondeterministic formulae with less or more than a (polynomial) threshold on the number of nondeterministic bits. 3. A near-quadratic lower bound on quantum formula size, as well as a polynomial separation between the sizes of quantum formulae with and without multiple read random inputs.

The research also constructs a programmable quantum gate with large success probability to validate the lower bound method. The methods for quantum and probabilistic formulae employ a variant of the Neˇciporuk bound in terms of the VC-dimension.

Implications: This research has significant implications for the field of complexity theory. It provides new methods for proving lower bounds on formula size, which are particularly useful for randomized, nondeterministic, and quantum formulae. The results also contribute to our understanding of the relationship between formula size and circuit depth, and provide insights into the power and limitations of different modes of computation.

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