2 papers
cs.DS2022
Privately Estimating Graph Parameters in Sublinear time
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee
We initiate a systematic study of algorithms that are both differentially private and run in sublinear time for several problems in which the goal is to estimate natural graph para…
cs.DM2019
Estimating Gaps in Martingales and Applications to Coin-Tossing: Constructions and Hardness
Hamidreza Amini Khorasgani, Hemanta K. Maji, Tamalika Mukherjee
Consider designing a distributed coin-tossing protocol for n processors such that the probability of heads is X0 in [0,1], and an adversary can reset one processor to change the di…