39 citations · 308 across the 129 of their papers we have counts for
11 papers · 1 filter
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
Karthik C. S., Pasin Manurangsi
Given a set of points in , the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the -metric. Clos…
When Do Envy-Free Allocations Exist?
Pasin Manurangsi, Warut Suksompong
We consider a fair division setting in which indivisible items are to be allocated among agents, where the agents have additive utilities and the agents' utilities for indi…
The Computational Complexity of Training ReLU(s)
Pasin Manurangsi, Daniel Reichman
We consider the computational complexity of training depth-2 neural networks composed of rectified linear units (ReLUs). We show that, even for the case of a single ReLU, finding a…
A Note on Max -Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation
Pasin Manurangsi
In Maximum -Vertex Cover (Max -VC), the input is an edge-weighted graph and an integer , and the goal is to find a subset of vertices that maximizes the total…
Multitasking Capacity: Hardness Results and Improved Constructions
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths +5
We consider the problem of determining the maximal such that every matching of size (or at most ) in a bipartite graph contains an induced matching of s…
Mildly Exponential Time Approximation Algorithms for Vertex Cover, Uniform Sparsest Cut and Related Problems
Pasin Manurangsi, Luca Trevisan
In this work, we study the trade-off between the running time of approximation algorithms and their approximation guarantees. By leveraging a structure of the `hard' instances of t…
A Note on Degree vs Gap of Min-Rep Label Cover and Improved Inapproximability for Connectivity Problems
Pasin Manurangsi
This note concerns the trade-off between the degree of the constraint graph and the gap in hardness of approximating the Min-Rep variant of Label Cover (aka Projection Game). We ma…
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
Irit Dinur, Pasin Manurangsi
We study the 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph , an alphabet set and, for each ,…
Sherali-Adams Integrality Gaps Matching the Log-Density Threshold
Eden Chlamtáč, Pasin Manurangsi
The log-density method is a powerful algorithmic framework which in recent years has given rise to the best-known approximations for a variety of problems, including Densest--Su…
Losing Treewidth by Separating Subsets
Anupam Gupta, Euiwoong Lee, Jason Li +2
We study the problem of deleting the smallest set of vertices (resp. edges) from a given graph such that the induced subgraph (resp. subgraph) belongs to so…
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S. +1
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…