<p>I'm looking into communication complexity with real numbers. One problem if we want to define this is that one can encode many real numbers $0.a_1a_2a_3... , 0.b_1b_2b_3..., 0.c_1c_2c_3...$ using only one number $0.a_1b_1c_1a_2b_2c_2...$</p>

<p>To get around this problem, existing papers that deal with this issue (such as Abelson (1978), Luo and Tsitiklis, and Chen(1994)) assume that the messages that can be sent between Alice and Bob must be continuously differentiable functions of the inputs $x_1,...,x_n$. </p>

<p>Do we need differentiability? Is there any problem if the messages are assumed to be continuous (not necessarily differentiable) functions?  I know that there's no continuous bijective function $f: \mathbb{R}^n \to \mathbb{R}$ for $n &gt; 1$, so it seems like just assuming continuity should be enough. </p>

<p>Thanks!</p>

CC BY-SA 3.0
2015-06-11T17:07:43.013Z
I know nothing about this set-up, but anyway there are continuous *surjections* $\mathbb R\to\mathbb R^n$, which sounds to me like something that can be used to encode many reals into one just like in the first paragraph.
Emil Jeřábek
CC BY-SA 3.0
2015-06-12T05:50:26.517Z
@Emil: But we would rather need a $\mathbb R^n \to \mathbb R$ and that always has level curves that contain parts that are like $\mathbb R$.
domotorp
<communication-complexity>
Communication Complexity with real numbers
Asterix
# Communication Complexity with real numbers

(Asked by: username_0 on 2015-06-04)

I'm looking into communication complexity with real numbers. One problem if we want to define this is that one can encode many real numbers $0.a\_1a\_2a\_3... , 0.b\_1b\_2b\_3..., 0.c\_1c\_2c\_3...$ using only one number $0.a\_1b\_1c\_1a\_2b\_2c\_2...$

To get around this problem, existing papers that deal with this issue (such as Abelson (1978), Luo and Tsitiklis, and Chen(1994)) assume that the messages that can be sent between Alice and Bob must be continuously differentiable functions of the inputs $x\_1,...,x\_n$.

Do we need differentiability? Is there any problem if the messages are assumed to be continuous (not necessarily differentiable) functions? I know that there's no continuous bijective function $f: \mathbb{R}^n \to \mathbb{R}$ for $n > 1$, so it seems like just assuming continuity should be enough.

Thanks!

**Tags:** communication-complexity

> **Comments:**
> **username_1**: I know nothing about this set-up, but anyway there are continuous *surjections* $\mathbb R\to\mathbb R^n$, which sounds to me like something that can be used to encode many reals into one just like in the first paragraph.  
> **username_2**: @Emil: But we would rather need a $\mathbb R^n \to \mathbb R$ and that always has level curves that contain parts that are like $\mathbb R$.  

---

## 0 answers

