înregistrare Logare
Puncte:1
Blanco avatar Crypto

Existența OWF-urilor vs $\mathbf{EXP} \neq \mathbf{BPP}$

drapel us
Blanco

În CRYPTO 2021, Liu și Pass au publicat o lucrare cu titlu „Cu privire la posibilitatea de a baza criptografia pe $\mathbf{EXP} \neq \mathbf{BPP}$.

Unul dintre principalele rezultate ale acestei lucrări poate fi interpretat ca o indicație că existența OWF-urilor este echivalentă cu $\mathbf{EXP} \neq \mathbf{BPP}$. $\mathbf{EXP} \neq \mathbf{BPP}$ este o presupunere slabă, care este relația dintre această ipoteză și duritatea medie a cazului? Orice introducere și comentariu despre această lucrare este binevenită.

65
0 + 0
Puncte:2
Mark avatar Crypto
drapel ng
Mark

$\mathsf{EXP}\neq \mathsf{BPP}$ este ipoteza tipică utilizată în literatura de derandomizare. Cuvintele de căutat sunt „Nisan-Widgerson” și „Impagliazzo-Widgerson”. De exemplu, rezumatul lui Impagliazzo-Widgerson citeste:

Demonstrăm că dacă $\mathsf{BPP}\neq \mathsf{EXP}$, apoi fiecare problemă în $\mathsf{BPP}$ poate fi rezolvat determinist în timp subexponențial pe aproape fiecare intrare (pe fiecare ansamblu eșantionabil pentru infinit de multe dimensiunile de intrare). Acesta este primul rezultat de derandomizare pentru $\mathsf{BPP}$ bazat pe ipoteze uniforme, non-criptografice de duritate. Aceasta implică următorul decalaj în complexitatea instanței medii a problemelor în $\mathsf{BPP}$ : fie aceste complexități sunt întotdeauna sub-exponențiale, fie conțin funcții exponențiale arbitrar mari.

În general, atunci când căutați într-o nouă teză de doctorat, poate fi ușor mai ușor de citit decât lucrările, așa că dacă sunteți interesat mai mult teza lui Marco Carmosino poate fi de folos.

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

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.