Au fil des années, je me suis habitué à voir de nombreux théorèmes du TCS prouver à l'aide d'une analyse de Fourier discrète. La transformation de Walsh-Fourier (Hadamard) est utile dans pratiquement tous les sous-domaines du SCS, notamment les tests de propriété, le pseudo-aléatoire, la complexité...
Inspiré par cette question et en particulier par le dernier paragraphe de la réponse de Ou, j'ai la question suivante: Connaissez-vous des applications de la théorie de la représentation du groupe symétrique dans TCS? Le groupe symétrique est le groupe de toutes les permutations de avec une...
Soit une fonction booléenne et considérons f comme une fonction de à . Dans ce langage, l'expansion de Fourier de f est simplement l'expansion de f en termes de monômes libres carrés. (Ces monômes forment une base pour l'espace des fonctions réelles sur . La somme des carrés des coefficients est...
Une machine PHPHPH accès oracle à une fonction booléenne aléatoire f:{0,1}n→{−1,1}f:{0,1}n→{−1,1}f:\{0,1\}^n \to \{ -1,1 \} , et deux spectres de Fourier ggg et hhh . Le spectre de Fourier d'une fonction fff est défini comme F:{0,1}n→RF:{0,1}n→RF:\{0,1\}^n \to R :...
Une propriété de base des espaces vectoriels est qu'un espace vectoriel V⊆Fn2V⊆F2nV \subseteq \mathbb{F}_2^n de dimension n−dn−dn-d peut être caractérisé par ddd contraintes linéaires linéairement indépendantes - c'est-à-dire qu'il existe ddd vecteurs linéairement indépendants...
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 ?A
On dit qu'une fonction booléenne f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\} est une k-kk junta si fff a au plus kkk variables d'influence. Soit f : { 0 , 1 } n → { 0 , 1 }f:{0,1}n→{0,1}f: \{0,1\}^n \to \{0,1\} une junte de 2 k2k2k . Notons les variables de fff par x 1 , x 2 ,...
Dans un problème sur lequel je travaille actuellement, une extension de l'opérateur de bruit survient naturellement et j'étais curieux de savoir s'il y avait eu des travaux antérieurs. Permettez-moi d'abord de réviser l'opérateur de bruit de base TεTεT_{\varepsilon} sur les fonctions booléennes à...
Quelle est la complexité de requête la plus connue de l'algorithme d'apprentissage Goldreich-Levin? Les notes de cours du blog de Luca Trevisan , Lemma 3, l'indiquent comme . Est-ce le plus connu en termes de dépendance à n ? Je serai particulièrement reconnaissant pour une référence à une source...
Résultat 1: le théorème de Linial-Mansour-Nisan dit que le poids de Fourier des fonctions calculées par les circuits A C0UNEC0\mathsf{AC}^0 est concentré sur les sous-ensembles de petite taille à forte probabilité. Résultat 2: Le a son poids de Fourier concentré sur le coefficient du degré n .P A R...
Supposons que nous ayons une fonction f:Zn2→Rf:Z2n→Rf:\mathbb{Z}_2^n \to \mathbb{R} , telle que ∑x∈Zn2f(x)2=1∑x∈Z2nf(x)2=1\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1 (nous pouvons donc penser à {f(x)2}x∈Zn2{f(x)2}x∈Z2n\{ f(x)^2\} _{x\in \mathbb{Z}_2^n} comme une distribution) . Il est naturel de définir...
Un problème ouvert très intéressant dans l'étude des mesures de complexité de la fonction booléenne est la conjecture dite de sensibilité vs sensibilité de bloc. Pour plus d'informations sur la sensibilité par rapport à la sensibilité aux blocs, vous pouvez consulter le blog suivant de S. Aaronson...
Soit un groupe abélien fini, et soit P le polytope dans R Γ défini comme étant les points x satisfaisant les inégalités suivantes:ΓΓ\GammaPPPRΓRΓ\mathbb{R}^\Gammaxxx ∑g∈Gxg≤|G|xg≥0∀G≤Γ∀g∈Γ∑g∈Gxg≤|G|∀G≤Γxg≥0∀g∈Γ\begin{array}{cl} \sum_{g\in G} x_g \le |G| & \forall G \le \Gamma \\ x_g \ge 0 & \forall...
Braverman a montré que les distributions qui sont (logmϵ)O(d2)(logmϵ)O(d2)(log \frac{m}{\epsilon})^{O(d^2)}-indépendant indépendant ϵϵ\epsilon-fond profondeur ddd AC0AC0AC^0 circuits de taille mmm en "collant ensemble" l'approximation de Smolensky et l'approximation de Fourier de...