?
Making Randomness Public in Unbounded-Round Information Complexity
P. 296–309.
Kozachinskiy A.
In press
In book
Vol. 9139. , Springer, 2015.
Vereshchagin N., Дектярев М. В., Математический сборник 2025 Т. 216 № 6 С. 3–45
Полудуплексная коммуникационная сложность с противником определена в работе [Hoover, K., Impagliazzo, R., Mihajlin, I., Smal, A. V. Half-Duplex Communication Complexity, ISAAC 2018.] Полудуплексные коммуникационные протоколы обобщают классические протоколы, определенные Эндрю Яо в [Yao, A. C.-C. Some Complexity Questions Related to Distributive Computing (Preliminary Report), STOC 1979]. До сих пор было неизвестным, различаются ли коммуникационные сложности, определяемые этими моделями. В ...
Added: August 23, 2025
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
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
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
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
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
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
Kozachinskiy A., , in: Computer Science – Theory and Applications. 11th International Computer Science Symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9-13, 2016, ProceedingsVol. 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., 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
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., , in: CSR 2014 : 9th International Computer Science Symposium in Russia. ProceedingsVol. 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
Vereshchagin N., / 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
Brody J., Buhrman H., Koucky M. et al., / 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
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