Computationally Efficient Replicable Learning of Parities and Applications

Moshe Noivirt, Jessica Sorrell, Eliad Tsfadia

We study the computational relationship between replicability (Impagliazzo et al. [STOC `22], Ghazi et al. [NeurIPS `21]) and other stability notions. Specifically, we focus on rep…