• 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
  • 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
June 5, 2026
Neural Network Maps as a Method for Constructing Mathematical Models
Scientists from HSE University–Nizhny Novgorod and the Institute of Physics Belgrade, Serbia, are jointly exploring the application of machine learning techniques and neural networks to the study of nonlinear dynamics. Natalya Stankevich, Leading Research Fellow at the Laboratory of Topological Methods in Dynamics of the Faculty of Informatics, Mathematics, and Computer Science at HSE University–Nizhny Novgorod, spoke to the HSE News Service about this international project.
June 5, 2026
‘In the Age of Technology, It Is Interesting to Look into the Past and Think about What We Can Take from It
Polina Tabakova decided to apply for a Philology degree at HSE in Nizhny Novgorod because she grew up in Mari El and did not want to move far away from the Russian forests. In an interview for the Young Scientists of HSE University project, she spoke about the genre of the campus novel, the existential drama of Kolobok, and a blackout version of Eugene Onegin.
June 5, 2026
HSE Scientists Develop Method to Compress Large Language Models Without Losing Quality
Researchers from the AI and Digital Science Institute at the HSE Faculty of Computer Science have developed a new compression method for large language models such as GPT and LLaMA that reduces their size by 25–36% without additional training or significant loss of accuracy. This is the first approach to use mathematical transformations—specifically, rotations of model weights—to make models more amenable to compression with structured matrices. The study results have been published in ACL Findings 2025. The code is available on GitHub.

 

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