亚洲男人的天堂2018av,欧美草比,久久久久久免费视频精选,国色天香在线看免费,久久久久亚洲av成人片仓井空

We consider the \emph{exact plurality consensus} problem for \emph{population protocols}. Here, $n$ anonymous agents start each with one of $k$ opinions. Their goal is to agree on the initially most frequent opinion (the \emph{plurality opinion}) via random, pairwise interactions. The case of $k = 2$ opinions is known as the \emph{majority problem}. Recent breakthroughs led to an always correct, exact majority population protocol that is both time- and space-optimal, needing $O(\log n)$ states per agent and, with high probability, $O(\log n)$ time~[Doty, Eftekhari, Gasieniec, Severson, Stachowiak, and Uznanski; 2021]. We know that any always correct protocol requires $\Omega(k^2)$ states, while the currently best protocol needs $O(k^{11})$ states~[Natale and Ramezani; 2019]. For ordered opinions, this can be improved to $O(k^6)$~[Gasieniec, Hamilton, Martin, Spirakis, and Stachowiak; 2016]. We design protocols for plurality consensus that beat the quadratic lower bound by allowing a negligible failure probability. While our protocols might fail, they identify the plurality opinion with high probability even if the bias is $1$. Our first protocol achieves this via $k-1$ tournaments in time $O(k \cdot \log n)$ using $O(k + \log n)$ states. While it assumes an ordering on the opinions, we remove this restriction in our second protocol, at the cost of a slightly increased time $O(k \cdot \log n + \log^2 n)$. By efficiently pruning insignificant opinions, our final protocol reduces the number of tournaments at the cost of a slightly increased state complexity $O(k \cdot \log\log n + \log n)$. This improves the time to $O(n / x_{\max} \cdot \log n + \log^2 n)$, where $x_{\max}$ is the initial size of the plurality. Note that $n/x_{\max}$ is at most $k$ and can be much smaller (e.g., in case of a large bias or if there are many small opinions).

For a state $\rho_{A_1^n B}$, we call a sequence of states $(\sigma_{A_1^k B}^{(k)})_{k=1}^n$ an approximation chain if for every $1 \leq k \leq n$, $\rho_{A_1^k B} \approx_\epsilon \sigma_{A_1^k B}^{(k)}$. In general, it is not possible to lower bound the smooth min-entropy of such a $\rho_{A_1^n B}$, in terms of the entropies of $\sigma_{A_1^k B}^{(k)}$ without incurring very large penalty factors. In this paper, we study such approximation chains under additional assumptions. We begin by proving a simple entropic triangle inequality, which allows us to bound the smooth min-entropy of a state in terms of the R\'enyi entropy of an arbitrary auxiliary state while taking into account the smooth max-relative entropy between the two. Using this triangle inequality, we create lower bounds for the smooth min-entropy of a state in terms of the entropies of its approximation chain in various scenarios. In particular, utilising this approach, we prove approximate versions of the asymptotic equipartition property and entropy accumulation. In our companion paper, we show that the techniques developed in this paper can be used to prove the security of quantum key distribution in the presence of source correlations.

We analyze an algorithmic question about immersion theory: for which $m$, $n$, and $CAT=\mathbf{Diff}$ or $\mathbf{PL}$ is the question of whether an $m$-dimensional $CAT$-manifold is immersible in $\mathbb{R}^n$ decidable? As a corollary, we show that the smooth embeddability of an $m$-manifold with boundary in $\mathbb{R}^n$ is undecidable when $n-m$ is even and $11m \geq 10n+1$.

Given a graph~$G$, the domination number, denoted by~$\gamma(G)$, is the minimum cardinality of a dominating set in~$G$. Dual to the notion of domination number is the packing number of a graph. A packing of~$G$ is a set of vertices whose pairwise distance is at least three. The packing number~$\rho(G)$ of~$G$ is the maximum cardinality of one such set. Furthermore, the inequality~$\rho(G) \leq \gamma(G)$ is well-known. Henning et al.\ conjectured that~$\gamma(G) \leq 2\rho(G)+1$ if~$G$ is subcubic. In this paper, we progress towards this conjecture by showing that~${\gamma(G) \leq \frac{120}{49}\rho(G)}$ if~$G$ is a bipartite cubic graph. We also show that $\gamma(G) \leq 3\rho(G)$ if~$G$ is a maximal outerplanar graph, and that~$\gamma(G) \leq 2\rho(G)$ if~$G$ is a biconvex graph. Moreover, in the last case, we show that this upper bound is tight.

Let $\mathbf{G}:=(G_1, G_2, G_3)$ be a triple of graphs on the same vertex set $V$ of size $n$. A rainbow triangle in $\mathbf{G}$ is a triple of edges $(e_1, e_2, e_3)$ with $e_i\in G_i$ for each $i$ and $\{e_1, e_2, e_3\}$ forming a triangle in $V$. The triples $\mathbf{G}$ not containing rainbow triangles, also known as Gallai colouring templates, are a widely studied class of objects in extremal combinatorics. In the present work, we fully determine the set of edge densities $(\alpha_1, \alpha_2, \alpha_3)$ such that if $\vert E(G_i)\vert> \alpha_i n^2$ for each $i$ and $n$ is sufficiently large, then $\mathbf{G}$ must contain a rainbow triangle. This resolves a problem raised by Aharoni, DeVos, de la Maza, Montejanos and \v{S}\'amal, generalises several previous results on extremal Gallai colouring templates, and proves a recent conjecture of Frankl, Gy\"ori, He, Lv, Salia, Tompkins, Varga and Zhu.

Classical Krylov subspace projection methods for the solution of linear problem $Ax = b$ output an approximate solution $\widetilde{x}\simeq x$. Recently, it has been recognized that projection methods can be understood from a statistical perspective. These probabilistic projection methods return a distribution $p(\widetilde{x})$ in place of a point estimate $\widetilde{x}$. The resulting uncertainty, codified as a distribution, can, in theory, be meaningfully combined with other uncertainties, can be propagated through computational pipelines, and can be used in the framework of probabilistic decision theory. The problem we address is that the current probabilistic projection methods lead to the poorly calibrated posterior distribution. We improve the covariance matrix from previous works in a way that it does not contain such undesirable objects as $A^{-1}$ or $A^{-1}A^{-T}$, results in nontrivial uncertainty, and reproduces an arbitrary projection method as a mean of the posterior distribution. We also propose a variant that is numerically inexpensive in the case the uncertainty is calibrated a priori. Since it usually is not, we put forward a practical way to calibrate uncertainty that performs reasonably well, albeit at the expense of roughly doubling the numerical cost of the underlying projection method.

We expound on some known lower bounds of the quadratic Wasserstein distance between random vectors in $\mathbb{R}^n$ with an emphasis on affine transformations that have been used in manifold learning of data in Wasserstein space. In particular, we give concrete lower bounds for rotated copies of random vectors in $\mathbb{R}^2$ by computing the Bures metric between the covariance matrices. We also derive upper bounds for compositions of affine maps which yield a fruitful variety of diffeomorphisms applied to an initial data measure. We apply these bounds to various distributions including those lying on a 1-dimensional manifold in $\mathbb{R}^2$ and illustrate the quality of the bounds. Finally, we give a framework for mimicking handwritten digit or alphabet datasets that can be applied in a manifold learning framework.

The development of cubical type theory inspired the idea of "extension types" which has been found to have applications in other type theories that are unrelated to homotopy type theory or cubical type theory. This article describes these applications, including on records, metaprogramming, controlling unfolding, and some more exotic ones.

We introduce $\varepsilon$-approximate versions of the notion of Euclidean vector bundle for $\varepsilon \geq 0$, which recover the classical notion of Euclidean vector bundle when $\varepsilon = 0$. In particular, we study \v{C}ech cochains with coefficients in the orthogonal group that satisfy an approximate cocycle condition. We show that $\varepsilon$-approximate vector bundles can be used to represent classical vector bundles when $\varepsilon > 0$ is sufficiently small. We also introduce distances between approximate vector bundles and use them to prove that sufficiently similar approximate vector bundles represent the same classical vector bundle. This gives a way of specifying vector bundles over finite simplicial complexes using a finite amount of data, and also allows for some tolerance to noise when working with vector bundles in an applied setting. As an example, we prove a reconstruction theorem for vector bundles from finite samples. We give algorithms for the effective computation of low-dimensional characteristic classes of vector bundles directly from discrete and approximate representations and illustrate the usage of these algorithms with computational examples.

Foucaud {\it et al.} recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Let $G$ be a graph with vertex set $V(G)$, $M$ a subset of $V(G)$, and $e$ be an edge in $E(G)$, and let $P(M, e)$ be the set of pairs $(x,y)$ such that $d_G(x, y)\neq d_{G-e}(x, y)$ where $x\in M$ and $y\in V(G)$. $M$ is called a \emph{distance-edge-monitoring set} if every edge $e$ of $G$ is monitored by some vertex of $M$, that is, the set $P(M, e)$ is nonempty. The {\em distance-edge-monitoring number} of $G$, denoted by $\operatorname{dem}(G)$, is defined as the smallest size of distance-edge-monitoring sets of $G$. For two graphs $G,H$ of order $m,n$, respectively, in this paper we prove that $\max\{m\operatorname{dem}(H),n\operatorname{dem}(G)\} \leq\operatorname{dem}(G\,\Box \,H) \leq m\operatorname{dem}(H)+n\operatorname{dem}(G) -\operatorname{dem}(G)\operatorname{dem}(H)$, where $\Box$ is the Cartesian product operation. Moreover, we characterize the graphs attaining the upper and lower bounds and show their applications on some known networks. We also obtain the distance-edge-monitoring numbers of join, corona, cluster, and some specific networks.