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

We study the behavior of a label propagation algorithm (LPA) on the Erd\H{o}s-R\'enyi random graph $\mathcal{G}(n,p)$. Initially, given a network, each vertex starts with a random label in the interval $[0,1]$. Then, in each round of LPA, every vertex switches its label to the majority label in its neighborhood (including its own label). At the first round, ties are broken towards smaller labels, while at each of the next rounds, ties are broken uniformly at random. The algorithm terminates once all labels stay the same in two consecutive iterations. LPA is successfully used in practice for detecting communities in networks (corresponding to vertex sets with the same label after termination of the algorithm). Perhaps surprisingly, LPA's performance on dense random graphs is hard to analyze, and so far convergence to consensus was known only when $np\ge n^{3/4+\varepsilon}$, where LPA converges in three rounds. By defining an alternative label attribution procedure which converges to the label propagation algorithm after three rounds, a careful multi-stage exposure of the edges allows us to break the $n^{3/4+\varepsilon}$ barrier and show that, when $np \ge n^{5/8+\varepsilon}$, a.a.s.\ the algorithm terminates with a single label. Moreover, we show that, if $np\gg n^{2/3}$, a.a.s.\ this label is the smallest one, whereas if $n^{5/8+\varepsilon}\le np\ll n^{2/3}$, the surviving label is a.a.s.\ not the smallest one. En passant, we show a presumably new monotonicity lemma for Binomial random variables that might be of independent interest.

We address the regression problem for a general function $f:[-1,1]^d\to \mathbb R$ when the learner selects the training points $\{x_i\}_{i=1}^n$ to achieve a uniform error bound across the entire domain. In this setting, known historically as nonparametric regression, we aim to establish a sample complexity bound that depends solely on the function's degree of smoothness. Assuming periodicity at the domain boundaries, we introduce PADUA, an algorithm that, with high probability, provides performance guarantees optimal up to constant or logarithmic factors across all problem parameters. Notably, PADUA is the first parametric algorithm with optimal sample complexity for this setting. Due to this feature, we prove that, differently from the non-parametric state of the art, PADUA enjoys optimal space complexity in the prediction phase. To validate these results, we perform numerical experiments over functions coming from real audio data, where PADUA shows comparable performance to state-of-the-art methods, while requiring only a fraction of the computational time.

We propose a method for estimating a log-concave density on $\mathbb R^d$ from samples, under the assumption that there exists an orthogonal transformation that makes the components of the random vector independent. While log-concave density estimation is hard both computationally and statistically, the independent components assumption alleviates both issues, while still maintaining a large non-parametric class. We prove that under mild conditions, at most $\tilde{\mathcal{O}}(\epsilon^{-4})$ samples (suppressing constants and log factors) suffice for our proposed estimator to be within $\epsilon$ of the original density in squared Hellinger distance. On the computational front, while the usual log-concave maximum likelihood estimate can be obtained via a finite-dimensional convex program, it is slow to compute -- especially in higher dimensions. We demonstrate through numerical experiments that our estimator can be computed efficiently, making it more practical to use.

The Hartman-Watson distribution with density $f_r(t)$ is a probability distribution defined on $t \geq 0$ which appears in several problems of applied probability. The density of this distribution is expressed in terms of an integral $\theta(r,t)$ which is difficult to evaluate numerically for small $t\to 0$. Using saddle point methods, we obtain the first two terms of the $t\to 0$ expansion of $\theta(\rho/t,t)$ at fixed $\rho >0$. An error bound is obtained by numerical estimates of the integrand, which is furthermore uniform in $\rho$. As an application we obtain the leading asymptotics of the density of the time average of the geometric Brownian motion as $t\to 0$. This has the form $\mathbb{P}(\frac{1}{t} \int_0^t e^{2(B_s+\mu s)} ds \in da) \sim (2\pi t)^{-1/2} g(a,\mu) e^{-\frac{1}{t} J(a)} da/a$, with an exponent $J(a)$ which reproduces the known result obtained previously using Large Deviations theory.

We prove that there exist functions $f,g:\mathbb{N}\to\mathbb{N}$ such that for all nonnegative integers $k$ and $d$, for every graph $G$, either $G$ contains $k$ cycles such that vertices of different cycles have distance greater than $d$ in $G$, or there exists a subset $X$ of vertices of $G$ with $|X|\leq f(k)$ such that $G-B_G(X,g(d))$ is a forest, where $B_G(X,r)$ denotes the set of vertices of $G$ having distance at most $r$ from a vertex of $X$.

In this paper, based on the theory of defining sets, two classes of at most six-weight linear codes over $\mathbb{F}_p$ are constructed. The weight distributions of the linear codes are determined by means of Gaussian period and Weil sums. In some case, there is an almost optimal code with respect to Griesmer bound, which is also an optimal one according to the online code table. The linear codes can also be employed to get secret sharing schemes.

We consider the quantum query complexity of local search as a function of graph geometry. Given a graph $G = (V,E)$ with $n$ vertices and black box access to a function $f : V \to \mathbb{R}$, the goal is find a vertex $v$ that is a local minimum, i.e. with $f(v) \leq f(u)$ for all $(u,v) \in E$, using as few oracle queries as possible. We show that the quantum query complexity of local search on $G$ is $\Omega\bigl( \frac{n^{\frac{3}{4}}}{\sqrt{g}} \bigr)$, where $g$ is the vertex congestion of the graph. For a $\beta$-expander with maximum degree $\Delta$, this implies a lower bound of $ \Omega\bigl(\frac{\sqrt{\beta} \; n^{\frac{1}{4}}}{\sqrt{\Delta} \; \log{n}} \bigr)$. We obtain these bounds by applying the strong weighted adversary method to a construction by Br\^anzei, Choo, and Recker (2024). As a corollary, on constant degree expanders, we derive a lower bound of $\Omega\bigl(\frac{n^{\frac{1}{4}}}{ \sqrt{\log{n}}} \bigr)$. This improves upon the best prior quantum lower bound of $\Omega\bigl( \frac{n^{\frac{1}{8}}}{\log{n}}\bigr) $ by Santha and Szegedy (2004). In contrast to the classical setting, a gap remains in the quantum case between our lower bound and the best-known upper bound of $O\bigl( n^{\frac{1}{3}} \bigr)$ for such graphs.

We consider the problem of enumerating all minimal transversals (also called minimal hitting sets) of a hypergraph $\mathcal{H}$. An equivalent formulation of this problem known as the \emph{transversal hypergraph} problem (or \emph{hypergraph dualization} problem) is to decide, given two hypergraphs, whether one corresponds to the set of minimal transversals of the other. The existence of a polynomial time algorithm to solve this problem is a long standing open question. In \cite{fredman_complexity_1996}, the authors present the first sub-exponential algorithm to solve the transversal hypergraph problem which runs in quasi-polynomial time, making it unlikely that the problem is (co)NP-complete. In this paper, we show that when one of the two hypergraphs is of bounded VC-dimension, the transversal hypergraph problem can be solved in polynomial time, or equivalently that if $\mathcal{H}$ is a hypergraph of bounded VC-dimension, then there exists an incremental polynomial time algorithm to enumerate its minimal transversals. This result generalizes most of the previously known polynomial cases in the literature since they almost all consider classes of hypergraphs of bounded VC-dimension. As a consequence, the hypergraph transversal problem is solvable in polynomial time for any class of hypergraphs closed under partial subhypergraphs. We also show that the proposed algorithm runs in quasi-polynomial time in general hypergraphs and runs in polynomial time if the conformality of the hypergraph is bounded, which is one of the few known polynomial cases where the VC-dimension is unbounded.

Let $\mathcal{O}$ be a set of $k$ orientations in the plane, and let $P$ be a simple polygon in the plane. Given two points $p,q$ inside $P$, we say that $p$ $\mathcal{O}$-\emph{sees} $q$ if there is an $\mathcal{O}$-\emph{staircase} contained in $P$ that connects $p$ and~$q$. The \emph{$\mathcal{O}$-Kernel} of the polygon $P$, denoted by $\mathcal{O}$-$\rm kernel(P)$, is the subset of points of $P$ which $\mathcal{O}$-see all the other points in $P$. This work initiates the study of the computation and maintenance of $\mathcal{O}$-$\rm kernel(P)$ as we rotate the set $\mathcal{O}$ by an angle $\theta$, denoted by $\mathcal{O}$-$\rm kernel_{\theta}(P)$. In particular, we consider the case when the set $\mathcal{O}$ is formed by either one or two orthogonal orientations, $\mathcal{O}=\{0^\circ\}$ or $\mathcal{O}=\{0^\circ,90^\circ\}$. For these cases and $P$ being a simple polygon, we design efficient algorithms for computing the $\mathcal{O}$-$\rm kernel_{\theta}(P)$ while $\theta$ varies in $[-\frac{\pi}{2},\frac{\pi}{2})$, obtaining: (i)~the intervals of angle~$\theta$ where $\mathcal{O}$-$\rm kernel_{\theta}(P)$ is not empty, (ii)~a value of angle~$\theta$ where $\mathcal{O}$-$\rm kernel_{\theta}(P)$ optimizes area or perimeter. Further, we show how the algorithms can be improved when $P$ is a simple orthogonal polygon. In addition, our results are extended to the case of a set $\mathcal{O}=\{\alpha_1,\dots,\alpha_k\}$.