Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing …
P Manurangsi - Proceedings of the Fourteenth Annual ACM-SIAM …, 2020 - SIAM
We show, assuming the (randomized) Gap Exponential Time Hypothesis (Gap-ETH), that
the following tasks cannot be done in T (k)· N o (k)-time for any function T where N denote …
the following tasks cannot be done in T (k)· N o (k)-time for any function T where N denote …
The strongish planted clique hypothesis and its consequences
We formulate a new hardness assumption, the Strongish Planted Clique Hypothesis
(SPCH), which postulates that any algorithm for planted clique must run in time $ n^{\Omega …
(SPCH), which postulates that any algorithm for planted clique must run in time $ n^{\Omega …
Parameterized complexity and approximability of directed odd cycle transversal
A directed odd cycle transversal of a directed graph (digraph) D is a vertex set S that
intersects every odd directed cycle of D. In the Directed Odd Cycle Transversal (DOCT) …
intersects every odd directed cycle of D. In the Directed Odd Cycle Transversal (DOCT) …
On closest pair in euclidean metric: Monochromatic is as hard as bichromatic
CS Karthik, P Manurangsi - Combinatorica, 2020 - Springer
Given a set of n points in ℝ d, the (monochromatic) Closest Pair problem asks to find a pair
of distinct points in the set that are closest in the ℓ p-metric. Closest Pair is a fundamental …
of distinct points in the set that are closest in the ℓ p-metric. Closest Pair is a fundamental …
Fine-grained hardness of CVP (P)—Everything that we can prove (and nothing else)
We show a number of fine-grained hardness results for the Closest Vector Problem in the ℓp
norm (CVP p), and its approximate and non-uniform variants. First, we show that CVP p …
norm (CVP p), and its approximate and non-uniform variants. First, we show that CVP p …
The complexity of adversarially robust proper learning of halfspaces with agnostic noise
I Diakonikolas, DM Kane… - Advances in Neural …, 2020 - proceedings.neurips.cc
We study the computational complexity of adversarially robust proper learning of halfspaces
in the distribution-independent agnostic PAC model, with a focus on $ L_p $ perturbations …
in the distribution-independent agnostic PAC model, with a focus on $ L_p $ perturbations …
Almost polynomial factor inapproximability for parameterized k-clique
CS Karthik, S Khot - 37th Computational Complexity Conference …, 2022 - drops.dagstuhl.de
The k-Clique problem is a canonical hard problem in parameterized complexity. In this
paper, we study the parameterized complexity of approximating the k-Clique problem where …
paper, we study the parameterized complexity of approximating the k-Clique problem where …
Parameterized Inapproximability of the Minimum Distance Problem over All Fields and the Shortest Vector Problem in All ℓp Norms
We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite
field and parameterized by the input distance bound is W [1]-hard to approximate within any …
field and parameterized by the input distance bound is W [1]-hard to approximate within any …
Eth-hardness of approximating 2-csps and directed steiner network
I Dinur, P Manurangsi - arXiv preprint arXiv:1805.03867, 2018 - arxiv.org
We study the 2-ary constraint satisfaction problems (2-CSPs), which can be stated as
follows: given a constraint graph $ G=(V, E) $, an alphabet set $\Sigma $ and, for each $\{u …
follows: given a constraint graph $ G=(V, E) $, an alphabet set $\Sigma $ and, for each $\{u …
Counting and finding homomorphisms is universal for parameterized complexity theory
M Roth, P Wellnitz - Proceedings of the Fourteenth Annual ACM-SIAM …, 2020 - SIAM
Counting homomorphisms from a graph H into another graph G is a fundamental problem of
(parameterized) counting complexity theory. In this work, we study the case where both …
(parameterized) counting complexity theory. In this work, we study the case where both …