39 citations · 308 across the 129 of their papers we have counts for
15 papers · 1 filter
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries
Badih Ghazi, Ravi Kumar, Pasin Manurangsi
In this work, we study the problem of answering queries with -differential privacy, where each query has sensitivity one. We give an algorithm for this task that achiev…
Sample-efficient proper PAC learning with approximate differential privacy
Badih Ghazi, Noah Golowich, Ravi Kumar +1
In this paper we prove that the sample complexity of properly learning a class of Littlestone dimension with approximate differential privacy is , ignoring priva…
Tight Hardness Results for Training Depth-2 ReLU Networks
Surbhi Goel, Adam Klivans, Pasin Manurangsi +1
We prove several hardness results for training depth-2 neural networks with the ReLU activation function; these networks are simply weighted sums (that may include negative coeffic…
To Close Is Easier Than To Open: Dual Parameterization To k-Median
Jarosław Byrka, Szymon Dudycz, Pasin Manurangsi +2
The -Median problem is one of the well-known optimization problems that formalize the task of data clustering. Here, we are given sets of facilities and clients , and the…
The Strongish Planted Clique Hypothesis and Its Consequences
Pasin Manurangsi, Aviad Rubinstein, Tselil Schramm
We formulate a new hardness assumption, the Strongish Planted Clique Hypothesis (SPCH), which postulates that any algorithm for planted clique must run in time (so…
Robust and Private Learning of Halfspaces
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
In this work, we study the trade-off between differential privacy and adversarial robustness under L2-perturbations in the context of learning halfspaces. We prove nearly tight bou…
On Distributed Differential Privacy and Counting Distinct Elements
Lijie Chen, Badih Ghazi, Ravi Kumar +1
We study the setup where each of users holds an element from a discrete set, and the goal is to count the number of distinct elements across all users, under the constraint of…
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…
Algorithmic Persuasion with Evidence
Martin Hoefer, Pasin Manurangsi, Alexandros Psomas
In a game of persuasion with evidence, a sender has private information. By presenting evidence on the information, the sender wishes to persuade a receiver to take a single action…
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 perturbations.…
Consensus Halving for Sets of Items
Paul W. Goldberg, Alexandros Hollender, Ayumi Igarashi +2
Consensus halving refers to the problem of dividing a resource into two parts so that every agent values both parts equally. Prior work has shown that when the resource is represen…
Near-tight closure bounds for Littlestone and threshold dimensions
Badih Ghazi, Noah Golowich, Ravi Kumar +1
We study closure properties for the Littlestone and threshold dimensions of binary hypothesis classes. Given classes of Boolean functions wit…
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee +1
Parameterization and approximation are two popular ways of coping with NP-hard problems. More recently, the two have also been combined to derive many interesting results. We surve…
Closing Gaps in Asymptotic Fair Division
Pasin Manurangsi, Warut Suksompong
We study a resource allocation setting where discrete items are to be divided among agents with additive utilities, and the agents' utilities for individual items are drawn…
Pure Differentially Private Summation from Anonymous Messages
Badih Ghazi, Noah Golowich, Ravi Kumar +3
The shuffled (aka anonymous) model has recently generated significant interest as a candidate distributed privacy framework with trust assumptions better than the central model but…