Pasin Manurangsi

Linear Discrepancy is Π_2-Hard to Approximate

In this note, we prove that the problem of computing the linear discrepa...
07/02/2021 ∙ by Pasin Manurangsi, et al. ∙ 0 ∙ share

read it
Google COVID-19 Vaccination Search Insights: Anonymization Process Description

This report describes the aggregation and anonymization process applied ...
07/02/2021 ∙ by Shailesh Bavadekar, et al. ∙ 0 ∙ share

read it
On the Complexity of Fair House Allocation

We study fairness in house allocation, where m houses are to be allocate...
06/13/2021 ∙ by Naoyuki Kamiyama, et al. ∙ 0 ∙ share

read it
Contextual Recommendations and Low-Regret Cutting-Plane Algorithms

We consider the following variant of contextual linear bandits motivated...
06/09/2021 ∙ by Sreenivas Gollapudi, et al. ∙ 0 ∙ share

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

Differential privacy (DP) is a formal notion for quantifying the privacy...
06/08/2021 ∙ by Badih Ghazi, et al. ∙ 0 ∙ share

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

We study the allocation of indivisible goods among groups of agents usin...
05/04/2021 ∙ by Pasin Manurangsi, et al. ∙ 0 ∙ share

read it
Generalized Kings and Single-Elimination Winners in Random Tournaments

Tournaments can be used to model a variety of practical scenarios includ...
05/01/2021 ∙ by Pasin Manurangsi, et al. ∙ 0 ∙ share

read it
Locally Private k-Means in One Round

We provide an approximation algorithm for k-means clustering in the one-...
04/20/2021 ∙ by Alisa Chang, et al. ∙ 0 ∙ share

read it
On Deep Learning with Label Differential Privacy

In many machine learning applications, the training data can contain hig...
02/11/2021 ∙ by Badih Ghazi, et al. ∙ 0 ∙ share

read it
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries

In this work, we study the problem of answering k queries with (ϵ, δ)-di...
12/16/2020 ∙ by Badih Ghazi, et al. ∙ 0 ∙ share

read it
Sample-efficient proper PAC learning with approximate differential privacy

In this paper we prove that the sample complexity of properly learning a...
12/07/2020 ∙ by Badih Ghazi, et al. ∙ 0 ∙ share

read it
Robust and Private Learning of Halfspaces

In this work, we study the trade-off between differential privacy and ad...
11/30/2020 ∙ by Badih Ghazi, et al. ∙ 0 ∙ share

read it
Tight Hardness Results for Training Depth-2 ReLU Networks

We prove several hardness results for training depth-2 neural networks w...
11/27/2020 ∙ by Surbhi Goel, et al. ∙ 0 ∙ share

read it
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...
11/16/2020 ∙ by Jaroslaw Byrka, et al. ∙ 0 ∙ share

read it
The Strongish Planted Clique Hypothesis and Its Consequences

We formulate a new hardness assumption, the Strongish Planted Clique Hyp...
11/11/2020 ∙ by Pasin Manurangsi, et al. ∙ 0 ∙ share

read it
On Distributed Differential Privacy and Counting Distinct Elements

We study the setup where each of n users holds an element from a discret...
09/21/2020 ∙ by Lijie Chen, et al. ∙ 5 ∙ share

read it
Algorithmic Persuasion with Evidence

We consider a game of persuasion with evidence between a sender and a re...
08/28/2020 ∙ by Martin Hoefer, et al. ∙ 0 ∙ share

read it
Differentially Private Clustering: Tight Approximation Ratios

We study the task of differentially private clustering. For several basi...
08/18/2020 ∙ by Badih Ghazi, et al. ∙ 1 ∙ share

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

We study the computational complexity of adversarially robust proper lea...
07/30/2020 ∙ by Ilias Diakonikolas, et al. ∙ 1 ∙ share

read it
Consensus Halving for Sets of Items

Consensus halving refers to the problem of dividing a resource into two ...
07/14/2020 ∙ by Paul W. Goldberg, et al. ∙ 0 ∙ share

read it
Near-tight closure bounds for Littlestone and threshold dimensions

We study closure properties for the Littlestone and threshold dimensions...
07/07/2020 ∙ by Badih Ghazi, et al. ∙ 0 ∙ share

read it
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms

Parameterization and approximation are two popular ways of coping with N...
06/08/2020 ∙ by Andreas Emil Feldmann, et al. ∙ 0 ∙ share

read it
Closing Gaps in Asymptotic Fair Division

We study a resource allocation setting where m discrete items are to be ...
04/12/2020 ∙ by Pasin Manurangsi, et al. ∙ 0 ∙ share

read it
Pure Differentially Private Summation from Anonymous Messages

The shuffled (aka anonymous) model has recently generated significant in...
02/05/2020 ∙ by Badih Ghazi, et al. ∙ 0 ∙ share

read it
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-...
10/25/2019 ∙ by Pasin Manurangsi, et al. ∙ 0 ∙ share

read it
Private Aggregation from Fewer Anonymous Messages

Consider the setup where n parties are each given a number x_i ∈F_q and ...
09/24/2019 ∙ by Badih Ghazi, et al. ∙ 0 ∙ share

read it
Parameterized Intractability of Even Set and Shortest Vector Problem

The k-Even Set problem is a parameterized variant of the Minimum Distanc...
09/04/2019 ∙ by Arnab Bhattacharyya, et al. ∙ 0 ∙ share

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

We study the problem of properly learning large margin halfspaces in th...
08/29/2019 ∙ by Ilias Diakonikolas, et al. ∙ 7 ∙ share

read it
Approximation and Hardness of Shift-Bribery

In the Shift-Bribery problem we are given an election, a preferred candi...
08/28/2019 ∙ by Piotr Faliszewski, et al. ∙ 0 ∙ share

read it
The Price of Fairness for Indivisible Goods

We investigate the efficiency of fair allocations of indivisible goods u...
05/13/2019 ∙ by Xiaohui Bei, et al. ∙ 0 ∙ share

read it
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...
12/03/2018 ∙ by Karthik C. S., et al. ∙ 0 ∙ share

read it
When Do Envy-Free Allocations Exist?

We consider a fair division setting in which m indivisible items are to ...
11/05/2018 ∙ by Pasin Manurangsi, et al. ∙ 0 ∙ share

read it
The Computational Complexity of Training ReLU(s)

We consider the computational complexity of training depth-2 neural netw...
10/09/2018 ∙ by Pasin Manurangsi, et al. ∙ 0 ∙ share

read it
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...
10/09/2018 ∙ by Pasin Manurangsi, et al. ∙ 0 ∙ share

read it
Multitasking Capacity: Hardness Results and Improved Constructions

We consider the problem of determining the maximal α∈ (0,1] such that ev...
09/08/2018 ∙ by Noga Alon, et al. ∙ 0 ∙ share

read it
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...
07/25/2018 ∙ by Pasin Manurangsi, et al. ∙ 0 ∙ share

read it
A Note on Degree vs Gap of Min-Rep Label Cover and Improved Inapproximability for Connectivity Problems

This note concerns the trade-off between the degree of the constraint gr...
07/03/2018 ∙ by Pasin Manurangsi, et al. ∙ 0 ∙ share

read it
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network

We study the 2-ary constraint satisfaction problems (2-CSPs), which can ...
05/10/2018 ∙ by Irit Dinur, et al. ∙ 0 ∙ share

read it
Sherali-Adams Integrality Gaps Matching the Log-Density Threshold

The log-density method is a powerful algorithmic framework which in rece...
04/20/2018 ∙ by Eden Chlamtáč, et al. ∙ 0 ∙ share

read it
Losing Treewidth by Separating Subsets

We study the problem of deleting the smallest set S of vertices (resp.ed...
04/04/2018 ∙ by Anupam Gupta, et al. ∙ 0 ∙ share

read it
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH

The k-Even Set problem is a parameterized variant of the Minimum Distanc...
03/26/2018 ∙ by Arnab Bhattacharyya, et al. ∙ 0 ∙ share

read it
On the Parameterized Complexity of Approximating Dominating Set

We study the parameterized complexity of approximating the k-Dominating ...
11/29/2017 ∙ by Karthik C. S., et al. ∙ 0 ∙ share

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

We consider questions that arise from the intersection between the areas...
08/14/2017 ∙ by Parinya Chalermsook, et al. ∙ 0 ∙ share

read it
Parameterized Approximation Algorithms for Directed Steiner Network Problems

(See paper for full abstract) Given an edge-weighted directed graph G=...
07/20/2017 ∙ by Rajesh Chitnis, et al. ∙ 0 ∙ share

read it

Pasin Manurangsi

Featured Co-authors