
Linear Discrepancy is Π_2Hard to Approximate
In this note, we prove that the problem of computing the linear discrepa...
read it

Google COVID19 Vaccination Search Insights: Anonymization Process Description
This report describes the aggregation and anonymization process applied ...
read it

On the Complexity of Fair House Allocation
We study fairness in house allocation, where m houses are to be allocate...
read it

Contextual Recommendations and LowRegret CuttingPlane Algorithms
We consider the following variant of contextual linear bandits motivated...
read it

Private Counting from Anonymous Messages: NearOptimal Accuracy with Vanishing Communication Overhead
Differential privacy (DP) is a formal notion for quantifying the privacy...
read it

Almost EnvyFreeness for Groups: Improved Bounds via Discrepancy Theory
We study the allocation of indivisible goods among groups of agents usin...
read it

Generalized Kings and SingleElimination Winners in Random Tournaments
Tournaments can be used to model a variety of practical scenarios includ...
read it

Locally Private kMeans in One Round
We provide an approximation algorithm for kmeans clustering in the one...
read it

On Deep Learning with Label Differential Privacy
In many machine learning applications, the training data can contain hig...
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...
read it

Sampleefficient proper PAC learning with approximate differential privacy
In this paper we prove that the sample complexity of properly learning a...
read it

Robust and Private Learning of Halfspaces
In this work, we study the tradeoff between differential privacy and ad...
read it

Tight Hardness Results for Training Depth2 ReLU Networks
We prove several hardness results for training depth2 neural networks w...
read it

To Close Is Easier Than To Open: Dual Parameterization To kMedian
The kMedian problem is one of the wellknown optimization problems that...
read it

The Strongish Planted Clique Hypothesis and Its Consequences
We formulate a new hardness assumption, the Strongish Planted Clique Hyp...
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...
read it

Algorithmic Persuasion with Evidence
We consider a game of persuasion with evidence between a sender and a re...
read it

Differentially Private Clustering: Tight Approximation Ratios
We study the task of differentially private clustering. For several basi...
read it

The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise
We study the computational complexity of adversarially robust proper lea...
read it

Consensus Halving for Sets of Items
Consensus halving refers to the problem of dividing a resource into two ...
read it

Neartight closure bounds for Littlestone and threshold dimensions
We study closure properties for the Littlestone and threshold dimensions...
read it

A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
Parameterization and approximation are two popular ways of coping with N...
read it

Closing Gaps in Asymptotic Fair Division
We study a resource allocation setting where m discrete items are to be ...
read it

Pure Differentially Private Summation from Anonymous Messages
The shuffled (aka anonymous) model has recently generated significant in...
read it

Tight Running Time Lower Bounds for Strong Inapproximability of Maximum kCoverage, Unique Set Cover and Related Problems (via tWise Agreement Testing Theorem)
We show, assuming the (randomized) Gap Exponential Time Hypothesis (Gap...
read it

Private Aggregation from Fewer Anonymous Messages
Consider the setup where n parties are each given a number x_i ∈F_q and ...
read it

Parameterized Intractability of Even Set and Shortest Vector Problem
The kEven Set problem is a parameterized variant of the Minimum Distanc...
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...
read it

Approximation and Hardness of ShiftBribery
In the ShiftBribery problem we are given an election, a preferred candi...
read it

The Price of Fairness for Indivisible Goods
We investigate the efficiency of fair allocations of indivisible goods u...
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...
read it

When Do EnvyFree Allocations Exist?
We consider a fair division setting in which m indivisible items are to ...
read it

The Computational Complexity of Training ReLU(s)
We consider the computational complexity of training depth2 neural netw...
read it

A Note on Max kVertex Cover: Faster FPTAS, Smaller Approximate Kernel and Improved Approximation
In Maximum kVertex Cover (Max kVC), the input is an edgeweighted grap...
read it

Multitasking Capacity: Hardness Results and Improved Constructions
We consider the problem of determining the maximal α∈ (0,1] such that ev...
read it

Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems
In this work, we study the tradeoff between the running time of approxi...
read it

A Note on Degree vs Gap of MinRep Label Cover and Improved Inapproximability for Connectivity Problems
This note concerns the tradeoff between the degree of the constraint gr...
read it

ETHHardness of Approximating 2CSPs and Directed Steiner Network
We study the 2ary constraint satisfaction problems (2CSPs), which can ...
read it

SheraliAdams Integrality Gaps Matching the LogDensity Threshold
The logdensity method is a powerful algorithmic framework which in rece...
read it

Losing Treewidth by Separating Subsets
We study the problem of deleting the smallest set S of vertices (resp.ed...
read it

Parameterized Intractability of Even Set and Shortest Vector Problem from GapETH
The kEven Set problem is a parameterized variant of the Minimum Distanc...
read it

On the Parameterized Complexity of Approximating Dominating Set
We study the parameterized complexity of approximating the kDominating ...
read it

From GapETH to FPTInapproximability: Clique, Dominating Set, and More
We consider questions that arise from the intersection between the areas...
read it

Parameterized Approximation Algorithms for Directed Steiner Network Problems
(See paper for full abstract) Given an edgeweighted directed graph G=...
read it
Pasin Manurangsi
is this you? claim profile