The Taub Faculty of Computer Science Events and Talks

Can preprocessing help reduce computational costs? We study this question in the context of communication complexity, focusing on a simple "simultaneous messages" setting in which computationally unbounded Alice and Bob each send a single message to a computationally bounded Carol. A big part of our work concentrates on the task of computing the inner product function modulo 2 by a polynomial-sized bounded-depth Boolean circuit. Without preprocessing this task was shown to be impossible, and we show that this is still not possible even if we allow preprocessing limited to sublinear stretch of the inputs. Another part of our work goes beyond inner product and bounded-depth circuits, and explores other computational problems and constraints on Carol in the simultaneous messages framework. The above question turns out to be closely related to another question, which is independently motivated by cryptographic applications. Suppose that two distributions X and Y are k-indistinguishable, in the sense that their projections to any k coordinates are identically distributed. Can some constant-depth circuit distinguish between X and Y? A celebrated theorem by Braverman implies a negative answer when X is uniform, whereas a work of Bogdanov et al. shows that this is not the case in general. We initiate a systematic study of this question for natural classes of "simple" distributions, including ones that arise in cryptographic applications, obtaining positive results, negative results, and barriers.