On Alternating vs. Parity Communication Complexity

We prove that for any O(1)-alternating communication protocol of length L computing a function f and for 0 ! ffi there is a parity communication protocol of length O((L \Gamma log ffi ) O(1) ) computing a function differing from f in at most a ffi -fraction of the inputs. This can be generalized to computations based on arithmetic over any finite field. A consequence is a new proof and improvement of a connection between matrix rigidity over finite fields and alternating communication complexity that was first observed by Razborov [Raz89]. As a side result we prove upper bounds on the rigidity over any field of a 0-1-matrix A in terms of the numbers of constant submatrices required to cover A. Keywords: Communication complexity, Approximation method, Randomized proof of existence, Matrix rigidity 1 Introduction Alternating communication protocols where introduced by Babai et al. [BFS86] and generalize the following base model: Two players share an input (x; y) (where access is res..