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

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

Результат 2: вес Фурье у сконцентрирован на коэффициенте степени . $\mathsf{PARITY}$ $n$

Вопрос: Есть ли способ доказать (если это доказуемо), что не вычисляется цепями через / с использованием результатов 1 и 2? $\mathsf{PARITY}$ $\mathsf{AC}^0$

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis Stattrav
источник

Разве это не очевидное применение теоремы Линиала-Мансура-Нисана? То, как доказана теорема LMN (в частности, доказано ли это вероятностным аргументом или нет), не имеет значения.

Цуёси Ито

в то же время разве не доказана теорема Линиала-Мансура-Нисана, если принять теорему Хастада? Это выглядит как собака, гоняющаяся за собственным хвостом ...

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

Вот как нижняя граница для размера схемы AC0, аппроксимирующей четность, определяется в заметках Райана О'Доннелла . См. Следствие 32.

Сашо Николов

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

Сашо Николов

@Strattav Тогда вы можете задать этот вопрос.

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

Ответы:

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

\sum_{S : | S | > k} \hat{f} (S)^{2} \leq 2^{- Ω (k / (\log M)^{d - 1})}

$\sum_{S:|S|> k} \hat f(S)^{2} \leq 2^{-\Omega(k/(\log M)^{d-1})}$

$\Rightarrow \hat f([n])^{2} \leq 2^{-\Omega(n/(\log M)^{d-1})}$

$\Rightarrow |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}$

не что иноекак соотношение F с функцией четности . Пусть быть доля входовгде отличается от . $|\hat f([n])|$ $(\prod_{i = 1}^{n}x_i)$ $\delta$ $f$ $PARITY$

\begin{aligned} 1 - 2 δ \leq | 1 - 2 δ | & = | \hat{f} ([n]) | \leq 2^{- Ω (n / (\log M)^{d - 1})} \\ \Rightarrow δ & \geq 1 - 2^{- Ω (n / (\log M)^{d - 1})} \end{aligned}

$\begin{align} 1 -2 \delta \leq |1 - 2\delta| &= |\hat f([n])| \leq 2^{-\Omega(n/(\log M)^{d-1})}\\ \Rightarrow \delta &\geq 1 - 2^{-\Omega(n/(\log M)^{d-1})} \end{align}$

Таким образом, если М , для равным , $poly(n)$ $f$ $PARITY$

\begin{aligned} δ & \leq \frac{1}{2^{n}} \\ \Rightarrow 2^{n} & \geq 2^{(c n / (\log M)^{d - 1})} \\ \Rightarrow (\log M)^{d - 1} & \geq (c - 1) n \\ \Rightarrow M & \geq 2^{Ω (n^{1 / d - 1})} \end{aligned}

$\begin{align} \delta &\leq \frac{1}{2^n}\\ \Rightarrow 2^n &\geq 2^{(cn/(\log M)^{d-1})}\\ \Rightarrow (\log M)^{d-1} &\geq (c-1)n \\ \Rightarrow M &\geq 2^{\Omega (n^{1/d-1})} \end{align}$

Таким образом, теорема LMN не только доказывает, что не может быть вычислена цепями , но также показывает, что имеет низкую корреляцию с цепями . $PARITY$ $AC^{0}$ $PARITY$ $AC^{0}$

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