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 ...
share
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 ...
research
∙
03/04/2023
On Maximum Bipartite Matching with Separation
Maximum bipartite matching is a fundamental algorithmic problem which ca...
research
∙
11/23/2022
Differentially Private Fair Division
Fairness and privacy are two important concerns in social decision-makin...
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...
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...
research
∙
04/24/2022
Fixing Knockout Tournaments With Seeds
Knockout tournaments constitute a popular format for organizing sports c...
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...
research
∙
12/11/2021
The Price of Justified Representation
In multiwinner approval voting, the goal is to select k-member committee...
research
∙
12/07/2021
Private Robust Estimation by Stabilizing Convex Relaxations
We give the first polynomial time and sample (ϵ, δ)-differentially priva...
research
∙
11/05/2021
Tight Bounds for Differentially Private Anonymized Histograms
In this note, we consider the problem of differentially privately (DP) c...
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...
research
∙
08/30/2021
Justifying Groups in Multiwinner Approval Voting
Justified representation (JR) is a standard notion of representation in ...
research
∙
08/03/2021
Large-Scale Differentially Private BERT
In this work, we study the large-scale pretraining of BERT-Large with di...
research
∙
07/02/2021
Linear Discrepancy is Π_2-Hard to Approximate
In this note, we prove that the problem of computing the linear discrepa...
research
∙
07/02/2021
Google COVID-19 Vaccination Search Insights: Anonymization Process Description
This report describes the aggregation and anonymization process applied ...
research
∙
06/13/2021
On the Complexity of Fair House Allocation
We study fairness in house allocation, where m houses are to be allocate...
research
∙
06/09/2021
Contextual Recommendations and Low-Regret Cutting-Plane Algorithms
We consider the following variant of contextual linear bandits motivated...
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...
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...
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...
research
∙
04/20/2021
Locally Private k-Means in One Round
We provide an approximation algorithm for k-means clustering in the one-...
research
∙
02/11/2021
On Deep Learning with Label Differential Privacy
In many machine learning applications, the training data can contain hig...
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...
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...
research
∙
11/30/2020
Robust and Private Learning of Halfspaces
In this work, we study the trade-off between differential privacy and ad...
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...
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...
research
∙
11/11/2020
The Strongish Planted Clique Hypothesis and Its Consequences
We formulate a new hardness assumption, the Strongish Planted Clique Hyp...
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...
research
∙
08/28/2020
Algorithmic Persuasion with Evidence
We consider a game of persuasion with evidence between a sender and a re...
research
∙
08/18/2020
Differentially Private Clustering: Tight Approximation Ratios
We study the task of differentially private clustering. For several basi...
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...
research
∙
07/14/2020
Consensus Halving for Sets of Items
Consensus halving refers to the problem of dividing a resource into two ...
research
∙
07/07/2020
Near-tight closure bounds for Littlestone and threshold dimensions
We study closure properties for the Littlestone and threshold dimensions...
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...
research
∙
04/12/2020
Closing Gaps in Asymptotic Fair Division
We study a resource allocation setting where m discrete items are to be ...
research
∙
02/05/2020
Pure Differentially Private Summation from Anonymous Messages
The shuffled (aka anonymous) model has recently generated significant in...
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-...
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 ...
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...
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...
research
∙
08/28/2019
Approximation and Hardness of Shift-Bribery
In the Shift-Bribery problem we are given an election, a preferred candi...
research
∙
05/13/2019
The Price of Fairness for Indivisible Goods
We investigate the efficiency of fair allocations of indivisible goods u...
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...
research
∙
11/05/2018
When Do Envy-Free Allocations Exist?
We consider a fair division setting in which m indivisible items are to ...
research
∙
10/09/2018
The Computational Complexity of Training ReLU(s)
We consider the computational complexity of training depth-2 neural netw...
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...
research
∙
09/08/2018
Multitasking Capacity: Hardness Results and Improved Constructions
We consider the problem of determining the maximal α∈ (0,1] such that ev...
research
∙
07/25/2018