Farid Ablayev, Airat Khasianov, Alexander Vasiliev

We consider Generalized Equality, the Hidden Subgroup,

and related problems in the context of quantum Ordered Binary

Decision Diagrams. For the decision versions of considered problems

we show polynomial upper bounds in terms of quantum OBDD width. We

apply a new modification of the fingerprinting technique and present

the algorithms ...
more >>>

Emanuele Viola

Suppose each of $k \le n^{o(1)}$ players holds an $n$-bit number $x_i$ in its hand. The players wish to determine if $\sum_{i \le k} x_i = s$. We give a public-coin protocol with error $1\%$ and communication $O(k \lg k)$. The communication bound is independent of $n$, and for $k ... more >>>

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

The \textsc{equality} problem is usually one's first encounter with

communication complexity and is one of the most fundamental problems in the

field. Although its deterministic and randomized communication complexity

were settled decades ago, we find several new things to say about the

problem by focusing on two subtle aspects. The ...
more >>>

Amit Chakrabarti, Sagar Kale

We develop a paradigm for studying multi-player deterministic communication,

based on a novel combinatorial concept that we call a {\em strong fooling

set}. Our paradigm leads to optimal lower bounds on the per-player

communication required for solving multi-player $\textsc{equality}$

problems in a private-message setting. This in turn gives a ...
more >>>

Hamed Hatami, Pooya Hatami

Several theorems and conjectures in communication complexity state or speculate that the complexity of a matrix in a given communication model is controlled by a related analytic or algebraic matrix parameter, e.g., rank, sign-rank, discrepancy, etc. The forward direction is typically easy as the structural implications of small complexity often ... more >>>