User:Cschff

Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

Welcome to the Communication-Complexity Garden, the botanical companion to the Communication-Complexity Zoo. This field guide lists rigorously defined functions.

Gardeners: Florian Speelman and Christian Schaffner

To create a new problem, click on the edit link of the problem before or after the one that you want to add and copy the format, and save.

Table of Contents

2-party functions: Equality - Index -

Uncategorized problems: Index -

The Problems

Equality: Are two strings equal?

If Alice has a string $x\in \left\{0,1\right\}^{n}$ and Bob has a string $y\in \left\{0,1\right\}^{n}$, define EQUALITY(x, y) = 1 if and only if x = y.

Algorithms: ?

Memberships:

---

Index: What is the bit of x with index i?

Alice has a string $x\in \left\{0,1\right\}^{n}$, Bob holds input $i\in [n]$. Define INDEX(x,i)=x_i

Algorithms: ?

Memberships: ∈ NP ∩ coAM.

---