Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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 >>>

TR15-090 | 1st June 2015
Alexander Kozachinsky

On Slepian--Wolf Theorem with Interaction

Revisions: 1

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 >>>

TR14-062 | 22nd March 2014
Alexander Kozachinsky

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

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 >>>

ISSN 1433-8092 | Imprint