Sofya Raskhodnikova

activity

20072023

most citedEfficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions

25 citations · 43 across the 10 of their papers we have counts for

collaborators

Showing 2017Show all

2 papers · 1 filter

cs.CC2017★ 5 cited

A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor +2

A Boolean function $f : {0, 1}^{d} \mapsto {0, 1}$ is unate if, along each coordinate, the function is either nondecreasing or nonincreasing. In this note, we prove that any nonadapt…

cs.DS2017★ 1 cited

Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor +2

We study the problem of testing unateness of functions $f : {0, 1}^{d} \to R .$ We give a $O (\frac{d}{ε} \cdot lo g \frac{d}{ε})$ -query nonadaptive tester and a $O (\frac{d}{ε})$ -quer…