Просмотр исходного текста страницы Comb2020 2021

= Комбинаторные конструкции в теоретической информатике (3-ий курс ТИ) 2021 год =

Лекции проходят по пятницам 13:00-14:20, семинары также по пятницам 14:40-16:00 через Zoom по ссылке https://zoom.us/j/97847376308?pwd=NTQ2ZnZVdldHZ2xtTHlYTUdNM24xdz09С Идентификатор конференции: 97847376308 пароль 557552

Ссылка на доску: https://drive.google.com/drive/folders/1JwrAZgF8NXajZvnXuUG_6NFEv7vWjlqs?usp=sharing

Если Zoom виснет, лекции переносятся в Google Meet https://meet.google.com/noy-cait-jph

Первая лекция и семинар 15 января.

==Новости==

=== 1 сентября ===

Время пересдачи 8 сентября сдвинуто на 16:00.

=== 26 июня ===
Проверены все задачи экзамена. Для аппеляции по всем задачам кроме 4 и 6 пишите сегодня в телеграмм AlexeySMilovanov.

=== 25 июня ===
Проверены 4 и 6 задачи экзамена. Сегодня и завтра я могу принять апелляции (пишите на почту). Критерии проверки и оценки в файле со всеми результатами. - Верещагин.

[https://www.dropbox.com/s/dlt2q221fl2zdzd/exam_25_06_2021solutions.pdf?dl=0 Решения задач]

=== 18 июня ===
В связи с переходом на дистанционный режим экзамен 25 июня (а не 23-го, как было ошибочно указано ранее) будет онлайн с прокторнингом и будет продолжаться 90 минут (начало в 10:40). Более подробная инструкция тут:

1.  Экзамен письменный и проходит с прокторингом через Зум: 
https://zoom.us/j/94581215175
Присоединиться к конференции надо на десять минут раньше, то есть, в 10:30. В 10:40 станут доступны задания, которые надо  загрузить по [https://www.dropbox.com/s/x3sebhgkututbad/exam-25-06-2021.pdf?dl=0 (ссылке)].  Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com.  Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.

2.  Экзамен длится 90 минут. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций: https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0, https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.

3.  Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.

=== 15 июня ===
[https://www.dropbox.com/s/2ggcr4krv3a4me9/exam_CCTI.pdf?dl=0 Тренировочный вариант экзамена]

=== 14 июня ===
[https://docs.google.com/spreadsheets/d/1C1_ww5-lBuI_X4FVXu5ctinm6ycAUxZ8IFsEcUUvtBc/edit?usp=sharing Ссылка] на запись на коллоквиум.
[https://zoom.us/j/94741828556?pwd=L281YTlYV2xrS1RhQ0xCQVU3dFdodz09 Ссылка на конференцию Zoom для сдачи коллоквиума]

=== 14 июня ===

В связи с переходом на дистанционный режим
факультета компьютерных наук на наступающей неделе, с 14 по 19 июня, коллоквиум 18 июня будет он-лайн. Пользоваться можно любыми материалами, билет будет выдан за 1 час до начала ответа (для этого надо подключиться к конференции за 1 час до начала сдачи), но время ответа ограничено 25 минутами. Кроме того, изменится формат билета, в билет будет включен еще один вопрос на формулировку теоремы или определение, за которое будет начисляться 2 балла,
каждый из теор. вопросов будет оцениваться в 4 балла.

=== 4 июня ===
Коллоквиум будет 18 июня в ауд.  R208 в 10:30. [https://www.dropbox.com/s/ef0514u08o7oiaw/colloq2021.pdf?dl=0 Программа коллоквиума.]

=== 29 мая ===
Выложена [https://www.dropbox.com/s/ef0514u08o7oiaw/colloq2021.pdf?dl=0 программа коллоквиума]

=== 28 мая ===
Выложено четвёртое домашнее задание

=== 21 мая ===
Экзамен состоится 23 июня с 10:30. 
Экзамен письменный очный, длится 120 минут.

=== 22 апреля ===
Выложено третье домашнее задание

=== 25 марта ===
Выложено второе домашнее задание

=== 11 февраля ===
Выложено первое домашнее задание

==== 15 января ====
Добавлена [https://www.dropbox.com/sh/qe4p5oxyj6y42pr/AAB2jG92VGHt9BfxoU8hAxLJa?dl=0 Ссылка на записи на доске, сделанные во время лекции]

==Контакты== 

Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com

Семинарист: Милованов Алексей Сергеевич almas239@gmail.com, телеграм: AlexeySMilovanov

Группа в Телеграм: https://t.me/joinchat/RXhbmrjQzig8QLiw

==Краткое описание==

Экспандеры и их применения: теорема Рейнгольда о разрешимости связности для неориентированных графов на логарифмической памяти, построение генераторов псевдослучайных чисел, экспандерные коды.

Коды с исправлением ошибок для компьютерных наук.

Представление булевых функций деревьями разрешения и многочленами. 


==Отчётность по курсу и критерии оценки==

Итоговая оценка складывается из оценок за домашние задания, оценок за тесты, и оценки за коллоквиум и экзамен. Оценки за колллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.3, а оценки за домашние задания и тесты - с коэффициентом 0.2.

В домашних заданиях иногда будут бонусные задания. За каждую решеннную бонусную задачу к итоговой оценке будет прибавляться 0.5 балла.  

=== Тесты === 
В конце каждой лекции будет предлагаться десятиминутный тест с простыми задачами. Целью тестов является контроль за тем, чтобы студенты
внимательно слушали лекцию. К написанию теста допускаются только присутствовавшие на лекции (разрешается десятиминутное опоздание к началу лекции). За каждый тест 
выставляется оценка, равная доле правильных ответов, умноженной на 10.
Общая оценка за тесты равняется среднему арифметическому оценок за все тесты.

=== Домашние задания===
В течение двух модулей студентам будет дано 4 домашних задания. 
Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается не менее 14 дней, решение ДЗ нужно сдавать семинаристу или лектору устно (онлайн). Сдача домашних заданий после их срока невозможна.

Сдать ДЗ лектору можно по вторникам с 10 до 20, средам с 18 до 20, четвергам с 10 до 20 с помощью Google Meet https://meet.google.com/noy-cait-jph

Сдать ДЗ семинаристу можно в понедельник, субботу или воскресение по предварительной договорённости.

===Коллоквиум и письменный экзамен===
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.

Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один  раз). Это же относится и к тем, кто не смог прийти на экзамен. На пересдачу также могут прийти те, кто в итоге получил менее 4 баллов. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной. 

===Правила округления=== 
В вычислениях текущие оценки и промежуточные величины не округляются. Результат
вычисляется точно и округляется (арифметически) только в момент выставления итоговой оценки.

====Коллоквиум====
Коллоквиум будет 18 июня в ауд.  R208 с 10:30-13:30.  

[https://www.dropbox.com/s/ef0514u08o7oiaw/colloq2021.pdf?dl=0 Программа коллоквиума.]

====Экзамен====
В связи с переходом на дистанционный режим экзамен 25 июня (а не 23-го, как было ошибочно указано ранее) будет онлайн с прокторнингом и будет продолжаться 90 минут (начало в 10:40). Более подробная инструкция тут:

1.  Экзамен письменный и проходит с прокторингом через Зум: 
https://zoom.us/j/94581215175
Присоединиться к конференции надо на десять минут раньше, то есть, в 10:30. В 10:40 станут доступны задания, которые надо  загрузить по [https://www.dropbox.com/s/x3sebhgkututbad/exam-25-06-2021.pdf?dl=0 (ссылке)]. Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com.  Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.

2.  Экзамен длится 90 минут. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций: https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 https://www.dropbox.com/s/4eakm5abultga7x/DecisionTrees.pdf?dl=0, https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0, писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.

3.  Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.

====Пересдачи====

Пересдачи состоятся 1 и 8 сентября. Пересдача комиссии - 15 сентября. Все пересдачи проходят он-лайн.

Пересдать можно коллоквиум и/или письменный экзамен (ранее полученная оценка при этом аннулируется). 

На пересдачу 1 сентября никто не записался. 

Пересдача 8 сентября. Для пересдачи коллоквиума надо подключиться к конференции в 16:00, получить билет из программы коллоквиума и через час его сдавать ([https://www.dropbox.com/s/ef0514u08o7oiaw/colloq2021.pdf?dl=0 по обычным правилам]). Для пересдачи экзамена надо подключиться к конференции в 16:00 и получить вариант. Если студент сдает и коллоквиум, и экзамен, то экзамен сдается сразу после коллоквиума. Экзамен с прокторингом сдается по тем же правилам, что и в сессию, с аналогичным набором задач.

Пересдача комиссии 15 сентября. Для пересдачи надо подключиться к конференции https://zoom.us/j/91461977972 в 15:00 (Вахитов) и https://meet.google.com/kwo-mkrw-cig?authuser=0&hl=en_GB в 16:00 (Рамусь) и получить билет из программы коллоквиума. Через час, то есть, в 16:00 для Вахитова и в 17:00 для Рамуся начнется сдача комиссии. В ходе сдаче студенту может быть дана 1 или 2 задачи. Все полученные ранее оценки аннулируются и выставленная комиссией оценка является итоговой.

==Примерные сроки контрольных мероприятий==

Первое домашнее будет выложено 11 февраля, срок сдачи 4 марта.

Второе домашнее будет выложено 25 марта, крайний срок сдачи 15 апреля.

Третье домашнее будет выложено 22 апреля, крайний срок сдачи 13 мая.

Четвертое домашнее будет выложено 27 мая, крайний срок сдачи - 17 июня.

==Домашние задания  ==




[https://www.dropbox.com/s/anfjigs9fjqvegn/hw1_expanders.pdf?dl=0 Домашнее задание 1] Cрок сдачи 4.03.2021

[https://www.dropbox.com/s/0tso7xdebecqm73/hw2_expanders.pdf?dl=0 Домашнее задание 2] Срок сдачи 15.04.2021

[https://www.dropbox.com/s/btmjoyf1x9vgu5n/CCTI_3.pdf?dl=0 Домашнее задание 3] Срок сдачи 13.05.2021

[https://www.dropbox.com/s/fji1td797iz4tlu/CCTI_4.pdf?dl=0 Домашнее задание 4] Срок сдачи 17.06.2021

==Результаты ==
[https://www.dropbox.com/scl/fi/z8d7384cwf2e1mfzdimlo/results.xlsx?dl=0&rlkey=92hfs1kvcy19tjcpl4w5f3jtd Общая ведомость оценок (в нее вносятся и результаты тестов)]

[https://drive.google.com/drive/folders/1TIy7t8d__Eq5ZkVGc84hEj0u1cNSzIVN?usp=sharing Результаты тестов]

==Прочитанные лекции==

[https://www.youtube.com/playlist?list=PLEwK9wdS5g0otnz2d5xArMHyloteZLR5_ Записи лекций и семинаров]

[https://www.dropbox.com/sh/qe4p5oxyj6y42pr/AAB2jG92VGHt9BfxoU8hAxLJa?dl=0 Ссылка на записи на доске, сделанные во время лекции]

====Лекция 1 (15 января).  ====

Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
Реберное расширение и его связь с вершинным расширением.

====Лекция 2 (22 января).  ====

Матрица графа и ее собственные числа.
Максимальное по абсолютной величине собственное число регулярного графа. 
Лемма о перемешивании. От спектрального экспандера к комбинаторному.

====Лекция 3 (29 января).  ====
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа. Формула для числа Каталана (без доказательства).

====Лекция 4 (5 февраля). ====

Вероятностное доказательство существования  d-регулярного спектрального экспандера с d^c вершинами.

====Лекция 5 (12 февраля). ====
Степень графа и тензорное произведение графов и их собственные числа. 
Зигзаг-произведение графов и первая оценка его собственных чисел. 

====Лекция 6 (19 февраля). ====
Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
Вторая оценка для спектрального зазора зигзаг-произведения.

====Лекция 7 (26 февраля). ====
Второе собственное число связного недвудольного графа.

Алгоритм Рейнгольда.

====Лекция 8 (5 марта). ====
Применение экспандеров для дерандомизации. 

====Лекция 9 (12 марта). ====
Экспандер Маргулиса.

====Лекция 10 (19 марта). ====
Двудольные экспандеры: определение и вероятностное доказательство существования.

====Лекция 11 (26 марта). ====

Экспандер Варди - Парвареша.

====Лекция 12 (9 апреля). ====
Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.

====Лекция 13 (16 апреля).  ====
Оценка Хэмминга. 
Линейные коды, проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга.
Оценка Гилберта. 

====Лекция 14 (23 апреля) ====

Функция Шеннона. Графики оценок Хэмминга и Гилберта. Оценка Варшамова - Гилберта. Случайные линейные коды.

====Лекция 15 (30 апреля) ====
Коды Возенкрафта. Каскадные коды. Декодирование каскадного кода.

====Лекция 16.  (14 мая) ====
Коды Форни. Экспандерные коды: определение, последовательный алгоритм декодирования.

====Лекция 17  (21 мая) ====
Оценка Плоткина и коды Адамара. Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.

====Лекция 18 (28 мая ) ====
Доказательство оценок Хэмминга и Гилберта.
Деревья разрешения, метод противника. Сертификатная сложность. Чувствительность и блочная чувствительность. Неравенствo D < C^2

====Лекция 19 (4 июня). ====
Вероятностные деревья и неравенство bs = O(R).
Неравенствo D < C*bs.
Неравенство C< bs*s. 

====Лекция 20 (11 июня). ====
Представление булевых функций многочленами с действительными коэффициентами.
Теорема Маркова.
Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди).
Связь между чувствительностью и степенью многочлена (Hao Huang), без доказательства.

==Семинары  ==

=== Семинар 1 (15 января) ===
[https://jamboard.google.com/d/15TB6_iZW1cd7wK5mGuzfJbE7vmBBCtbeMPPzjjEpF0M/edit?usp=sharing Доска]
[https://www.dropbox.com/s/zmh1pxi6bpuek1o/cw1.pdf?dl=0 Листок 1  (комбинаторные экспандеры)]

=== Семинар 2 (22 января) ===
[https://jamboard.google.com/d/1jFFFGM6vXwLYC3fbhpTb7ylc9ZFMU3U1HjJfSh9yr6M/edit?usp=sharing Доска] [https://www.dropbox.com/s/pu34evbm8y2maqe/cw_2.pdf?dl=0 Листок 2  (спектр графов)]

=== Семинар 3 (29 января) ===
[https://jamboard.google.com/d/13VaSk9iQs5XPvakLMuvLiCGmKA41E0Qey4c1HWNJIzo/edit?usp=sharing Доска] [https://www.dropbox.com/s/4pi5nlbw4xu9wmg/cw_3.pdf?dl=0 Листок 3 ]

=== Семинар 4 (5 февраля) ===
[https://jamboard.google.com/d/10Z44MB2F2occAHvqJ4PrSpQvlgFenAC6k4N7uJpXv5w/edit?usp=sharing Доска] [https://www.dropbox.com/s/7vnehil6djh8y79/cw_4.pdf?dl=0 Листок 4]

=== Семинар 5 (12 февраля) ===
[https://jamboard.google.com/d/1mfGj2sLgBOpKfsZjvuahPzfJUk6wm5zhninahVDKUwo/edit?usp=sharing Доска] [https://www.dropbox.com/s/ihc3k6jregc9e6z/cw_5.pdf?dl=0 Листок 5]

=== Семинар 6 (19 февраля) ===
[https://jamboard.google.com/d/1h79fb2Nug016xprBRoD74ZDEeUAQ7sClfbrPGx0lTeI/edit?usp=sharing Доска] [https://www.dropbox.com/s/wupmaf9ynus9oxv/cw_6.pdf?dl=0 Листок 6]

=== Семинар 7 (26 февраля) ===
[https://jamboard.google.com/d/1rX6f9LyJ6SvhYmanIF84BG_bR6ZzMesnTlKY3uxifcQ/edit?usp=sharing Доска] [https://www.dropbox.com/s/7jkedcoj8g8p9p8/cw_7.pdf?dl=0 Листок 7]

=== Семинар 8 (5 марта) ===

[https://jamboard.google.com/d/1dyKtH9f1zdYCFDns83kxXHsYqONjdGxWpdw-uaAraGA/edit?usp=sharing Доска] [https://www.dropbox.com/s/ufbizzkfklhhmhz/cw_8.pdf?dl=0 Листок 8]

=== Семинар 9 (12 марта) ===
[https://jamboard.google.com/d/1awQ5fqIkaENm91WkSoFXvrYEue65yiNu9Q0GXsgE9O0/edit?usp=sharing Доска] [https://www.dropbox.com/s/r8hz79f1fa1ndjs/cw_9.pdf?dl=0 Листок 9]

=== Семинар 10 (19 марта) ===
[https://jamboard.google.com/d/1kjRHLzpG0HWqGPSnIlr-ZGWKzDPailwz87UlXoHj1Gc/edit?usp=sharing Доска] [https://www.dropbox.com/s/t6qfr25e8r8mduw/cw_10.pdf?dl=0 Листок 10]

=== Семинар 11 (26 марта) ===
[https://jamboard.google.com/d/1oQXvMNVkZHETueXWy6USr2YpJKgT5AeuIj-IJ-CJjBA/edit?usp=sharing Доска] [https://www.dropbox.com/s/1aj3ypcq0t0kfkg/cw_11.pdf?dl=0 Листок 11]


=== Семинар 12 (9 апреля) ===
[https://jamboard.google.com/d/1jTOBiX-gIAlsVdle6cEaHNL7Q9NCWQ_HRFhGCDfUTEo/edit?usp=sharing Доска] [https://www.dropbox.com/s/rlwh8uzn2r199ve/cw_12.pdf?dl=0 Листок 12]

=== Семинар 13 (16 апреля) ===
[https://jamboard.google.com/d/1hllQuFEhbXf8gF9MzuDzkrveCjr7KxmchwAekLknFL8/edit?usp=sharing Доска] [https://www.dropbox.com/s/fzaev9wgqszjrc1/cw_13.pdf?dl=0 Листок 13]

=== Семинар 14 (23 апреля) ===
[https://jamboard.google.com/d/106LwxU3Ka7TG8E3IM_LU8_fdAJzyKrlhKJaFtOQw1Wc/edit?usp=sharing Доска] [https://www.dropbox.com/s/iwzik10dli0msx8/cw_14.pdf?dl=0 Листок 14]

=== Семинар 15 (30 апреля) ===
[https://jamboard.google.com/d/1Cd_lpV-O-Xc3_V-s_dOixN0D1CCqSk6sx9BunRX1A3U/edit?usp=sharing Доска] [https://www.dropbox.com/s/jt20v54p3g36shi/cw_15.pdf?dl=0 Листок 15]

=== Семинар 16 (14 мая) ===
[https://jamboard.google.com/d/19A2vtH6NxD63mu8L94fy-zBw64lWsCjKzeo3hy7iZaI/edit?usp=sharing Доска] [https://www.dropbox.com/s/6689hmged6mq9s4/cw_16.pdf?dl=0 Листок 16]

=== Семинар 17 (21 мая) ===
[https://jamboard.google.com/d/1m9VRnjirxzsx6opLOkP4wAdiYJEFAdkTDEJdJykYYU0/edit?usp=sharing Доска] [https://www.dropbox.com/s/30nbn8qoey1sggu/cw_17.pdf?dl=0 Листок 17]


=== Семинар 18 (28 мая) ===
[https://jamboard.google.com/d/10B76x8eCre_Bwz9a0rU8I0FcsalqLbsm_brLI19QLWU/edit?usp=sharing Доска] [https://www.dropbox.com/s/yzxt4cv4pcxctuo/cw_18.pdf?dl=0 Листок 18]

=== Семинар 19 (4 июня) ===

[https://jamboard.google.com/d/1YPP85Y37bfS_rULYUxhKSxSeoLaAXNtbP_MaAJfAoxo/edit?usp=sharing Доска] [https://www.dropbox.com/s/hlm2xgdiypk1ypz/cw_19.pdf?dl=0 Листок 19]

=== Семинар 20 (11 июня) ===

[https://jamboard.google.com/d/1UcyZ7H8K_nxVCNZkexqXTxQrbVQ633QzHNbYgnto6L4/edit?usp=sharing Доска] [https://www.dropbox.com/s/9h46829jva4gat3/cw_20.pdf?dl=0 Листок 20]

==Конспекты лекций==
[https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 Конспекты лекций об экспандерах, полученные переработкой книги Ромащенко]

[https://www.dropbox.com/s/y4vifj9lzd5xic8/DecisionTrees.pdf?dl=0 Конспект лекций о деревьях разрешения.]

[https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0 Конспект лекций о кодах с исправлением ошибок] (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."

[https://www.dropbox.com/s/exx1jyype7dks5b/sensitivity.pdf?dl=0 Sensitivity for dummies (решение  Sensitivity conjecture).]

==Рекомендуемая литература  ==

[https://www.mccme.ru/~anromash/courses/expanders-notes-2014.pdf А.Е. Ромащенко. Экспандеры: конструкции и приложения.]

[https://www.researchgate.net/publication/2508255_On_the_Degree_of_Boolean_Functions_as_Real_Polynomials Noam Nisan, Mario Szegedy. On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4(4) · January 1995]

N. Nisan, CREW PRAM's and decision trees, STOC 1989, pages 327-335.

Alexander Razborov, Nikolay Vereshchagin. One Property of Cross-Intersecting Families. ECCC TR99-014.  https://eccc.weizmann.ac.il/report/1999/014/