Abstract-Over de senaste 30 åren har många algoritmer utformats för symmetri brott problem i LOCAL-modellen, såsom maximal matchning, MIS, vertex färgning, och kant färgning. För de flesta problem är den bästa randomiserade algoritmen minst exponentiellt snabbare än den bästa deterministiska algoritmen. Vi bevisar att dessa exponentiella luckor är nödvändiga och etablerar många samband mellan de deterministiska och randomiserade komplexiteterna i LOCAL-modellen. Var och en av våra resultat har en mycket övertygande take-away budskap: 1) Bygger på de nyligen randomiserade nedre gränserna av Brandt et al. [1], visar vi att den randomiserade komplexiteten hos Δ-färgning av ett träd med maximal grad Δ är O(log Δ log n + log * n), för alla Δ ≥ 55, medan dess deterministiska komplexitet är  och (log Δ n) för alla Δ ≥ 3. Detta innebär också en stor åtskillnad mellan deterministiska komplexiteten hos Δ-färgning och (Δ + 1)-färgande träd. 2) Vi bevisar att alla deterministiska algoritmer för en naturlig klass av problem som körs i O(1) + o(log Δ n) rundor kan omvandlas till att köras i O(log * n − log * Δ + 1) rundor. Om den omvandlade algoritmen bryter mot en lägre gräns (även tillåter randomisering), då kan man dra slutsatsen att problemet kräver  och (log Δ n) tid deterministiskt. Detta ger ett alternativt bevis på att deterministiskt Δ-färga ett träd med små Δ tar  och (log Δ n) rundor. 3) Vi bevisar att den slumpmässiga komplexiteten hos alla naturliga problem på fall av storlek n är åtminstone dess deterministiska komplexitet i fall av storlek ε log n. Detta visar att en deterministisk (log Δ n) lägre gräns för eventuella problem (Δ-färgning ett träd, till exempel) innebär en slumpmässig (log Δ log n) lägre gräns. Det illustrerar också att grafsplittring teknik som används i nyligen randomiserade symmetri brott algoritmer är absolut nödvändigt för LOCAL-modellen. Det är t.ex. uppenbart omöjligt att förbättra termen 2 O ( Ă log log n) i komplexiteten hos de bästa MIS och (Δ+1)-färgsalgoritmerna utan att också förbättra 2 O ( Ă log n) -round PanconesiSrinivasan algoritm.
För det andra, när det gäller problem som MIS, visade REF att en förbättring av den randomiserade komplexiteten kräver en förbättring av den deterministiska komplexiteten.
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model