Almost Optimal Dispersers

A disperser is a bipartite graph with the property that every subset A of of cardinality at least K, has at least fraction of the vertices of as neighbors. Such graphs have many applications in derandomization. Saks, Srinivasan and Zhou presented an explicit construction of a disperser with an almost optimal degree , for every . We extend their result for every parameter . Received November 12, 1998/Revised June 20, 2000 RID="*" ID="*" This work was partially done while the author was at the Department of Computer Science, Weizmann Institute of Science, Rehovot, Israel. This work was supported by a Phil Zacharia postdoctoral fellowship.