• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • One-Sided Error Communication Complexity of Gap Hamming Distance
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2028
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
September 9, 2026
‘Balkan Hospitality Opens Doors: Studying Dialects on the Verge of Extinction
You cannot study spoken dialects from books. Instead, you need to go to a village, seek out its elders, and earn the trust of local residents before you can record hours of spontaneous stories. This is how Natalia Muravleva, Associate Professor at the Faculty of Humanities, conducts her research. Her internship in Serbia continued her long-standing study of dialects spoken by Macedonian settlers. In this interview, she discusses how diaspora cultural centres help researchers reach informants, why native speakers need to be interviewed only in their own language (otherwise, as she puts it, they may 'break'), and how a single field season helped her finalise her monograph. She also shares warm memories of autumn in Belgrade and of colleagues with whom grammar can be discussed in three languages at once.
September 9, 2026
Scientists Train Neural Network to Generate Process Plans from 3D Models
Researchers at the HSE FCS AI and Digital Science Institute have developed CAD2TechSpec, a framework that converts 3D models of mechanical parts into machining process plans—step-by-step instructions for machine tools. The solution aims to reduce the time required for the design and preparation of technical process documentation in mechanical engineering, aircraft manufacturing, and other high-tech industries. The study findings have been published in PeerJ Computer Science.
September 7, 2026
Biologists Discover 'Molecular Fingerprint' of Preeclampsia
Researchers at HSE University employed a new method to model hypoxia in placental cells during pregnancies complicated by preeclampsia and identified molecular markers of tissue hypoxia. Since hypoxia is one of the key mechanisms underlying preeclampsia, these findings are important for a more accurate and timely diagnosis of the disease and for the development of effective treatment methods. The paper has been published in Placenta.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

One-Sided Error Communication Complexity of Gap Hamming Distance

P. 1–15.
Klenin E., Kozachinskiy A.
Language: English
DOI
Text on another site
Keywords: communication complexitygap hamming distanceone-sided error
Publication based on the results of:
Теоретическая информатика (2018)

In book

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Vol. 117. , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018.
Similar publications
Полудуплексная коммуникационная сложность с противником может быть меньше классической коммуникационной сложности
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
Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games
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
Counting the Number of Perfect Matchings, and Generalized Decision Trees
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
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties
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
Euclidean Distance Matrices and Separations in Communication Complexity Theory
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
On Slepian–Wolf Theorem with Interaction
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
On Slepian–Wolf Theorem with Interaction
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
Towards a Reverse Newman’s Theorem in Interactive Information Complexity
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
Making Randomness Public in Unbounded-Round Information Complexity
Kozachinskiy A., , in: Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015Vol. 9139.: Springer, 2015. P. 296–309.
Added: February 29, 2016
Polynomial threshold functions and Boolean threshold circuits
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
Randomized communication complexity of approximating Kolmogorov complexity
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
Randomized communication complexity of appropximating Kolmogorov complexity
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
Towards a Reverse Newman's Theorem in Interactive Information Complexity
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
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit