En trompant

J'ai quelques questions concernant la tromperie des circuits à profondeur constante.

On sait que $\log^{O(d)}(n)$ sens de l'indépendance est nécessaire pour tromper $AC^0$ circuits de profondeur $d$ , où $n$ est la taille de l'entrée. Comment peut-on le prouver?
Puisque ce qui précède est vrai, tout générateur pseudo-aléatoire qui trompe circuits de profondeur doit nécessairement avoir une longueur de graine , ce qui signifierait alors que l'on ne peut pas s'attendre à prouver via les PRG. Je crois que est toujours une question ouverte, donc cela signifie que l'on doit utiliser des techniques autres que les PRG pour prouver . Je trouve cela bizarre car, au moins dans le cas de , nous pensons que les PRG sont essentiellement la seule façon de répondre à cette question. $AC^0$ $d$ $l = \Omega(\log^d(n))$ $RAC^0 = AC^0$ $RAC^0 \stackrel{?}{=} AC^0$ $RAC^0 = AC^0$ $P \stackrel{?}{=} BPP$

Je pense que je manque quelque chose de vraiment basique ici.

cc.complexity-theory cr.crypto-security circuit-complexity derandomization pseudorandom-generators Communauté
la source

Environ 1). L'indépendance du polylogue est certainement suffisante pour tromper

A C^{0}

$AC^{0}$ cause de la percée de Braverman, mais pourquoi prétendez-vous que c'est nécessaire?

Alessandro Cosentino

En fait, je ne sais pas si j'ai déjà vu une mention officielle de 1.) dans un article, etc., mais je crois que cela est connu. Découvrez le commentaire 29 de Scott Aaronson ici: scottaaronson.com/blog/?p=381

Je pense que l'énoncé correct devrait être que si vous voulez tromper AC0 par l'indépendance k-sage, alors est nécessaire. Cela ne dit pas qu'un PRG est comme ça.

k = p o l y l o g (n)

$k = polylog(n)$

Mahdi Cheraghchi

ok, ça a du sens maintenant. Autre précision: l'expression "techniques de dérandomisation autres que les PRG" a-t-elle un sens? Un PRG par définition (au moins dans la théorie de la complexité) n'est-il pas quelque chose que nous utilisons pour dérandomiser? @AbhishekBhrushundi: btw, j'aime la question. Il est bon de clarifier ce genre de choses sur cstheory ;-)

Alessandro Cosentino

Réponses:

1) Ce que l'on entend par nécessaire est qu'une façon de générer une distribution indépendante dans le sens est de casser l'entrée en blocs de bits, et de laisser le ème bit de chaque bloc être la parité de la autres bits dans le bloc. Évidemment, cette distribution peut être rompue simplement en calculant la parité sur bits. Le résultat que vous revendiquez découle du fait que les circuits poly ( ) de profondeur peuvent calculer la parité sur bits. $k$ $k+1$ $(k+1)$ $k$ $k$ $n$ $d$ $\log^{d-1} n$

2) Le n ° 1) ne parle que d'une construction spécifique de distributions indépendantes sensées. En théorie, il existe des générateurs de graines qui trompent les circuits à profondeur limitée de taille poly (cela découle également de limites inférieures suffisamment fortes contre des circuits à profondeur limitée, bien que les compromis standard entre dureté et aléatoire ne suffisent pas, voir par exemple la discussion d'un document par Agrawal dans la section 3.2 de http://www.ccs.neu.edu/home/viola/papers/JournalCCC03.pdf ). $k$ $O(\log n)$

Manu
la source

L'indépendance du polylog n'est peut-être pas le seul moyen de tromper les circuits . Pour illustrer cet exemple, considérons la classe des polynômes linéaires. Tout ensemble zéro d'un polynôme linéaire est indépendant de mais bien sûr, cela ne trompe pas les polynômes linéaires. Par conséquent, les distributions indépendantes ne trompent pas cette classe. Bien sûr, cela ne signifie pas que seules les distributions indépendantes dans le sens trompent cette classe (les espaces biaisés par trompent et sont des espaces de taille polynomiale). $AC^{0}$ $(n-1)$ $(n-1)$ $n$ $\epsilon$

Je suppose que ce que l'on veut dire quand ils disent " une indépendance dans le sens des est nécessaire", c'est qu'il existe des exemples de distributions avec une indépendance plus petite, et on sait qu'ils ne trompent pas . $\log^{O(d)} n$ $AC^{0}$

Ramprasad
la source