Обязательное условие для изучения GCT

Кажется, что теория геометрической сложности требует больших знаний математики, таких как алгебраическая геометрия, теория представлений.

Хотя я учусь на CS и не занимаюсь классами очень абстрактной и чистой математики, мне интересна эта программа.

Есть ли список «минимальных знаний» для изучения этой теории?

Этот список включает в себя конспекты лекций CS или математических отделов, обзоры любого журнала или конференций, а также учебники по чистой математике.

[ РЕДАКТИРОВАТЬ: Добавлено позже ] Спасибо за ваши комментарии.

Общая теория вычислений: я прочитал книгу Сипсера под названием «Введение в теорию вычислений»

Теория сложности: В частности, меня интересуют конкретные модели для нижних границ сложности. Таким образом, я прочитал часть «конкретных нижних границ» в учебнике Арора-Барака. У меня также есть базовые знания в нескольких главах книги о сложности общения, написанной Нисаном.

Основная математика: я узнал об основанной на доказательствах линейной алгебре, такой как общее определение векторного пространства и т. Д., А также точный аргумент вычислений, основанный на аргументе эпсилон-дельта.

Алгебра: я узнал об определении и примерах группы, кольца и поля. У меня был класс для студентов CS, и я не узнал об общем понимании этой алгебраической системы.

Короткий ответ : действительно минимальные знания по математике для понимания первой половины плана GCT, после того как вы увидели немного групп, колец и полей, в основном изложены в главе 3 моей диссертации (бесстыдная самостоятельная вставка ). Эта глава, однако, является неполной, поскольку я не рассматриваю часть теории представлений. Теория репрезентации имеет решающее значение для второй половины плана (именно поэтому я работаю над расширением этой главы, чтобы включить ее).

Если вы действительно хотите попасть в GCT, Симметрия, Представления и Инварианты Гудмана и Уоллаха и Действия и Инварианты алгебраических групп У. Феррерса Сантоса относительно автономны и содержат много полезной информации, относящейся к GCT. Я не уверен, являются ли они лучшими источниками для изучения, поскольку я узнал о них только после того, как узнал большую часть этого материала, но они хороши с точки зрения соотношения того, что они освещают, и того, что имеет отношение к GCT. Фултон и Харрис отлично подходят для теории представлений, и многие примеры / упражнения в книге имеют отношение к GCT.

Более длинный ответ : это действительно зависит от того, что / сколько вы хотите узнать о GCT, как указал Виджай. Темы ниже только то , что я думаю , что это фон необходимо, так как это был вопрос. Я не уверен, что это полный список - я бы порекомендовал попробовать прочитать некоторые статьи о GCT, а когда вы заблудились, поищите справочные материалы. Когда вы изучаете справочный материал, все чаще возвращаетесь к документам GCT и смотрите, сможете ли вы следовать дальше.

(В зависимости от того, что вы хотите выучить, я на самом деле не согласен с Зейю в том, что вы должны сначала попробовать какую-нибудь коммутативную алгебру, хотя в какой-то момент в изучении GCT это станет необходимым.)

Если вы хотите понять, например, недавнюю работу Малмулей по FOCS , вы захотите понять:

• принцип «жесткость против случайности» (см. « Импальяццо - Кабанец» , а также, возможно , список работ Билла Гасарча о твердости и случайности )
• базовая алгебраическая геометрия с точностью до нульстелленсатца Гильберта и нормировочной леммы Нётера. Их можно найти в любом базовом учебнике по алгебраической геометрии и, вероятно, в большинстве заметок о нем.
• некоторая классическая теория инвариантов (для этой статьи вам не нужны теория геоемтрических инвариантов, схемы и книга Мамфорда-Фогарти-Кирвана). На ум приходит книга Штурмфельса «Алгоритмы в теории инвариантов» .
• Для некоторых результатов в статье, но ни в коем случае не для статьи в целом, вам могут понадобиться некоторые из (и эти ссылки также можно найти в статье): теория представлений как у Фултона и Харриса , результаты о матричных инвариантах [ Артин, Прочеси, Разымслов], ...$SL_n$

Если вы хотите понять общую схему подхода GCT, но с некоторыми математическими подробностями , я бы предложил:

• Постоянная и детерминантная проблема. # P-полнота перманента и GapL-полнота детерминанта. У Агравала есть хороший обзор (только немного устаревший) по этому вопросу, и доказательства полноты можно найти в книге Бургиссера «Полнота и редукция в алгебраической теории сложности» .

• Группы и групповые действия (алгебраические группы и действия алгебраических групп полезны, но не обязательны на этом уровне). Вы должны понимать теорему об орбите-стабилизаторе.

• Аффинная алгебраическая геометрия через Nullstellensatz Гильберта. В основном вам просто нужно понять соответствие между аффинными алгебраическими многообразиями и их координатными кольцами.

• Основная теория представлений как у Фултона и Харриса . Помимо базовых определений, вам нужно знать полную сводимость этих представлений и тот факт, что представления классифицируются по разделам, но вам не обязательно нужно знать доказательство / конструкции последних.$GL_n$$GL_n$

Если вы хотите глубоко понять, что происходит (и я не уверен, что могу претендовать на то, чтобы быть там, но я думаю, что знаю, что мне нужно знать, чтобы туда попасть), вы, вероятно, также должны понимать:

• Структура редуктивных алгебраических групп и замыканий орбит в их представлениях. Мне нравится книга В. Феррерса Сантоса для этого, но также Линейные алгебраические группы Бореля , Классические группы Вейля и другие классики.

• Техника Луна-Вуст ​​(Теорема Луна-Вуста, сложность Луна-Вуст)

• Таннакская двойственность (см. Статью Делиня-Милна ; это будет трудное чтение без некоторого фона в теории категорий и аффинных алгебраических группах). По сути, это говорит о том, что «(про) аффинные алгебраические группы определяются их представлениями». Я не думаю, что вам нужна вся статья, а именно, как восстановить группу из ее категории представлений (Кор. 3.4).

• Больше теории представлений , особенно в применении к координатным кольцам алгебраических групп и их замыканиям орбит. Мне очень нравится книга Гудмана и Уоллаха за это, особенно потому, что она в основном самодостаточна, и в ней есть много именно того, что вам нужно для понимания GCT. (Кроме того, многие из пояснительных / боковых разделов и упражнений в Фултоне и Харрисе прямо на грани GCT, особенно те, которые касаются коэффициентов Литтлвуда-Ричардсона и Кронекера.)

Если вы действительно хотите поработать над теорией представлений , вы, вероятно, захотите понять более алгебраическую комбинаторику / теорию комбинаторных представлений. Я действительно не знаю всех правильных ссылок для этого, но, безусловно, понимание правила Литтлвуда-Ричардсона является обязательным, и книга Фултона «Молодые таблицы» хороша для этого.

Самые последние статьи на эту сторону, о которых я знаю, это Блясиак , Кумар , Боуман, Де Висшер и Орельяна .

В зависимости от того, в каком направлении вы хотите идти, вы также можете посмотреть на квантовые группы, хотя это необязательно (примечание: это не особый случай групп, а обобщение в определенном направлении).

С более геометрической стороны , вы захотите взглянуть на такие вещи, как дифференциальная геометрия для касательных и осциллирующих пространств, кривизна, двойные многообразия и тому подобное, которые лежат в основе самой известной нижней границы для перми против дет из-за Миньона - Рессайре и следом за Ландсбергом - Манивелем - Рессайром . ( Mignon - Ressayre можно понять без каких-либо из этих вещей, но вы можете свободно рассматривать их работу как изучение кривизны некоторых разновидностей; для менее свободного взгляда посмотрите использование двойных разновидностей в Landsberg - Manivel - Ressayre . ) (См. Также Cai, Chen и Li , что расширяет Миньон-Рессайр на все странные характеристики.) См. Также Ландсберг и Кадиш .

Если вы заинтересованы в подходе GCT к умножению матриц , все дело в тензорном ранге, граничном ранге и секущих разновидностях. Я бы посоветовал взглянуть на бумаги Бургиссера - Икенмейера , Ландсберга и Оттавиани , Ландсберга , обзор и книгу Ландсберга . Конечно, было бы также хорошо знать классические вещи по умножению матриц (как верхние, так и нижние границы), но это отдельная червячная банка.