Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Computational Complexity under Communication Constraints
event speaker icon
Avi Kaplan (Ph.D. Thesis Seminar)
event date icon
Sunday, 15.01.2023, 15:00
event location icon
Zoom Lecture: 95627681547 and Taub 301
event speaker icon
Advisor: Prof. Yuval Filmus, Prof. Yuval Ishai
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.