Polynomial threshold functions and Boolean threshold circuits

Обнаружение сообществ в сложных сетях — фундаментальная проблема, открытая для новых подходов в различных научных областях. Мы представляем новый метод обнаружения сообществ, основанный на потоке Риччи на графах. Наша техника итеративно обновляет веса ребер (их метрические длины) в соответствии с их (комбинаторной) версией кривизны Риччи Фостера, вычисленной на основе эффективного расстояния сопротивления между узлами. Известно, ...

Добавлено: 15 января 2026 г.

Implementing Transport Coding in OMNeT++ for Message Delay Reduction

Петрованов И. С., Сергеев А. В., / Series Computer Science "arxiv.org". 2025. No. 2512.18332.

Добавлено: 24 декабря 2025 г.

Hessian-based lightweight neural network for brain vessel segmentation on a minimal training dataset

Меньшиков И. А., Бернадотт А. К., Елфимов Н. С., / Series arXie "Statistical mechanics". 2025.

Добавлено: 1 декабря 2025 г.

Эффективный алгоритм торговли на фондовом рынке: ретроспективный анализ, основанный на данных по S&P-500.

Рубчинский А. А., Чубарова Д. А., / Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2025. No. WP7/2025/01.

Добавлено: 9 ноября 2025 г.

Полудуплексная коммуникационная сложность с противником может быть меньше классической коммуникационной сложности

Верещагин Н. К., Дектярев М. В., Математический сборник 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]. До сих пор было неизвестным, различаются ли коммуникационные сложности, определяемые этими моделями. В ...

Добавлено: 23 августа 2025 г.

Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games

Игнатьев А. А., 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.

Добавлено: 9 ноября 2023 г.

Multiparty Karchmer-Wigderson Games and Threshold Circuits

Alexander Kozachinskiy, Vladimir Podolskii, Theory of Computing 2022 Vol. 18 No. 15 P. 1–33

Добавлено: 10 декабря 2022 г.

Counting the Number of Perfect Matchings, and Generalized Decision Trees

Вялый М. Н., Problems of Information Transmission 2021 Vol. 57 No. 2 P. 143–160

Добавлено: 20 августа 2021 г.

Inner Product and Set Disjointness: Beyond Logarithmically Many Parties

Подольский В. В., Sherstov A., ACM Transactions on Computation Theory 2020 Vol. 12 No. 4 P. 26

Добавлено: 23 декабря 2020 г.

One-Sided Error Communication Complexity of Gap Hamming Distance

Klenin E., Козачинский А. Н., , in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)Vol. 117.: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. P. 1–15.

Добавлено: 28 августа 2018 г.

Euclidean Distance Matrices and Separations in Communication Complexity Theory

Шитов Я. Н., Discrete and Computational Geometry 2019 Vol. 61 No. 3 P. 653–660

Добавлено: 15 марта 2018 г.

On Slepian–Wolf Theorem with Interaction

Козачинский А. Н., 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 ...

Добавлено: 9 февраля 2017 г.

On Slepian–Wolf Theorem with Interaction

Козачинский А. Н., , 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.

Добавлено: 16 сентября 2016 г.

Towards a Reverse Newman’s Theorem in Interactive Information Complexity

Brody J., Buhrman H., Koucký M. и др., Algorithmica 2016 Vol. 76 No. 3 P. 749–781

Добавлено: 2 марта 2016 г.

Making Randomness Public in Unbounded-Round Information Complexity

Козачинский А. Н., , in: Computer Science -- Theory and Applications 10th International Computer Science Symposium in Russia, CSR 2015Vol. 9139.: Springer, 2015. P. 296–309.

Добавлено: 29 февраля 2016 г.

Randomized communication complexity of approximating Kolmogorov complexity

Верещагин Н. К., , in: CSR 2014 : 9th International Computer Science Symposium in Russia. ProceedingsVol. 8476.: Berlin: Springer, 2014. P. 365–374.

Добавлено: 6 октября 2014 г.

Randomized communication complexity of appropximating Kolmogorov complexity

Верещагин Н. К., / Series Tecnical report "Electronic Colloquium on Computational Complexity". 2013. No. TR13-178.

Добавлено: 14 декабря 2013 г.

Towards a Reverse Newman's Theorem in Interactive Information Complexity

Brody J., Buhrman H., Koucky M. и др., / Series Technical report "Electronic Colloquium on Computational Complexity". 2013. No. TR12-179.

Добавлено: 14 декабря 2013 г.