Low Influence, Utility, and Independence in Differential Privacy: A\n Curious Case of $3 \\choose 2$

We study the relationship between randomized low influence functions and\ndifferentially private mechanisms. Our main aim is to formally determine\nwhether differentially private mechanisms are low influence and whether low\ninfluence randomized functions can be differentially private. We show that\ndifferential privacy does not necessarily imply low influence in a formal\nsense. However, low influence implies approximate differential privacy. These\nresults hold for both independent and non-independent randomized mechanisms,\nwhere an important instance of the former is the widely-used additive noise\ntechniques in the differential privacy literature. Our study also reveals the\ninteresting dynamics between utility, low influence, and independence of a\ndifferentially private mechanism. As the name of this paper suggests, we show\nthat any two such features are simultaneously possible. However, in order to\nhave a differentially private mechanism that has both utility and low\ninfluence, even under a very mild utility condition, one has to employ\nnon-independent mechanisms.\n