Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > EQUALITY:
Reports tagged with Equality:
TR08-085 | 19th June 2008
Farid Ablayev, Airat Khasianov, Alexander Vasiliev

#### On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

Revisions: 1

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

TR11-152 | 12th November 2011
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 >>> TR12-153 | 9th November 2012 Joshua Brody, Amit Chakrabarti, Ranganath Kondapally #### Certifying Equality With Limited Interaction Revisions: 1 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 >>> TR16-111 | 20th July 2016 Amit Chakrabarti, Sagar Kale #### Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics 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 >>>

ISSN 1433-8092 | Imprint