Статьи 2004-2005 гг. — Школа математики

Эта страница содержит ссылки на некоторые статьи, опубликованные в 2004-2005 учебном году. Мы намерены регулярно обновлять эту страницу, поэтому, если вы знаете о каких-либо новых ссылках / ссылках, сообщите нам об этом. Кроме того, этот год оказался еще более междисциплинарным, чем обычно, и многие статьи трудно отнести к категориям «сложность», «алгоритмы» или «комбинаторные». Таким образом, в отличие от предыдущих лет, мы даже не пытаемся проводить такую ​​классификацию. Однако мы все же попытаемся выделить несколько тем, по которым общение между резидентами программы было особенно интенсивным. Все остальные бумаги перечислены в алфавитном порядке.

Дерандомизация, псевдослучайность и приложения

• Б. Барак, Г. Киндлер, Р. Шалтиель, Б. Судаков, А. Вигдерсон, Моделирование независимости: новые конструкции конденсаторов, графов Рэмси, диспергаторов и экстракторов, Труды 37-го ежегодного симпозиума ACM по теории вычислений, 2005 г. , страницы 1-10
• Р. Градвол, Г. Киндлер, О. Рейнгольд, А. Та-Шма, О параметре ошибки диспергаторов, Материалы 9-го Международного семинара по рандомизации и вычислениям (RANDOM 2005) , страницы 294-305

Методы TCS/DM в статистической механике

• Д. Галвин, Медленное перемешивание локальной динамики для трехцветных раскрасок на регулярных двудольных графах
• Д. Галвин, Ограничение статистической суммы спиновых систем, Electronic Journal of Combinatorics , 13(1): R72, 2006
• Д. Галвин, П. Тетали, Медленное смешивание глауберовой динамики для жесткой модели на регулярных двудольных графах, Случайные структуры и алгоритмы , 28: 427-443, 2006
• Ф. Мартинелли, А. Синклер, Д. Вейц, Быстрое смешивание для независимых множеств, раскраски и другие модели на деревьях, Случайные структуры и алгоритмы , 31: 134-172, 2007
• Д. Вейц, Комбинаторные критерии единственности мер Гиббса, Случайные структуры и алгоритмы , 27(4): 445-475, 2005
• Д. Вайц, Обратный отсчет дерева

Неравенства типа Гротендика

• Н. Алон, К. Макарычев, Ю. Макарычев, А. Наор, Квадратичные формы на графах, Mathematicae Inventiones , 163: 499-522, 2006
• С. Арора, Э. Бергер, Э. Хазан, Г. Киндлер, С. Сафра, О неаппроксимируемости квадратичных программ, Материалы 46-го симпозиума по основам компьютерных наук , 2005, страницы 206-215

Другие документы

• С. Ааронсон, Оракулы тонкие, но не вредоносные, Труды 21-й ежегодной конференции IEEE по вычислительной сложности
  , 2006 г., страницы 261-273
• С. Ааронсон, NP-полные проблемы и физическая реальность, ACM SIGACT News , 36(1): 30-52, 2005
• С. Ааронсон, Квантовые вычисления, постселекция и вероятностное полиномиальное время, Proceedings of the Royal Society A , 461(2063): 3473-3482, 2005
• С. Ааронсон, Сложность соглашения, Труды 37-го ежегодного симпозиума ACM по теории вычислений, 2005 , страницы 634-643
• Р. Аарони, Э. Бергер, Теорема Менгера для бесконечных графов
• Р. Аарони, Э. Бергер, Пересечение матроида и симплициального комплекса, Труды Американского математического общества , 358(11): 4895-4917, 2006
• М. Алехнович, С. Арора, И. Турлакис, К результатам сильной неприближимости в иерархии Ловаса-Шрайвера, Труды 37-го ежегодного симпозиума ACM по теории вычислений, 2005 , страницы 294-303
• М. Алехнович, А. Бородин, Дж. Буреш-Оппенгейм, Р. Импальяццо, А. Маген, Т. Питасси, На пути к модели поиска с возвратом и динамического программирования, Труды 9-го0003 20-я ежегодная конференция IEEE по вычислительной сложности, 2005 г. , стр. 308-322
• М. Алехнович, С. Хот, Г. Киндлер, Н. Вишной, Сложность аппроксимации задачи ближайших векторов с предварительной обработкой, Материалы 46-го симпозиума по основам информатики, 2005 , страницы 216-225
• М. Алехнович, С. Хот, Т. Питасси, Неаппроксимируемость задач с фиксированными параметрами
• Н. Алон, Рейтинговые турниры, SIAM J. по дискретной математике , 20:137-142, 2006
• Н. Алон, Б. Боллобас, А. Гьярфас, Дж. Лехель, А. Скотт, Максимально направленные сокращения в ациклических орграфах, Journal of Graph Theory
  , 55: 1–13, 2007
• Н. Алон, Э. Фишер, И. Ньюман, Проверка свойств двудольного графа, SIAM Journal on Computing , 37: 959-976, 2007
• Н. Алон, М. Кривелевич, Дж. Спенсер, Т. Сабо, Игры с расхождениями, Электронный журнал комбинаторики , 12:R51, 2005
• Н. Алон, М. Кривелевич, Б. Судаков, Вложение почти остовных деревьев ограниченных степеней, Комбинаторика , 27: 629-644, 2007
• Н. Алон, И. Ньюман, А. Шен, Г. Тардос, Н. Верещагин, Разбиение многомерных множеств на небольшое число однородных частей, European Journal of Combinatorics , 28:134-144, 2007
• Н. Алон, Р. Радойчич, Б. Судаков, Дж. Вондрак, Результат типа Рамсея для гиперкуба, Journal of Graph Theory , 53: 196-208, 2006
• Н. Алон, А. Шапира, Характеристика (естественных) свойств графа, проверяемых с односторонней ошибкой, , SIAM Journal on Computing , 37: 1703-1727, 2008
• Н. Алон, А. Шапира, Б. Судаков, Аддитивная аппроксимация для задач удаления ребер, Материалы 46-го симпозиума по основам компьютерных наук, 2005 , страницы 419-428
• Б. Барак, Р. Канетти, Дж. Линделл, Р. Пасс, Т. Рабин, Безопасные вычисления без аутентификации, Труды 25-й ежегодной международной конференции по криптологии (КРИПТО 2005) , страницы 361-377
• Б. Барак, С. Халеви, Модель и архитектура псевдослучайной генерации и приложений к /dev/random, Труды 12-я конференция ACM по компьютерной и коммуникационной безопасности, 2005 г. , стр. 203-212
• Б. Барак, А. Сахай, Как играть почти в любую ментальную игру через сеть — Параллельная композиция с использованием суперполиномиального моделирования, Труды 46-го симпозиума по основам компьютерных наук, 2005 г.
  , страницы 543-552
• П. Бим, Т. Питасси, Н. Сегерлинд, А. Вигдерсон, Сильная теорема о прямом произведении для коррупции и многопартийной NOF-коммуникационной сложности непересекаемости множеств, Вычислительная сложность , 15(4): 391-432, 2006
• Э. Бергер, Р. Зив, Примечание о номере обложки и номере независимости в гиперграфах
• Ф. Бономо, М. Чудновский, Г. Дюран, Частичные характеристики клико-совершенных графов I: подклассы графов без клешней, Discrete Applied Mathematics , 156(7): 1058-1082, 2008
• Ф. Бономо, М. Чудновский, Г. Дюран, Частичные характеристики клико-совершенных графов II: графы без ромбов и спиральные дуги окружности
• М. Чудновский, В. Каннингем, Дж. Гилен, Алгоритм упаковки ненулевых A-путей в графах с групповыми метками
• М. Чудновский, Александра Овецкая, Раскрашивание квазилинейных графов, Journal of Graph Theory
  , 54(1): 41-50, 2007
• Н. Гоял, Г. Киндлер, М.