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
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
- NSF-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
-
-
The ability to achieve coordinated behavior --engineered or emergent-- on networked systems has attracted widespread interest over several fields. This has led to remarkable advances on the development of a theoretical understanding of the conditions under which agents within a network can reach agreement (consensus) or develop coordinated behaviors such as synchronization. However, fewer advances have been made toward explaining another commonly observed phenomena in tightly-connected networks systems: output responses of nodes in the networks are almost identical to each other despite heterogeneity in their individual dynamics. In this work, we leverage tools from high-dimensional probability to provide an initial answer to this phenomena. More precisely, we show that for linear networks of nodal random transfer functions, as the networks size and connectivity grows, every node in the network follows the same response to an input or disturbance irrespectively of the source of this input. We term this behavior as dynamics concentration as it stems from the fact that the network transfer matrix uniformly converges in probability to a unique dynamic response --i.e., it concentrates-- determined by the distribution of the random transfer function of each node. We further discuss the implications of our analysis in the context of model reduction and robustness, and provide numerical evidence that similar phenomena occur in small deterministic networks over a properly defined frequency band.more » « less
-
We consider how to generate graphs of arbitrary size whose chromatic numbers can be chosen (or are well-bounded) for testing graph coloring algorithms on parallel computers. For the distance-1 graph coloring problem, we identify three classes of graphs with this property. The first is the Erdős-Rényi random graph with prescribed expected degree, where the chromatic number is known with high probability. It is also known that the Greedy algorithm colors this graph using at most twice the number of colors as the chromatic number. The second is a random geometric graph embedded in hyperbolic space where the size of the maximum clique provides a tight lower bound on the chromatic number. The third is a deterministic graph described by Mycielski, where the graph is recursively constructed such that its chromatic number is known and increases with graph size, although the size of the maximum clique remains two. For Jacobian estimation, we bound the distance-2 chromatic number of random bipartite graphs by considering its equivalence to distance-1 coloring of an intersection graph. We use a “balls and bins” probabilistic analysis to establish a lower bound and an upper bound on the distance-2 chromatic number. The regimes of graph sizes and probabilities that we consider are chosen to suit the Jacobian estimation problem, where the number of columns and rows are asymptotically nearly equal, and have number of nonzeros linearly related to the number of columns. Computationally we verify the theoretical predictions and show that the graphs are often be colored optimally by the serial and parallel Greedy algorithms.more » « less
-
A source generates time-stamped update packets that are sent to a server and then forwarded to a monitor. This occurs in the presence of an adversary that can infer information about the source by observing the output process of the server. The server wishes to release updates in a timely way to the monitor but also wishes to minimize the information leaked to the adversary. We analyze the trade-off between the age of information (AoI) and the maximal leakage for systems in which the source generates updates as a Bernoulli process. For a time slotted system in which sending an update requires one slot, we consider three server policies: (1) Memoryless with Bernoulli Thinning (MBT): arriving updates are queued with some probability and head-of-line update is released after a geometric holding time; (2) Deterministic Accumulate-and-Dump (DAD): the most recently generated update (if any) is released after a fixed time; (3) Random Accumulate-and-Dump (RAD): the most recently generated update (if any) is released after a geometric waiting time. We show that for the same maximal leakage rate, the DAD policy achieves lower age compared to the other two policies but is restricted to discrete age-leakage operating points.more » « less
-
more » « less
We study a model of random graph where vertices are
n i.i.d. uniform random points on the unit sphereS d in, and a pair of vertices is connected if the Euclidean distance between them is at least 2− ϵ . We are interested in the chromatic number of this graph asn tends to infinity. It is not too hard to see that ifϵ >0 is small and fixed, then the chromatic number isd +2 with high probability. We show that this holds even ifϵ →0 slowly enough. We quantify the rate at whichϵ can tend to zero and still have the same chromatic number. The proof depends on combining topological methods (namely the Lyusternik–Schnirelman–Borsuk theorem) with geometric probability arguments. The rate we obtain is best possible, up to a constant factor—ifϵ →0 faster than this, we show that the graph is (d +1)‐colorable with high probability.25
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imrn/rnaa050
