Parameterization and approximation are two popular ways of coping with NP-hard
problems. More recently, the two have also been combined to derive many interesting …

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 …

Over the past decade, many results have focused on the design of parameterized
approximation algorithms for W [1]-hard problems. However, there are fundamental …

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 …

We study the parameterized problem of satisfying “almost all” constraints of a given formula
F over a fixed, finite Boolean constraint language Γ, with or without weights. More precisely …

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 …

We present a new technique for designing fixed-parameter algorithms for graph cut
problems in undirected graphs, which we call flow augmentation. Our technique is …

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 …

Computational problems on point lattices play a central role in many areas of computer
science including integer programming, coding theory, cryptanalysis, and especially the …

We survey recent results on the broad family of problems that can be cast as valued
constraint satisfaction problems (VCSPs). We discuss general methods for analysing the …