Optimality of Matrix Mechanism on ℓpp-metric

In this paper, we introduce the ℓpp-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 ℓ22-error metric (Edmonds et al., STOC 2020) and ℓp2-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 ℓpp error, generalizing the bounds in Henzinger et al. (SODA 2023) for p=2.