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

We show polynomial-time quantum algorithms for the following problems: (*) Short integer solution (SIS) problem under the infinity norm, where the public matrix is very wide, the modulus is a polynomially large prime, and the bound of infinity norm is set to be half of the modulus minus a constant. (*) Learning with errors (LWE) problem given LWE-like quantum states with polynomially large moduli and certain error distributions, including bounded uniform distributions and Laplace distributions. (*) Extrapolated dihedral coset problem (EDCP) with certain parameters. The SIS, LWE, and EDCP problems in their standard forms are as hard as solving lattice problems in the worst case. However, the variants that we can solve are not in the parameter regimes known to be as hard as solving worst-case lattice problems. Still, no classical or quantum polynomial-time algorithms were known for the variants of SIS and LWE we consider. For EDCP, our quantum algorithm slightly extends the result of Ivanyos et al. (2018). Our algorithms for variants of SIS and EDCP use the existing quantum reductions from those problems to LWE, or more precisely, to the problem of solving LWE given LWE-like quantum states. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.

Multi-agent reinfocement learning (MARL) is often modeled using the framework of Markov games (also called stochastic games or dynamic games). Most of the existing literature on MARL concentrates on zero-sum Markov games but is not applicable to general-sum Markov games. It is known that the best-response dynamics in general-sum Markov games are not a contraction. Therefore, different equilibrium in general-sum Markov games can have different values. Moreover, the Q-function is not sufficient to completely characterize the equilibrium. Given these challenges, model based learning is an attractive approach for MARL in general-sum Markov games. In this paper, we investigate the fundamental question of \emph{sample complexity} for model-based MARL algorithms in general-sum Markov games and show that $\tilde{\mathcal{O}}(|\mathcal{S}|\,|\mathcal{A}| (1-\gamma)^{-2} \alpha^{-2})$ samples are sufficient to obtain a $\alpha$-approximate Markov perfect equilibrium with high probability, where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the joint action space of all players, and $\gamma$ is the discount factor, and the $\tilde{\mathcal{O}}(\cdot)$ notation hides logarithmic terms. To obtain these results, we study the robustness of Markov perfect equilibrium to model approximations. We show that the Markov perfect equilibrium of an approximate (or perturbed) game is always an approximate Markov perfect equilibrium of the original game and provide explicit bounds on the approximation error. We illustrate the results via a numerical example.

In this paper, we focus on the analysis of the regularized Wasserstein barycenter problem. We provide uniqueness and a characterization of the barycenter for two important classes of probability measures: (i) Gaussian distributions and (ii) $q$-Gaussian distributions; each regularized by a particular entropy functional. We propose an algorithm based on gradient projection method in the space of matrices in order to compute these regularized barycenters. We also consider a general class of $\varphi$-exponential measures, for which only the non-regularized barycenter is studied. Finally, we numerically show the influence of parameters and stability of the algorithm under small perturbation of data.

We introduce a model of register automata over infinite trees with extrema constraints. Such an automaton can store elements of a linearly ordered domain in its registers, and can compare those values to the suprema and infima of register values in subtrees. We show that the emptiness problem for these automata is decidable. As an application, we prove decidability of the countable satisfiability problem for two-variable logic in the presence of a tree order, a linear order, and arbitrary atoms that are MSO definable from the tree order. As a consequence, the satisfiability problem for two-variable logic with arbitrary predicates, two of them interpreted by linear orders, is decidable.

Identification of a linear time-invariant dynamical system from partial observations is a fundamental problem in control theory. Particularly challenging are systems exhibiting long-term memory. A natural question is how learn such systems with non-asymptotic statistical rates depending on the inherent dimensionality (order) $d$ of the system, rather than on the possibly much larger memory length. We propose an algorithm that given a single trajectory of length $T$ with gaussian observation noise, learns the system with a near-optimal rate of $\widetilde O\left(\sqrt\frac{d}{T}\right)$ in $\mathcal{H}_2$ error, with only logarithmic, rather than polynomial dependence on memory length. We also give bounds under process noise and improved bounds for learning a realization of the system. Our algorithm is based on multi-scale low-rank approximation: SVD applied to Hankel matrices of geometrically increasing sizes. Our analysis relies on careful application of concentration bounds on the Fourier domain -- we give sharper concentration bounds for sample covariance of correlated inputs and for $\mathcal H_\infty$ norm estimation, which may be of independent interest.

We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. For every problem of the form $\operatorname{Holant}\left(f\mid =_3 \right)$, where $f$ is any integer-valued ternary symmetric constraint function on Boolean variables, we prove that it is either P-time computable or #P-hard, depending on an explicit criterion of $f$. The constraint function can take both positive and negative values, allowing for cancellations. The dichotomy extends easily to rational valued functions of the same type. In addition, we discover a new phenomenon: there is a set $\mathcal{F}$ with the property that for every $f \in \mathcal{F}$ the problem $\operatorname{Holant}\left(f\mid =_3 \right)$ is planar P-time computable but #P-hard in general, yet its planar tractability is by a combination of a holographic transformation by $\left[\begin{smallmatrix} 1 & 1 \\ 1 & -1 \end{smallmatrix}\right]$ to FKT together with an independent global argument.

We consider deterministic algorithms for the well-known hidden subgroup problem ($\mathsf{HSP}$): for a finite group $G$ and a finite set $X$, given a function $f:G \to X$ and the promise that for any $g_1, g_2 \in G, f(g_1) = f(g_2)$ iff $g_1H=g_2H$ for a subgroup $H \le G$, the goal of the decision version is to determine whether $H$ is trivial or not, and the goal of the identification version is to identify $H$. An algorithm for the problem should query $f(g)$ for $g\in G$ at least as possible. Nayak \cite{Nayak2021} asked whether there exist deterministic algorithms with $O(\sqrt{\frac{|G|}{|H|}})$ query complexity for $\mathsf{HSP}$. We answer this problem by proving the following results, which also extend the main results of Ref. [30], since here the algorithms do not rely on any prior knowledge of $H$. (i)When $G$ is a general finite Abelian group, there exist an algorithm with $O(\sqrt{\frac{|G|}{|H|}})$ queries to decide the triviality of $H$ and an algorithm to identify $H$ with $O(\sqrt{\frac{|G|}{|H|}\log |H|}+\log |H|)$ queries. (ii)In general there is no deterministic algorithm for the identification version of $\mathsf{HSP}$ with query complexity of $O(\sqrt{\frac{|G|}{|H|}})$, since there exists an instance of $\mathsf{HSP}$ that needs $\omega(\sqrt{\frac{|G|}{|H|}})$ queries to identify $H$.\footnote{$f(x)$ is said to be $\omega(g(x))$ if for every positive constant $C$, there exists a positive constant $N$ such that for $x>N$, $f(x)\ge C\cdot g(x)$, which means $g$ is a strict lower bound for $f$.} On the other hand, there exist instances of $\mathsf{HSP}$ with query complexity far smaller than $O(\sqrt{\frac{|G|}{|H|}})$, whose query complexity is $O(\log \frac{|G|}{|H|})$ and even $O(1)$.

Complex valued systems with an indefinite matrix term arise in important applications such as for certain time-harmonic partial differential equations such as the Maxwell's equation and for the Helmholtz equation. Complex systems with symmetric positive definite matrices can be solved readily by rewriting the complex matrix system in two-by-two block matrix form with real matrices which can be efficiently solved by iteration using the preconditioned square block (PRESB) preconditioning method and preferably accelerated by the Chebyshev method. The appearances of an indefinite matrix term causes however some difficulties. To handle this we propose different forms of matrix splitting methods, with or without any parameters involved. A matrix spectral analyses is presented followed by extensive numerical comparisons of various forms of the methods.

We study the problem of maximizing the probability that (i) an electric component or financial institution $X$ does not default before another component or institution $Y$ and (ii) that $X$ and $Y$ default jointly within the class of all random variables $X,Y$ with given univariate continuous distribution functions $F$ and $G$, respectively, and show that the maximization problems correspond to finding copulas maximizing the mass of the endograph $\Gamma^\leq(T)$ and the graph $\Gamma(T)$ of $T=G \circ F^-$, respectively. After providing simple, copula-based proofs for the existence of copulas attaining the two maxima $\overline{m}_T$ and $\overline{w}_T$ we generalize the obtained results to the case of general (not necessarily monotonic) transformations $T:[0,1] \rightarrow [0,1]$ and derive simple and easily calculable formulas for $\overline{m}_T$ and $\overline{w}_T$ involving the distribution function $F_T$ of $T$ (interpreted as random variable on $[0,1]$). The latter are then used to charac\-terize all non-decreasing transformations $T:[0,1] \rightarrow [0,1]$ for which $\overline{m}_T$ and $\overline{w}_T$ coincide. A strongly consistent estimator for the maximum probability that $X$ does not default before $Y$ is derived and proven to be asymptotically normal under very mild regularity conditions. Several examples and graphics illustrate the main results and falsify some seemingly natural conjectures.

We discuss estimating the probability that the sum of nonnegative independent and identically distributed random variables falls below a given threshold, i.e., $\mathbb{P}(\sum_{i=1}^{N}{X_i} \leq \gamma)$, via importance sampling (IS). We are particularly interested in the rare event regime when $N$ is large and/or $\gamma$ is small. The exponential twisting is a popular technique for similar problems that, in most cases, compares favorably to other estimators. However, it has some limitations: i) it assumes the knowledge of the moment generating function of $X_i$ and ii) sampling under the new IS PDF is not straightforward and might be expensive. The aim of this work is to propose an alternative IS PDF that approximately yields, for certain classes of distributions and in the rare event regime, at least the same performance as the exponential twisting technique and, at the same time, does not introduce serious limitations. The first class includes distributions whose probability density functions (PDFs) are asymptotically equivalent, as $x \rightarrow 0$, to $bx^{p}$, for $p>-1$ and $b>0$. For this class of distributions, the Gamma IS PDF with appropriately chosen parameters retrieves approximately, in the rare event regime corresponding to small values of $\gamma$ and/or large values of $N$, the same performance of the estimator based on the use of the exponential twisting technique. In the second class, we consider the Log-normal setting, whose PDF at zero vanishes faster than any polynomial, and we show numerically that a Gamma IS PDF with optimized parameters clearly outperforms the exponential twisting IS PDF. Numerical experiments validate the efficiency of the proposed estimator in delivering a highly accurate estimate in the regime of large $N$ and/or small $\gamma$.