Noise Sensitivity on Equivalence Relations
StuKon, Heidelberg, Germany, Jul 2025
*Talk from another meeting
Noise sensitivity was first introduced by Benjamini, Kalai and Schramm in their seminal work on Boolean functions. We propose a construction of a similar taste on binary relations. By flipping every relation with a small probability p, a natural question on recoverability arises, to which we give a positive answer in the case of an equivalence relation (X,∼). We prove that equivalence relations are noise-stable under the prescribed model. In particular, we propose a simple reconstruction algorithm, and show that it achieves an asymptotically zero misclassification error.