Toutes les fonctions dont le poids de Fourier est concentré sur les petits ensembles calculées par les circuits AC0?

Toutes les fonctions dont le poids de Fourier est concentré sur les ensembles de petite taille (ou termes de faible degré) sont-elles calculées par les circuits ? $\mathsf{AC}^0$

cc.complexity-theory circuit-complexity boolean-functions fourier-analysis Stattrav
la source

Cette question semble intéressante, bien qu'il me manque un peu de contexte dans l'analyse de Fourier. J'apprécierais les références à la littérature connexe.

Markus

@Markus: ce livre 2.0 de Ryan O'Donnell est une excellente référence: contrib.andrew.cmu.edu/~ryanod

Alessandro Cosentino

presque l'inverse de Linial, Mansour, Nissan 1993 ? résultat aaronsons, contre - exemple de Linial-Nissan généralisé semble proche? mais à mon humble avis, cela devait être un moyen de généraliser le résultat de 1993 d'une manière ou d'une autre ... peut-être de manière considérable ...

vzn

une autre idée similaire au lieu de AC ^ 0, plus difficile à réfuter, serait la profondeur illimitée mais les circuits limités par la porte totale délimités par une "petite" fonction disent polynôme etc ...? afaik également la relation entre les circuits monotones et les coefficients de Fourier n'est pas si bien connue ...?

vzn

voir aussi l' indépendance polylogarithmique dupe les circuits AC ^ 0 par braverman

vzn

Réponses:

Considérez la fonction suivante sur $\{0,1\}^n$ : Il est clair que cette fonction est difficile pour AC ⁰ . D'un autre côté, la fonction est presque constante, donc presque tout son spectre de Fourier est au premier niveau.

f (x) = x_{0} \land \dots \land x_{n - \sqrt{n} - 1} \land (x_{n - \sqrt{n}} \oplus \dots \oplus x_{n - 1}) .

$f(x) = x_0 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1}).$

Si vous voulez un contre-exemple équilibré, considérez Cette fonction est presque toujours égale à , donc presque tout son spectre de Fourier est sur les deux premiers niveaux.

g (x) = x_{0} \oplus [x_{1} \land \dots \land x_{n - \sqrt{n} - 1} \land (x_{n - \sqrt{n}} \oplus \dots \oplus x_{n - 1})] .

$g(x) = x_0 \oplus \left[x_1 \land \cdots \land x_{n-\sqrt{n}-1} \land (x_{n-\sqrt{n}} \oplus \cdots \oplus x_{n-1})\right].$

x_{0}

$x_0$

Yuval Filmus
la source

Avez-vous des exemples robustes où la fonction ne peut pas être approximée dans AC0?

MCH

Une fonction concentrée sur les premiers niveaux

est toujours proche d'une fonction dépendant des

, donc si nous ne sommes intéressés que par les niveaux

, alors il n'y a pas d'exemples robustes.

O (1)

$O(1)$

O (1)

$O(1)$

O (1)

$O(1)$

Yuval Filmus du

@YuvalFilmus Que signifie le niveau de spectre de Fourier? Pourquoi cette fonction est-elle difficile pour

A C^{0}

$AC^0$

@Arul Un niveau de Fourier se compose de tous les coefficients de Fourier correspondant à des ensembles d'une taille donnée. Nous les considérons comme classés par ordre croissant de taille. Quant à savoir pourquoi cette fonction est difficile pour AC0, c'est un exercice. Astuce: la parité est difficile pour AC0.

Yuval Filmus

Il existe plusieurs façons de comprendre la question selon la signification précise de «petite taille» et «concentré».

1) Si vous considérez les fonctions booléennes de telle sorte que de leur norme l-2 soit concentré sur des petite taille, alors la réponse est non - la fonction majoritaire est un exemple tel que de la l La norme -2 est sur les ensembles bornés et n'est pas dans . $1-o(1)$ $S$ $1-o(1)$ ${\rm AC^0}$

2) Il existe un théorème de Bourgain selon lequel si la concentration est bien supérieure à celle de la fonction majoritaire, alors la fonction est approximativement une junte, et dépend donc de variables O (1).

3) Vous pouvez demander que l'influence totale qui est l'attente de | S | par rapport à la distribution décrite par est faible. Pour les fonctions dans l'influence totale est au plus de . Si l'influence totale est O (1) alors la fonction est proche d'une Junta, c'est-à-dire dépendant des variables O (1). $\hat f^2(S)$ $AC^0$ ${\rm polylog} (n)$

4) Si l'influence totale est il est possible mais pas connu que la fonction soit proche d'une fonction dans . $O(\log n)$ $AC^0$

5) Si l'influence totale est une autre possibilité est fonction de la profondeur bornée et de . Il est possible, mais inconnu, que chaque fonction du polylogue d'influence totale (n) soit proche d'une telle fonction. $O(polylog (n))$ $n^{polylog (n)}$

Gil Kalai
la source