Antag att n processorer är ordnade i en ring och kan kommunicera endast med sina närmaste grannar. Vi visar att alla probabilistiska algoritmer för 3 färgning ringen måste ta minst 1 2 log n 2 rundor, annars är sannolikheten att alla processorer är färgade lagligt mindre än 1 2. En liknande tidsbunden håller för att välja en maximal oberoende uppsättning. Bandet är tätt (upp till en konstant faktor) mot bakgrund av deterministiska algoritmerna Cole och Vishkin CV] och förlänger den nedre gränsen för deterministiska algoritmer av Linial L].
Till exempel, REF bevisar detta för 3-färgning ringen.
A lower bound on probabilistic algorithms for distributive ring coloring
{'venue': 'SIAM J. Discrete Math.', 'journal': 'SIAM J. Discrete Math.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}