39 citations · 308 across the 129 of their papers we have counts for
6 papers · 1 filter
Tight Running Time Lower Bounds for Strong Inapproximability of Maximum -Coverage, Unique Set Cover and Related Problems (via -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 -time for any function where d…
Private Aggregation from Fewer Anonymous Messages
Badih Ghazi, Pasin Manurangsi, Rasmus Pagh +1
Consider the setup where parties are each given a number and the goal is to compute the sum in a secure fashion and with as little communica…
Parameterized Intractability of Even Set and Shortest Vector Problem
Arnab Bhattacharyya, Édouard Bonnet, László Egri +5
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix $\m…
Nearly Tight Bounds for Robust Proper Learning of Halfspaces with a Margin
Ilias Diakonikolas, Daniel M. 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 -dimensional half…
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 fi…
The Price of Fairness for Indivisible Goods
Xiaohui Bei, Xinhang Lu, Pasin Manurangsi +1
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 suc…