User:Cschff
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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in\left\{0,1\right\}^n} and Bob has a string Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in\left\{0,1\right\}^n} , Bob holds input Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i\in [n]} . Define INDEX(x,i)=x_i
Algorithms: ?