Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra~(SICOMP 2018) for Boolean functions to the case of real-valued functions $f \colon \{0,1\}^d\to\mat…