# Accurate and Scalable Matrix Mechanisms via Divide and Conquer

arXiv: https://arxiv.org/abs/2604.00868 · HTML: https://mlsanity.com/paper/2604.00868/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 42 references that are in the map.
- First posted on arXiv 1 Apr 2026.

## Builds on (most cited first, 15 of 15)

- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Winning the NIST Contest: A scalable and general approach to differentially private synthetic data](https://mlsanity.com/paper/2108.04978/) (2021)
- [AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data](https://mlsanity.com/paper/2201.12677/) (2022)
- [Differentially Private Query Release Through Adaptive Projection](https://mlsanity.com/paper/2103.06641/) (2021)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Optimizing error of high-dimensional statistical queries under differential privacy](https://mlsanity.com/paper/1808.03537/) (2018)
- [Dual Query: Practical Private Query Release for High Dimensional Data](https://mlsanity.com/paper/1402.1526/) (2014)
- [Optimizing Fitness-For-Use of Differentially Private Linear Queries](https://mlsanity.com/paper/2012.00135/) (2020)
- [Convex Optimization for Linear Query Processing under Approximate Differential Privacy](https://mlsanity.com/paper/1602.04302/) (2016)
- [Ektelo: A Framework for Defining Differentially-Private Computations](https://mlsanity.com/paper/1808.03555/) (2018)
- [Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries](https://mlsanity.com/paper/2512.21499/) (2025)
- [Answering Private Linear Queries Adaptively using the Common Mechanism](https://mlsanity.com/paper/2212.00135/) (2022)
- [Fast Private Adaptive Query Answering for Large Data Domains](https://mlsanity.com/paper/2602.05674/) (2026)
- [Efficient and Private Marginal Reconstruction with Local Non-Negativity](https://mlsanity.com/paper/2410.01091/) (2024)

## Built on by (most cited first, 1 of 1)

- [Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees](https://mlsanity.com/paper/2605.22756/) (2026)

## Abstract (arXiv)

Matrix mechanisms are often used to provide unbiased differentially private query answers when publishing statistics or creating synthetic data. Recent work has developed matrix mechanisms, such as ResidualPlanner and Weighted Fourier Factorizations, that scale to high dimensional datasets while providing optimality guarantees for workloads such as marginals and circular product queries. They operate by adding noise to a linearly independent set of queries that can compactly represent the desired workloads. In this paper, we present QuerySmasher, an alternative scalable approach based on a divide-and-conquer strategy. Given a workload that can be answered from various data marginals, QuerySmasher splits each query into sub-queries and re-assembles the pieces into mutually orthogonal sub-workloads. These sub-workloads represent small, low-dimensional problems that can be independently and optimally answered by existing low-dimensional matrix mechanisms. QuerySmasher then stitches these solutions together to answer queries in the original workload. We show that QuerySmasher subsumes prior work, like ResidualPlanner (RP), ResidualPlanner+ (RP+), and Weighted Fourier Factorizations (WFF). We prove that it can dominate those approaches, under sum squared error, for all workloads. We also experimentally demonstrate the scalability and accuracy of QuerySmasher.