דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Rounding Parallel Repetitions of Unique Games
event speaker icon
ענב וינרב (מדעי המחשב, הטכניון)
event date icon
יום ראשון, 15.2.2009, 12:00
event location icon
חדר 601, בניין טאוב
We consider the following question: given a two-argument boolean function $f$, represented as an $N\times N$ binary matrix, how hard is to determine the (deterministic) communication complexity of $f$?

We address two aspects of this question. On the computational side, we prove that, under appropriate cryptographic assumptions (such as the intractability of factoring), the deterministic communication complexity of $f$ is hard to approximate to within some constant. Under stronger (yet arguably reasonable) assumptions, we obtains even stronger hardness results that match the best known approximation.

On the analytic side, we present a family of functions for which determining the communication complexity (or even obtaining non-trivial lower bounds on it) imply proving circuit lower bounds for some corresponding problems. Such connections between circuit complexity and communication complexity were known before (Karchmer-Wigderson 1988) only in the more involved context of relations (search problems) and not in the context of functions (decision problems). This result, in particular, may explain the difficulty of analyzing the communication complexity of certain functions such as the ``clique vs. independent-set'' family of functions, introduced by Yannakakis (1988). Joint work with Eyal Kushilevitz
[בחזרה לאינדקס האירועים]