Pasin Manurangsi

Differential Privacy Meets Fixed Parameter Tractability: Algorithms and Lower Bounds

Pritish Kamath, Ravi Kumar, Pasin Manurangsi

We study combinatorial optimization problems under the constraint of $ε$ -differential privacy ( $ε$ -DP). Given the strong lower bounds for explicitly outputting solutions, we work w…

Tight Bounds on the Cost of Adaptivity for the Meyerson Sketch

Edith Cohen, Elena Gribelyuk, Pasin Manurangsi +1

In online facility location, points arrive one at a time, and the algorithm must either open a facility at the arriving point or route the point to an existing facility. The Meyers…

Online Differentially Private Consistent Clustering

Edith Cohen, Vadym Doroshenko, Badih Ghazi +7

We study differentially private (DP) $k$ -means and $k$ -median clustering in the online streaming setting. In this model, points arrive sequentially, and at each time step, we need…

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.…

Fixed-Parameter Tractability of Private Synthetic Data Generation

Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +3

We study the problem of generating synthetic data under differential privacy. We establish fixed-parameter tractability (FPT) for this problem where the parameter is the treewidth…

A Note on Approximability of Densest At-Least-k-Subgraph

Bundit Laekhanukit, Pasin Manurangsi, Ohad Trabelsi

We study the Densest At-Least- $k$ -Subgraph (DAL $k$ S) problem, in which we are given an undirected graph $G$ and an integer $k$ , and the goal is to find a subgraph of $G$ 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,…

Improved Approximation Algorithm for Maximum Balanced Biclique

Pasin Manurangsi

We study the Maximum Balanced Biclique (MBB) problem: Given a bipartite graph $G$ with $n$ vertices on each side, find a balanced biclique in $G$ with maximum size. We give a polyn…

The Price of Privacy For Approximating Max-CSP

Prathamesh Dharangutte, Jingcheng Liu, Pasin Manurangsi +3

We study approximation algorithms for Maximum Constraint Satisfaction Problems (Max-CSPs) under differential privacy (DP) where the constraints are considered sensitive data. Infor…

cs.DS2025

Improved Differentially Private Algorithms for Rank Aggregation

Quentin Hillebrand, Pasin Manurangsi, Vorapong Suppakitpaisarn +1

Rank aggregation is a task of combining the rankings of items from multiple users into a single ranking that best represents the users' rankings. Alabi et al. (AAAI'22) presents di…

Fine Grained Lower Bounds for Multidimensional Knapsack

Ilan Doron-Arad, Ariel Kulik, Pasin Manurangsi

We study the $d$ -dimensional knapsack problem. We are given a set of items, each with a $d$ -dimensional cost vector and a profit, along with a $d$ -dimensional budget vector. The go…

On Computing Pairwise Statistics with Local Differential Privacy

Badih Ghazi, Pritish Kamath, Ravi Kumar +2

We study the problem of computing pairwise statistics, i.e., ones of the form $(2 n)^{- 1} \sum_{i \neq = j} f (x_{i}, x_{j})$ , where $x_{i}$ denotes the input to the $i$ th user, with…

Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization

Badih Ghazi, Pritish Kamath, Ravi Kumar +2

In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation: if an algorithm is one-sided add-DP, then its subsampled…

Improved Lower Bound for Differentially Private Facility Location

Pasin Manurangsi

We consider the differentially private (DP) facility location problem in the so called super-set output setting proposed by Gupta et al. [SODA 2010]. The current best known expecte…

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back

Pasin Manurangsi

In the Max $k$ -Weight SAT (aka Max SAT with Cardinality Constraint) problem, we are given a CNF formula with $n$ variables and $m$ clauses together with a positive integer $k$ . The…

User-Level Differential Privacy With Few Examples Per User

Badih Ghazi, Pritish Kamath, Ravi Kumar +3

Previous work on user-level differential privacy (DP) [Ghazi et al. NeurIPS 2021, Bun et al. STOC 2023] obtained generic algorithms that work for various learning tasks. However, t…

cs.DS2023★ 1 cited

Hardness of Approximating Bounded-Degree Max 2-CSP and Independent Set on k-Claw-Free Graphs

Euiwoong Lee, Pasin Manurangsi

We consider the question of approximating Max 2-CSP where each variable appears in at most $d$ constraints (but with possibly arbitrarily large alphabet). There is a simple $(\frac…

cs.DS2023★ 1 cited

Optimizing Hierarchical Queries for the Attribution Reporting API

Matthew Dawson, Badih Ghazi, Pritish Kamath +8

We study the task of performing hierarchical queries based on summary reports from the {\em Attribution Reporting API} for ad conversion measurement. We demonstrate that methods fr…

On Differentially Private Sampling from Gaussian and Product Distributions

Badih Ghazi, Xiao Hu, Ravi Kumar +1

Given a dataset of $n$ i.i.d. samples from an unknown distribution $P$ , we consider the problem of generating a sample from a distribution that is close to $P$ in total variation d…

Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient

Badih Ghazi, Ravi Kumar, Pasin Manurangsi

We obtain a new protocol for binary counting in the $ε$ -shuffle-DP model with error $O (1/ ε)$ and expected communication $\tilde{O}\left(\frac{\log n}{\varepsilo…