Låta C vara en klass av sannolikhetsfördelningar över en ändlig uppsättning  på. En funktion D :  på → {0, 1} m är en dispergerare för C med entropy tröskel k och fel om för någon distribution X i C sådan att X ger positiv sannolikhet till minst 2 k element vi har att distributionen D(X) ger positiv sannolikhet till minst (1 - ) 2 m element. En lång rad av forskning ägnas åt att ge explicit (som är polynomisk tid beräkningsbar) dispergerare (och relaterade objekt som kallas "extractors") för olika klasser av distributioner samtidigt försöker maximera m som funktion av k. För flera intressanta klasser av distributioner finns det explicita konstruktioner i litteraturen av noll-terror dispergerare med "liten" outputlängd m. I detta papper utvecklar vi en allmän teknik för att förbättra utdatalängden av noll-terror dispergerare. Denna strategi fungerar för flera klasser av källor och är inspirerad av en omvandling som förbättrar utsugarnas produktionslängd (som gavs i [32] och byggde på tidigare arbeten av [17]). Våra tekniker skiljer sig från [32] och ger i synnerhet icke-triviala resultat i det felfria fallet. Med vårt tillvägagångssätt konstruerar vi förbättrade noll-terror 2-källorsdispergerare. Mer exakt, Vi visar att för varje konstant δ > 0 det finns en konstant η > 0 sådan att för tillräckligt stor n det finns en poly-tid beräkningsbar funktion D : {0, 1} n × {0, 1} n → {0, 1} ηn sådan att för varje två oberoende distributioner X 1, X 2 över {0, 1} n sådan att stödja minst 2 δn element, utdatadistributionen D(X 1, X 2 ) har fullt stöd. Detta förbättrar produktionslängden för tidigare konstruktioner genom [2] och har tillämpningar i Ramsey-teorin och vid konstruktion av vissa datastrukturer [15]. Vi använder också våra tekniker för att ge explicita konstruktioner av noll-terrordispergerare för bitfixerande källor och affina källor över polynomiskt stora fält. Dessa konstruktioner förbättrar de mest kända explicita konstruktionerna på grund av [28, 16] och uppnår m = (k) för bitfixerande källor och m = k − o(k) för affina källor över polynomstorleksfält.
Gabizon och Shaltiel REF konstruerade ett svagare objekt som kallas en dispergerare över stora fält för affina källor.
Increasing the output length of zero-error dispersers
{'venue': 'In RANDOM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}