Приложения теории представлений симметрической группы

42

Вдохновленный этим вопросом и, в частности, последним абзацем ответа Ор, у меня есть следующий вопрос:

Знаете ли вы какие-либо приложения теории представлений симметрической группы в TCS?

Симметрическая группа $S_n$ является группой всех перестановок $\{1, \ldots, n\}$ с композицией групповых операций. Представление $S_n$ является гомоморфизмом из $S_n$ в общую линейную группу обратимых $n \times n$ комплексных матриц. Представление действует на $\mathbb{C}^n$ путем умножения матриц. Неприводимое представление $S_n$ - это действие, не оставляющее собственного подпространства в $\mathbb{C}^n$ инвариантным. Неприводимые представления конечных групп позволяют определитьПреобразование Фурье над неабелевыми группами . Это преобразование Фурье имеет некоторые хорошие свойства дискретного преобразования Фурье над циклическими / абелевыми группами. Например, свертка становится точечным умножением в базисе Фурье.

Теория представлений симметрической группы прекрасно комбинаторна. Каждое неприводимое представление $S_n$ соответствует целочисленному разбиению $n$ . Нашли ли эта структура и / или преобразование Фурье над симметрической группой какое-либо применение в TCS?

co.combinatorics permutations fourier-analysis gr.group-theory Сашо Николов
источник

см. также приложения симметричной группы , Википедия

vzn

все очень интересные ответы. мне будет трудно выбрать один, чтобы принять.

Сашо Николов

Достойное чисто теоретическое введение / обзор, Таблицы Юнга и Представления Симметрической группы, Чжао

Взн

2

Эта статья только что попала в количественный анализ arXiv: решение двухсторонней типичности с использованием теории представлений симметрической группы Яниса Нецеля.

Тайсон Уильямс

Матричная факторизация на основе симметрии Эгнером и Пушелем использует элементы

и теории представлений для эффективной факторизации / декомпозиции / умножения матриц. см. S3.2 о симметрии Пермь-Пермь.

S_{n}

$S_n$

ВЗН

27

Вот несколько других примеров.

Diaconis и Shahshahani (1981) изучили, сколько случайных транспозиций требуется для генерации почти равномерной перестановки. Они доказали резкий порог 1/2 n log (n) +/- O (n). Генерация случайной перестановки со случайными транспозициями .
Кассабов (2005) доказал, что на симметрической группе можно построить ограниченный степенной экспандер. Симметричные группы и графы расширителей .
Куперберг, Ловетт и Пелед (2012) доказали, что существуют небольшие наборы перестановок, которые действуют равномерно на k-кортежи. Вероятностное существование жестких комбинаторных структур .

Шахар Ловетт
источник

3

Спасибо Shachar, и добро пожаловать в cstheory! Я позволил себе исправить ваши ссылки: они были немного несоответствующими

Сашо Николов

14

$S_n$ $H_0(S_n)$ $(\min,+)$

А. Тискин. Полулокальное сравнение строк: алгоритмические методы и приложения. http://arxiv.org/abs/0707.3619

Александр Тискин
источник

Спасибо! Это выглядит очень интересно, и я обязательно проверю это.

Сашо Николов

14

Вот один пример, который я знаю:

«О гипотезе« лог-ранга »в сложности коммуникации» , Р.Раз, Б.Шпикер,

Proceeding of the 34th FOCS, 1993, pp. 168-177
Combinatorica 15(4) (1995) pp. 567-588

Я считаю, что там гораздо больше.

Клим
источник

3

Не могли бы вы обобщить, что модели представления и как это применяется?

Виджай Д

@VijayD, вероятно, Клим знает больше, но проблема здесь в том, как сложность связи функции связан с журналом его ранга (думая о как вещественная матрица). Они строят ранга и CC . Ранг вычисляется путем записи его в виде суммы матриц в регулярном представлении

f : {0, 1}^{n} \times {0, 1}^{n} \to {0, 1}

$f:\{0,1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$

f

$f$

2^{d} \times 2^{d}

$2^d \times 2^d$

f

$f$

2^{O (n)}

$2^{O(n)}$

Ω (n \log \log n)

$\Omega(n \log \log n)$

f

$f$

S_{n}

$S_n$

Сашо Николова

На самом деле я читал эту статью некоторое время назад, так что теперь я точно не помню ее.

Клим

11

Вот пример из квантовых вычислений:

Роланд, Джереми; Ротетлер, Мартин; Магнин, Лойк; Амбайнис, Андрис (2011), «Противники с симметричной симуляцией для генерации квантовых состояний», Материалы 26-й ежегодной конференции IEEE 2011 года по вычислительной сложности, CCC '11, IEEE Computer Society, стр. 167–177, doi: 10.1109 / CCC. 2011,24

Они показывают, что сложность квантового запроса некоторой проблемы, называемой стиранием индекса, равна использующей теорию представлений симметрической группы для построения оптимальной матрицы противника для включения в метод квантового противника. $\Omega(\sqrt{n})$

Робин Котари
источник

10

Кнут 3-й том «Искусства компьютерного программирования» посвящен поиску и сортировке и уделяет много внимания комбинаторике и перестановкам, а также соответствию Робинсона-Шенстеда-Кнута , которое является центральным в теории представлений симметрической группы.
Есть несколько работ Эллис-Фридгут-Пилпель и Эллис-Фридгут-Фильмус, которые решают экстремальные комбинаторные задачи с использованием гармонического анализа на . Не совсем TCS, но довольно близко. $S_n$
В начале 90-х годов Айтай получил замечательные результаты по модульному представлению которые были мотивированы вопросами сложности вычислений. Я не помню деталей или того, была ли она опубликована, но это стоит изучить! $S_n$

Гил Калай
источник

Спасибо Гил! Я полагаю, что одна из статей Аджаджа, которую вы имеете в виду, это: eccc.hpi-web.de/eccc-reports/1994/TR94-015/index.html . Я думаю, что применение заключается в доказательстве сложности принципа голубя, но я пока не совсем понимаю связь.

Сашо Николов

6

Симметрическая группа не поддается строгой выборке Фурье по Мур, Рассел, Шульман

«мы показываем, что скрытая проблема подгруппы над симметричной группой не может быть эффективно решена с помощью сильной выборки Фурье ... Эти результаты применимы к частному случаю, связанному с проблемой изоморфизма графов».

со связью с решением проблемы изоморфизма графов с помощью подходов QM

с 5 Теория представлений симметрической группы

ВЗН
источник

5

Больше статистики, чем информатики, но все же интересно: в главе 8 монографии Диакониса о групповых представлениях в области вероятности и статистики разрабатываются методы спектрального анализа данных, связанных с группойЭто расширяет классический спектральный анализ данных, скажем, временных рядов, где натуральное - это действительные числа или целые числа, которые складываются. Имеет смысл принять за когда данные заданы ранжированием. Монография посвящена интерпретации коэффициентов Фурье ранжирования данных. В этом случае набор данных представлен разреженным $G$ $G$ $G$ $S_n$ $f:S_n \rightarrow \mathbb{R}^+$ который отображает ранжирование (заданное перестановкой) в той части населения, которая предпочитает ранжирование.

Также в той же главе анализ Фурье по симметричным и другим группам используется для получения моделей и тестов ANOVA.

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

Сашо Николов
источник

Какова естественная структура группы для ранжирования проблем?

Суреш Венкат

1

@Suresh Я имел в виду симметричную группу, но мой последний абзац - более желаемое, чем все остальное. Я имел в виду хунтоподобную проблему ранжирования: изучение функции которая зависит от относительного упорядочения только нескольких элементов из нескольких выборок. Возможно, методы Фурье могут дать нетривиальные границы выборки

f : S_{n} \to {0, 1}

$f:S_n \rightarrow \{0, 1\}$

[n]

$[n]$

Сашо Николов

5

Теория представлений симметрической группы играет ключевую роль в подходе теории геометрической сложности к нижним оценкам определителя или умножения матриц.

Бюргиссер и Икенмейер доказывают нижнюю границу ранга умножения матриц, используя теорию представлений . $S_n$
Относительно того, как теория представления связана с нижними оценками определителя, см. Теория геометрической сложности II: На пути к явным препятствиям для вложений между многообразиями классов и Теория геометрической сложности VI: The ip через позитивность $S_n$

Джошуа Грохов
источник

4

Кандидатская диссертация Хуанса, ВЕРОЯТНОСТНОЕ ОБОСНОВАНИЕ И ОБУЧЕНИЕ НА ПЕРМУМУЛЯЦИЯХ: использование структурных разложений симметрической группы . приложение представляет собой «настоящий сценарий отслеживания нескольких людей на основе камеры».
Теоретико-вероятностный вывод Фурье над перестановками Хуанга, Гострина, Гибаса; Журнал исследований машинного обучения 10 (2009) 997-1070. см., например, раздел 5. Теория представлений в симметрической группе
еще одна мультитрековая заявка. Отслеживание нескольких объектов с представлениями симметрической группы (2007) Кондора, Говарда, Джебары
Распределение вероятностей обучения по перестановкам с помощью коэффициентов Фурье, Irurozki, Calvo, Lozano (Dept CS / AI). см. раздел 2 Преобразование Фурье на симметрической группе

ВЗН
источник

1

Я бы предложил объединить этот ответ с другой ссылкой на перестановки в обучении

Сашо Николов,

хорошо ... слияние ...

vzn

см. также Интерпретация фазового спектра в Фурье-анализе данных частичного ранжирования и подход обработки сигналов к Фурье-анализу данных ранжирования: важность фазы Какаралой, которая, кажется, расширяет гораздо более раннюю работу Diaconis

vzn

-1

Применение теории представлений симметрических групп для вычисления хроматических полиномов графов Клина и Печа

ВЗН
источник

ps application

vzn

-2

эта высоко цитируемая статья Билса, 1997, STOC, кажется, доказывает, что квантовые вычисления преобразований Фурье по симметричным группам находятся в BQP, т.е. квантовом полиномиальном времени

ВЗН
источник

2

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

Сашо Николов

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

Сашо Николов

хорошо, Мур и др. процитировали Билса, но это не то, как я нашел бумагу Билса. может слиться позже, но сейчас какой-то аудитории, похоже, не нравится этот рефери

Била

я не уверен, я думаю, что это хорошая ссылка. одна проблема для меня заключается в том, что вы не объясняете, почему важно иметь возможность вычислять неабелево преобразование Фурье, как оно мотивировано.

Сашо Николов

1

Я бы предпочел, чтобы ответы стояли сами по себе и давали читателю достаточно подсказок, чтобы можно было решить, читать этот документ полностью или нет. Я хотел бы, чтобы ответ показал более поверхностное понимание материала.

Сашо Николов

-5

более старый пример, но все еще с недавними / текущими исследованиями, некоторые из этой теории обнаруживаются в математике «совершенного шаффла» , рассматриваемого как элемент симметричной группы и который был известным открытием в то время. В [1] упоминается применение идеального алгоритма тасования к параллельной обработке, а также соединение с Cooley-Tukey O (n log n) DFT. [2] более свежая. идеальное перемешивание проявляется при параллельной обработке [3], проектировании памяти и сортировке сетей.

[1] Математика совершенного шаффла. Автор Диаконис, Грэм, Кантор. 1983

[2] Циклы многоходовой совершенной в случайном порядке перестановки Эллиса, Вентилятор, Shallit (2002)

[3] Параллельная обработка с идеальным перемешиванием Стоуна, 1971

[4] Омега сеть на основе идеального перетасовки

[5] Параллельная и последовательная перестановка на месте и совершенная перетасовка с использованием инволюций Yang et al (2012)

ВЗН
источник

1

Используется ли теория представлений в этих статьях?

Сашо Николов

Похоже, это особый случай

2012 года

2

что является частным случаем чего? идеальный случайный случай - это перестановка. я спрашиваю, теория представлений используется в доказательствах в этих статьях? Я не нашел ни одного.

Сашо Николов

3

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

Сашо Николов

Несовершенная перетасовка тоже интересна, но весь ответ - идеальная перетасовка. Похоже, что те же самые результаты могут быть пересмотрены или подтверждены теорией представлений, или же они используют некоторые основные аспекты без явной / прямой ссылки на них. В примечании шахарского ответа цитируется Дьяконис, один и тот же автор одной из статей этого ответа. другими словами, вышеупомянутые авторы наверняка могли бы ответить на ваш вопрос лучше, но я ожидаю, что они ответят хотя бы несколько утвердительно =) ... кроме того, вы только что описали теорию представлений как "прекрасно комбинаторную" в своем собственном вопросе!

ВЗН

Приложения теории представлений симметрической группы

Ответы: