Randomized Computations on Large Data Sets: Tight Lower Bounds

Martin Grohe, Andre Hernich, Nicole Schweikardt

We study the randomized version of a computation model (introduced by Grohe, Koch, and Schweikardt (ICALP'05); Grohe and Schweikardt (PODS'05)) that restricts random access to exte…