Puncte:3

Argument hibrid fără eșantionare eficientă

drapel sy

Să zicem că am $k$ distribuţii, unde $k$ este polinomial mare, $D_1, D_2, \ldots, D_k$ astfel încât fiecare $D_i$ nu se distinge din punct de vedere computațional de distribuția uniformă.

Este adevărat că distribuția $D_1 D_2 \ldots D_k$ este, de asemenea, imposibil de distins din punct de vedere computațional de $k$ copii ale distribuirii uniforme?

Acest lucru este valabil dacă fiecare $D_i$ este eficient eșantionabil. Dar să zicem că nu sunt.

Faptul rămâne adevărat, printr-un mod inteligent de a ocoli cerința de eșantionare?

Puncte:3
drapel us

Aceasta este o întrebare foarte interesantă. M-am uitat în jur și am găsit o hârtie numită Indistincbilitatea computațională: O ierarhie a eșantionului de Goldreich și Sudan. Acesta conține o dovadă că nu ține.

BlackHat18 avatar
drapel sy
Doar o precizare. Această lucrare vorbește despre două distribuții și despre setarea când ni se oferă $k$ mostre din oricare distribuție din cele două.Dar, aici, fie ni se dă câte un eșantion din $k$ distribuții diferite (fiecare nu se poate distinge din punct de vedere computațional de uniformă), fie ni se oferă $k$ eșantioane din distribuția uniformă. Credeți că tehnicile care funcționează pentru primul set (cel al lucrării) funcționează și pentru al doilea set (cel al întrebării mele)?
Yehuda Lindell avatar
drapel us
Există, de asemenea, referințe în lucrare la lucrări anterioare care tratează întrebarea de bază. Intuiția mea spune că acest lucru ar trebui să se traducă în setări similare, dar, desigur, intuiția trebuie întotdeauna verificată.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.