In their seminal work on the Stable Marriage Problem (SM), Gale and Shapley introduced a generalization of SM referred to as the Stable Roommates Problem (SR). An instance of SR consists of a set of 2n agents, and each agent has preferences in the form of a ranked list of all other agents. The goal is to find a one-to-one matching between the agents that is stable in the sense that no pair of agents have a mutual incentive to deviate from the matching. Unlike the (bipartite) stable marriage problem, in SR, stable matchings need not exist. Irving devised an algorithm that finds a stable matching or reports that none exists in O(n²) time. In their influential 1989 text, Gusfield and Irving posed the question of whether Ω(n²) time is required for SR solvability - the task of deciding if an SR instance admits a stable matching. In this paper, we show that any (randomized) algorithm that decides SR solvability requires Ω(n²) adaptive Boolean queries to the agents' preferences (in expectation). Our argument follows from a reduction from the communication complexity of the set disjointness function. The query lower bound implies quadratic time lower bounds for Turing machines, and memory access lower bounds for random access machines. Thus, we establish that Irving’s algorithm is optimal (up to a logarithmic factor) in a very strong sense.

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 (kNN). We prove that computing an optimal training-time (a.k.a. poisoning) attack against kNN 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 kNN is vulnerable in practice and that dimensionality reduction is an effective defense. We conclude with a discussion of open problems illuminated by our analysis.

In classical statistics and distribution testing, it is often assumed that elements can be sampled exactly from some distribution 𝒫, and that when an element x is sampled, the probability 𝒫(x) of sampling x is also known. In this setting, recent work in distribution testing has shown that many algorithms are robust in the sense that they still produce correct output if the elements are drawn from any distribution 𝒬 that is sufficiently close to 𝒫. This phenomenon raises interesting questions: under what conditions is a "noisy" distribution 𝒬 sufficient, and what is the algorithmic cost of coping with this noise? In this paper, we investigate these questions for the problem of estimating the sum of a multiset of N real values x_1, …, x_N. This problem is well-studied in the statistical literature in the case 𝒫 = 𝒬, where the Hansen-Hurwitz estimator [Annals of Mathematical Statistics, 1943] is frequently used. We assume that for some (known) distribution 𝒫, values are sampled from a distribution 𝒬 that is pointwise close to 𝒫. That is, there is a parameter γ < 1 such that for all x_i, (1 - γ) 𝒫(i) ≤ 𝒬(i) ≤ (1 + γ) 𝒫(i). For every positive integer k we define an estimator ζ_k for μ = ∑_i x_i whose bias is proportional to γ^k (where our ζ₁ reduces to the classical Hansen-Hurwitz estimator). As a special case, we show that if 𝒬 is pointwise γ-close to uniform and all x_i ∈ {0, 1}, for any ε > 0, we can estimate μ to within additive error ε N using m = Θ(N^{1-1/k}/ε^{2/k}) samples, where k = ⌈lg ε/lg γ⌉. We then show that this sample complexity is essentially optimal. Interestingly, our upper and lower bounds show that the sample complexity need not vary uniformly with the desired error parameter ε: for some values of ε, perturbations in its value have no asymptotic effect on the sample complexity, while for other values, any decrease in its value results in an asymptotically larger sample complexity.

Counting and sampling small subgraphs are fundamental algorithmic tasks. Motivated by the need to handle massive datasets efficiently, recent theoretical work has examined the problems in the sublinear time regime. In this work, we consider the problem of sampling a k-clique in a graph from an almost uniform distribution. Specifically the algorithm should output each k-clique with probability (1±ε)/n_k, where n_k denotes the number of k-cliques in the graph and ε is a given approximation parameter. To this end, the algorithm may perform degree, neighbor, and pair queries. We focus on the class of graphs with arboricity at most α, and prove that the query complexity of the problem is Θ^*(min{nα , max {(((nα)^(k/2))/n_k)^{1/(k-1)}, (nα^(k-1))/n_k}}), where n is the number of vertices in the graph, and Θ^*(⋅) suppresses dependencies on (log n/ε)^O(k). Our upper bound is based on defining a special auxiliary graph H_k, such that sampling edges almost uniformly in H_k translates to sampling k-cliques almost uniformly in the original graph G. We then build on a known edge-sampling algorithm (Eden, Ron and Rosenbaum, ICALP19) to sample edges in H_k. The challenge is simulating queries to H_k while being given query access only to G. Our lower bound follows from a construction of a family of graphs with arboricity α such that in each graph there are n_k k-cliques, where one of these cliques is "hidden" and hence hard to sample.

It is well known that every stable matching instance I has a rotation poset R(I) that can be computed efficiently and the downsets of R(I) are in one-to-one correspondence with the stable matchings of I. Furthermore, for every poset P, an instance I(P) can be constructed efficiently so that the rotation poset of I(P) is isomorphic to P. In this case, we say that I(P) realizes P. Many researchers exploit the rotation poset of an instance to develop fast algorithms or to establish the hardness of stable matching problems.

Assume we have a graph problem that is locally checkable but not locally solvable---given a solution we can check that it is feasible by verifying all constant-radius neighborhoods, but to find a feasible solution each node needs to explore the input graph at least up to distance Ω (log n) in order to produce its own part of the solution.

In this paper, we revisit the problem of sampling edges in an unknown graph $G = (V, E)$ from a distribution that is (pointwise) almost uniform over $E$. We consider the case where there is some a priori upper bound on the arboriciy of $G$. Given query access to a graph $G$ over $n$ vertices and of average degree $d$ and arboricity at most $α$, we design an algorithm that performs $O\!\left(\fracα{d} \cdot \frac{\log^3 n}{\varepsilon}\right)$ queries in expectation and returns an edge in the graph such that every edge $e \in E$ is sampled with probability $(1 \pm \varepsilon)/m$. The algorithm performs two types of queries: degree queries and neighbor queries. We show that the upper bound is tight (up to poly-logarithmic factors and the dependence in $\varepsilon$), as $Ω\!\left(\fracα{d} \right)$ queries are necessary for the easier task of sampling edges from any distribution over $E$ that is close to uniform in total variational distance. We also prove that even if $G$ is a tree (i.e., $α= 1$ so that $\fracα{d}=Θ(1)$), $Ω\left(\frac{\log n}{\log\log n}\right)$ queries are necessary to sample an edge from any distribution that is pointwise close to uniform, thus establishing that a $\mathrm{poly}(\log n)$ factor is necessary for constant $α$. Finally we show how our algorithm can be applied to obtain a new result on approximately counting subgraphs, based on the recent work of Assadi, Kapralov, and Khanna (ITCS, 2019).

We consider packet forwarding on a tree with all packets destined for the root, assuming each link may forward at most c ≥ 1 packets each time step. We use the Adversarial Queuing Theory injection model, where a (ρ, σ)-adversary may inject at most σ + ρ · t packets into the network at arbitrary locations during any time interval of length t. The goal is to find a forwarding protocol that minimizes the maximal buffer space required to avoid overflows against a (ρ, σ)-adversary with ρ ≤ c. We consider protocols from the locality viewpoint. A protocol is called d-local if the actions of a node depend only on the current state of nodes at distance at most d. A D-local protocol, where D is the network diameter, is called centralized. It is known that buffers of size Θ(σ + ρ) are necessary and sufficient for centralized protocols. The buffer requirement of O(1)-local protocols was recently proved to be Θ(ρ log D+σ). In this paper, for any d ≥ 2, we describe a d-local algorithm whose buffer space requirement is O (⌈log D/d⌉ ρ + σ). This result is tight, up d to constant factors. In particular, it implies that O(log D) locality is sufficient to achieve the best worst-case performance possible even for centralized algorithms. We also give evidence suggesting that the buffer requirement of a local algorithm designed for trees is good also when the routes do not constitute a single-destination tree.

Synchronizing clocks in distributed systems is well-understood, both in terms of fault-tolerance in fully connected systems, and the optimal achievable local skew in general fault-free networks. However, so far nothing non-trivial is known about the local skew that can be achieved in non-fully-connected topologies even under a single Byzantine fault. In this work, we show that asymptotically optimal local skew can be achieved in the presence of Byzantine faults.

We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate 0 ≤ ρ ≤ 1 and burstiness σ ≤ 0. In this model, we analyze the size of buffers required to avoid overflows in the basic case of a path. Our main results characterize the space required by the average rate and the number of distinct destinations: we show that O(ℓ d1/ℓ + σ) space suffice, where d is the number of distinct destinations and ℓ=⌋1/ρ⌊ and we show that Ω(1 over ℓ d1/ℓ + σ) space is necessary. For directed trees, we describe an algorithm whose buffer space requirement is at most 1 + d' + σ where d' is the maximum number of destinations on any root-leaf path.

In a celebrated work, Blais, Brody, and Matulef developed a technique for proving property testing lower bounds via reductions from communication complexity. Their work focused on testing properties of functions, and yielded new lower bounds as well as simplified analyses of known lower bounds. Here, we take a further step in generalizing the methodology of Blais et al. to analyze the query complexity of graph parameter estimation problems. In particular, our technique decouples the lower bound arguments from the representation of the graph, allowing it to work with any query type. We illustrate our technique by providing new simpler proofs of previously known tight lower bounds for the query complexity of several graph problems: estimating the number of edges in a graph, sampling edges from an almost-uniform distribution, estimating the number of triangles (and more generally, $r$-cliques) in a graph, and estimating the moments of the degree distribution of a graph. We also prove new lower bounds for estimating the edge connectivity of a graph and estimating the number of instances of any fixed subgraph in a graph. We show that the lower bounds for estimating the number of triangles and edge connectivity also hold in a strictly stronger computational model that allows access to uniformly random edge samples.

We consider packet forwarding in acyclic networks with bounded adversarial packet injections. We focus on the model of adversarial queuing theory, where each packet is injected into the network with a prescribed path to its destination, and both the long-range average rate and the short-range burst size are bounded. Each edge has an associated buffer that stores packets while they wait to cross the edge. Our goal is to minimize the buffer space required to avoid overflows.

Verifying that a network configuration satisfies a given boolean predicate is a fundamental problem in distributed computing. Many variations of this problem have been studied, for example, in the context of proof labeling schemes (PLS), locally checkable proofs (LCP), and non-deterministic local decision (NLD). In all of these contexts, verification time is assumed to be constant. Korman, Kutten and Masuzawa presented a proof-labeling scheme for MST, with poly-logarithmic verification time, and logarithmic memory at each vertex. In this paper we introduce the notion of a t-PLS, which allows the verification procedure to run for super-constant time. Our work analyzes the tradeoffs of t-PLS between time, label size, message length, and computation space. We construct a universal t-PLS and prove that it uses the same amount of total communication as a known one-round universal PLS, and t factor smaller labels. In addition, we provide a general technique to prove lower bounds for space- time tradeoffs of t-PLS. We use this technique to show an optimal tradeoff for testing that a network is acyclic (cycle free). Our optimal t-PLS for acyclicity uses label size and computation space O((log n)/t). We further describe a recursive O(log* n) space verifier for acyclicity which does not assume previous knowledge of the run-time t.

In their seminal work on the Stable Marriage Problem, Gale and Shapley describe an algorithm which finds a stable matching in O(n2) communication rounds. Their algorithm has a natural interpretation as a distributed algorithm where each player is represented by a single processor. In this distributed model, Floreen, Kaski, Polishchuk, and Suomela recently showed that for bounded preference lists, terminating the Gale-Shapley algorithm after a constant number of rounds results in an almost stable matching. In this paper, we describe a new deterministic distributed algorithm which finds an almost stable matching in O(log5 n) communication rounds for arbitrary preferences. We also present a faster randomized variant which requires O(log2 n) rounds. This run-time can be improved to O(1) rounds for "almost regular" (and in particular complete) preferences. To our knowledge, these are the first sub-polynomial round distributed algorithms for any variant of the stable marriage problem with unbounded preferences.

The Gale-Shapley algorithm for the Stable Marriage Problem is known to take Θ(n2) steps to find a stable marriage in the worst case, but only Θ(n log n) steps in the average case (with n women and n men). In 1976, Knuth asked whether the worst-case running time can be improved in a model of computation that does not require sequential access to the whole input. A partial negative answer was given by Ng and Hirschberg, who showed that Θ(n2) queries are required in a model that allows certain natural random-access queries to the participants' preferences. A significantly more general — albeit slightly weaker — lower bound follows from Segal's elaborate analysis of communication complexity, namely that Ω(n2) Boolean queries are required in order to find a stable marriage, regardless of the set of allowed Boolean queries. Using a reduction to the communication complexity of the disjointness problem, we give a far simpler, yet significantly more powerful argument showing that Ω(n2) Boolean queries of any type are indeed required. Notably, unlike Segal's lower bound, our lower bound generalizes also to (A) randomized algorithms, (B) finding approximately-stable marriages (C) verifying the stability (or the approximate stability) of a proposed marriage, (D) allowing arbitrary separate preprocessing of the women's preferences profile and of the men's preferences profile, and (E) several variants of the basic problem, such as whether a given pair is married in every/some stable marriage.