From the 2 of 36 linked papers with an AI index.
37 papers
Decisive Margins in Differentially Private Voting
Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn +1
Differential privacy protects individual voting records by injecting randomness into the published outcome, but this noise can lead to erroneous results when an election is close.…
Approximation Algorithms for Geometric Maximum Coverage
Sujoy Bhore, Timothy M. Chan, Pasin Manurangsi
We study the maximum coverage problem for geometric set systems: given a set of points, a set of geometric objects, and a number , select objects maximizing the number of po…
On the Computational Complexity of (Extended) Threshold Dimension and (Semi-)Ladder Index
Pasin Manurangsi
The paper investigates the difficulty of computing the threshold dimension and extended threshold dimension of hypothesis classes, proving NP‑hardness, co‑NP‑hardness, and strong h…
Fixed-Parameter Tractability of Private Synthetic Data Generation
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +3
The paper investigates generating differentially private synthetic data and shows that the problem is fixed-parameter tractable when parameterized by the treewidth of the query fam…
A Note on Approximability of Densest At-Least-k-Subgraph
Bundit Laekhanukit, Pasin Manurangsi, Ohad Trabelsi
We study the Densest At-Least--Subgraph (DALS) problem, in which we are given an undirected graph and an integer , and the goal is to find a subgraph of with at le…
Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
Lynn Chua, Badih Ghazi, Ravi Kumar +3
We study the problem of Stochastic Convex Optimization (SCO) under the constraint of local Label Differential Privacy (L-LDP). In this setting, the features are considered public,…