Какие препятствия для расширения

13

Доказательство Омер Рейнгольда , что дает алгоритм USTCON (В U ndirected граф со специальными вершинами S и т , они Con подсоединены?) , Используя только logspace. Основная идея состоит в том, чтобы построить график расширителя из исходного графика, а затем выполнить обход в графике расширителя. График экспандера составляется путем возведения в квадрат исходного графика логарифмически много раз. На графике расширителя диаметр является только логарифмическим, поэтому достаточно выполнить поиск по логарифмической глубине в DFS.Lзнак равноSLsT

Расширение результата до подразумевало бы существование алгоритма логического пространства для DSTCON - то же самое, но для D- ориентированных графов. (Иногда просто STCON.) Мой вопрос, может быть, немного мягкий, каковы основные препятствия для распространения доказательства Рейнгольда на это?Lзнак равноNL

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

Есть ли главный недостаток в этой концепции? Или нет хороших конструкций таких расширителей? Или это как-то требует больше памяти, чем ненаправленная версия?

Я, к сожалению, не могу найти много на графиках направленного расширителя. Фактически все, что я мог найти, было /math/2628930/how-can-one-construct-a-directed-expander-graph-with-varying-degree-distribution (что остается без ответа) и https://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers . Есть ли другой термин, под которым я должен искать?

Алекс Мейбург
источник
3
Эта статья дает некоторое представление о расширении до L = R L : people.seas.harvard.edu/~salil/research/regular-abs.htmlLзнак равноSLLзнак равнорL
sdcvvc
2
Смотрите пункт 3. здесь . Вы можете возразить, что это полная спекуляция, но обратите внимание, что в ответ Скотта в основном говорится то же самое о случайном исследовании ориентированных графов.
Томас Климпел

Ответы:

19

Центральная проблема заключается в том, что на ориентированных графах даже действительно случайное блуждание не попадает во все вершины в ожидаемое полиномиальное время, не говоря уже о псевдослучайном блуждании. Стандартный контрпример здесь представляет собой ориентированный граф с вершинами, упорядоченными слева направо, где каждая вершина имеет ребро, ведущее к вершине справа (за исключением самой правой вершины t ), и каждая вершина также имеет ребро, ведущее все обратный путь к самой левой вершине, с . Чтобы добраться от s до t случайным блужданием, нужно ~ 2 n времени. Итак, что же представляет собой рандомизированный алгоритм малого пространства для направленной связи, который мы надеемся дерандомизировать, аналогично тому, что сделал Рейнгольд дляNTssT2N ? (Другими словами, как мы показываем R L = N L , не говоря уже о L = N L ?). Для направленной связности, конечно, есть алгоритм Савича, но для этого требуетсяпространство O ( log 2 n ) , а для общих графов никому не удавалось улучшить его за полвека, с использованием случайности или без нее.USTСОNрLзнак равноNLLзнак равноNLО(журнал2N)

Скотт Ааронсон
источник
Пример алгоритма, который я бы описал, был бы, примерно - ну, вы запускаете операцию Рейнгольда «квадрат и зигзаг» несколько раз, чтобы начать. Я предполагаю, что модификация состояла бы в том, что вместо квадрата, содержащего только пути длины 2 в исходном графе, он включает пути длины 1 и 2. Попробуйте все логарифмически глубокие последовательности, например, его. Если мы нумеруем вершины вашего графа как 1, 2, .. n, то первый «квадрат» графа соединяет 1 к 2 и 3, следующий «квадрат» соединяет его с 2345 и т. Д. Зигзагообразные шаги сохраняют градусы низкий. Очевидно грубый, но я не вижу, почему это терпит неудачу.
Алекс Мейбург
N2Θ(журналN)N2Θ(журналN)журналN