Kol and Raz [STOC 2013] showed how to simulate any alternating two-party communication protocol designed to work over the noiseless channel, by a protocol that works over a stochastic channel that corrupts each sent symbol with probability $\epsilon>0$ independently, with only a $1+\mathcal{O}(\sqrt{\H(\epsilon)})$ blowup to the communication. In particular, this ... more >>>

We prove a lower bound on the communication complexity of computing the $n$-fold xor of an arbitrary function $f$, in terms of the communication complexity and rank of $f$. We prove that $D(f^{\oplus n}) \geq n \cdot \Big(\frac{\Omega(D(f))}{\log rk(f)} -\log rk(f)\Big )$, where here $D(f), D(f^{\oplus n})$ represent the ... more >>>

Time efficient decoding algorithms for error correcting codes often require linear space. However, locally decodable codes yield more efficient randomized decoders that run in time $n^{1+o(1)}$ and space $n^{o(1)}$. In this work we focus on deterministic decoding.
Gronemeier showed that any non-adaptive deterministic decoder for a good code running ... more >>>