An official website of the United States government
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
more »
« less
Topologies of Random Geometric Complexes on Riemannian Manifolds in the Thermodynamic Limit
Abstract We investigate the topologies of random geometric complexes built over random points sampled on Riemannian manifolds in the so-called “thermodynamic” regime. We prove the existence of universal limit laws for the topologies; namely, the random normalized counting measure of connected components (counted according to homotopy type) is shown to converge in probability to a deterministic probability measure. Moreover, we show that the support of the deterministic limiting measure equals the set of all homotopy types for Euclidean connected geometric complexes of the same dimension as the manifold.
more »
« less
- Award ID(s):
- 1653552
- PAR ID:
- 10286247
- Date Published:
- Journal Name:
- International Mathematics Research Notices
- ISSN:
- 1073-7928
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abbott, Derek (Ed.)Abstract Convergent cross-mapping (CCM) has attracted increased attention recently due to its capability to detect causality in nonseparable systems under deterministic settings, which may not be covered by the traditional Granger causality. From an information-theoretic perspective, causality is often characterized as the directed information (DI) flowing from one side to the other. As information is essentially nondeterministic, a natural question is: does CCM measure DI flow? Here, we first causalize CCM so that it aligns with the presumption in causality analysis—the future values of one process cannot influence the past of the other, and then establish and validate the approximate equivalence of causalized CCM (cCCM) and DI under Gaussian variables through both theoretical derivations and fMRI-based brain network causality analysis. Our simulation result indicates that, in general, cCCM tends to be more robust than DI in causality detection. The underlying argument is that DI relies heavily on probability estimation, which is sensitive to data size as well as digitization procedures; cCCM, on the other hand, gets around this problem through geometric cross-mapping between the manifolds involved. Overall, our analysis demonstrates that cross-mapping provides an alternative way to evaluate DI and is potentially an effective technique for identifying both linear and nonlinear causal coupling in brain neural networks and other settings, either random or deterministic, or both.more » « less
-
Kabanets, Valentine (Ed.)We study pseudo-deterministic query complexity - randomized query algorithms that are required to output the same answer with high probability on all inputs. We prove Ω(√n) lower bounds on the pseudo-deterministic complexity of a large family of search problems based on unsatisfiable random CNF instances, and also for the promise problem (FIND1) of finding a 1 in a vector populated with at least half one’s. This gives an exponential separation between randomized query complexity and pseudo-deterministic complexity, which is tight in the quantum setting. As applications we partially solve a related combinatorial coloring problem, and we separate random tree-like Resolution from its pseudo-deterministic version. In contrast to our lower bound, we show, surprisingly, that in the zero-error, average case setting, the three notions (deterministic, randomized, pseudo-deterministic) collapse.more » « less
-
We study graph-theoretic properties of the trace of a random walk on a random graph. We show that for any $$\varepsilon>0$$ there exists $C>1$ such that the trace of the simple random walk of length $$(1+\varepsilon)n\ln{n}$$ on the random graph $$G\sim\gnp$$ for $$p>C\ln{n}/n$$ is, with high probability, Hamiltonian and $$\Theta(\ln{n})$$-connected. In the special case $p=1$$ (i.e.\ when $$G=K_n$), we show a hitting time result according to which, with high probability, exactly one step after the last vertex has been visited, the trace becomes Hamiltonian, and one step after the last vertex has been visited for the $$k$$'th time, the trace becomes $2k$-connected.more » « less
-
Suppose $$F:=(f_1,\ldots,f_n)$$ is a system of random $$n$$-variate polynomials with $$f_i$$ having degree $$\leq\!d_i$$ and the coefficient of $$x^{a_1}_1\cdots x^{a_n}_n$$ in $$f_i$$ being an independent complex Gaussian of mean $$0$$ and variance $$\frac{d_i!}{a_1!\cdots a_n!\left(d_i-\sum^n_{j=1}a_j \right)!}$$. Recent progress on Smale's 17$$\thth$$ Problem by Lairez --- building upon seminal work of Shub, Beltran, Pardo, B\"{u}rgisser, and Cucker --- has resulted in a deterministic algorithm that finds a single (complex) approximate root of $$F$$ using just $$N^{O(1)}$$ arithmetic operations on average, where $$N\!:=\!\sum^n_{i=1}\frac{(n+d_i)!}{n!d_i!}$$ ($$=n(n+\max_i d_i)^{O(\min\{n,\max_i d_i)\}}$$) is the maximum possible total number of monomial terms for such an $$F$$. However, can one go faster when the number of terms is smaller, and we restrict to real coefficient and real roots? And can one still maintain average-case polynomial-time with more general probability measures? We show the answer is yes when $$F$$ is instead a binomial system --- a case whose numerical solution is a key step in polyhedral homotopy algorithms for solving arbitrary polynomial systems. We give a deterministic algorithm that finds a real approximate root (or correctly decides there are none) using just $$O(n^3\log^2(n\max_i d_i))$$ arithmetic operations on average. Furthermore, our approach allows Gaussians with arbitrary variance. We also discuss briefly the obstructions to maintaining average-case time polynomial in $$n\log \max_i d_i$$ when $$F$$ has more terms.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imrn/rnaa050
