Hyperdimensional computing (HDC) is a biologically-inspired framework which represents symbols with high-dimensional vectors, and uses vector operations to manipulate them. The ensemble of a particular vector space and a prescribed set of vector operations (e.g., addition-like for “bundling” and outer-product-like for “binding”), as targeted to HDC, forms a vector symbolic architecture (VSA). While VSAs have been employed in numerous learning applications and have been studied empirically, many theoretical questions about VSAs remain open. In this paper, we analyze the representation capacities of four common VSAs: MAP-I (vectors take integer values), MAP-B (binary vectors and operations), and two VSAs based on sparse binary vectors. “Representation capacity” here refers to bounds on the dimensions of the VSA vectors required to perform certain symbolic tasks, such as testing for set membership and estimating set intersection sizes for two sets of symbols, to a given degree of accuracy. We also propose a novel variant of a Hopfield network (a simple model of associative memory), and analyze its ability to perform some of the same tasks that are typically asked of VSAs. Our analyses establish and leverage connections between VSAs, matrix sketching algorithms, and Bloom filters. In particular, some of our analyses amount to showing that certain random projections with less than full randomness have length-preserving properties, and we give novel analyses of Bloom filters and Counting Bloom filters, with regard to rapid estimation of the size of set intersections.

Consider a random geometric 2-dimensional simplicial complex X sampled as follows: first, sample n vectors u1,…,un uniformly at random on Sd−1; then, for each triple i,j,k ∈ [n], add {i,j,k} and all of its subsets to X if and only if ⟨ ui,uj ⟩ ≥ τ, ⟨ ui,uk ⟩ ≥ τ, and ⟨ uj, uk ⟩ ≥ τ. We prove that for every ε > 0, there exists a choice of d = Θ(logn) and τ = τ(ε,d) so that with high probability, X is a high-dimensional expander of average degree nε in which each 1-link has spectral gap bounded away from 1/2.

We present a framework for speeding up the time it takes to sample from discrete distributions $μ$ defined over subsets of size $k$ of a ground set of $n$ elements, in the regime $k\ll n$. We show that having estimates of marginals $\mathbb{P}_{S\sim μ}[i\in S]$, the task of sampling from $μ$ can be reduced to sampling from distributions $ν$ supported on size $k$ subsets of a ground set of only $n^{1-α}\cdot \operatorname{poly}(k)$ elements. Here, $1/α\in [1, k]$ is the parameter of entropic independence for $μ$. Further, the sparsified distributions $ν$ are obtained by applying a sparse (mostly $0$) external field to $μ$, an operation that often retains algorithmic tractability of sampling from $ν$. This phenomenon, which we dub domain sparsification, allows us to pay a one-time cost of estimating the marginals of $μ$, and in return reduce the amortized cost needed to produce many samples from the distribution $μ$, as is often needed in upstream tasks such as counting and inference. For a wide range of distributions where $α=Ω(1)$, our result reduces the domain size, and as a corollary, the cost-per-sample, by a $\operatorname{poly}(n)$ factor. Examples include monomers in a monomer-dimer system, non-symmetric determinantal point processes, and partition-constrained Strongly Rayleigh measures. Our work significantly extends the reach of prior work of Anari and Dereziński who obtained domain sparsification for distributions with a log-concave generating polynomial (corresponding to $α=1$). As a corollary of our new analysis techniques, we also obtain a less stringent requirement on the accuracy of marginal estimates even for the case of log-concave polynomials; roughly speaking, we show that constant-factor approximation is enough for domain sparsification, improving over $O(1/k)$ relative error established in prior work.

The random geometric graph model GRGd(n,p) is a distribution over graphs in which the edges capture a latent geometry. To sample G ∼ GRGd(n,p), we identify each of our n vertices with an independently and uniformly sampled vector from the d-dimensional unit sphere Sd−1, and we connect pairs of vertices whose vectors are “sufficiently close,” such that the marginal probability of an edge is p. Because of the underlying geometry, this model is natural for applications in data science and beyond.

We present an elementary way to transform an expander graph into a simplicial complex where all high order random walks have a constant spectral gap, i.e., they converge rapidly to the stationary distribution. As an upshot, we obtain new constructions, as well as a natural probabilistic model to sample constant degree high-dimensional expanders. In particular, we show that given an expander graph $G$, adding self loops to $G$ and taking the tensor product of the modified graph with a high-dimensional expander produces a new high-dimensional expander. Our proof of rapid mixing of high order random walks is based on the decomposable Markov chains framework introduced by Jerrum et al.