Можно ли доказать

14

Результат 1: Теорема Линиала-Мансура-Нисана говорит о том, что вес Фурье функций, вычисленных по схемам сосредоточен на подмножествах малого размера с высокой вероятностью.AC0

Результат 2: вес Фурье у сконцентрирован на коэффициенте степени n .PARITYn

Вопрос: Есть ли способ доказать (если это доказуемо), что не вычисляется цепями A C 0 через / с использованием результатов 1 и 2?PARITYAC0

Stattrav
источник
7
Разве это не очевидное применение теоремы Линиала-Мансура-Нисана? То, как доказана теорема LMN (в частности, доказано ли это вероятностным аргументом или нет), не имеет значения.
Цуёси Ито
3
в то же время разве не доказана теорема Линиала-Мансура-Нисана, если принять теорему Хастада? Это выглядит как собака, гоняющаяся за собственным хвостом ...
Алессандро Косентино,
3
Вот как нижняя граница для размера схемы AC0, аппроксимирующей четность, определяется в заметках Райана О'Доннелла . См. Следствие 32.
Сашо Николов
5
я думаю, что более интересный вопрос в вашем комментарии: каждая функция, чей спектр Фурье сконцентрирован на низкоуровневых коэффициентах, вычисляется малогабаритными цепями AC0.
Сашо Николов
7
@Strattav Тогда вы можете задать этот вопрос.
Тайсон Уильямс,

Ответы:

11

Теорема LMN показывает, что если f - булева функция вычисляемая цепью AC 0 размера M,(f:{1,1}n{1,1})AC0

S:|S|>kf^(S)22Ω(k/(logM)d1)

f^([n])22Ω(n/(logM)d1)

|f^([n])|2Ω(n/(logM)d1)

не что иноекак соотношение F с функцией четности ( Π п я = 1 х я ) . Пусть δ быть доля входовгде F отличается от Р R I T Y .|f^([n])|(i=1nxi)δfPARITY

12δ|12δ|=|f^([n])|2Ω(n/(logM)d1)δ12Ω(n/(logM)d1)

Таким образом, если М , для F равным Р R I T Y ,poly(n)fPARITY

δ12n2n2(cn/(logM)d1)(logM)d1(c1)nM2Ω(n1/d1)

Таким образом, теорема LMN не только доказывает, что не может быть вычислена цепями A C 0 , но также показывает, что P A R I T Y имеет низкую корреляцию с цепями A C 0 .PARITYAC0PARITYAC0

Туласи
источник