25 citations · 43 across the 10 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
cs.DS2020
Erasure-Resilient Sublinear-Time Graph Algorithms
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova +1
We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input gra…
cs.DM2020
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…