Arrow Research search

Author name cluster

Pasin Manurangsi

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

64 papers
2 author rows

Possible papers

64

AAAI Conference 2026 Conference Paper

Fair Allocation of Indivisible Goods with Variable Groups

  • Paul Gölz
  • Ayumi Igarashi
  • Pasin Manurangsi
  • Warut Suksompong

We study the fair allocation of indivisible goods with variable groups. In this model, the goal is to partition the agents into groups of given sizes and allocate the goods to the groups in a fair manner. We show that for any number of groups and corresponding sizes, there always exists an envy-free up to one good (EF1) outcome, thereby generalizing an important result from the individual setting. Our result holds for arbitrary monotonic utilities and comes with an efficient algorithm. We also prove that an EF1 outcome is guaranteed to exist even when the goods lie on a path and each group must receive a connected bundle. In addition, we consider a probabilistic model where the utilities are additive and drawn randomly from a distribution. We show that if there are n agents and the number of goods m is divisible by the number of groups k, then an envy-free outcome exists with high probability if m = ω(log n), and this bound is tight. On the other hand, if m is not divisible by k, then an envy-free outcome is unlikely to exist as long as m = o(√n).

PDF Details DOI

AAAI Conference 2026 Conference Paper

Improved Differentially Private Algorithms for Rank Aggregation

  • Quentin Hillebrand
  • Pasin Manurangsi
  • Vorapong Suppakitpaisarn
  • Phanu Vajanopath

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 differentially-private (DP) polynomial-time approximation schemes (PTASes) and 5-approximation algorithms with certain additive errors for the Kemeny rank aggregation problem in both central and local models. In this paper, we present improved DP PTASes with smaller additive error in the central model. Furthermore, we are first to study the footrule rank aggregation problem under DP. We give a near-optimal algorithm for this problem; as a corollary, this leads to 2-approximation algorithms with the same additive error as the 5-approximation algorithms of Alabi et al. for the Kemeny rank aggregation problem in both central and local models.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Asymptotic Analysis of Weighted Fair Division

  • Pasin Manurangsi
  • Warut Suksompong
  • Tomohiko Yokoyama

Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if m items are divided among n agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that m = Omega(n log n / log log n), generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of m = n / (1 - \mu) for the transition from non-existence to existence, where \mu in (0, 1) denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if m = omega(sqrt{r}), where r denotes the ratio between the two weights.

PDF Details DOI

TCS Journal 2025 Journal Article

Asymptotic analysis of weighted fair division

  • Pasin Manurangsi
  • Warut Suksompong
  • Tomohiko Yokoyama

Several resource allocation settings involve agents with unequal entitlements represented by weights. We analyze weighted fair division from an asymptotic perspective: if m items are divided among n agents whose utilities are independently sampled from a probability distribution, when is it likely that a fair allocation exist? We show that if the ratio between the weights is bounded, a weighted envy-free allocation exists with high probability provided that m = Ω ( n log n / log log n ), generalizing a prior unweighted result. For weighted proportionality, we establish a sharp threshold of m = n / ( 1 − μ ) for the transition from non-existence to existence, where μ ∈ ( 0, 1 ) denotes the mean of the distribution. In addition, we prove that for two agents, a weighted envy-free (and weighted proportional) allocation is likely to exist if m = ω ( r ), where r denotes the ratio between the two weights.

Details DOI

IJCAI Conference 2025 Conference Paper

Asymptotic Fair Division: Chores Are Easier Than Goods

  • Pasin Manurangsi
  • Warut Suksompong

When dividing items among agents, two of the most widely studied fairness notions are envy-freeness and proportionality. We consider a setting where m chores are allocated to n agents and the disutility of each chore for each agent is drawn from a probability distribution. We show that an envy-free allocation exists with high probability provided that m >= 2n, and moreover, m must be at least n+Theta(n) in order for the existence to hold. On the other hand, we prove that a proportional allocation is likely to exist as long as m = omega(1), and this threshold is asymptotically tight. Our results reveal a clear contrast with the allocation of goods, where a larger number of items is necessary to ensure existence for both notions.

PDF Details DOI

I&C Journal 2025 Journal Article

Complexity of round-robin allocation with potentially noisy queries

  • Zihan Li
  • Pasin Manurangsi
  • Jonathan Scarlett
  • Warut Suksompong

We study the complexity of a fundamental algorithm for fairly allocating indivisible items, the round-robin algorithm. For n agents and m items, we show that the algorithm can be implemented in time O ( n m log ⁡ ( m / n ) ) in the worst case. If the agents' preferences are uniformly random, we establish an improved (expected) running time of O ( n m + m log ⁡ m ). On the other hand, assuming comparison queries between items, we prove that Ω ( n m + m log ⁡ m ) queries are necessary to implement the algorithm, even when randomization is allowed. We also derive bounds in noise models where the answers to queries are incorrect with some probability. Our proofs involve novel applications of tools from multi-armed bandits, information theory, as well as posets and linear extensions.

Details DOI

AIJ Journal 2025 Journal Article

Differentially private fair division

  • Pasin Manurangsi
  • Warut Suksompong

Fairness and privacy are two important concerns in social decision-making processes such as resource allocation. We study privacy in the fair allocation of indivisible resources using the well-established framework of differential privacy. We present algorithms for approximate envy-freeness and proportionality when two instances are considered to be adjacent if they differ only on the utility of a single agent for a single item. On the other hand, we provide strong negative results for both fairness criteria when the adjacency notion allows the entire utility function of a single agent to change.

Details DOI

IJCAI Conference 2025 Conference Paper

Dividing Conflicting Items Fairly

  • Ayumi Igarashi
  • Pasin Manurangsi
  • Hirotaka Yoneda

We study the allocation of indivisible goods under conflicting constraints, represented by a graph. In this framework, vertices correspond to goods and edges correspond to conflicts between a pair of goods. Each agent is allocated an independent set in the graph. In a recent work of Kumar et al. (AAMAS, 2024), it was shown that a maximal EF1 allocation exists for interval graphs and two agents with monotone valuations. We significantly extend this result by establishing that a maximal EF1 allocation exists for any graph when the two agents have monotone valuations. To compute such an allocation, we present a polynomial-time algorithm for additive valuations, as well as a pseudo-polynomial time algorithm for monotone valuations. Moreover, we complement our findings by providing a counterexample demonstrating a maximal EF1 allocation may not exist for three agents with monotone valuations; further, we establish NP-hardness of determining the existence of such allocations for every fixed number n >= 3 of agents. All of our results for goods also apply to the allocation of chores.

PDF Details DOI

TCS Journal 2025 Journal Article

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 goal is to find an assignment where at most k variables are set to one that satisfies as many constraints as possible. Recently, Jain et al. [20] gave an FPT approximation scheme (FPT-AS) with running time 2 O ( ( d k / ϵ ) d ) ⋅ ( n + m ) O ( 1 ) for Max k-Weight SAT when the incidence graph is K d, d -free. They asked whether a polynomial-size approximate kernel exists. In this work, we answer this question positively by giving a ( 1 − ϵ ) -approximate kernel with ( d k ϵ ) O ( d ) variables. This also implies an improved FPT-AS with running time ( d k / ϵ ) O ( d k ) ⋅ ( n + m ) O ( 1 ). Our approximate kernel is based mainly on a couple of greedy strategies together with a sunflower lemma-style reduction rule.

Details DOI

TCS Journal 2025 Journal Article

Ordinal maximin guarantees for group fair division

  • Pasin Manurangsi
  • Warut Suksompong

We investigate fairness in the allocation of indivisible items among groups of agents using the notion of maximin share (MMS). While previous work has shown that no nontrivial multiplicative MMS approximation can be guaranteed in this setting for general group sizes, we demonstrate that ordinal relaxations are much more useful. For example, we show that if n agents are distributed equally across g groups, there exists a 1-out-of-k MMS allocation for k = O ( g log ⁡ ( n / g ) ), while if all but a constant number of agents are in the same group, we obtain k = O ( log ⁡ n / log ⁡ log ⁡ n ). We also establish the tightness of these bounds and provide non-asymptotic results for the case of two groups. Our proofs leverage connections to combinatorial covering designs.

Details DOI

NeurIPS Conference 2025 Conference Paper

Private Hyperparameter Tuning with Ex-Post Guarantee

  • Badih Ghazi
  • Pritish Kamath
  • Alexander Knop
  • Ravi Kumar
  • Pasin Manurangsi
  • Chiyuan Zhang

The conventional approach in differential privacy (DP) literature formulates the privacy-utility tradeoff with a "privacy-first" perspective: for a predetermined level of privacy, a certain utility is achievable. However, practitioners often operate under a "utility-first" paradigm, prioritizing a desired level of utility and then determining the corresponding privacy cost. Wu et al. [2019] initiated a formal study of this ``utility-first'' perspective by introducing ex-post DP. They demonstrated that by adding correlated Laplace noise and progressively reducing it on demand, a sequence of increasingly accurate estimates of a private parameter can be generated, with the privacy cost attributed only to the least noisy iterate released. This led to a Laplace mechanism variant that achieves a specified utility with minimal privacy loss. However, their work, and similar findings by Whitehouse et al. [2023], are primarily limited to simple mechanisms based on Laplace or Gaussian noise. In this paper, we significantly generalize these results. In particular, we extend the findings of Wu et al. [2019] and Liu and Talwar [2019] to support any sequence of private estimators, incurring at most a doubling of the original privacy budget. Furthermore, we demonstrate that hyperparameter tuning for these estimators, including the selection of an optimal privacy budget, can be performed without additional privacy cost. Finally, we extend our results to ex-post R\'{e}nyi DP, further broadening the applicability of utility-first privacy mechanisms.

PDF Details

ICLR Conference 2025 Conference Paper

Unlearn and Burn: Adversarial Machine Unlearning Requests Destroy Model Accuracy

  • Yangsibo Huang
  • Daogao Liu
  • Lynn Chua
  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar 0001
  • Pasin Manurangsi
  • Milad Nasr

Machine unlearning algorithms, designed for selective removal of training data from models, have emerged as a promising approach to growing privacy concerns. In this work, we expose a critical yet underexplored vulnerability in the deployment of unlearning systems: the assumption that the data requested for removal is always part of the original training set. We present a threat model where an attacker can degrade model accuracy by submitting adversarial unlearning requests for data \textit{not} present in the training set. We propose white-box and black-box attack algorithms and evaluate them through a case study on image classification tasks using the CIFAR-10 and ImageNet datasets, targeting a family of widely used unlearning methods. Our results show extremely poor test accuracy following the attack—3.6% on CIFAR-10 and 0.4% on ImageNet for white-box attacks, and 8.5% on CIFAR-10 and 1.3% on ImageNet for black-box attacks. Additionally, we evaluate various verification mechanisms to detect the legitimacy of unlearning requests and reveal the challenges in verification, as most of the mechanisms fail to detect stealthy attacks without severely impairing their ability to process valid requests. These findings underscore the urgent need for research on more robust request verification methods and unlearning protocols, should the deployment of machine unlearning systems become more prevalent in the future.

Details

NeurIPS Conference 2024 Conference Paper

Differentially Private Optimization with Sparse Gradients

  • Badih Ghazi
  • Cristóbal Guzmán
  • Pritish Kamath
  • Ravi Kumar
  • Pasin Manurangsi

Motivated by applications of large embedding models, we study differentially private (DP) optimization problems under sparsity of individual gradients. We start with new near-optimal bounds for the classic mean estimation problem but with sparse data, improving upon existing algorithms particularly for the high-dimensional regime. The corresponding lower bounds are based on a novel block-diagonal construction that is combined with existing DP mean estimation lower bounds. Next, we obtain pure- and approximate-DP algorithms with almost optimal rates for stochastic convex optimization with sparse gradients; the former represents the first nearly dimension-independent rates for this problem. Furthermore, by introducing novel analyses of bias reduction in mean estimation and randomly-stopped biased SGD we obtain nearly dimension-independent rates for near-stationary points for the empirical risk in nonconvex settings under approximate-DP.

PDF Details DOI

ICML Conference 2024 Conference Paper

How Private are DP-SGD Implementations?

  • Lynn Chua
  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar 0001
  • Pasin Manurangsi
  • Amer Sinha
  • Chiyuan Zhang

We demonstrate a substantial gap between the privacy guarantees of the Adaptive Batch Linear Queries (ABLQ) mechanism under different types of batch sampling: (i) Shuffling, and (ii) Poisson subsampling; the typical analysis of Differentially Private Stochastic Gradient Descent (DP-SGD) follows by interpreting it as a post-processing of ABLQ. While shuffling-based DP-SGD is more commonly used in practical implementations, it has not been amenable to easy privacy analysis, either analytically or even numerically. On the other hand, Poisson subsampling-based DP-SGD is challenging to scalably implement, but has a well-understood privacy analysis, with multiple open-source numerically tight privacy accountants available. This has led to a common practice of using shuffling-based DP-SGD in practice, but using the privacy analysis for the corresponding Poisson subsampling version. Our result shows that there can be a substantial gap between the privacy analysis when using the two types of batch sampling, and thus advises caution in reporting privacy parameters for DP-SGD.

Details

ICML Conference 2024 Conference Paper

Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization

  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar 0001
  • Pasin Manurangsi
  • Adam Sealfon

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 variant satisfies two-sided DP. From this, we obtain several improved algorithms for private combinatorial optimization problems, including decomposable submodular maximization and set cover. Our error guarantees are asymptotically tight and our algorithm satisfies pure-DP while previously known algorithms (Gupta et al. , 2010; Chaturvedi et al. , 2021) are approximate-DP. We also show an application of our technique beyond combinatorial optimization by giving a pure-DP algorithm for the shifting heavy hitter problem in a stream; previously, only an approximate-DP algorithm was known (Kaplan et al. , 2021; Cohen & Lyu, 2023).

Details

ICLR Conference 2024 Conference Paper

LabelDP-Pro: Learning with Label Differential Privacy via Projections

  • Badih Ghazi
  • Yangsibo Huang
  • Pritish Kamath
  • Ravi Kumar 0001
  • Pasin Manurangsi
  • Chiyuan Zhang

Label differentially private (label DP) algorithms seek to preserve the privacy of the labels in a training dataset in settings where the features are known to the adversary. In this work, we study a new family of label DP training algorithms. Unlike most prior label DP algorithms that have been based on label randomization, our algorithm naturally leverages the power of the central model of DP. It interleaves gradient projection operations with private stochastic gradient descent steps in order to improve the utility of the trained model while guaranteeing the privacy of the labels. We show that such projection-based algorithms can be made practical and that they improve on the state-of-the art for label DP training in the high-privacy regime. We complement our empirical evaluation with theoretical results shedding light on the efficacy of our method through the lens of bias-variance trade-offs.

Details

IJCAI Conference 2024 Conference Paper

Ordinal Maximin Guarantees for Group Fair Division

  • Pasin Manurangsi
  • Warut Suksompong

We investigate fairness in the allocation of indivisible items among groups of agents using the notion of maximin share (MMS). While previous work has shown that no nontrivial multiplicative MMS approximation can be guaranteed in this setting for general group sizes, we demonstrate that ordinal relaxations are much more useful. For example, we show that if n agents are distributed equally across g groups, there exists a 1-out-of-k MMS allocation for k = O(g log(n/g)), while if all but a constant number of agents are in the same group, we obtain k = O(log n / log log n). We also establish the tightness of these bounds and provide non-asymptotic results for the case of two groups.

PDF Details DOI

NeurIPS Conference 2024 Conference Paper

Scalable DP-SGD: Shuffling vs. Poisson Subsampling

  • Lynn Chua
  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar
  • Pasin Manurangsi
  • Amer Sinha
  • Chiyuan Zhang

We provide new lower bounds on the privacy guarantee of multi-epoch Adaptive Batch Linear Queries (ABLQ) mechanism with shuffled batch sampling, demonstrating substantial gaps when compared to Poisson subsampling; prior analysis was limited to a single epoch. Since the privacy analysis of Differentially Private Stochastic Gradient Descent (DP-SGD) is obtained by analyzing the ABLQ mechanism, this brings into serious question the common practice of implementing Shuffling based DP-SGD, but reporting privacy parameters as if Poisson subsampling was used. To understand the impact of this gap on the utility of trained machine learning models, we introduce a novel practical approach to implement Poisson subsampling at scale using massively parallel computation, and efficiently train models with the same. We provide a comparison between the utility of models trained with Poisson subsampling based DP-SGD, and the optimistic estimates of utility when using shuffling, via our new lower bounds on the privacy guarantee of ABLQ with shuffling.

PDF Details DOI

SODA Conference 2023 Conference Paper

Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds

  • Justin Y. Chen
  • Badih Ghazi
  • Ravi Kumar 0001
  • Pasin Manurangsi
  • Shyam Narayanan
  • Jelani Nelson
  • Yinzhan Xu

We study the problem of releasing the weights of all-pairs shortest paths in a weighted undirected graph with differential privacy (DP). In this setting, the underlying graph is fixed and two graphs are neighbors if their edge weights differ by at most 1 in the ℓ 1 -distance. We give an algorithm with additive error Õ ( n 2/3 /ε) in the ε-DP case and an algorithm with additive error in the (ε, δ)-DP case, where n denotes the number of vertices. This positively answers a question of Sealfon [Sea16, Sea20], who asked whether a o ( n )- error algorithm exists. We also show that an additive error of Ω ( n 1/6 ) is necessary for any sufficiently small ε, δ > 0. Furthermore, we show that if the graph is promised to have reasonably bounded weights, one can improve the error further to roughly in the ε-DP case and roughly in the (ε, δ)-DP case. Previously, it was only known how to obtain Õ ( n 2/3 /ε 1/3 ) additive error in the ε-DP case and additive error in the (ε, δ)-DP case for bounded-weight graphs [Sea16]. Finally, we consider a relaxation where a multiplicative approximation is allowed. We show that, with a multiplicative approximation factor k, the additive error can be reduced to Õ( n 1/2+ O (1/ k ) /ε) in the ε-DP case and Õ ( n 1/3+O(1/ k ) /ε) in the (ε, δ)-DP case.

Details

AAAI Conference 2023 Conference Paper

Differentially Private Fair Division

  • Pasin Manurangsi
  • Warut Suksompong

Fairness and privacy are two important concerns in social decision-making processes such as resource allocation. We study privacy in the fair allocation of indivisible resources using the well-established framework of differential privacy. We present algorithms for approximate envy-freeness and proportionality when two instances are considered to be adjacent if they differ only on the utility of a single agent for a single item. On the other hand, we provide strong negative results for both fairness criteria when the adjacency notion allows the entire utility function of a single agent to change.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Differentially Private Heatmaps

  • Badih Ghazi
  • Junfeng He
  • Kai Kohlhoff
  • Ravi Kumar
  • Pasin Manurangsi
  • Vidhya Navalpakkam
  • Nachiappan Valliappan

We consider the task of producing heatmaps from users' aggregated data while protecting their privacy. We give a differentially private (DP) algorithm for this task and demonstrate its advantages over previous algorithms on real-world datasets. Our core algorithmic primitive is a DP procedure that takes in a set of distributions and produces an output that is close in Earth Mover's Distance (EMD) to the average of the inputs. We prove theoretical bounds on the error of our algorithm under a certain sparsity assumption and that these are essentially optimal.

PDF Details DOI

TCS Journal 2023 Journal Article

Justifying groups in multiwinner approval voting

  • Edith Elkind
  • Piotr Faliszewski
  • Ayumi Igarashi
  • Pasin Manurangsi
  • Ulrike Schmidt-Kraepelin
  • Warut Suksompong

Justified representation (JR) is a standard notion of representation in multiwinner approval voting. Not only does a JR committee always exist, but previous work has also shown through experiments that the JR condition can typically be fulfilled by groups of fewer than k candidates, where k is the target size of the committee. In this paper, we study such groups—known as n / k -justifying groups—both theoretically and empirically. First, we show that under the impartial culture model, n / k -justifying groups of size less than k / 2 are likely to exist, which implies that the number of JR committees is usually large. We then present efficient approximation algorithms that compute a small n / k -justifying group for any given instance, and a polynomial-time exact algorithm when the instance admits a tree representation. In addition, we demonstrate that small n / k -justifying groups can often be useful for obtaining a gender-balanced JR committee even though the problem is NP-hard.

Details DOI

NeurIPS Conference 2023 Conference Paper

On Computing Pairwise Statistics with Local Differential Privacy

  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar
  • Pasin Manurangsi
  • Adam Sealfon

We study the problem of computing pairwise statistics, i. e. , ones of the form $\binom{n}{2}^{-1} \sum_{i \ne j} f(x_i, x_j)$, where $x_i$ denotes the input to the $i$th user, with differential privacy (DP) in the local model. This formulation captures important metrics such as Kendall's $\tau$ coefficient, Area Under Curve, Gini's mean difference, Gini's entropy, etc. We give several novel and generic algorithms for the problem, leveraging techniques from DP algorithms for linear queries.

PDF Details

NeurIPS Conference 2023 Conference Paper

On Differentially Private Sampling from Gaussian and Product Distributions

  • Badih Ghazi
  • Xiao Hu
  • Ravi Kumar
  • Pasin Manurangsi

We study the problem, where given a dataset of $n$ i. i. d. samples from an unknown distribution $P$, we seek to generate a sample from a distribution that is close to $P$ in total variation distance, under the constraint of differential privacy. We study the settings where $P$ is a multi-dimensional Gaussian distribution with different assumptions: known covariance, unknown bounded covariance, and unknown unbounded covariance. We present new differentially private sampling algorithms, and show that they achieve near-optimal sample complexity in the first two settings. Moreover, when $P$ is a product distribution on the binary hypercube, we obtain a pure-DP algorithm whereas only an approximate-DP algorithm (with slightly worse sample complexity) was previously known.

PDF Details

ICML Conference 2023 Conference Paper

On User-Level Private Convex Optimization

  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar 0001
  • Pasin Manurangsi
  • Raghu Meka
  • Chiyuan Zhang

We introduce a new mechanism for stochastic convex optimization (SCO) with user-level differential privacy guarantees. The convergence rates of this mechanism are similar to those in the prior work of Levy et al. 2021 and Narayanan et al. 2022, but with two important improvements. Our mechanism does not require any smoothness assumptions on the loss. Furthermore, our bounds are also the first where the minimum number of users needed for user-level privacy has no dependence on the dimension and only a logarithmic dependence on the desired excess error. The main idea underlying the new mechanism is to show that the optimizers of strongly convex losses have low local deletion sensitivity, along with a new output perturbation method for functions with low local deletion sensitivity, which could be of independent interest.

Details

NeurIPS Conference 2023 Conference Paper

Optimal Unbiased Randomizers for Regression with Label Differential Privacy

  • Ashwinkumar Badanidiyuru Varadaraja
  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar
  • Ethan Leeman
  • Pasin Manurangsi
  • Avinash V Varadarajan
  • Chiyuan Zhang

We propose a new family of label randomizers for training regression models under the constraint of label differential privacy (DP). In particular, we leverage the trade-offs between bias and variance to construct better label randomizers depending on a privately estimated prior distribution over the labels. We demonstrate that these randomizers achieve state-of-the-art privacy-utility trade-offs on several datasets, highlighting the importance of reducing bias when training neural networks with label DP. We also provide theoretical results shedding light on the structural properties of the optimal unbiased randomizers.

PDF Details

ICLR Conference 2023 Conference Paper

Regression with Label Differential Privacy

  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar 0001
  • Ethan Leeman
  • Pasin Manurangsi
  • Avinash V. Varadarajan
  • Chiyuan Zhang

We study the task of training regression models with the guarantee of _label_ differential privacy (DP). Based on a global prior distribution of label values, which could be obtained privately, we derive a label DP randomization mechanism that is optimal under a given regression loss function. We prove that the optimal mechanism takes the form of a "randomized response on bins", and propose an efficient algorithm for finding the optimal bin values. We carry out a thorough experimental evaluation on several datasets demonstrating the efficacy of our algorithm.

Details

NeurIPS Conference 2023 Conference Paper

Sparsity-Preserving Differentially Private Training of Large Embedding Models

  • Badih Ghazi
  • Yangsibo Huang
  • Pritish Kamath
  • Ravi Kumar
  • Pasin Manurangsi
  • Amer Sinha
  • Chiyuan Zhang

As the use of large embedding models in recommendation systems and language applications increases, concerns over user data privacy have also risen. DP-SGD, a training algorithm that combines differential privacy with stochastic gradient descent, has been the workhorse in protecting user privacy without compromising model accuracy by much. However, applying DP-SGD naively to embedding models can destroy gradient sparsity, leading to reduced training efficiency. To address this issue, we present two new algorithms, DP-FEST and DP-AdaFEST, that preserve gradient sparsity during the private training of large embedding models. Our algorithms achieve substantial reductions ($10^6 \times$) in gradient size, while maintaining comparable levels of accuracy, on benchmark real-world datasets.

PDF Details

FOCS Conference 2023 Conference Paper

Towards Separating Computational and Statistical Differential Privacy

  • Badih Ghazi
  • Rahul Ilango
  • Pritish Kamath
  • Ravi Kumar 0001
  • Pasin Manurangsi

Computational differential privacy (CDP) is a natural relaxation of the standard notion of (statistical) differential privacy (SDP) proposed by Beimel, Nissim, and Omri (CRYPTO 2008) and Mironov, Pandey, Reingold, and Vadhan (CRYPTO 2009). In contrast to SDP, CDP only requires privacy guarantees to hold against computationally-bounded adversaries rather than computationally-unbounded statistical adversaries. Despite the question being raised explicitly in several works (e. g. , Bun, Chen, and Vadhan, TCC 2016), it has remained tantalizingly open whether there is any task achievable with the CDP notion but not the SDP notion. Even a candidate such task is unknown. Indeed, it is even unclear what the truth could be! In this work, we give the first construction of a task achievable with the CDP notion but not the SDP notion, under the following strong but plausible cryptographic assumptions: •Non-Interactive Witness Indistinguishable Proofs, •Laconic Collision-Resistant Keyless Hash Functions, •Differing-Inputs Obfuscation for Public-Coin Samplers. In particular, we construct a task for which there exists an $\varepsilon$-CDP mechanism with $\varepsilon=O(1)$ achieving $1-o(1)$ utility, but any $(\varepsilon, \delta)$-SDP mechanism, including computationally-unbounded ones, that achieves a constant utility must use either a super-constant $\varepsilon$ or an inverse-polynomially large $\delta$. To prove this, we introduce a new approach for showing that a mechanism satisfies CDP: first we show that a mechanism is “private” against a certain class of decision tree adversaries, and then we use cryptographic constructions to “lift” this into privacy against computationally bounded adversaries. We believe this approach could be useful to devise further tasks separating CDP from SDP.

Details

NeurIPS Conference 2023 Conference Paper

User-Level Differential Privacy With Few Examples Per User

  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar
  • Pasin Manurangsi
  • Raghu Meka
  • Chiyuan Zhang

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, their focus was on the *example-rich* regime, where the users have so many examples that each user could themselves solve the problem. In this work we consider the *example-scarce* regime, where each user has only a few examples, and obtain the following results: * For approximate-DP, we give a generic transformation of any item-level DP algorithm to a user-level DP algorithm. Roughly speaking, the latter gives a (multiplicative) savings of $O_{\varepsilon, \delta}(\sqrt{m})$ in terms of the number of users required for achieving the same utility, where $m$ is the number of examples per user. This algorithm, while recovering most known bounds for specific problems, also gives new bounds, e. g. , for PAC learning. * For pure-DP, we present a simple technique for adapting the exponential mechanism [McSherry & Talwar, FOCS 2007] to the user-level setting. This gives new bounds for a variety of tasks, such as private PAC learning, hypothesis selection, and distribution learning. For some of these problems, we show that our bounds are near-optimal.

PDF Details

TCS Journal 2022 Journal Article

Almost envy-freeness for groups: Improved bounds via discrepancy theory

  • Pasin Manurangsi
  • Warut Suksompong

We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always be satisfied, we provide several bounds on the optimal relaxations that can be guaranteed. For instance, our bounds imply that when the number of groups is constant and the n agents are divided into groups arbitrarily, there exists an allocation that is envy-free up to Θ ( n ) goods, and this bound is tight. Moreover, we show that while such an allocation can be found efficiently, it is NP-hard to compute an allocation that is envy-free up to o ( n ) goods even when a fully envy-free allocation exists. Our proofs make extensive use of tools from discrepancy theory.

Details DOI

NeurIPS Conference 2022 Conference Paper

Anonymized Histograms in Intermediate Privacy Models

  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar
  • Pasin Manurangsi

We study the problem of privately computing the $\mbox{\it anonymized histogram}$ (a. k. a. $\mbox{\it unattributed histogram}$), which is defined as the histogram without item labels. Previous works have provided algorithms with $\ell_1$- and $\ell_2^2$-errors of $O_\varepsilon(\sqrt{n})$ in the central model of differential privacy (DP). In this work, we provide an algorithm with a nearly matching error guarantee of $\widetilde{O}_\varepsilon(\sqrt{n})$ in the shuffle DP and pan-private models. Our algorithm is very simple: it just post-processes the discrete Laplace-noised histogram! Using this algorithm as a subroutine, we show applications in privately estimating symmetric properties of distributions such as entropy, support coverage, and support size.

PDF Details

NeurIPS Conference 2022 Conference Paper

Cryptographic Hardness of Learning Halfspaces with Massart Noise

  • Ilias Diakonikolas
  • Daniel Kane
  • Pasin Manurangsi
  • Lisheng Ren

We study the complexity of PAC learning halfspaces in the presence of Massart noise. In this problem, we are given i. i. d. labeled examples $(\mathbf{x}, y) \in \mathbb{R}^N \times \{ \pm 1\}$, where the distribution of $\mathbf{x}$ is arbitrary and the label $y$ is a Massart corruption of $f(\mathbf{x})$, for an unknown halfspace $f: \mathbb{R}^N \to \{ \pm 1\}$, with flipping probability $\eta(\mathbf{x}) \leq \eta < 1/2$. The goal of the learner is to compute a hypothesis with small 0-1 error. Our main result is the first computational hardness result for this learning problem. Specifically, assuming the (widely believed) subexponential-time hardness of the Learning with Errors (LWE) problem, we show that no polynomial-time Massart halfspace learner can achieve error better than $\Omega(\eta)$, even if the optimal 0-1 error is small, namely $\mathrm{OPT} = 2^{-\log^{c} (N)}$ for any universal constant $c \in (0, 1)$. Prior work had provided qualitatively similar evidence of hardness in the Statistical Query model. Our computational hardness result essentially resolves the polynomial PAC learnability of Massart halfspaces, by showing that known efficient learning algorithms for the problem are nearly best possible.

PDF Details

ICML Conference 2022 Conference Paper

Faster Privacy Accounting via Evolving Discretization

  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar 0001
  • Pasin Manurangsi

We introduce a new algorithm for numerical composition of privacy random variables, useful for computing the accurate differential privacy parameters for compositions of mechanisms. Our algorithm achieves a running time and memory usage of $polylog(k)$ for the task of self-composing a mechanism, from a broad class of mechanisms, $k$ times; this class, e. g. , includes the sub-sampled Gaussian mechanism, that appears in the analysis of differentially private stochastic gradient descent (DP-SGD). By comparison, recent work by Gopi et al. (NeurIPS 2021) has obtained a running time of $\widetilde{O}(\sqrt{k})$ for the same task. Our approach extends to the case of composing $k$ different mechanisms in the same class, improving upon the running time and memory usage in their work from $\widetilde{O}(k^{1. 5})$ to $\wtilde{O}(k)$.

Details

IJCAI Conference 2022 Conference Paper

Fixing Knockout Tournaments With Seeds

  • Pasin Manurangsi
  • Warut Suksompong

Knockout tournaments constitute a popular format for organizing sports competitions. While prior results have shown that it is often possible to manipulate a knockout tournament by fixing the bracket, these results ignore the prevalent aspect of player seeds, which can significantly constrain the chosen bracket. We show that certain structural conditions that guarantee that a player can win a knockout tournament without seeds are no longer sufficient in light of seed constraints. On the other hand, we prove that when the pairwise match outcomes are generated randomly, all players are still likely to be knockout winners under the same probability threshold with seeds as without seeds. In addition, we investigate the complexity of deciding whether a manipulation is possible when seeds are present.

PDF Details DOI

JAAMAS Journal 2022 Journal Article

Generalized kings and single-elimination winners in random tournaments

  • Pasin Manurangsi
  • Warut Suksompong

Abstract Tournaments can be used to model a variety of practical scenarios including sports competitions and elections. A natural notion of strength of alternatives in a tournament is a generalized king: an alternative is said to be a k - king if it can reach every other alternative in the tournament via a directed path of length at most k. In this paper, we provide an almost complete characterization of the probability threshold such that all, a large number, or a small number of alternatives are k -kings with high probability in two random models. We show that, perhaps surprisingly, all changes in the threshold occur in the range of constant k, with the biggest change being between \(k=2\) and \(k=3\). In addition, we establish an asymptotically tight bound on the probability threshold for which all alternatives are likely able to win a single-elimination tournament under some bracket.

Details DOI

NeurIPS Conference 2022 Conference Paper

Private Isotonic Regression

  • Badih Ghazi
  • Pritish Kamath
  • Ravi Kumar
  • Pasin Manurangsi

In this paper, we consider the problem of differentially private (DP) algorithms for isotonic regression. For the most general problem of isotonic regression over a partially ordered set (poset) $\mathcal{X}$ and for any Lipschitz loss function, we obtain a pure-DP algorithm that, given $n$ input points, has an expected excess empirical risk of roughly $\mathrm{width}(\mathcal{X}) \cdot \log|\mathcal{X}| / n$, where $\mathrm{width}(\mathcal{X})$ is the width of the poset. In contrast, we also obtain a near-matching lower bound of roughly $(\mathrm{width}(\mathcal{X}) + \log |\mathcal{X}|) / n$, that holds even for approximate-DP algorithms. Moreover, we show that the above bounds are essentially the best that can be obtained without utilizing any further structure of the poset. In the special case of a totally ordered set and for $\ell_1$ and $\ell_2^2$ losses, our algorithm can be implemented in near-linear running time; we also provide extensions of this algorithm to the problem of private isotonic regression with additional structural constraints on the output function.

PDF Details

AAAI Conference 2022 Conference Paper

Private Rank Aggregation in Central and Local Models

  • Daniel Alabi
  • Badih Ghazi
  • Ravi Kumar
  • Pasin Manurangsi

In social choice theory, (Kemeny) rank aggregation is a wellstudied problem where the goal is to combine rankings from multiple voters into a single ranking on the same set of items. Since rankings can reveal preferences of voters (which a voter might like to keep private), it is important to aggregate preferences in such a way to preserve privacy. In this work, we present differentially private algorithms for rank aggregation in the pure and approximate settings along with distributionindependent utility upper and lower bounds. In addition to bounds in the central model, we also present utility bounds for the local model of differential privacy.

PDF Details

AAAI Conference 2022 Conference Paper

The Price of Justified Representation

  • Edith Elkind
  • Piotr Faliszewski
  • Ayumi Igarashi
  • Pasin Manurangsi
  • Ulrike Schmidt-Kraepelin
  • Warut Suksompong

In multiwinner approval voting, the goal is to select kmember committees based on voters’ approval ballots. A well-studied concept of proportionality in this context is the justified representation (JR) axiom, which demands that no large cohesive group of voters remains unrepresented. However, the JR axiom may conflict with other desiderata, such as coverage (maximizing the number of voters who approve at least one committee member) or social welfare (maximizing the number of approvals obtained by committee members). In this work, we investigate the impact of imposing the JR axiom (as well as the more demanding EJR axiom) on social welfare and coverage. Our approach is threefold: we derive worst-case bounds on the loss of welfare/coverage that is caused by imposing JR, study the computational complexity of finding ‘good’ committees that provide JR (obtaining a hardness result, an approximation algorithm, and an exact algorithm for one-dimensional preferences), and examine this setting empirically on several synthetic datasets.

PDF Details

IJCAI Conference 2021 Conference Paper

Almost Envy-Freeness for Groups: Improved Bounds via Discrepancy Theory

  • Pasin Manurangsi
  • Warut Suksompong

We study the allocation of indivisible goods among groups of agents using well-known fairness notions such as envy-freeness and proportionality. While these notions cannot always be satisfied, we provide several bounds on the optimal relaxations that can be guaranteed. For instance, our bounds imply that when the number of groups is constant and the $n$ agents are divided into groups arbitrarily, there exists an allocation that is envy-free up to $\Theta(\sqrt{n})$ goods, and this bound is tight. Moreover, we show that while such an allocation can be found efficiently, it is NP-hard to compute an allocation that is envy-free up to $o(\sqrt{n})$ goods even when a fully envy-free allocation exists. Our proofs make extensive use of tools from discrepancy theory.

PDF Details DOI

AIJ Journal 2021 Journal Article

Approximation and hardness of Shift-Bribery

  • Piotr Faliszewski
  • Pasin Manurangsi
  • Krzysztof Sornat

In the Shift-Bribery problem we are given an election, a preferred candidate, and the costs of shifting this preferred candidate up the voters' preference orders. The goal is to find such a set of shifts that ensures that the preferred candidate wins the election. We give the first polynomial-time approximation scheme for the Shift-Bribery problem for the case of positional scoring rules, and for the Copeland rule we show strong inapproximability results.

Details DOI

NeurIPS Conference 2021 Conference Paper

Contextual Recommendations and Low-Regret Cutting-Plane Algorithms

  • Sreenivas Gollapudi
  • Guru Guruganesh
  • Kostas Kollias
  • Pasin Manurangsi
  • Renato Leme
  • Jon Schneider

We consider the following variant of contextual linear bandits motivated by routing applications in navigational engines and recommendation systems. We wish to learn a hidden $d$-dimensional value $w^*$. Every round, we are presented with a subset $\mathcal{X}_t \subseteq \mathbb{R}^d$ of possible actions. If we choose (i. e. recommend to the user) action $x_t$, we obtain utility $\langle x_t, w^* \rangle$ but only learn the identity of the best action $\arg\max_{x \in \X_t} \langle x, w^* \rangle$. We design algorithms for this problem which achieve regret $O(d\log T)$ and $\exp(O(d \log d))$. To accomplish this, we design novel cutting-plane algorithms with low “regret” -- the total distance between the true point $w^*$ and the hyperplanes the separation oracle returns. We also consider the variant where we are allowed to provide a list of several recommendations. In this variant, we give an algorithm with $O(d^2 \log d)$ regret and list size $\poly(d)$. Finally, we construct nearly tight algorithms for a weaker variant of this problem where the learner only learns the identity of an action that is better than the recommendation. Our results rely on new algorithmic techniques in convex geometry (including a variant of Steiner’s formula for the centroid of a convex set) which may be of independent interest.

PDF Details

NeurIPS Conference 2021 Conference Paper

Deep Learning with Label Differential Privacy

  • Badih Ghazi
  • Noah Golowich
  • Ravi Kumar
  • Pasin Manurangsi
  • Chiyuan Zhang

The Randomized Response (RR) algorithm is a classical technique to improve robustness in survey aggregation, and has been widely adopted in applications with differential privacy guarantees. We propose a novel algorithm, Randomized Response with Prior (RRWithPrior), which can provide more accurate results while maintaining the same level of privacy guaranteed by RR. We then apply RRWithPrior to learn neural networks with label differential privacy (LabelDP), and show that when only the label needs to be protected, the model performance can be significantly improved over the previous state-of-the-art private baselines. Moreover, we study different ways to obtain priors, which when used with RRWithPrior can additionally improve the model performance, further reducing the accuracy gap between private and non-private models. We complement the empirical results with theoretical analysis showing that LabelDP is provably easier than protecting both the inputs and labels.

PDF Details

ICML Conference 2021 Conference Paper

Differentially Private Aggregation in the Shuffle Model: Almost Central Accuracy in Almost a Single Message

  • Badih Ghazi
  • Ravi Kumar 0001
  • Pasin Manurangsi
  • Rasmus Pagh
  • Amer Sinha

The shuffle model of differential privacy has attracted attention in the literature due to it being a middle ground between the well-studied central and local models. In this work, we study the problem of summing (aggregating) real numbers or integers, a basic primitive in numerous machine learning tasks, in the shuffle model. We give a protocol achieving error arbitrarily close to that of the (Discrete) Laplace mechanism in central differential privacy, while each user only sends 1 + o(1) short messages in expectation.

Details

IJCAI Conference 2021 Conference Paper

Generalized Kings and Single-Elimination Winners in Random Tournaments

  • Pasin Manurangsi
  • Warut Suksompong

Tournaments can be used to model a variety of practical scenarios including sports competitions and elections. A natural notion of strength of alternatives in a tournament is a generalized king: an alternative is said to be a k-king if it can reach every other alternative in the tournament via a directed path of length at most k. In this paper, we provide an almost complete characterization of the probability threshold such that all, a large number, or a small number of alternatives are k-kings with high probability in two random models. We show that, perhaps surprisingly, all changes in the threshold occur in the regime of constant k, with the biggest change being between k = 2 and k = 3. In addition, we establish an asymptotically tight bound on the probability threshold for which all alternatives are likely able to win a single-elimination tournament under some bracket.

PDF Details DOI

ICML Conference 2021 Conference Paper

Locally Private k-Means in One Round

  • Alisa Chang
  • Badih Ghazi
  • Ravi Kumar 0001
  • Pasin Manurangsi

We provide an approximation algorithm for k-means clustering in the \emph{one-round} (aka \emph{non-interactive}) local model of differential privacy (DP). Our algorithm achieves an approximation ratio arbitrarily close to the best \emph{non private} approximation algorithm, improving upon previously known algorithms that only guarantee large (constant) approximation ratios. Furthermore, ours is the first constant-factor approximation algorithm for k-means that requires only \emph{one} round of communication in the local DP model, positively resolving an open question of Stemmer (SODA 2020). Our algorithmic framework is quite flexible; we demonstrate this by showing that it also yields a similar near-optimal approximation algorithm in the (one-round) shuffle DP model.

Details

STOC Conference 2021 Conference Paper

Sample-efficient proper PAC learning with approximate differential privacy

  • Badih Ghazi
  • Noah Golowich
  • Ravi Kumar 0001
  • Pasin Manurangsi

In this paper we prove that the sample complexity of properly learning a class of Littlestone dimension d with approximate differential privacy is Õ( d 6 ), ignoring privacy and accuracy parameters. This result answers a question of Bun et al. (FOCS 2020) by improving upon their upper bound of 2 O ( d ) on the sample complexity. Prior to our work, finiteness of the sample complexity for privately learning a class of finite Littlestone dimension was only known for improper private learners, and the fact that our learner is proper answers another question of Bun et al., which was also asked by Bousquet et al. (NeurIPS 2020). Using machinery developed by Bousquet et al., we then show that the sample complexity of sanitizing a binary hypothesis class is at most polynomial in its Littlestone dimension and dual Littlestone dimension. This implies that a class is sanitizable if and only if it has finite Littlestone dimension. An important ingredient of our proofs is a new property of binary hypothesis classes that we call irreducibility, which may be of independent interest.

Details

NeurIPS Conference 2021 Conference Paper

User-Level Differentially Private Learning via Correlated Sampling

  • Badih Ghazi
  • Ravi Kumar
  • Pasin Manurangsi

Most works in learning with differential privacy (DP) have focused on the setting where each user has a single sample. In this work, we consider the setting where each user holds $m$ samples and the privacy protection is enforced at the level of each user's data. We show that, in this setting, we may learn with a much fewer number of users. Specifically, we show that, as long as each user receives sufficiently many samples, we can learn any privately learnable class via an $(\epsilon, \delta)$-DP algorithm using only $O(\log(1/\delta)/\epsilon)$ users. For $\epsilon$-DP algorithms, we show that we can learn using only $O_{\epsilon}(d)$ users even in the local model, where $d$ is the probabilistic representation dimension. In both cases, we show a nearly-matching lower bound on the number of users required. A crucial component of our results is a generalization of global stability [Bun, Livni, Moran, FOCS 2020] that allows the use of public randomness. Under this relaxed notion, we employ a correlated sampling strategy to show that the global stability can be boosted to be arbitrarily close to one, at a polynomial expense in the number of samples.

PDF Details

NeurIPS Conference 2020 Conference Paper

Differentially Private Clustering: Tight Approximation Ratios

  • Badih Ghazi
  • Ravi Kumar
  • Pasin Manurangsi

We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient differentially private algorithms that achieve essentially the same approximation ratios as those that can be obtained by any non-private algorithm, while incurring only small additive errors. This improves upon existing efficient algorithms that only achieve some large constant approximation factors. Our results also imply an improved algorithm for the Sample and Aggregate privacy framework. Furthermore, we show that one of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.

PDF Details

ICML Conference 2020 Conference Paper

Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead

  • Badih Ghazi
  • Ravi Kumar 0001
  • Pasin Manurangsi
  • Rasmus Pagh

Differential privacy (DP) is a formal notion for quantifying the privacy loss of algorithms. Algorithms in the central model of DP achieve high accuracy but make the strongest trust assumptions whereas those in the local DP model make the weakest trust assumptions but incur substantial accuracy loss. The shuffled DP model [Bittau et al 2017, Erlingsson et al 2019, Cheu et al 19] has recently emerged as a feasible middle ground between the central and local models, providing stronger trust assumptions than the former while promising higher accuracies than the latter. In this paper, we obtain practical communication-efficient algorithms in the shuffled DP model for two basic aggregation primitives used in machine learning: 1) binary summation, and 2) histograms over a moderate number of buckets. Our algorithms achieve accuracy that is arbitrarily close to that of central DP algorithms with an expected communication per user essentially matching what is needed without any privacy constraints! We demonstrate the practicality of our algorithms by experimentally evaluating them and comparing their performance to several widely-used protocols such as Randomized Response [Warner 1965] and RAPPOR [Erlingsson et al. 2014].

Details

NeurIPS Conference 2020 Conference Paper

The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise

  • Ilias Diakonikolas
  • Daniel M. Kane
  • Pasin Manurangsi

We study the computational complexity of adversarially robust proper learning of halfspaces in the distribution-independent agnostic PAC model, with a focus on $L_p$ perturbations. We give a computationally efficient learning algorithm and a nearly matching computational hardness result for this problem. An interesting implication of our findings is that the $L_{\infty}$ perturbations case is provably computationally harder than the case $2 \leq p < \infty$.

PDF Details

IJCAI Conference 2020 Conference Paper

Tight Approximation for Proportional Approval Voting

  • Szymon Dudycz
  • Pasin Manurangsi
  • Jan Marcinkowski
  • Krzysztof Sornat

In approval-based multiwinner elections, we are given a set of voters, a set of candidates, and, for each voter, a set of candidates approved by the voter. The goal is to find a committee of size k that maximizes the total utility of the voters. In this paper, we study approximability of Thiele rules, which are known to be NP-hard to solve exactly. We provide a tight polynomial time approximation algorithm for a natural class of geometrically dominant weights that includes such voting rules as Proportional Approval Voting or p-Geometric. The algorithm is relatively simple: first we solve a linear program and then we round a solution by employing a framework called pipage rounding due to Ageev and Sviridenko (2004) and Calinescu et al. (2011). We provide a matching lower bound via a reduction from the Label Cover problem. Moreover, assuming a conjecture called Gap-ETH, we show that better approximation ratio cannot be obtained even in time f(k)*pow(n, o(k)).

PDF Details DOI

SODA Conference 2020 Conference Paper

Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k -Coverage, Unique Set Cover and Related Problems (via t -Wise Agreement Testing Theorem)

  • Pasin Manurangsi

We show, assuming the (randomized) Gap Exponential Time Hypothesis (Gap-ETH), that the following tasks cannot be done in T ( k ) · N o ( k ) -time for any function T where N denote the input size: ( )-approximation for M ax k -C overage for any constant ɛ > 0, ( )-approximation for k -M edian (in general metrics) for any constant ɛ > 0. ( )-approximation for k -M ean (in general metrics) for any constant ɛ > 0. Any constant factor approximation for k -U nique S et C over, k -N earest C odeword P roblem and k -C losest V ector P roblem. (1 + δ )-approximation for k -M inimum Distance P roblem and k -S hortest V ector P roblem for some δ > 0. Since all problems considered here can be trivially solved in N O ( k ) time, our running time lower bounds are tight up to a constant factor in the exponent. In terms of approximation ratios, M ax k -C overage is well-known to admit polynomial-time ( )-approximation algorithms, and, recently, it was shown that k -M edian and k -M edian are approximable to within factors of ( ) and ( ) respectively in FPT time [20]; hence, our inapproximability ratios are also tight for these three problems. For the remaining problems, no non-trivial FPT approximation algorithms are known. The starting point of all our hardness results is the L abel C over problem (with projection constraints). We show that L abel C over cannot be approximated to within any constant factor in T ( k ) · N o ( k ) time, where N and k denote the size of the input and the number of nodes on the side with the larger alphabet respectively. With this hardness, the above results follow immediately from known reductions. The hardness of L abel C over is in turn shown via a t-wise agreement testing theorem of the following form: given local boolean functions f 1, …, f k on domains S 1, …, S k ⊆ [ n ], if random t functions “weakly agree” with sufficiently large probability, then we can find a global boolean function g: [ n ] → {0, 1} that “mostly agrees” with “many” of the local functions. We prove such a statement in the regime where S 1, …, S k are “random-looking” sets of size Θ( n / k ).

Details

AAAI Conference 2019 Conference Paper

Approximation and Hardness of Shift-Bribery

  • Piotr Faliszewski
  • Pasin Manurangsi
  • Krzysztof Sornat

In the SHIFT-BRIBERY problem we are given an election, a preferred candidate, and the costs of shifting this preferred candidate up the voters’ preference orders. The goal is to find such a set of shifts that ensures that the preferred candidate wins the election. We give the first polynomial-time approximation scheme for the case of positional scoring rules, and for the Copeland rule we show strong inapproximability results.

PDF Details

AIJ Journal 2019 Journal Article

Computing a small agreeable set of indivisible items

  • Pasin Manurangsi
  • Warut Suksompong

We study the problem of assigning a small subset of indivisible items to a group of agents so that the subset is agreeable to all agents, meaning that all agents value the subset as least as much as its complement. For an arbitrary number of agents and items, we derive a tight worst-case bound on the number of items that may need to be included in such a set. We then present polynomial-time algorithms that find an agreeable set whose size matches the worst-case bound when there are two or three agents. We also show that finding small agreeable sets is possible even when we only have access to the agents' preferences on single items. Furthermore, we investigate the problem of efficiently computing an agreeable set whose size approximates the size of the smallest agreeable set for any given instance. We consider two well-known models for representing the preferences of the agents—the value oracle model and additive utilities—and establish tight bounds on the approximation ratio that can be obtained by algorithms running in polynomial time in each of these models.

Details DOI

SODA Conference 2019 Conference Paper

Losing Treewidth by Separating Subsets

  • Anupam Gupta 0001
  • Euiwoong Lee
  • Jason Li 0006
  • Pasin Manurangsi
  • Michal Wlodarczyk 0001

We study the problem of deleting the smallest set S of vertices (resp. edges) from a given graph G such that the induced subgraph (resp. subgraph) G\S belongs to some class ℋ. We consider the case where graphs in ℋ have treewidth bounded by t, and give a general framework to obtain approximation algorithms for both vertex and edge-deletion settings from approximation algorithms for certain natural graph partitioning problems called k -S ubset V ertex S eparator and k -S ubset E dge S eparator, respectively. For the vertex deletion setting, our framework combined with the current best result for k -S ubset V ertex S eparator, improves approximation ratios for basic problems such as k -T reewidth V ertex D eletion and P lanar -ℱ V ertex D eletion. Our algorithms are simpler than previous works and give the first deterministic and uniform approximation algorithms under the natural parameterization. For the edge deletion setting, we give improved approximation algorithms for k -S ubset E dge S eparator combining ideas from LP relaxations and important separators. We present their applications in bounded-degree graphs, and also give an APX-hardness result for the edge deletion problems.

Details

NeurIPS Conference 2019 Conference Paper

Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin

  • Ilias Diakonikolas
  • Daniel Kane
  • Pasin Manurangsi

We study the problem of {\em properly} learning large margin halfspaces in the agnostic PAC model. In more detail, we study the complexity of properly learning $d$-dimensional halfspaces on the unit ball within misclassification error $\alpha \cdot \opt_{\gamma} + \eps$, where $\opt_{\gamma}$ is the optimal $\gamma$-margin error rate and $\alpha \geq 1$ is the approximation ratio. We give learning algorithms and computational hardness results for this problem, for all values of the approximation ratio $\alpha \geq 1$, that are nearly-matching for a range of parameters. Specifically, for the natural setting that $\alpha$ is any constant bigger than one, we provide an essentially tight complexity characterization. On the positive side, we give an $\alpha = 1. 01$-approximate proper learner that uses $O(1/(\eps^2\gamma^2))$ samples (which is optimal) and runs in time $\poly(d/\eps) \cdot 2^{\tilde{O}(1/\gamma^2)}$. On the negative side, we show that {\em any} constant factor approximate proper learner has runtime $\poly(d/\eps) \cdot 2^{(1/\gamma)^{2-o(1)}}$, assuming the Exponential Time Hypothesis.

PDF Details

IJCAI Conference 2019 Conference Paper

The Price of Fairness for Indivisible Goods

  • Xiaohui Bei
  • Xinhang Lu
  • Pasin Manurangsi
  • Warut Suksompong

We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, these notions cannot always be satisfied for indivisible goods, leading to certain instances being ignored in the analysis. In this paper, we focus instead on notions with guaranteed existence, including envy-freeness up to one good (EF1), balancedness, maximum Nash welfare (MNW), and leximin. We mostly provide tight or asymptotically tight bounds on the worst-case efficiency loss for allocations satisfying these notions.

PDF Details

AAAI Conference 2019 Conference Paper

When Do Envy-Free Allocations Exist?

  • Pasin Manurangsi
  • Warut Suksompong

We consider a fair division setting in which m indivisible items are to be allocated among n agents, where the agents have additive utilities and the agents’ utilities for individual items are independently sampled from a distribution. Previous work has shown that an envy-free allocation is likely to exist when m = Ω(n log n) but not when m = n+o(n), and left open the question of determining where the phase transition from non-existence to existence occurs. We show that, surprisingly, there is in fact no universal point of transition— instead, the transition is governed by the divisibility relation between m and n. On the one hand, if m is divisible by n, an envy-free allocation exists with high probability as long as m ≥ 2n. On the other hand, if m is not “almost” divisible by n, an envy-free allocation is unlikely to exist even when m = Θ(n log n/ log log n).

PDF Details

STOC Conference 2018 Conference Paper

On the parameterized complexity of approximating dominating set

  • Karthik C. S. 0001
  • Bundit Laekhanukit
  • Pasin Manurangsi

We study the parameterized complexity of approximating the k -Dominating Set (domset) problem where an integer k and a graph G on n vertices are given as input, and the goal is to find a dominating set of size at most F ( k ) · k whenever the graph G has a dominating set of size k . When such an algorithm runs in time T ( k )poly( n ) (i.e., FPT-time) for some computable function T , it is said to be an F ( k )-FPT-approximation algorithm for k -domset. Whether such an algorithm exists is listed in the seminal book of Downey and Fellows (2013) as one of the ”most infamous” open problems in Parameterized Complexity. This work gives an almost complete answer to this question by showing the non-existence of such an algorithm under W[1]≠FPT and further providing tighter running time lower bounds under stronger hypotheses. Specifically, we prove the following for every computable functions T , F and every constant ε > 0: (i) Assuming W[1]≠FPT, there is no F ( k )-FPT-approximation algorithm for k -domset, (ii) Assuming the Exponential Time Hypothesis (ETH), there is no F ( k )-approximation algorithm for k -domset that runs in T ( k ) n o ( k ) time, (iii) Assuming the Strong Exponential Time Hypothesis (SETH), for every integer k ≥ 2, there is no F ( k )-approximation algorithm for k -domset that runs in T ( k ) n k − ε time, (iv) Assuming the k -sum Hypothesis, for every integer k ≥ 3, there is no F ( k )-approximation algorithm for k -domset that runs in T ( k ) n ⌈ k /2 ⌉ − ε time. Previously, only constant ratio FPT-approximation algorithms were ruled out under W[1]≠FPT and (log 1/4 − ε k )-FPT-approximation algorithms were ruled out under ETH [Chen and Lin, FOCS 2016]. Recently, the non-existence of an F ( k )-FPT-approximation algorithm for any function F was shown under gapETH [Chalermsook et al., FOCS 2017]. Note that, to the best of our knowledge, no running time lower bound of the form n δ k for any absolute constant δ > 0 was known before even for any constant factor inapproximation ratio. Our results are obtained by establishing a connection between communication complexity and hardness of approximation, generalizing the ideas from a recent breakthrough work of Abboud et al. [FOCS 2017]. Specifically, we show that to prove hardness of approximation of a certain parameterized variant of the label cover problem, it suffices to devise a specific protocol for a communication problem that depends on which hypothesis we rely on. Each of these communication problems turns out to be either a well studied problem or a variant of one; this allows us to easily apply known techniques to solve them.

Details

STOC Conference 2017 Conference Paper

Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph

  • Pasin Manurangsi

In the Densest k -Subgraph (D k S) problem, given an undirected graph G and an integer k , the goal is to find a subgraph of G on k vertices that contains maximum number of edges. Even though Bhaskara et al.'s state-of-the-art algorithm for the problem achieves only O ( n 1/4 + ϵ ) approximation ratio, previous attempts at proving hardness of approximation, including those under average case assumptions, fail to achieve a polynomial ratio; the best ratios ruled out under any worst case assumption and any average case assumption are only any constant (Raghavendra and Steurer) and 2 O(log 2/3 n ) (Alon et al.) respectively. In this work, we show, assuming the exponential time hypothesis (ETH), that there is no polynomial-time algorithm that approximates Densest k -Subgraph to within n 1/(loglog n ) c factor of the optimum, where c > 0 is a universal constant independent of n . In addition, our result has perfect completeness, meaning that we prove that it is ETH-hard to even distinguish between the case in which G contains a k -clique and the case in which every induced k -subgraph of G has density at most 1/ n -1/(loglog n ) c in polynomial time. Moreover, if we make a stronger assumption that there is some constant ε > 0 such that no subexponential-time algorithm can distinguish between a satisfiable 3SAT formula and one which is only (1 - ε)-satisfiable (also known as Gap-ETH), then the ratio above can be improved to n f ( n ) for any function f whose limit is zero as n goes to infinity (i.e. f ϵ o (1)).

Details

SODA Conference 2017 Conference Paper

Approximation Algorithms for Label Cover and The Log-Density Threshold

  • Eden Chlamtac
  • Pasin Manurangsi
  • Dana Moshkovitz
  • Aravindan Vijayaraghavan

Many known optimal NP-hardness of approximation results are reductions from a problem called Label Cover. The input is a bipartite graph G = ( L, R, E ) and each edge e = ( x, y ) ∊ E carries a projection π ∊ that maps labels to x to labels to y. The objective is to find a labeling of the vertices that satisfies as many of the projections as possible. It is believed that the best approximation ratio efficiently achievable for La bel -Co ver is of the form N −c where N = nk, n is the number of vertices, k is the number of labels, and 0 ≤ c < 1 is some constant. Inspired by a framework originally developed for Densest k -SuBGRAPH, we propose a “log density threshold” for the approximability of Label-Cover. Specifically, we suggest the possibility that the Label-Cover approximation problem undergoes a computational phase transition at the same threshold at which local algorithms for its random counterpart fail. This threshold is We then design, for any ∊ > 0, a polynomial-time approximation algorithm for semirandom Label-Cover whose approximation ratio is In our semi-random model, the input graph is random (or even just expanding), and the projections on the edges are arbitrary. For worst-case La bel -Co ver we show a polynomial- time algorithm whose approximation ratio is roughly Ν-°· 2 33. The previous best efficient approximation ratio was Ν −0 · 25. We present some evidence towards an Ν −c threshold by constructing integrality gaps for Ν ω(1) rounds of the Sum-of-squares/Lasserre hierarchy of the natural relaxation of Label Cover. For general 2CSP the “log density threshold” is Ν −0 · 25, and we give a polynomial-time algorithm in the semi-random model whose approximation ratio is Ν −0 · 25 + ∊ for any ∊ > 0.

Details

IJCAI Conference 2017 Conference Paper

Computing an Approximately Optimal Agreeable Set of Items

  • Pasin Manurangsi
  • Warut Suksompong

We study the problem of finding a small subset of items that is agreeable to all agents, meaning that all agents value the subset at least as much as its complement. Previous work has shown worst-case bounds, over all instances with a given number of agents and items, on the number of items that may need to be included in such a subset. Our goal in this paper is to efficiently compute an agreeable subset whose size approximates the size of the smallest agreeable subset for a given instance. We consider three well-known models for representing the preferences of the agents: ordinal preferences on single items, the value oracle model, and additive utilities. In each of these models, we establish virtually tight bounds on the approximation ratio that can be obtained by algorithms running in polynomial time.

PDF Details

FOCS Conference 2017 Conference Paper

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

  • Parinya Chalermsook
  • Marek Cygan
  • Guy Kortsarz
  • Bundit Laekhanukit
  • Pasin Manurangsi
  • Danupon Nanongkai
  • Luca Trevisan 0001

We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e. g. , [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = ω(1))? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i. e. , there is no o(OPT)-FPT-approximation algorithm for Clique and no f(OPT)-FPT-approximation algorithm for DomSet, for any function f (e. g. , this holds even if f is an exponential or the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (GapETH) [4], [5], which states that no 2 o(n) -time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - ε)-satisfiable for some constant ε > 0. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, the problem of finding maximum subgraphs with hereditary properties (e. g. , Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs. Previously only exact versions of these problems were known to be W[1]-hard [6], [7], [8]. Additionally, we rule out k o(1) -FPT-approximation algorithm for Densest k-Subgraph although this ratio does not yet match the trivial O(k)-approximation algorithm. To the best of our knowledge, prior results only rule out constant factor approximation for Clique [9], [10] and log 1/4+ε (OPT) approximation for DomSet for any constant ε > 0 [11]. Our result on Clique significantly improves on [9], [10]. However, our result on DomSet is incomparable to [11] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.

Details
v2026.09.13