{"ID":2894213,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.10946","arxiv_id":"2507.10946","title":"Solving Linear Programs with Differential Privacy","abstract":"We study the problem of solving linear programs of the form $Ax\\le b$, $x\\ge0$ with differential privacy. For homogeneous LPs $Ax\\ge0$, we give an efficient $(ε,δ)$-differentially private algorithm which with probability at least $1-β$ finds in polynomial time a solution that satisfies all but $O(\\frac{d^{2}}ε\\log^{2}\\frac{d}{δβ}\\sqrt{\\log\\frac{1}{ρ_{0}}})$ constraints, for problems with margin $ρ_{0}\u003e0$. This improves the bound of $O(\\frac{d^{5}}ε\\log^{1.5}\\frac{1}{ρ_{0}}\\mathrm{poly}\\log(d,\\frac{1}δ,\\frac{1}β))$ by [Kaplan-Mansour-Moran-Stemmer-Tur, STOC '25]. For general LPs $Ax\\le b$, $x\\ge0$ with potentially zero margin, we give an efficient $(ε,δ)$-differentially private algorithm that w.h.p drops $O(\\frac{d^{4}}ε\\log^{2.5}\\frac{d}δ\\sqrt{\\log dU})$ constraints, where $U$ is an upper bound for the entries of $A$ and $b$ in absolute value. This improves the result by Kaplan et al. by at least a factor of $d^{5}$. Our techniques build upon privatizing a rescaling perceptron algorithm by [Hoberg-Rothvoss, IPCO '17] and a more refined iterative procedure for identifying equality constraints by Kaplan et al.","short_abstract":"We study the problem of solving linear programs of the form $Ax\\le b$, $x\\ge0$ with differential privacy. For homogeneous LPs $Ax\\ge0$, we give an efficient $(ε,δ)$-differentially private algorithm which with probability at least $1-β$ finds in polynomial time a solution that satisfies all but $O(\\frac{d^{2}}ε\\log^{2}\\...","url_abs":"https://arxiv.org/abs/2507.10946","url_pdf":"https://arxiv.org/pdf/2507.10946v1","authors":"[\"Alina Ene\",\"Huy Le Nguyen\",\"Ta Duy Nguyen\",\"Adrian Vladu\"]","published":"2025-07-15T03:22:47Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}