Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear QueriesResearch Paper
A private query mechanism must balance the accuracy of its answers with the information it reveals about individual records. It also consumes randomness. When many queries are answered, generating the necessary independent random bits becomes a resource question of its own. Randomness complexity measures the expected number of unbiased bits consumed, in the…