We study the parameterized complexity of training two-layer neural networks with respect to the dimension of the input data and the number of hidden neurons, considering ReLU and linear threshold activation functions. Albeit the computational complexity of these problems has been studied numerous times in recent years, several questions are still open. We answer questions by Arora et al. (ICLR 2018) and Khalife and Basu (IPCO 2022) showing that both problems are NP-hard for two dimensions, which excludes any polynomial-time algorithm for constant dimension. We also answer a question by Froese et al. (JAIR 2022) proving W[1]-hardness for four ReLUs (or two linear threshold neurons) with zero training error. Finally, in the ReLU case, we show fixed-parameter tractability for the combined parameter number of dimensions and number of ReLUs if the network is assumed to compute a convex map. Our results settle the complexity status regarding these parameters almost completely.

In barter exchanges, participants swap goods with one another without exchanging money; these exchanges are often facilitated by a central clearinghouse, with the goal of maximizing the aggregate quality (or number) of swaps. Barter exchanges are subject to many forms of uncertainty--in participant preferences, the feasibility and quality of various swaps, and so on. Our work is motivated by kidney exchange, a real-world barter market in which patients in need of a kidney transplant swap their willing living donors, in order to find a better match. Modern exchanges include 2-and 3-way swaps, making the kidney exchange clearing problem NP-hard. Planned transplants often \emph{fail} for a variety of reasons--if the donor organ is rejected by the recipient's medical team, or if the donor and recipient are found to be medically incompatible.

Clustering is a challenging task particularly due to two impediments. The first problem is that clustering, in the absence of domain knowledge, is usually an under-specified task; the solution of choice may vary significantly between different intended applications.

Recent work [Ma et al., 2019] shows that in the non-convex case, sampling

First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. The paper studies the problem of finding a small subset S* of the a set S of labelled points such that the 1-Nearest Neighbour classifier is consistent with S. The motivation is to speed-up 1NN classification of new points. The problem of finding a minimal set S* is known to be NP-hard, so the paper is concerned with approximations. Apparently all the previous results on the problems concerned heuristics. The present papers presents an algorithm whose approximation is shown to be optimal, in the sense that doing significantly better is NP-hard.

Recent work [Ma et al., 2019] shows that in the non-convex case, sampling