Key points are not available for this paper at this time.
In this paper, we introduce the ₚᵖ-error metric (for p 2) when answering linear queries under the constraint of differential privacy. We characterize such an error under (, ) -differential privacy. Before this paper, tight characterization in the hardness of privately answering linear queries was known under ₂²-error metric (Edmonds et al. , STOC 2020) and ₚ²-error metric for unbiased mechanisms (Nikolov and Tang, ITCS 2024). As a direct consequence of our results, we give tight bounds on answering prefix sum and parity queries under differential privacy for all constant p in terms of the ₚᵖ error, generalizing the bounds in Henzinger et al. (SODA 2023) for p=2.
Liu et al. (Tue,) studied this question.