Pasin Manurangsi

research

∙ 09/08/2023

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

We consider the question of approximating Max 2-CSP where each variable ...

0 Euiwoong Lee, et al. ∙

research

∙ 07/19/2023

A Note on Hardness of Computing Recursive Teaching Dimension

In this short note, we show that the problem of computing the recursive ...

0 Pasin Manurangsi, et al. ∙

research

∙ 03/04/2023

On Maximum Bipartite Matching with Separation

Maximum bipartite matching is a fundamental algorithmic problem which ca...

0 Pasin Manurangsi, et al. ∙

research

∙ 11/23/2022

Differentially Private Fair Division

Fairness and privacy are two important concerns in social decision-makin...

0 Pasin Manurangsi, et al. ∙

research

∙ 11/02/2022

Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique

We study the complexity of computing (and approximating) VC Dimension an...

0 Pasin Manurangsi, et al. ∙

research

∙ 07/28/2022

Cryptographic Hardness of Learning Halfspaces with Massart Noise

We study the complexity of PAC learning halfspaces in the presence of Ma...

0 Ilias Diakonikolas, et al. ∙

research

∙ 04/24/2022

Fixing Knockout Tournaments With Seeds

Knockout tournaments constitute a popular format for organizing sports c...

0 Pasin Manurangsi, et al. ∙

research

∙ 03/03/2022

Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems

We study several questions related to diversifying search results. We gi...

0 Amir Abboud, et al. ∙

research

∙ 12/11/2021

The Price of Justified Representation

In multiwinner approval voting, the goal is to select k-member committee...

0 Edith Elkind, et al. ∙

research

∙ 12/07/2021

Private Robust Estimation by Stabilizing Convex Relaxations

We give the first polynomial time and sample (ϵ, δ)-differentially priva...

0 Pravesh K. Kothari, et al. ∙

research

∙ 11/05/2021

Tight Bounds for Differentially Private Anonymized Histograms

In this note, we consider the problem of differentially privately (DP) c...

0 Pasin Manurangsi, et al. ∙

research

∙ 09/27/2021

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

The shuffle model of differential privacy has attracted attention in the...

0 Badih Ghazi, et al. ∙

research

∙ 08/30/2021

Justifying Groups in Multiwinner Approval Voting

Justified representation (JR) is a standard notion of representation in ...

0 Edith Elkind, et al. ∙

research

∙ 08/03/2021

Large-Scale Differentially Private BERT

In this work, we study the large-scale pretraining of BERT-Large with di...

26 Rohan Anil, et al. ∙

research

∙ 07/02/2021

Linear Discrepancy is Π_2-Hard to Approximate

In this note, we prove that the problem of computing the linear discrepa...

0 Pasin Manurangsi, et al. ∙

research

∙ 07/02/2021

Google COVID-19 Vaccination Search Insights: Anonymization Process Description

This report describes the aggregation and anonymization process applied ...

0 Shailesh Bavadekar, et al. ∙

research

∙ 06/13/2021

On the Complexity of Fair House Allocation

We study fairness in house allocation, where m houses are to be allocate...

0 Naoyuki Kamiyama, et al. ∙

research

∙ 06/09/2021

Contextual Recommendations and Low-Regret Cutting-Plane Algorithms

We consider the following variant of contextual linear bandits motivated...

0 Sreenivas Gollapudi, et al. ∙

research

∙ 06/08/2021

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

Differential privacy (DP) is a formal notion for quantifying the privacy...

0 Badih Ghazi, et al. ∙

research

∙ 05/04/2021

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

We study the allocation of indivisible goods among groups of agents usin...

0 Pasin Manurangsi, et al. ∙

research

∙ 05/01/2021

Generalized Kings and Single-Elimination Winners in Random Tournaments

Tournaments can be used to model a variety of practical scenarios includ...

0 Pasin Manurangsi, et al. ∙

research

∙ 04/20/2021

Locally Private k-Means in One Round

We provide an approximation algorithm for k-means clustering in the one-...

0 Alisa Chang, et al. ∙

research

∙ 02/11/2021

On Deep Learning with Label Differential Privacy

In many machine learning applications, the training data can contain hig...

0 Badih Ghazi, et al. ∙

research

∙ 12/16/2020

On Avoiding the Union Bound When Answering Multiple Differentially Private Queries

In this work, we study the problem of answering k queries with (ϵ, δ)-di...

0 Badih Ghazi, et al. ∙

research

∙ 12/07/2020

Sample-efficient proper PAC learning with approximate differential privacy

In this paper we prove that the sample complexity of properly learning a...

0 Badih Ghazi, et al. ∙

research

∙ 11/30/2020

Robust and Private Learning of Halfspaces

In this work, we study the trade-off between differential privacy and ad...

0 Badih Ghazi, et al. ∙

research

∙ 11/27/2020

Tight Hardness Results for Training Depth-2 ReLU Networks

We prove several hardness results for training depth-2 neural networks w...

0 Surbhi Goel, et al. ∙

research

∙ 11/16/2020

To Close Is Easier Than To Open: Dual Parameterization To k-Median

The k-Median problem is one of the well-known optimization problems that...

0 Jaroslaw Byrka, et al. ∙

research

∙ 11/11/2020

The Strongish Planted Clique Hypothesis and Its Consequences

We formulate a new hardness assumption, the Strongish Planted Clique Hyp...

0 Pasin Manurangsi, et al. ∙

research

∙ 09/21/2020

On Distributed Differential Privacy and Counting Distinct Elements

We study the setup where each of n users holds an element from a discret...

5 Lijie Chen, et al. ∙

research

∙ 08/28/2020

Algorithmic Persuasion with Evidence

We consider a game of persuasion with evidence between a sender and a re...

0 Martin Hoefer, et al. ∙

research

∙ 08/18/2020

Differentially Private Clustering: Tight Approximation Ratios

We study the task of differentially private clustering. For several basi...

1 Badih Ghazi, et al. ∙

research

∙ 07/30/2020

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

We study the computational complexity of adversarially robust proper lea...

1 Ilias Diakonikolas, et al. ∙

research

∙ 07/14/2020

Consensus Halving for Sets of Items

Consensus halving refers to the problem of dividing a resource into two ...

0 Paul W. Goldberg, et al. ∙

research

∙ 07/07/2020

Near-tight closure bounds for Littlestone and threshold dimensions

We study closure properties for the Littlestone and threshold dimensions...

0 Badih Ghazi, et al. ∙

research

∙ 06/08/2020

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

Parameterization and approximation are two popular ways of coping with N...

0 Andreas Emil Feldmann, et al. ∙

research

∙ 04/12/2020

Closing Gaps in Asymptotic Fair Division

We study a resource allocation setting where m discrete items are to be ...

0 Pasin Manurangsi, et al. ∙

research

∙ 02/05/2020

Pure Differentially Private Summation from Anonymous Messages

The shuffled (aka anonymous) model has recently generated significant in...

0 Badih Ghazi, et al. ∙

research

∙ 10/25/2019

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

We show, assuming the (randomized) Gap Exponential Time Hypothesis (Gap-...

0 Pasin Manurangsi, et al. ∙

research

∙ 09/24/2019

Private Aggregation from Fewer Anonymous Messages

Consider the setup where n parties are each given a number x_i ∈F_q and ...

0 Badih Ghazi, et al. ∙

research

∙ 09/04/2019

Parameterized Intractability of Even Set and Shortest Vector Problem

The k-Even Set problem is a parameterized variant of the Minimum Distanc...

0 Arnab Bhattacharyya, et al. ∙

research

∙ 08/29/2019

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

We study the problem of properly learning large margin halfspaces in th...

7 Ilias Diakonikolas, et al. ∙

research

∙ 08/28/2019

Approximation and Hardness of Shift-Bribery

In the Shift-Bribery problem we are given an election, a preferred candi...

0 Piotr Faliszewski, et al. ∙

research

∙ 05/13/2019

The Price of Fairness for Indivisible Goods

We investigate the efficiency of fair allocations of indivisible goods u...

0 Xiaohui Bei, et al. ∙

research

∙ 12/03/2018

On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

Given a set of n points in R^d, the (monochromatic) Closest Pair proble...

0 Karthik C. S., et al. ∙

research

∙ 11/05/2018

When Do Envy-Free Allocations Exist?

We consider a fair division setting in which m indivisible items are to ...

0 Pasin Manurangsi, et al. ∙

research

∙ 10/09/2018

The Computational Complexity of Training ReLU(s)

We consider the computational complexity of training depth-2 neural netw...

0 Pasin Manurangsi, et al. ∙

research

∙ 10/09/2018

A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation

In Maximum k-Vertex Cover (Max k-VC), the input is an edge-weighted grap...

0 Pasin Manurangsi, et al. ∙

research

∙ 09/08/2018

Multitasking Capacity: Hardness Results and Improved Constructions

We consider the problem of determining the maximal α∈ (0,1] such that ev...

0 Noga Alon, et al. ∙

research

∙ 07/25/2018

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems

In this work, we study the trade-off between the running time of approxi...

0 Pasin Manurangsi, et al. ∙

Pasin Manurangsi

Featured Co-authors