https://wiki.sarg.dev/index.php?action=history&feed=atom&title=Disperser 2026-08-03T16:15:18Z Revision history for this page on the wiki MediaWiki 1.44.2 https://wiki.sarg.dev/index.php?title=Disperser&diff=4912&oldid=prev 2020-12-27T16:07:22Z

<p><a href="/index.php?title=User:Monkbot/task_18&amp;action=edit&amp;redlink=1" class="new" title="User:Monkbot/task 18 (page does not exist)">Task 18 (cosmetic)</a>: eval 1 template: hyphenate params (1×);</p> <p><b>New page</b></p><div>{{Multiple issues|<br /> {{more citations needed|date=August 2012}}<br /> {{technical|date=January 2014}}<br /> }}<br /> <br /> A &#039;&#039;&#039;disperser&#039;&#039;&#039; is a one-sided [[randomness extractor|extractor]].&lt;ref&gt;{{cite journal|first=Ronen|last=Shaltiel|title=Recent developments in explicit constructions of extractors|journal=Bulletin of the EATCS|year=2002|volume=77|pages=67–95|url=https://cs.haifa.ac.il/~ronen/online_papers/survey.ps|access-date=2018-04-10}}&lt;/ref&gt; Where an extractor requires that every event gets the same [[probability]] under the [[Continuous uniform distribution|uniform distribution]] and the extracted distribution, only the latter is required for a disperser. So for a disperser, an event &lt;math&gt;A \subseteq \{0,1\}^{m}&lt;/math&gt; we have:<br /> &lt;math&gt;Pr_{U_{m}}[A] &gt; 1 - \epsilon&lt;/math&gt;<br /> <br /> &#039;&#039;&#039;Definition (Disperser):&#039;&#039;&#039; &#039;&#039;A&#039;&#039; &lt;math&gt;(k, \epsilon)&lt;/math&gt;&#039;&#039;-disperser is a function&#039;&#039;<br /> <br /> &lt;math&gt;Dis: \{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}&lt;/math&gt;<br /> <br /> &#039;&#039;such that for every distribution&#039;&#039; &lt;math&gt;X&lt;/math&gt; &#039;&#039;on&#039;&#039; &lt;math&gt;\{0,1\}^{n}&lt;/math&gt; &#039;&#039;with&#039;&#039; &lt;math&gt;H_{\infty}(X) \geq k&lt;/math&gt; &#039;&#039;the support of the distribution&#039;&#039; &lt;math&gt;Dis(X,U_{d})&lt;/math&gt; &#039;&#039;is of size at least&#039;&#039; &lt;math&gt;(1-\epsilon)2^{m}&lt;/math&gt;.<br /> <br /> ==Graph theory==<br /> An &#039;&#039;&#039;(&#039;&#039;N&#039;&#039;, &#039;&#039;M&#039;&#039;, &#039;&#039;D&#039;&#039;, &#039;&#039;K&#039;&#039;, &#039;&#039;e&#039;&#039;)-disperser&#039;&#039;&#039; is a [[bipartite graph]] with &#039;&#039;N&#039;&#039; vertices on the left side, each with degree &#039;&#039;D&#039;&#039;, and &#039;&#039;M&#039;&#039; vertices on the right side, such that every [[subset]] of &#039;&#039;K&#039;&#039; vertices on the left side is connected to more than (1&amp;nbsp;&amp;minus;&amp;nbsp;&#039;&#039;e&#039;&#039;)&#039;&#039;M&#039;&#039; vertices on the right.<br /> <br /> An [[Extractor (mathematics)|extractor]] is a related type of graph that guarantees an even stronger property; every &#039;&#039;&#039;(&#039;&#039;N&#039;&#039;, &#039;&#039;M&#039;&#039;, &#039;&#039;D&#039;&#039;, &#039;&#039;K&#039;&#039;, &#039;&#039;e&#039;&#039;)-extractor&#039;&#039;&#039; is also an &#039;&#039;&#039;(&#039;&#039;N&#039;&#039;, &#039;&#039;M&#039;&#039;, &#039;&#039;D&#039;&#039;, &#039;&#039;K&#039;&#039;, &#039;&#039;e&#039;&#039;)-disperser&#039;&#039;&#039;.<br /> <br /> ==Other meanings==<br /> A disperser is a high-speed mixing device used to disperse or dissolve pigments and other solids into a liquid.<br /> <br /> ==See also==<br /> *[[Expander graph]]<br /> <br /> ==References==<br /> {{reflist}}<br /> <br /> [[Category:Graph families]]<br /> <br /> <br /> {{Combin-stub}}</div>

imported>Monkbot