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 >>>

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 >>>

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 >>>

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 >>>

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 >>>