Доклады и лекции в базе данных Math-Net.Ru
Randomized Lifting to Semi-Structured Communication Complexity Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar" 12 мая 2025 г. 16:00
Majority circuits and sorting networks of small depth Fourth Workshop on Digitalization and Computable Models (WDCM-2022) 26 октября 2022 г.
Weights of polynomial threshold functions Международная мини-конференция “Approximation and Matrix Complexity” 21 декабря 2021 г.
Лекция 13. Введение в теорию сложности Введение в теорию сложности 6 декабря 2021 г.
Лекция 12. Введение в теорию сложности Введение в теорию сложности 29 ноября 2021 г.
Лекция 11. Введение в теорию сложности Введение в теорию сложности 22 ноября 2021 г.
Лекция 10. Введение в теорию сложности Введение в теорию сложности 15 ноября 2021 г.
Лекция 9. Введение в теорию сложности Введение в теорию сложности 8 ноября 2021 г.
Лекция 8. Введение в теорию сложности Введение в теорию сложности 25 октября 2021 г.
Лекция 7. Введение в теорию сложности Введение в теорию сложности 18 октября 2021 г.
Лекция 6. Введение в теорию сложности Введение в теорию сложности 11 октября 2021 г.
Лекция 5. Введение в теорию сложности Введение в теорию сложности 4 октября 2021 г.
Лекция 4. Введение в теорию сложности Введение в теорию сложности 27 сентября 2021 г.
Лекция 3. Введение в теорию сложности Введение в теорию сложности 20 сентября 2021 г.
Лекция 2. Введение в теорию сложности Введение в теорию сложности 13 сентября 2021 г.
Лекция 1. Введение в теорию сложности Введение в теорию сложности 6 сентября 2021 г.
Макс-плюс многочлены и их корни Конференция международных математических центров мирового уровня 10 августа 2021 г.
Макс-плюс многочлены и их корни Общеинститутский семинар «Математика и ее приложения» Математического института им. В.А. Стеклова Российской академии наук 21 января 2021 г. 16:00
Макс-плюс многочлены и их корни Научная сессия МИАН, посвященная подведению итогов 2020 года 25 ноября 2020 г.
Занятие 7. NP-полнота следующих задач: NAE-3-SAT, 3-COL, SUBSET-SUM, CLIQUE, VERTEX-COVER Введение в теорию сложности 3 ноября 2020 г. 16:15
Занятие 6. Соотношение между классами P и P/poly. Задача CIRCUIT-SAT, ее NP-полнота. Задача 3-SAT, ее NP-полнота. Задача IND-SET, ее NP-полнота Введение в теорию сложности 27 октября 2020 г. 16:15
Занятие 5. Булевых схемы. Примеры: сложение, умножение, связность. Верхняя и нижняя оценки сложности вычисления булевых функций булевыми схемами Введение в теорию сложности 20 октября 2020 г. 16:15
Занятие 4. Класс NP, примеры. Соотношение с классами P и PSPACE. Недетерминированные машины Тьюринга, второе определение класса NP, эквивалентность определений. Полиномиальные сводимости, их основные свойства. NP-трудность и NP-полнота, их основные свойства Введение в теорию сложности 13 октября 2020 г. 16:15
Занятие 3. Теоремы об иерархии по времени и по памяти Введение в теорию сложности 6 октября 2020 г. 16:15
Занятие 2. Связь одноленточных и многоленточных машин Тьюринга. Универсальная машина Тьюринга. Вычисления с ограничением на время и память. Классы P, PSPACE, EXP. Примеры полиномиально вычислимых функций и полиномиально разрешимых языков Введение в теорию сложности 29 сентября 2020 г. 16:15
Занятие 1. Машины Тьюринга, вычисление функций на машинах Тьюринга, лемма об очистке мусора, многоленточные машины Тьюринга Введение в теорию сложности 22 сентября 2020 г. 16:15
Занятие 0. Устройство курса правила оценивания. Краткий обзор основ сложности вычислений. Классы с ограничением на память. Класс PSPACE, его свойства. Задача TQBF является PSPACE-полной. PSPACE=NPSPACE Введение в теорию сложности 15 сентября 2020 г. 16:15
Макс-плюс многочлены и их корни Узлы и теория представлений 25 февраля 2020 г.
Сложность вычисления некоторых функций коммуникационными протоколами с
большим числом участников Традиционная зимняя сессия МИАН–ПОМИ, посвященная теме «Математическая
логика» 24 декабря 2018 г.
Оценки сложности для баз данных, снабженных логическими теориями Конференция «Современная математика и ее приложения», посвященная подведению итогов реализации гранта РНФ № 14-50-00005 19 ноября 2018 г.
Сложность вычисления некоторых функций коммуникационными протоколамис большим числом участников «Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна) 6 марта 2018 г.
О корнях многочленов в мин-плюс алгебре «Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна) 21 ноября 2017 г.
Ontology-based data access meets circuit complexity Applied Mathematics Day 22 сентября 2017 г.
Computing Majority by Constant Depth Majority Circuits with Low Fan-in Gates Межкафедральный семинар МФТИ по дискретной математике 23 марта 2017 г.
Polynomials in min-plus algebra and related algorithmic problems Математическая логика, алгебра и вычислимость: двухдневная конференция, посвященная 85-летию С. И. Адяна 19 июля 2016 г.
Оценки длин преобразований запросов к снабженным логической теорией базам данных «Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна) 1 декабря 2015 г.
Оценки длин переформулировок запросов к снабженным логической теорией базам данных Научная сессия МИАН, посвященная подведению итогов 2015 года 11 ноября 2015 г.
Мин-плюс многочлены и циклические игры Коллоквиум Факультета компьютерных наук НИУ ВШЭ 30 апреля 2015 г.
Приближение булевых функций многочленами Общеинститутский семинар «Коллоквиум МИАН» 2 апреля 2015 г. 16:00
Об одном аналоге известной теоремы Гильберта о нулях для многочленов в алгебраической системе $(\mathbb{R}, \min, +)$ «Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна) 11 ноября 2014 г.
Пороговые элементы на множестве $\{1,2\}$ и пороговые схемы Колмогоровский семинар по сложности вычислений и сложности определений 1 апреля 2013 г.
Об аналоге теоремы Гильберта о нулях в алгебраической системе $(\mathbb{R}, \min, +)$ «Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна) 26 марта 2013 г.
О реализации булевых функций знаковыми функциями целочисленных многочленов «Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна) 4 декабря 2012 г.
Об уравнениях в алгебраической системе $(\mathbb Z,\min, +)$ «Алгоритмические вопросы алгебры и логики» (семинар С.И.Адяна) 15 мая 2012 г.
О некоторых классах пороговых булевых схем ограниченной глубины Традиционная новогодняя сессия МИАН-ПОМИ, 2009 «Логика и теоретическая информатика» 18 декабря 2009 г. 16:00
© , 2026
