### ?

## Making Randomness Public in Unbounded-Round Information Complexity

P. 296-309.

Kozachinskiy A.

In press

### In book

Vol. 9139. , Springer, 2015

Kozachinskiy A., , in : Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, Proceedings. Vol. 9691: Lecture Notes in Computer Science.: Switzerland : Springer, 2016. P. 207-222.

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 εε). Instead of one-way transmission we ...

Added: September 16, 2016

Brody J., Buhrman H., Koucky M. et al., / Hasso-Plattner-Institut. Series Technical report "Electronic Colloquium on Computational Complexity". 2013. No. TR12-179.

Newman’s theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with only a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and convert it into one that ...

Added: December 14, 2013

Brody J., Buhrman H., Koucký M. et al., Algorithmica 2016 Vol. 76 No. 3 P. 749-781

Newman's theorem states that we can take any public-coin
communication protocol and convert it into one that uses only
private randomness with only a little increase in communication
complexity. We consider a reversed scenario in the context of
information complexity: can we take a protocol that uses private
randomness and convert it into one that ...

Added: March 2, 2016

Kozachinskiy A., Theory of Computing Systems 2018 Vol. 62 No. 3 P. 583-599

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 ε). Instead of one-way transmission we allow them to interact. They may also ...

Added: February 9, 2017

Vereshchagin N., , in : CSR 2014 : 9th International Computer Science Symposium in Russia. Proceedings. Vol. 8476.: Berlin : Springer, 2014. P. 365-374.

The paper [Harry Buhrman, Michal Kouck ́, Nikolay Vereshcha y
gin. Randomized Individual Communication Complexity. IEEE Con ference on Computational Complexity 2008: 321-331] considered com munication complexity of the following problem. Alice has a bi nary string x and Bob a binary string y, both of length n, and they
want to compute or approximate Kolmogorov complexity C(x|y) of
x conditional to ...

Added: October 6, 2014

Proceedings of the First International Conference on Data Compression, Communications and Processing

NY : IEEE Computer Society, 2013

This book constitutes the refereed proceedings of the First International Conference on Data Compression, Communications and Processing held in Palinuro, Italy, in June 2011. ...

Added: October 30, 2013

Klenin E., Kozachinskiy A., , in : 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1-15.

Added: August 28, 2018

Hansen K. A., Podolskii V. V., Information and Computation 2015 Vol. 240 P. 56-73

We initiate a comprehensive study of the complexity of computing Boolean functions by polynomial threshold functions (PTFs) on general Boolean domains (as opposed to domains such as $\zon$ or $\mon$ that enforce multilinearity). A typical example of such a general Boolean domain, for the purpose of our results, is $\{1,2\}^n$. We are mainly interested in ...

Added: May 30, 2015

Vereshchagin N., / Hasso-Plattner-Institut. Series Tecnical report "Electronic Colloquium on Computational Complexity". 2013. No. TR13-178.

The paper [Harry Buhrman, Michal Kouck\'y, Nikolay Vereshchagin. Randomized Individual Communication Complexity. \emph{IEEE Conference on Computational Complexity} 2008: 321-331] considered communication complexity of the following problem. Alice has a binary string $x$ and Bob a binary string $y$, both of length $n$, and they want to compute or approximate Kolmogorov complexity $C(x|y)$ of $x$ conditional ...

Added: December 14, 2013

Vyalyi M., Problems of Information Transmission 2021 Vol. 57 No. 2 P. 143-160

We consider a generalization of the Pólya–Kasteleyn approach to counting the number of perfect matchings in a graph based on computing the symbolic Pfaffian of a directed adjacency matrix of the graph. Complexity of algorithms based on this approach is related to the complexity of the sign function of a perfect matching in generalized decision ...

Added: August 20, 2021

Ignatiev A., Mihajlin I., Smal A., , in : 33rd International Symposium on Algorithms and Computation (ISAAC 2022). LIPIcs, Volume 248. : Saarbrücken, Вадерн : Schloss-Dagstuhl - Leibniz Zentrum für Informatik, 2022. Ch. 66.

Added: November 9, 2023

Oleynik A., Авиакосмическое приборостроение 2014 № 10 С. 22-28

Questions of development of algorithms of information complex of high-rise and high-speed parameters of flight of the high-maneuverable plane for calculation of primary information are considered: static and full pressure, angles of attack and sliding . ...

Added: March 20, 2015

Podolskii V. V., Sherstov A., ACM Transactions on Computation Theory 2020 Vol. 12 No. 4 P. 26

A major goal in complexity theory is to understand the communication complexity of number-on-the-forehead problems f:({0, 1}^n)^k → {0, 1} with k > log n parties. We study the problems of inner product and set disjointness and determine their randomized communication complexity for every k ≥ log n, showing in both cases that Θ(1 + ⌈log n⌉/ log ⌈1 + k/ log n⌉) bits are necessary and ...

Added: December 23, 2020

Shitov Y., Discrete and Computational Geometry 2019 Vol. 61 No. 3 P. 653-660

A Euclidean distance matrix D(α) is defined by D_ij=(α_i−α_j)^2, where α=(α_1,…,α_n) is a real vector. We prove that D(α) cannot be written as a sum of [2sqrt(n)−2] nonnegative rank-one matrices, provided that the coordinates of α are algebraically independent. As a corollary, we provide an asymptotically optimal separation between the complexities of quantum and classical communication protocols computing a given matrix in expectation. ...

Added: March 15, 2018