
-
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
-
Sample-efficient 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 trade-off between differential privacy and ad...
read it
-
Tight Hardness Results for Training Depth-2 ReLU Networks
We prove several hardness results for training depth-2 neural networks w...
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...
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
-
Near-tight 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 k-Coverage, Unique Set Cover and Related Problems (via t-Wise 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 k-Even 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 Shift-Bribery
In the Shift-Bribery 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 Envy-Free 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 depth-2 neural netw...
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...
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 trade-off between the running time of approxi...
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...
read it
-
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
We study the 2-ary constraint satisfaction problems (2-CSPs), which can ...
read it
-
Sherali-Adams Integrality Gaps Matching the Log-Density Threshold
The log-density 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 Gap-ETH
The k-Even 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 k-Dominating ...
read it
-
From Gap-ETH to FPT-Inapproximability: 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 edge-weighted directed graph G=...
read it