All reports by Author Alexander Kozachinsky:

__
TR16-173
| 5th November 2016
__

Egor Klenin, Alexander Kozachinsky#### One-sided error communication complexity of Gap Hamming Distance

Revisions: 2

__
TR15-090
| 1st June 2015
__

Alexander Kozachinsky#### On Slepian--Wolf Theorem with Interaction

Revisions: 1

__
TR14-062
| 22nd March 2014
__

Alexander Kozachinsky#### On the role of private coins in unbounded-round Information Complexity

Egor Klenin, Alexander Kozachinsky

Assume that Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$. Their goal is to output 0, if $x$ and $y$ are at least $L$-close in Hamming distance, and output 1, if $x$ and $y$ are at least $U$-far in Hamming distance, where ... more >>>

Alexander Kozachinsky

In this paper we study interactive ``one-shot'' analogues of the classical Slepian-Wolf theorem. Alice receives a value of a random variable $X$, Bob receives a value of another random variable $Y$ that is jointly distributed with $X$. Alice's goal is to transmit $X$ to Bob (with some error probability $\varepsilon$). ... more >>>

Alexander Kozachinsky

We prove a version of "Reversed Newman Theorem" in context of information complexity: every private-coin communication protocol with information complexity $I$ and communication complexity $C$ can be replaced by public-coin protocol with the same behavior so that it's information complexity does not exceed $O\left(\sqrt{IC}\right)$. This result holds for unbounded-round communication ... more >>>