# User:Cschff

Jump to navigation
Jump to search

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

##### Discrete Logarithm: Reverse exponentiation

##### Equality: Are two strings equal?

If Alice has a string and Bob has a string , 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 , Bob holds input . Define INDEX(*x*,*i*)=x_i

Algorithms: ?