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
Uncategorized problems: Index -
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.
Index: What is the bit of x with index i?
Alice has a string , Bob holds input . Define INDEX(x,i)=x_i