Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs

АБВ
АБВ
АБВ

Обычная версия сайта

Приоритетные направления

по году

Тематика

28 августа 2026 г.

МИЭМ ВШЭ и МИЭТ договорились о научном сотрудничестве

26 августа Московский институт электроники и математики им. А.Н. Тихонова (МИЭМ) ВШЭ и Национальный исследовательский университет «Московский институт электронной техники» (МИЭТ) подписали договор о сотрудничестве. Соглашение направлено на развитие совместных исследований в области физики, перспективного материаловедения и электроники, объединяющих экспериментальные и вычислительные подходы, выполнение совместных опытно-конструкторских работ, а также подготовку заявок на российские и международные научные гранты.

25 августа 2026 г.

Исследователи ВШЭ сравнили рекомендательные алгоритмы по правилам спортивного турнира

Исследователи Института искусственного интеллекта и цифровых наук ФКН НИУ ВШЭ разработали подход, который помогает эффективнее подбирать рекомендательные алгоритмы. В нем разные методы попарно соревнуются, а по результатам всех поединков составляется общий рейтинг. Это помогает сократить число алгоритмов, которые нужно проверять при разработке новых сервисов, и сэкономить денежные и временные ресурсы.Исследование было представлено на 32-й конференции ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2026).

20 августа 2026 г.

<a>Исследователи НИУ ВШЭ и Сбера научили нейросети лучше угадывать предпочтения пользователей

Институт искусственного интеллекта и цифровых наук ФКН НИУ ВШЭ и Сбер представили новую архитектуру для рекомендательных систем: благодаря объединению двух классов моделей алгоритмы лучше угадывают интересы и потребности пользователей. Препринт работы опубликован на сайте arxiv.org и представлен на летнем фестивале «Урбан ML».

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

Публикации

?

Almost Tight Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs

2019.

Itsykson D., Artur Riazanov, Danil Sagunov, Petr Smirnov

В печати

Язык: английский

Текст на другом сайте

Delay Analysis of Massive Unsourced ALOHA-based Protocols with User Authentication

Nesterenkov O., Chemodanov A., Turlikov A., , in: 2022 Wave Electronics and its Application in Information and Telecommunication Systems (WECONF) 30 May - 3 June 2022, St. Petersburg, Russia.: IEEE, 2022. Ch. 180440 P. 1–5.

Добавлено: 28 октября 2022 г.

Arbitrarily accurate approximation of numerical characteristics of stationary ALOHA Channels

Burkov A. A., Shneer S., Turlikov A. M., , in: WAVE ELECTRONICS AND ITS APPLICATION IN INFORMATION AND TELECOMMUNICATION SYSTEMS. 2021. (WECONF 2021) St. Petersburg, Russia, 31 May - 4 June 2021.: IEEE, 2021. Ch. 9470700 P. 1–8.

Добавлено: 28 октября 2022 г.

On the Decision Tree Complexity of Threshold Functions

Чистопольская А. И., Подольский В. В., Theory of Computing Systems 2022

Добавлено: 13 сентября 2022 г.

On the Decision Tree Complexity of Threshold Functions

Чистопольская А. И., Подольский В. В., , in: Computer Science – Theory and Applications 15th International Computer Science Symposium in Russia, CSR 2020, Yekaterinburg, Russia, June 29 – July 3, 2020, ProceedingsVol. 12159.: Springer, 2020. P. 198–210.

Добавлено: 7 сентября 2020 г.

Erasure correction by low-density codes

Zyablov V., Рыбин П. С., Problems of Information Transmission 2009 Vol. 45 No. 3 P. 204–220

Добавлено: 11 декабря 2017 г.

Analysis of the relation between properties of LDPC codes and the tanner graph

Zyablov V., Рыбин П. С., Problems of Information Transmission 2012 Vol. 48 No. 4 P. 297–323

Добавлено: 11 декабря 2017 г.

Asymptotic bounds on the decoding error probability for two ensembles of LDPC codes

Рыбин П. С., Zyablov V., Problems of Information Transmission 2015 Vol. 51 No. 3 P. 205–216

Добавлено: 11 декабря 2017 г.

Computing majority by constant depth majority circuits with low fan-in gates

Kulikov A. S., Подольский В. В., , in: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). March 8–11, 2017, Hannover, GermanyТ. 66.: Лейпциг: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017. P. 1–14.

We study the following computational problem: for which values of k, the majority of n bits MAJn can be computed with a depth two formula whose each gate computes a majority function of at most k bits? The corresponding computational model is denoted by MAJk o MAJk. We observe that the minimum value of k ...

Добавлено: 1 июня 2017 г.

Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times

Mikhail Batsyn, Boris Goldengorin, Pavel Sukhov и др., , in: Models, Algorithms, and Technologies for Network AnalysisVol. 59.: NY: Springer, 2013. Ch. 2 P. 11–27.

The preemptive single machine scheduling problem of minimizing the total weighted completion time with equal processing times and arbitrary release dates is one of the four single machine scheduling problems with an open computational complexity status. In this paper we present lower and upper bounds for the exact solution of this problem based on the ...

Добавлено: 21 сентября 2013 г.