Lower bounds by probabilistic arguments

Abstract

The purpose of this paper is to resolve several open problems in the current literature on Boolean circuits, communication complexity, and hashing functions. These lower bound results share the common feature that their proofs utilize probabilistic arguments in an essential way. Specifically, we prove that, to compute the majority function of n Boolean variables, the size of any depth-3 monotone circuit must be greater than 2nε, and the size of any width-2 branching program must have super-polynomial growth. We also show that, for the problem of deciding whether i ≤ j for two n-bit integers i and j, the probabilistic ε-error one-way communication complexity is of order θ(n), while the two-way ε-error complexity is O((log n)2). We will also prove that, to compute i · j mod p for an n-bit prime p, the probabilistic ε-error two-way communication complexity is of order θ(n). Finally, we prove a conjecture of Ullman that uniform hashing is asymptotically optimal in its expected retrieval cost among open address hashing schemes.