A fast and simple randomized parallel algorithm for the maximal independent set problem

Ajtai, 1985, Deterministic Simulation of Probabilistic Constant Depth Circuits, 11

Alexi, 1984, RSA/Rabin bits are 12 + 1poly log(n) secure, 449

N. Alon and P. Erdõs, An application of graph theory to additive number theory, European J. Combin., in press.

Anderson, 1985

Babai, 1985, Sidon sets in groups and induced subgraphs of Cayley graphs, European J. Combin., 6, 101, 10.1016/S0195-6698(85)80001-9

P. Beame, Private communication by M. Luby.

Bernstein, 1945

Chor, 1985

Chor, 1985, The Bit Extraction Problem or t-Resilient Functions, 396

Cook, 1983, An overview of computational complexity, Comm. ACM, 26, 400, 10.1145/358141.358144

Erdõs, 1947, Some remarks on the theory of graphs, Bull. Amer. Math. Soc., 53, 292, 10.1090/S0002-9904-1947-08785-1

Erdõs, 1973, The Art of Counting

Frankl, 1977, A constructive lower bound for some Ramsey numbers, Ars Combinatoria, 3, 371

Frankl, 1981, Intersection theorems with geometric consequences, Combinatorica, 1, 357, 10.1007/BF02579457

Goldschlager, 1977, Synchronous Parallel Computation

Goldschlager, 1978, 89

Goldschlager, 1982, J. Assoc. Comput. Mach., 29, 1073, 10.1145/322344.322353

Israeli, 1984

Joffe, 1974, On a set of almost deterministic k-independent random variables, Ann. Probability, 2, 161, 10.1214/aop/1176996762

Karp, 1984, A Fast Parallel Algorithm for the Maximal Independent Set Problem, 266

Lancaster, 1965, Pairwise statistical independence, Ann. Math. Stat., 36, 1313, 10.1214/aoms/1177700007

Lovász, 1979

Luby, 1985, A Simple Parallel Algorithm for the Maximal Independent Set Problem, 1

MacWilliams, 1977

O'Brien, 1980, Pairwise independent random variables, Ann. Probability, 8, 170, 10.1214/aop/1176994834

Valiant, 1982, Parallel Computation, 173