15
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Jun 11, 2015 at 17:07
  • 1
    $\begingroup$ @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$. $\endgroup$
    – domotorp
    Commented Jun 12, 2015 at 5:50

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.