Паритет и

19

Четность и подобны неразлучным близнецам. Или так казалось за последние 30 лет. В свете результатов Райана возобновится интерес к маленьким классам. $AC^0$

Faxst Saxe Sipser от Yao до Hastad - это все паритетные и случайные ограничения. Разборов / Смоленский является приближенным полиномом с четностью (хорошо, мод-гейтс). Аспнес и др. Используют слабую степень по паритету. Кроме того, Аллендер Хертрампф и Бейгель Таруи собираются использовать Toda для небольших классов. И Разборов / Бим с принятием деревьев. Все это попадает в паритетную корзину.

1) Каковы другие естественные проблемы (кроме четности), которые могут быть показаны непосредственно, чтобы не быть в ? $AC^0$

2) Кто-нибудь знает о кардинально отличном подходе к нижней границе AC ^ 0, который был опробован?

cc.complexity-theory complexity-classes lower-bounds circuit-complexity V Vinay
источник

13

Результат Бенджамина Россмана о снижении для k-клики из STOC 2008. $AC^0$

Ссылки:

Пол Бим, "Учебник для начинающих с леммой ", Технический отчет 1994.
Бенджамин Россман, « О постоянной глубине сложности k-Clique », STOC 2008.

Кава
источник

Разве Россман не был поглощен праймером Бима, в котором также была клика? Конечно, аргументы более сложные.

V Vinay

@V Vinay: можешь дать ссылку на статью Пола Бима?

Каве

4

Результат Россмана показывает, что

клик не может быть вычислен схемами постоянной глубины размера

k

$k$

. Обратите внимание, что постоянная в показателе степенинезависит от глубины контура, где она улучшается на нижней границе Бима

.

Ω (n^{k / 4})

$\Omega(n^{k/4})$

n^{Ω (k / d^{2})}

$n^{\Omega(k/d^2)}$

Srikanth

@Srikanth, я думал, что V Vinay говорит, что у Beame более новый результат, но я не смог найти ничего на его странице. Спасибо за разъяснение.

Каве

1

Срикант прав насчет границ. Каве, не новая газета; Я использовал «subumed» в том смысле, что я указал Beame в своем вопросе и, следовательно, знал о нижней границе клики.

V Vinay

12

Существует подход «сверху вниз» Хостада, Юкны и Пудлака, как это сделано в их статье « Нижние границы сверху вниз для схем глубины три» . К сожалению, мы до сих пор не смогли расширить подход к более высоким глубинам.

Кристоффер Арнсфельт Хансен
источник

Да. Я думал, что у вас есть бумага под влиянием этого подхода?

V Vinay

10

$AC^{0}$

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

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

2

Большинство это то же самое на самом деле. Я должен был упомянуть об этом, хотя. Кроме того, в середине 80-х была опубликована статья Боппана о большинстве.

V Vinay

8

Два других «классических» метода - это метод «узкого места» Хакена и метод слияния Карчмера (так его назвал Ави Вигдерсон), которые гораздо проще применять в монотонной среде.

Юваль Фильмус
источник

Паритет и

Ответы: