We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index i such that x_i\neq y_i, in a zero-communication setting.

We give upper and lower ... more >>>

The disjointness problem - where Alice and Bob are given two subsets of \{1, \dots, n\} and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be ... more >>>

Buhrman, Cleve and Wigderson (STOC'98) observed that for every Boolean function f : \{-1, 1\}^n \to \{-1, 1\} and \bullet : \{-1, 1\}^2 \to \{-1, 1\} the two-party bounded-error quantum communication complexity of (f \circ \bullet) is O(Q(f) \log n), where Q(f) is the bounded-error quantum query complexity of f. ... more >>>

Given a Boolean function f: \{-1,1\}^n\rightarrow \{-1,1\}, define the Fourier distribution to be the distribution on subsets of [n], where each S\subseteq [n] is sampled with probability \widehat{f}(S)^2. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [FK96] seeks to relate two fundamental measures associated with the Fourier distribution: does ... more >>>