Кажется, что теория геометрической сложности требует больших знаний математики, таких как алгебраическая геометрия, теория представлений.
Хотя я учусь на CS и не занимаюсь классами очень абстрактной и чистой математики, мне интересна эта программа.
Есть ли список «минимальных знаний» для изучения этой теории?
Этот список включает в себя конспекты лекций CS или математических отделов, обзоры любого журнала или конференций, а также учебники по чистой математике.
[ РЕДАКТИРОВАТЬ: Добавлено позже ] Спасибо за ваши комментарии.
Общая теория вычислений: я прочитал книгу Сипсера под названием «Введение в теорию вычислений»
Теория сложности: В частности, меня интересуют конкретные модели для нижних границ сложности. Таким образом, я прочитал часть «конкретных нижних границ» в учебнике Арора-Барака. У меня также есть базовые знания в нескольких главах книги о сложности общения, написанной Нисаном.
Основная математика: я узнал об основанной на доказательствах линейной алгебре, такой как общее определение векторного пространства и т. Д., А также точный аргумент вычислений, основанный на аргументе эпсилон-дельта.
Алгебра: я узнал об определении и примерах группы, кольца и поля. У меня был класс для студентов CS, и я не узнал об общем понимании этой алгебраической системы.
источник
Ответы:
Короткий ответ : действительно минимальные знания по математике для понимания первой половины плана GCT, после того как вы увидели немного групп, колец и полей, в основном изложены в главе 3 моей диссертации (бесстыдная самостоятельная вставка ). Эта глава, однако, является неполной, поскольку я не рассматриваю часть теории представлений. Теория репрезентации имеет решающее значение для второй половины плана (именно поэтому я работаю над расширением этой главы, чтобы включить ее).
Если вы действительно хотите попасть в GCT, Симметрия, Представления и Инварианты Гудмана и Уоллаха и Действия и Инварианты алгебраических групп У. Феррерса Сантоса относительно автономны и содержат много полезной информации, относящейся к GCT. Я не уверен, являются ли они лучшими источниками для изучения, поскольку я узнал о них только после того, как узнал большую часть этого материала, но они хороши с точки зрения соотношения того, что они освещают, и того, что имеет отношение к GCT. Фултон и Харрис отлично подходят для теории представлений, и многие примеры / упражнения в книге имеют отношение к GCT.
Более длинный ответ : это действительно зависит от того, что / сколько вы хотите узнать о GCT, как указал Виджай. Темы ниже только то , что я думаю , что это фон необходимо, так как это был вопрос. Я не уверен, что это полный список - я бы порекомендовал попробовать прочитать некоторые статьи о GCT, а когда вы заблудились, поищите справочные материалы. Когда вы изучаете справочный материал, все чаще возвращаетесь к документам GCT и смотрите, сможете ли вы следовать дальше.
(В зависимости от того, что вы хотите выучить, я на самом деле не согласен с Зейю в том, что вы должны сначала попробовать какую-нибудь коммутативную алгебру, хотя в какой-то момент в изучении GCT это станет необходимым.)
Если вы хотите понять, например, недавнюю работу Малмулей по FOCS , вы захотите понять:
Если вы хотите понять общую схему подхода GCT, но с некоторыми математическими подробностями , я бы предложил:
Постоянная и детерминантная проблема. # P-полнота перманента и GapL-полнота детерминанта. У Агравала есть хороший обзор (только немного устаревший) по этому вопросу, и доказательства полноты можно найти в книге Бургиссера «Полнота и редукция в алгебраической теории сложности» .
Группы и групповые действия (алгебраические группы и действия алгебраических групп полезны, но не обязательны на этом уровне). Вы должны понимать теорему об орбите-стабилизаторе.
Аффинная алгебраическая геометрия через Nullstellensatz Гильберта. В основном вам просто нужно понять соответствие между аффинными алгебраическими многообразиями и их координатными кольцами.
Основная теория представлений как у Фултона и Харриса . Помимо базовых определений, вам нужно знать полную сводимость этих представлений и тот факт, что представления классифицируются по разделам, но вам не обязательно нужно знать доказательство / конструкции последних.GLn GLn
Если вы хотите глубоко понять, что происходит (и я не уверен, что могу претендовать на то, чтобы быть там, но я думаю, что знаю, что мне нужно знать, чтобы туда попасть), вы, вероятно, также должны понимать:
Структура редуктивных алгебраических групп и замыканий орбит в их представлениях. Мне нравится книга В. Феррерса Сантоса для этого, но также Линейные алгебраические группы Бореля , Классические группы Вейля и другие классики.
Техника Луна-Вуст (Теорема Луна-Вуста, сложность Луна-Вуст)
Таннакская двойственность (см. Статью Делиня-Милна ; это будет трудное чтение без некоторого фона в теории категорий и аффинных алгебраических группах). По сути, это говорит о том, что «(про) аффинные алгебраические группы определяются их представлениями». Я не думаю, что вам нужна вся статья, а именно, как восстановить группу из ее категории представлений (Кор. 3.4).
Больше теории представлений , особенно в применении к координатным кольцам алгебраических групп и их замыканиям орбит. Мне очень нравится книга Гудмана и Уоллаха за это, особенно потому, что она в основном самодостаточна, и в ней есть много именно того, что вам нужно для понимания GCT. (Кроме того, многие из пояснительных / боковых разделов и упражнений в Фултоне и Харрисе прямо на грани GCT, особенно те, которые касаются коэффициентов Литтлвуда-Ричардсона и Кронекера.)
Если вы действительно хотите поработать над теорией представлений , вы, вероятно, захотите понять более алгебраическую комбинаторику / теорию комбинаторных представлений. Я действительно не знаю всех правильных ссылок для этого, но, безусловно, понимание правила Литтлвуда-Ричардсона является обязательным, и книга Фултона «Молодые таблицы» хороша для этого.
Самые последние статьи на эту сторону, о которых я знаю, это Блясиак , Кумар , Боуман, Де Висшер и Орельяна .
В зависимости от того, в каком направлении вы хотите идти, вы также можете посмотреть на квантовые группы, хотя это необязательно (примечание: это не особый случай групп, а обобщение в определенном направлении).
С более геометрической стороны , вы захотите взглянуть на такие вещи, как дифференциальная геометрия для касательных и осциллирующих пространств, кривизна, двойные многообразия и тому подобное, которые лежат в основе самой известной нижней границы для перми против дет из-за Миньона - Рессайре и следом за Ландсбергом - Манивелем - Рессайром . ( Mignon - Ressayre можно понять без каких-либо из этих вещей, но вы можете свободно рассматривать их работу как изучение кривизны некоторых разновидностей; для менее свободного взгляда посмотрите использование двойных разновидностей в Landsberg - Manivel - Ressayre . ) (См. Также Cai, Chen и Li , что расширяет Миньон-Рессайр на все странные характеристики.) См. Также Ландсберг и Кадиш .
Если вы заинтересованы в подходе GCT к умножению матриц , все дело в тензорном ранге, граничном ранге и секущих разновидностях. Я бы посоветовал взглянуть на бумаги Бургиссера - Икенмейера , Ландсберга и Оттавиани , Ландсберга , обзор и книгу Ландсберга . Конечно, было бы также хорошо знать классические вещи по умножению матриц (как верхние, так и нижние границы), но это отдельная червячная банка.
источник