Ett kraftfullt tema i komplexitetsteori och pseudorandomness under de senaste decennierna har varit användningen av lägre gränser för att ge pseudorandomgeneratorer (PRG). Men, de allmänna resultaten med hjälp av denna hårdhet vs. randomness paradigm lider av en kvantitativ förlust i parametrar, och därmed inte ger icke-triviala konsekvenser för modeller där vi inte vet super-polynom lägre gränser men vet lägre gränser för en fast polynom. Vi visar att när sådana nedre gränser bevisas med hjälp av slumpmässiga restriktioner, kan vi konstruera PRGs som i huvudsak är bästa möjliga utan att i sin tur förbättra de nedre gränserna. Mer specifikt, säger att en krets familj har krympa exponent Om en slumpmässig restriktion lämnar en p-fraktion av variabler unset krymper storleken på någon krets i familjen med en faktor p Ε+o (1). Vår PRG använder ett frö av längd s 1/(ρ+1)+o (1) för att lura kretsar i familjen av storlek s. Genom att använda denna generiska konstruktion, vi får PRGs med polynomiskt små fel för följande klasser av kretsar av storlek s och med följande utsädeslängder: (1) För de Morgan formler, utsädeslängd s 1/3+o (1) ; (2) För formler över en godtycklig grund, utsädeslängd s 1/2+o (1) ; (3) För läs-en gång de Morgan formler, utsädeslängd s.234... ; (4) För grenning program av storlek s, utsädeslängd s 1/2+o (1). De tidigare bästa PRGs kända för dessa klasser använde frön av längd större än n/2 till utdata n bitar, och arbetade endast för storlek Russell Impagliazzo stöddes delvis av Simons Foundation, Ellentuck Fund, Friends of the Institute for Advanced Study, National Science Foundation under bidrag DMS-0835373, CCF-121351, och CCF-0832797, och av en Simons Investigator Award. Raghu Meka stöddes delvis av National Science Foundation genom bidrag CCF-1553605 och DMS-0835373. David Zuckerman fick delvis stöd av National Science Foundation genom bidrag CCF-0916160, CCF-1526952, CCF-1705028 och DMS-0835373 samt genom ett Simons Investigator Award. Författarens adress: R. Impagliazzo, University of California, San Diego; e-post: russell@cs.ucsd.edu; R. Meka, University of California, Los Angeles; e-post: raghum@cs.ucla.edu; D. Zuckerman, University of Texas i Austin; e-post: diz@cs.utexas.edu. Tillstånd att göra digitala eller papperskopior av hela eller delar av detta arbete för personligt bruk eller klassrum beviljas utan avgift, förutsatt att kopiorna inte görs eller distribueras för vinst eller kommersiella fördelar och att kopiorna är försedda med detta meddelande och den fullständiga hänvisningen på första sidan. Upphovsrätt till delar av detta verk som ägs av andra än upphovsmannen måste hedras. Abstraktering med kredit är tillåten. För att kopiera på annat sätt, eller återpublicera, för att posta på servrar eller för att omfördela till listor, krävs tidigare specifik behörighet och/eller avgift. Begär tillstånd från authoritys@acm.org. 11:2 R. Impagliazzo et al. Två av de viktigaste allmänna utmaningarna för komplexiteten är att visa konstruktiva lägre gränser för icke-uniforma mätningar av beräkningskomplex såsom kretsstorlek, och att visa att randomiserade algoritmer har effektiva deterministiska simuleringar. Paradigmet "Hardness vs. Randomness" [1, 6, 7, 21, 23, 36] visar att dessa frågor är kopplade till varandra. Mer exakt, dessa resultat visar hur man använder något problem som är svårt för en klass av kretsar för att skapa en pseudorandom generator (PRG) för samma klass av kretsar. Denna PRG kan sedan användas för att konstruera en relativt effektiv deterministisk version av någon probabilistisk algoritm med en motsvarande komplexitet. Detta har använts för att skapa villkorslösa PRGs för kretsklasser med kända lägre gränser, såsom för AC 0, samt för att få villkorliga resultat-implications mellan förekomsten av hårda problem och derandomization för klasser där inga starka lägre gränser är kända. I motsatt riktning är det lätt att se att varje PRG för en kretsklass omedelbart ger en motsvarande lägre gräns för klassen. Något mer förvånande, har det visat sig att någon effektiv deterministisk simulering av vissa probabilistiska algoritmer skulle ge kretsen lägre gränser [14, 17, 35]. Denna hårdhet vs. slumpmässighet anslutning är ett av de viktigaste verktygen i beräknings komplexitet. Det formaliserar intuitionen att effektiva algoritmer för "meta-beräkningsproblem", där indata är en beräkningsenhet från en viss klass, är kopplade till vår förmåga att bevisa lägre gränser för den klassen. Men att vara så allmän kommer till ett kvantitativt pris. Helst är sträckningen av en PRG (utgångslängden som funktion av ingångslängden) lika med den kända nedre gränsen. Men i hårdhet-random konstruktioner, det finns ett antal steg som varje förlora en stor polynom faktor. I synnerhet innebär detta att t.ex. en fyrhörning eller kubikkrets lägre gräns för en klass inte omedelbart ger någon icke-trivial PRG. För helt generiska, "svart-box", minskningar mellan ett svårt problem och en PRG, några av dessa kostnader är inneboende [5, 11, 28, 34]. I synnerhet är detta en fråga för de modeller där super-linjära men inte super-polynomiska gränser är kända, såsom Booleska formler. I detta arbete visar vi en allmän metod för att uppnå snäv "hårdhet-till-randomness" resultat från bevis på lägre gränser, snarare än som en svart-box konsekvens av de nedre gränserna. I synnerhet våra metoder gäller för lägre bundna bevis som innebär att begränsa några av ingångarna till kretsen. Vår konstruktion sker i två steg. Vi börjar med en lägre gräns bevisas av följande typ av krympa argument: om vi begränsar en storlek s krets lämnar en p-fraktion av variabler oset, den förväntade storleken på den begränsade kretsen är O (p Εs). Det bästa för vilket detta gäller är känd som "shrinkage exponent" av kretsklassen. Det första steget i vår konstruktion är att derandomisera krympar argumentet, visar att det finns en fördelning med liknande krympegenskaper som kan provtas med några bitar. Detta stadium av vårt argument är allmänt, men inte helt allmänt. Samma generella konstruktions- och analysidéer fungerar i en mängd olika modeller, men detaljerna beror på modellen. Sedan visar vi hur man går från en sådan distribution av restriktioner till en PRG. Denna del är generisk, är identisk för alla modeller, och är nära relaterad till generatorn från [24]. Det totala antalet bitar r som används av generatorn är ungefär 1/(1+ο) gånger det antal bitar som behövs för att ta prov från distributionen på restriktioner. Varje generator som använder r bitar för att lura tester av storlek s = s (r ) ger omedelbart ett problem som kräver storlek (r ) att beräkna i modellen. Så, om vår funktion s (r ) är nära de kända nedre gränserna, visar detta att vi i huvudsak har konverterat hela "hårdheten" i det lägre bundet till "randomness". Detta är verkligen fallet för en mängd olika naturliga modeller för beräkning. För Booleska formler över de Morgan bas, ger vi en generator med s (r ) = r 3−o (1), nästan matcha den kända nedre gränsen av s (n) = (n 3 /(log 2 n log n) på grund av Håstad ([12] med en polylogaritmisk
Specifikt, Vi betonar att även för läs-2 glömska grenningsprogram, är det bästa resultatet av Impagliazzo, Meka, och Zuckerman REF, som gav en PRG med frölängd s 1/2+o (1) för storlek s grenningsprogram (observera att beroendet här är på s snarare än på n).
Pseudorandomness from Shrinkage
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}