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...
Je lis l'annexe sur les limites inférieures de l'ACC pour NEXP dans le livre Arora et Barak's Computational Complexity . http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf L'un des lemmes clés est une transformation des circuits ACC0ACC0ACC^{0} en polynômes multilinéaires sur les...
Contexte: En apprentissage automatique, nous travaillons souvent avec des modèles graphiques pour représenter des fonctions de densité de probabilité dimensionnelle élevée. Si nous rejetons la contrainte qu'une densité intègre (somme) à 1, nous obtenons une fonction d'énergie structurée...
f:{−1,1}n→{−1,1}f:{−1,1}n→{−1,1}f\colon\{-1,1\}^n \to \{-1,1\}iiiInfi[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)]Infi[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)] \operatorname{Inf}_i[f] \stackrel{\rm def}{=} \Pr_{x\sim\{-1,1\}^n}[ f(x) \neq f(x^{\oplus i})] x⊕ix⊕ix^{\oplus...
Soit la fonction majoritaire, c'est-à-dire f ( x ) = 1 si et seulement si ∑ n i = 1 x i > n / 2 . Je me demandais s'il y avait une preuve simple du fait suivant (par «simple», je veux dire ne pas compter sur la méthode probabiliste comme Valiant 84 ou sur les réseaux de tri; fournissant de...
Soit une fonction booléenne de n variables booléennes. Soit g ( x ) = T ϵ ( f ) ( x ) la valeur attendue de f ( y ) lorsque y est obtenu à partir de x en inversant chaque coordonnée avec la probabilité ϵ / 2 .fffnnng(x)=Tϵ(f)(x)g(x)=Tϵ(f)(x)g(x)=T_\epsilon (f) (x)f(y)f(y)f(y)yyyxxxϵ/2ϵ/2\epsilon/2...
Il existe plusieurs résultats bien connus de limites inférieures de taille de circuit basés sur des restrictions aléatoires et le lemme de commutation .AC0AC0\mathsf{AC^0} Pouvons-nous développer un résultat de lemme de commutation pour prouver une taille de borne inférieure pour circuits T C 0...
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...
Soit une fonction booléenne de sensibilité s ( f ) et de sensibilité de bloc b s ( f ) .fffs(f)s(f)s(f)bs(f)bs(f)bs(f) La conjecture de conjecture de sensibilité Sensibilité-Bloc indique qu'il y a un tel que ∀ f , b s ( f ) ≤ s ( f ) c .c>0c>0c>0∀f, bs(f)≤s(f)c∀f, bs(f)≤s(f)c\forall f,\mbox{...
Voici un problème avec une saveur similaire à l'apprentissage des juntes: Entrée: Une fonction F: { 0 , 1 }n→ { - 1 , 1 }f:{0,1}n→{−1,1}f: \{0,1\}^n \rightarrow \{-1,1\} , représentée par un oracle d'appartenance, c'est-à-dire un oracle qui a donné XXx , renvoie F( x )F(X)f(x) . Objectif: trouver...
Il est bien connu que pour une classe de concept de dimension VC , il suffit d'obtenir exemples étiquetés pour PAC learn . Il n'est pas clair pour moi si l'algorithme d'apprentissage PAC (qui utilise ces nombreux échantillons) est approprié ou inapproprié? Dans les manuels de Kearns et Vazirani...
Quel est l'état de l'art sur la complexité des requêtes des formules 2-DNF d'apprentissage PAC appropriées avec des exemples de requêtes et sous une distribution uniforme ? Ou tout lien non trivial dessus? Parce que je ne connais pas du tout la théorie de l'apprentissage et que cette question est...
Supposons que nous ayons une fonction booléenne de . Il est clair qu'un vrai polynôme multivarié p ( x ) tel que f ( x ) = p ( x ) sur x ∈ { 0 , 1 } n peut être multilinéaire. Quelles sont les classes intéressantes de fonctions booléennes pour lesquelles le degré minimal de p ( x )F: { 0 , 1 }n→ {...
Étant donné un circuit booléen sur variables (qui utilise uniquement les portes NON, ET et OU), quelle est la manière la plus efficace d'extraire la formule booléenne représentée par le circuit? Existe-t-il un algorithme de polytime pour ce
Supposons que j'ai un circuit booléen qui calcule une fonction f : { 0 , 1 } n → { 0 , 1 } . Supposons que le circuit est composé de portes ET, OU et NON avec au plus fan-in et fan-out 2.CCCF: { 0 , 1 }n→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n \to \{0,1\} Soit une entrée donnée. Étant donné C et x , je...
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...
Dans la complexité de l'arbre de décision d'une fonction booléenne, une méthode de borne inférieure très connue est de trouver un polynôme (approximatif) qui représente la fonction. Paturi a donné une caractérisation des fonctions booléennes symétriques (partielles et totales) en termes de quantité...
Étant donné une fonction booléenne , nous avons le groupe d'automorphisme A u t ( f ) = { σ ∈ S n ∣ ∀ x , f ( σ ( x ) ) = f ( x ) } .fffAut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f)={σ∈Sn ∣∀x,f(σ(x))=f(x)}Aut(f) = \{\sigma \in S_n\ \mid \forall x, f(\sigma(x)) = f(x) \} Existe-t-il des bornes connues sur ?...
Disons que nous avons une fonction booléenne et que nous appliquons une restriction aléatoire δ sur f . De plus, disons que l'arbre de décision T qui calcule f se réduit à la taille O ( 1 ) en raison de la restriction aléatoire. Est-ce à dire que f a une influence totale très faible?F: { - 1 , 1...
Supposons que nous ayons une fonction telle que et est une distribution, c'est-à-dire .f:Zn2→Rf:Z2n→Rf:\mathbb{Z}_2^n \to \mathbb{R}∀x∈Zn2f(x)∈{12n,22n,…,2n2n},∀x∈Z2nf(x)∈{12n,22n,…,2n2n},\forall x\in \mathbb{Z}_2^n \quad f(x) \in \left\{\frac{1}{2^n}, \frac{2}{2^n}, \ldots, \frac{2^n}{2^n}...