2 papers
cs.DS2026
Markov Chains with Rewinding
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari +1
Motivated by techniques developed in recent progress on lower bounds for sublinear time algorithms (Behnezhad, Roghani and Rubinstein, STOC 2023, FOCS 2023, and STOC 2024) we intro…
cs.DS2025
Lower Bounds for Non-adaptive Local Computation Algorithms
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari +1
We study *non-adaptive* Local Computation Algorithms (LCA). A reduction of Parnas and Ron (TCS'07) turns any distributed algorithm into a non-adaptive LCA. Plugging known distribut…