Explicit OR-dispersers with polylogarithmic degree.

An (N, M, T)-OR-disperser is a bipartite multigraph G=(V, W, E) with |V| = N, and |W| = M, having the following expansion property: any subset of V having at least T vertices has a neighbor set of size at least M/2. For any pair of constants &xgr;, &lgr;, 1 ≥ &xgr; > &lgr; ≥ 0, an...

Mô tả đầy đủ

Chi tiết về thư mục

Xuất bản năm:	Journal of the ACM 45, 1 (1998).
Tác giả chính:	Saks, Michael
Định dạng:	Bài viết
Ngôn ngữ:	Tiếng Anh
Những chủ đề:	Theory of computation. Computation by abstract devices. Complexity measures and classes. Relations among complexity classes. Mathematics of computing. Discrete mathematics. Combinatorics. Combinatorial algorithms. Probability and statistics. Probabilistic algorithms (including Monte Carlo). Algorithms. Theory.