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

The present work is devoted to strong approximations of a generalized A\"{i}t-Sahalia model arising from mathematical finance. The numerical study of the considered model faces essential difficulties caused by a drift that blows up at the origin, highly nonlinear drift and diffusion coefficients and positivity-preserving requirement. In this paper, a novel explicit Euler-type scheme is proposed, which is easily implementable and able to preserve positivity of the original model unconditionally, i.e., for any time step-size $h >0$. A mean-square convergence rate of order $0.5$ is also obtained for the proposed scheme in both non-critical and general critical cases. Our work is motivated by the need to justify the multi-level Monte Carlo (MLMC) simulations for the underlying model, where the rate of mean-square convergence is required and the preservation of positivity is desirable particularly for large discretization time steps. Numerical experiments are finally provided to confirm the theoretical findings.

The present article aims to design and analyze efficient first-order strong schemes for a generalized A\"{i}t-Sahalia type model arising in mathematical finance and evolving in a positive domain $(0, \infty)$, which possesses a diffusion term with superlinear growth and a highly nonlinear drift that blows up at the origin. Such a complicated structure of the model unavoidably causes essential difficulties in the construction and convergence analysis of time discretizations. By incorporating implicitness in the term $\alpha_{-1} x^{-1}$ and a corrective mapping $\Phi_h$ in the recursion, we develop a novel class of explicit and unconditionally positivity-preserving (i.e., for any step-size $h>0$) Milstein-type schemes for the underlying model. In both non-critical and general critical cases, we introduce a novel approach to analyze mean-square error bounds of the novel schemes, without relying on a priori high-order moment bounds of the numerical approximations. The expected order-one mean-square convergence is attained for the proposed scheme. The above theoretical guarantee can be used to justify the optimal complexity of the Multilevel Monte Carlo method. Numerical experiments are finally provided to verify the theoretical findings.

In this paper, we consider the unique continuation problem for the Schr\"odinger equations. We prove a H\"older type conditional stability estimate and build up a parameterized stabilized finite element scheme adaptive to the \textit{a priori} knowledge of the solution, achieving error estimates in interior domains with convergence up to continuous stability. The approximability of the scheme to solutions with only $H^1$-regularity is studied and the convergence rate for solutions with regularity higher than $H^1$ is also shown. Comparisons in terms of different parameterization for different regularities will be illustrated with respect to the convergence and condition numbers of the linear systems. Finally, numerical experiments will be given to illustrate the theory.

One of the open problems in machine learning is whether any set-family of VC-dimension $d$ admits a sample compression scheme of size $O(d)$. In this paper, we study this problem for balls in graphs. For a ball $B=B_r(x)$ of a graph $G=(V,E)$, a realizable sample for $B$ is a signed subset $X=(X^+,X^-)$ of $V$ such that $B$ contains $X^+$ and is disjoint from $X^-$. A proper sample compression scheme of size $k$ consists of a compressor and a reconstructor. The compressor maps any realizable sample $X$ to a subsample $X'$ of size at most $k$. The reconstructor maps each such subsample $X'$ to a ball $B'$ of $G$ such that $B'$ includes $X^+$ and is disjoint from $X^-$. For balls of arbitrary radius $r$, we design proper labeled sample compression schemes of size $2$ for trees, of size $3$ for cycles, of size $4$ for interval graphs, of size $6$ for trees of cycles, and of size $22$ for cube-free median graphs. For balls of a given radius, we design proper labeled sample compression schemes of size $2$ for trees and of size $4$ for interval graphs. We also design approximate sample compression schemes of size 2 for balls of $\delta$-hyperbolic graphs.

In this article, we propose a new classification of $\Sigma^0_2$ formulas under the realizability interpretation of many-one reducibility (i.e., Levin reducibility). For example, ${\sf Fin}$, the decision of being eventually zero for sequences, is many-one/Levin complete among $\Sigma^0_2$ formulas of the form $\exists n\forall m\geq n.\varphi(m,x)$, where $\varphi$ is decidable. The decision of boundedness for sequences ${\sf BddSeq}$ and posets ${\sf PO}_{\sf top}$ are many-one/Levin complete among $\Sigma^0_2$ formulas of the form $\exists n\forall m\geq n\forall k.\varphi(m,k,x)$, where $\varphi$ is decidable. However, unlike the classical many-one reducibility, none of the above is $\Sigma^0_2$-complete. The decision of non-density of linear order ${\sf NonDense}$ is truly $\Sigma^0_2$-complete.

In this paper we extend to two-dimensional data two recently introduced one-dimensional compressibility measures: the $\gamma$ measure defined in terms of the smallest string attractor, and the $\delta$ measure defined in terms of the number of distinct substrings of the input string. Concretely, we introduce the two-dimensional measures $\gamma_{2D}$ and $\delta_{2D}$ as natural generalizations of $\gamma$ and $\delta$ and study some of their properties. Among other things, we prove that $\delta_{2D}$ is monotone and can be computed in linear time, and we show that, although it is still true that $\delta_{2D} \leq \gamma_{2D}$, the gap between the two measures can be $\Omega(\sqrt{n})$ for families of $n\times n$ matrices and therefore asymptotically larger than the gap in one-dimension. To complete the scenario of two-dimensional compressibility measures, we introduce also the measure $b_{2D}$ which generalizes to two dimensions the notion of optimal parsing. We prove that, somewhat surprisingly, the relationship between $b_{2D}$ and $\gamma_{2D}$ is significantly different than in the one-dimensional case. As an application of the measures $\gamma_{2D}$ and $\delta_{2D}$ we provide the first analysis of the space usage of the two-dimensional block tree introduced in [Brisaboa et al., Two-dimensional block trees, The computer Journal, 2023]. Finally, we present a linear time algorithm for constructing the two-dimensional block tree for arbitrary matrices, that is asymptotically faster than the (probabilistic) known solution which can only be used for binary matrices.

In 2017, Aharoni proposed the following generalization of the Caccetta-H\"{a}ggkvist conjecture: if $G$ is a simple $n$-vertex edge-colored graph with $n$ color classes of size at least $r$, then $G$ contains a rainbow cycle of length at most $\lceil n/r \rceil$. In this paper, we prove that, for fixed $r$, Aharoni's conjecture holds up to an additive constant. Specifically, we show that for each fixed $r \geq 1$, there exists a constant $c_r$ such that if $G$ is a simple $n$-vertex edge-colored graph with $n$ color classes of size at least $r$, then $G$ contains a rainbow cycle of length at most $n/r + c_r$.

Convergence rates for $L_2$ approximation in a Hilbert space $H$ are a central theme in numerical analysis. The present work is inspired by Schaback (Math. Comp., 1999), who showed, in the context of best pointwise approximation for radial basis function interpolation, that the convergence rate for sufficiently smooth functions can be doubled, compared to the general rate for functions in the "native space" $H$. Motivated by this, we obtain a general result for $H$-orthogonal projection onto a finite dimensional subspace of $H$: namely, that any known $L_2$ convergence rate for all functions in $H$ translates into a doubled $L_2$ convergence rate for functions in a smoother normed space $B$, along with a similarly improved error bound in the $H$-norm, provided that $L_2$, $H$ and $B$ are suitably related. As a special case we improve the known $L_2$ and $H$-norm convergence rates for kernel interpolation in reproducing kernel Hilbert spaces, with particular attention to a recent study (Kaarnioja, Kazashi, Kuo, Nobile, Sloan, Numer. Math., 2022) of periodic kernel-based interpolation at lattice points applied to parametric partial differential equations. A second application is to radial basis function interpolation for general conditionally positive definite basis functions, where again the $L_2$ convergence rate is doubled, and the convergence rate in the native space norm is similarly improved, for all functions in a smoother normed space $B$.

We give an almost complete characterization of the hardness of $c$-coloring $\chi$-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: 1) We give a new distributed algorithm that finds a $c$-coloring in $\chi$-chromatic graphs in $\tilde{\mathcal{O}}(n^{\frac{1}{\alpha}})$ rounds, with $\alpha = \bigl\lfloor\frac{c-1}{\chi - 1}\bigr\rfloor$. 2) We prove that any distributed algorithm for this problem requires $\Omega(n^{\frac{1}{\alpha}})$ rounds. Our upper bound holds in the classical, deterministic LOCAL model, while the near-matching lower bound holds in the non-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic LOCAL and randomized LOCAL but also quantum-LOCAL, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or $c$-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.

In this paper, we introduce a class of graphs which we call average hereditary graphs. Most graphs that occur in the usual graph theory applications belong to this class of graphs. Many popular types of graphs fall under this class, such as regular graphs, trees and other popular classes of graphs. We prove a new upper bound for the chromatic number of a graph in terms of its maximum average degree and show that this bound is an improvement on previous bounds. From this, we show a relationship between the average degree and the chromatic number of an average hereditary graph. This class of graphs is explored further by proving some interesting properties regarding the class of average hereditary graphs. An equivalent condition is provided for a graph to be average hereditary, through which we show that we can decide if a given graph is average hereditary in polynomial time. We then provide a construction for average hereditary graphs, using which an average hereditary graph can be recursively constructed. We also show that this class of graphs is closed under a binary operation, from this another construction is obtained for average hereditary graphs, and we see some interesting algebraic properties this class of graphs has. We then explore the effect on the complexity of graph 3-coloring problem when the input is restricted to average hereditary graphs.