39 citations · 308 across the 129 of their papers we have counts for
156 papers
CALLIOPE: Private Insights into AI Use, Without Embeddings
Edith Cohen, Vadym Doroshenko, Badih Ghazi +11
We introduce CALLIOPE, a top-down framework for discovering topic hierarchies in large corpora of unstructured data (e.g., LLM conversations), while supporting differential privacy…
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…
Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries
Surendra Ghentiyala, Pritish Kamath, Ravi Kumar +1
We study the question of answering linear queries with differential privacy using few (expected) random bits. We provide a randomness-efficient analog of the -norm m…
Online Differentially Private Consistent Clustering
Edith Cohen, Vadym Doroshenko, Badih Ghazi +7
We study differentially private (DP) -means and -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.…
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
We study the complexity of computing the Threshold dimension of a hypothesis class and its variant, the Extended threshold dimension. For the latter, we prove that it is both NP-ha…
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--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,…
Fair Allocation under Conflict Constraints
Sarfaraz Equbal, Rohit Gurjar, Ayumi Igarashi +6
We study the fair allocation of indivisible items subject to conflict constraints. In this framework, the items are represented as the vertices of a graph, with edges corresponding…
Improved Approximation Algorithm for Maximum Balanced Biclique
Pasin Manurangsi
We study the Maximum Balanced Biclique (MBB) problem: Given a bipartite graph with vertices on each side, find a balanced biclique in with maximum size. We give a polyn…
When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
Pritish Kamath, Ravi Kumar, Pasin Manurangsi
We study two conjectures posed in the analysis of Boolean functions , in both of which, the Majority function plays a central role: the "Majority is…
Polynomial-Time Algorithm for Thiele Voting Rules with Voter Interval Preferences
Pasin Manurangsi, Krzysztof Sornat
We present a polynomial-time algorithm for computing an optimal committee of size under any given Thiele voting rule for elections on the Voter Interval domain (i.e., when vote…
On Expansion of Random Regular Graphs: Improved Lower Bounds for Small Even Degrees
Pasin Manurangsi
We show that a simple scoring-based tie-breaking can help improve lower bounds for the expansion (aka isoperimetric number) of random regular graphs with small even degrees. Specif…
Optimal partition selection with Rényi differential privacy
Charlie Harrison, Pasin Manurangsi
A common problem in private data analysis is the partition selection problem, where each user holds a set of partitions (e.g. keys in a GROUP BY operation) from a possibly unbounde…
Denoising the US Census: Succinct Block Hierarchical Regression
Badih Ghazi, Pritish Kamath, Ravi Kumar +2
The US Census Bureau Disclosure Avoidance System (DAS) balances confidentiality and utility requirements for the decennial US Census (Abowd et al., 2022). The DAS was used in the 2…
Computational Hardness of Private Coreset
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +3
We study the problem of differentially private (DP) computation of coreset for the -means objective. For a given input set of points, a coreset is another set of points such tha…
Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
Alessandro Epasto, Xin Lyu, Pasin Manurangsi
We study the computational cost of differential privacy in terms of memory efficiency. While the trade-off between accuracy and differential privacy is well-understood, the inheren…
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…
Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity
Matthew Regehr, Bingshan Hu, Ethan Leeman +3
We study privacy filters, which enable privacy accounting for differentially private (DP) mechanisms with adaptively chosen privacy characteristics. We develop a general theory tha…
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…
Nearly-Optimal Private Selection via Gaussian Mechanism
Ethan Leeman, Pasin Manurangsi
Steinke (2025) recently asked the following intriguing open question: Can we solve the differentially private selection problem with nearly-optimal error by only (adaptively) invok…