Will Rosenbaum

Duncan Adamson, Will Rosenbaum, Paul G. Spirakis

In the last decade, subgraph detection and enumeration have emerged as central problems in distributed graph algorithms. This is largely due to the problems' theoretical challenges and practical applications. In this paper, we initiate the systematic study of distributed sub-hypergraph enumeration in hypergraphs. To this end, we (1) introduce several computational models for hypergraphs that generalize the CONGEST model for graphs and evaluate their relative computational power, (2) devise algorithms for distributed triangle and simplex enumeration in our computational models and prove their optimality in two such models by showing matching lower bounds, (3) introduce classes of sparse and "everywhere sparse" hypergraphs and describe efficient distributed algorithms for triangle and simplex enumeration in these classes, and (4) describe general techniques that we believe to be useful for designing efficient algorithms in our hypergraph models.

Ara Vartanian, Will Rosenbaum, Scott Alfeld

Nearest neighbor-based methods are commonly used for classification tasks and as subroutines of other data-analysis methods. An attacker with the capability of inserting their own data points into the training set can manipulate the inferred nearest neighbor structure. We distill this goal to the task of performing a training-set data insertion attack against $k$-Nearest Neighbor classification ($k$NN). We prove that computing an optimal training-time (a.k.a. poisoning) attack against $k$NN classification is NP-Hard, even when $k = 1$ and the attacker can insert only a single data point. We provide an anytime algorithm to perform such an attack, and a greedy algorithm for general $k$ and attacker budget. We provide theoretical bounds and empirically demonstrate the effectiveness and practicality of our methods on synthetic and real-world datasets. Empirically, we find that $k$NN is vulnerable in practice and that dimensionality reduction is an effective defense. We conclude with a discussion of open problems illuminated by our analysis.

Christine T. Cheng, Will Rosenbaum

In the Stable Roommates Problem (SR), a set of $2n$ agents rank one another in a linear order. The goal is to find a matching that is stable, one that has no pair of agents who mutually prefer each other over their assigned partners. We consider the problem of finding an {\it optimal} stable matching. Agents associate weights with each of their potential partners, and the goal is to find a stable matching that minimizes the sum of the associated weights. Efficient algorithms exist for finding optimal stable marriages in the Stable Marriage Problem (SM), but the problem is NP-hard for general SR instances. In this paper, we define a notion of structural distance between SR instances and SM instances, which we call the \emph{minimum crossing distance}. When an SR instance has minimum crossing distance $0$, the instance is structurally equivalent to an SM instance, and this structure can be exploited to find optimal stable matchings efficiently. More generally, we show that for an SR instance with minimum crossing distance $k$, optimal stable matchings can be computed in time $2^{O(k)} n^{O(1)}$. Thus, the optimal stable matching problem is fixed parameter tractable (FPT) with respect to minimum crossing distance.