A nearest neighbor representation of a Boolean function f is a set of vectors (anchors) labeled by 0 or 1 such that f(x) = 1 if and only if the closest anchor to x is labeled by 1. This model was introduced by Hajnal, Liu and Turán [2022], who studied bounds on the minimum number of anchors required to represent Boolean functions under different choices of anchors (real vs. Boolean vectors) as well as the analogous model of k-nearest neighbors representations. We initiate a systematic study of the representational power of nearest and k-nearest neighbors through Boolean circuit complexity. To this end, we establish a close connection between Boolean functions with polynomial nearest neighbor complexity and those that can be efficiently represented by classes based on linear inequalities - min-plus polynomial threshold functions - previously studied in relation to threshold circuits. This extends an observation of Hajnal et al. [2022]. Next, we further extend the connection between nearest neighbor representations and circuits to the k-nearest neighbors case. As an outcome of these connections we obtain exponential lower bounds on the k-nearest neighbors complexity of explicit n-variate functions, assuming k ≤ n^{1-ε}. Previously, no superlinear lower bound was known for any k > 1. At the same time, we show that proving superpolynomial lower bounds for the k-nearest neighbors complexity of an explicit function for arbitrary k would require a breakthrough in circuit complexity. In addition, we prove an exponential separation between the nearest neighbor and k-nearest neighbors complexity (for unrestricted k) of an explicit function. These results address questions raised by [Hajnal et al., 2022] of proving strong lower bounds for k-nearest neighbors and understanding the role of the parameter k. Finally, we devise new bounds on the nearest neighbor complexity for several families of Boolean functions.

We study the inoculation game, a game-theoretic abstraction of epidemic containment played on an undirected graph G : each player is associated with a node in G and can either acquire protection from a contagious process or risk infection. After decisions are made, an infection starts at a random node v and propagates through all unprotected nodes reachable from v . It is known that the price of anarchy (PoA) in n -node graphs can be as large as Θ ( n ) . Our main result is a tight upper bound of O ( n Δ ) on the PoA, where Δ is the maximum degree of the graph. Indeed, we provide constructions of graphs with maximum degree Δ for which the PoA is Ω ( n Δ ) . We also study additional factors that can reduce the PoA, such as higher thresholds for contagion and varying the costs of becoming infected vs. acquiring protection.

We consider the learning and communication complexity of subsequence containment. In the learning problem, we seek to learn a classifier that positively labels a binary string x if it contains a fixed binary string y as a subsequence. In the communication problem, x and y are partitioned between two players, Alice and Bob, who wish to determine if x contains y as a subsequence using a minimal amount of communication. We devise asymptotically tight bounds for the sample complexity (VC dimension) of the learning problem and the communication complexity of the communication problem. Our results illustrate that the sample complexity of our learning problem can be considerably larger when the subsequence occurs in non-contiguous locations.