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!

$\endgroup$
  • 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 supports Monica Jun 11 '15 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 Jun 12 '15 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.