Parité et

19

La parité et sont comme des jumeaux inséparables. Ou du moins, cela semble au cours des 30 dernières années. À la lumière du résultat de Ryan, il y aura un regain d'intérêt pour les petites classes. $AC^0$

Furst Saxe Sipser à Yao à Hastad sont toutes des restrictions de parité et aléatoires. Razborov / Smolensky est un polynôme approximatif avec parité (ok, mod gates). Aspnes et al utilisent un faible degré de parité. De plus, Allender Hertrampf et Beigel Tarui sont sur l'utilisation de Toda pour les petites classes. Et Razborov / Beame avec des arbres de décision. Tous ces éléments entrent dans le panier de parité.

1) Quels sont les autres problèmes naturels (en dehors de la parité) qui peuvent être montrés directement comme n'étant pas en ? $AC^0$

2) Quelqu'un connaît-il une approche radicalement différente de la borne inférieure sur AC ^ 0 qui a été essayée?

cc.complexity-theory complexity-classes lower-bounds circuit-complexity V Vinay
la source

13

Résultat de Benjamin Rossman sur la borne inférieure pour la k-clique du STOC 2008. $AC^0$

Les références:

Paul Beame, " A Switching Lemma Primer ", Rapport technique 1994.
Benjamin Rossman, « Sur la complexité à profondeur constante de k-Clique », STOC 2008.

Kaveh
la source

Rossman n'est-il pas englobé par l'amorce de Beame qui avait aussi de la clique? Les arguments sont bien sûr plus complexes.

V Vinay

@V Vinay: pouvez-vous donner un lien vers l'article de Paul Beame?

Kaveh

4

Le résultat de Rossman montre que la

-clique ne peut pas être calculée par des circuits à profondeur constante de taille

. Notez que la constante dans l'exposant ne dépend pas de la profondeur du circuit, c'est là qu'elle s'améliore sur la limite inférieure de

Beame .

k

$k$

Ω (n^{k / 4})

$\Omega(n^{k/4})$

n^{Ω (k / d^{2})}

$n^{\Omega(k/d^2)}$

Srikanth

@Srikanth, je pensais que V Vinay disait que Beame a un résultat plus récent mais je n'ai pu en trouver sur sa page. Merci pour la clarification.

Kaveh

1

Srikanth a raison sur les limites. Kaveh, pas un nouveau papier; J'ai utilisé "subsumé" dans le sens où j'avais énuméré Beame dans ma question et connaissais donc la limite inférieure de la clique.

V Vinay

12

Il y a l'approche "top-down" de Håstad, Jukna et Pudlák, comme cela est fait dans leur document Top down down borns for depth-three circuits . Malheureusement, jusqu'à présent, nous n'avons pas été en mesure d'étendre l'approche à des profondeurs plus élevées.

Kristoffer Arnsfelt Hansen
la source

Oui. Je pensais que vous aviez un article influencé par cette approche?

V Vinay

10

1) Le premier qui me vient à l'esprit est MAJORITÉ. Vous pouvez prouver qu'il n'est pas en avec les mêmes techniques. Voir la thèse de Håstad pour plus de détails. $AC^{0}$

2) Une approche topologique, ne fonctionnant à nouveau que pour les circuits de profondeur trois, a été proposée par Kriegel et Waack .

Alessandro Cosentino
la source

2

La majorité est vraiment la même chose. J'aurais dû le mentionner cependant. De plus, il y avait un article de Boppana sur Majority au milieu des années 80.

V Vinay

8

Les deux autres méthodes "classiques" sont la méthode du goulot d'étranglement de Haken et la méthode de fusion de Karchmer (ainsi nommée par Avi Wigderson), toutes deux beaucoup plus faciles à appliquer dans le cadre monotone.

Yuval Filmus
la source

Parité et

Réponses: