Search for: All records

ABSTRACT A random algebraic graph is defined by a group with a uniform distribution over it and a connection with expectation satisfying . The random graph with vertex set is formed as follows. First, independent variables are sampled uniformly from . Then, vertices are connected with probability . This model captures random geometric graphs over the sphere, torus, and hypercube; certain instances of the stochastic block model; and random subgraphs of Cayley graphs. The main question of interest to the current paper is: when is a random algebraic graph statistically and/or computationally distinguishable from ? Our results fall into two categories. (1) Geometric. We focus on the case and use Fourier‐analytic tools. We match and extend the following results from the prior literature: For hard threshold connections, we match for , and for ‐Lipschitz connections we extend the results of when to the non‐monotone setting. (2) Algebraic. We provide evidence for an exponential statistical‐computational gap. Consider any finite group and let be a set of elements formed by including each set of the form independently with probability Let be the distribution of random graphs formed by taking a uniformly random induced subgraph of size of the Cayley graph . Then, and are statistically indistinguishable with high probability over if and only if . However, low‐degree polynomial tests fail to distinguish and with high probability over when 

Abstract In the anisotropic random geometric graph model, vertices correspond to points drawn from a high‐dimensional Gaussian distribution and two vertices are connected if their distance is smaller than a specified threshold. We study when it is possible to hypothesis test between such a graph and an Erdős‐Rényi graph with the same edge probability. If is the number of vertices and is the vector of eigenvalues, Eldan and Mikulincer, Geo. Aspects Func. Analysis: Israel seminar, 2017 shows that detection is possible when and impossible when . We show detection is impossible when , closing this gap and affirmatively resolving the conjecture of Eldan and Mikulincer, Geo. Aspects Func. Analysis: Israel seminar, 2017. 

We aim to understand the extent to which the noise distribution in a planted signal-plus-noise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient graph. Instead of Erd\H{o}s-R\'enyi , which has independent edges, we take the ambient graph to be the \emph{random graph with triangles} (RGT) obtained by adding triangles to . We show that the RGT can be efficiently mapped to the corresponding , and moreover, that the planted clique (or dense subgraph) is approximately preserved under this mapping. This constitutes the first average-case reduction transforming dependent noise to independent noise. Together with the easier direction of mapping the ambient graph from Erd\H{o}s-R\'enyi to RGT, our results yield a strong equivalence between models. In order to prove our results, we develop a new general framework for reasoning about the validity of average-case reductions based on \emph{low sensitivity to perturbations}.