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

It is proven that a conjecture of Tao (2010) holds true for log-concave random variables on the integers: For every $n \geq 1$, if $X_1,\ldots,X_n$ are i.i.d. integer-valued, log-concave random variables, then $$ H(X_1+\cdots+X_{n+1}) \geq H(X_1+\cdots+X_{n}) + \frac{1}{2}\log{\Bigl(\frac{n+1}{n}\Bigr)} - o(1) $$ as $H(X_1) \to \infty$, where $H$ denotes the (discrete) Shannon entropy. The problem is reduced to the continuous setting by showing that if $U_1,\ldots,U_n$ are independent continuous uniforms on $(0,1)$, then $$ h(X_1+\cdots+X_n + U_1+\cdots+U_n) = H(X_1+\cdots+X_n) + o(1) $$ as $H(X_1) \to \infty$, where $h$ stands for the differential entropy. Explicit bounds for the $o(1)$-terms are provided.

A 2-packing set for an undirected graph $G=(V,E)$ is a subset $\mathcal{S} \subset V$ such that any two vertices $v_1,v_2 \in \mathcal{S}$ have no common neighbors. Finding a 2-packing set of maximum cardinality is a NP-hard problem. We develop a new approach to solve this problem on arbitrary graphs using its close relation to the independent set problem. Thereby, our algorithm red2pack uses new data reduction rules specific to the 2-packing set problem as well as a graph transformation. Our experiments show that we outperform the state-of-the-art for arbitrary graphs with respect to solution quality and also are able to compute solutions multiple orders of magnitude faster than previously possible. For example, we are able to solve 63% of our graphs to optimality in less than a second while the competitor for arbitrary graphs can only solve 5% of the graphs in the data set to optimality even with a 10 hour time limit. Moreover, our approach can solve a wide range of large instances that have previously been unsolved.

The deletion distance between two binary words $u,v \in \{0,1\}^n$ is the smallest $k$ such that $u$ and $v$ share a common subsequence of length $n-k$. A set $C$ of binary words of length $n$ is called a $k$-deletion code if every pair of distinct words in $C$ has deletion distance greater than $k$. In 1965, Levenshtein initiated the study of deletion codes by showing that, for $k\ge 1$ fixed and $n$ going to infinity, a $k$-deletion code $C\subseteq \{0,1\}^n$ of maximum size satisfies $\Omega_k(2^n/n^{2k}) \leq |C| \leq O_k( 2^n/n^k)$. We make the first asymptotic improvement to these bounds by showing that there exist $k$-deletion codes with size at least $\Omega_k(2^n \log n/n^{2k})$. Our proof is inspired by Jiang and Vardy's improvement to the classical Gilbert--Varshamov bounds. We also establish several related results on the number of longest common subsequences and shortest common supersequences of a pair of words with given length and deletion distance.

We present quantum algorithms for sampling from non-logconcave probability distributions in the form of $\pi(x) \propto \exp(-\beta f(x))$. Here, $f$ can be written as a finite sum $f(x):= \frac{1}{N}\sum_{k=1}^N f_k(x)$. Our approach is based on quantum simulated annealing on slowly varying Markov chains derived from unadjusted Langevin algorithms, removing the necessity for function evaluations which can be computationally expensive for large data sets in mixture modeling and multi-stable systems. We also incorporate a stochastic gradient oracle that implements the quantum walk operators inexactly by only using mini-batch gradients. As a result, our stochastic gradient based algorithm only accesses small subsets of data points in implementing the quantum walk. One challenge of quantizing the resulting Markov chains is that they do not satisfy the detailed balance condition in general. Consequently, the mixing time of the algorithm cannot be expressed in terms of the spectral gap of the transition density, making the quantum algorithms nontrivial to analyze. To overcome these challenges, we first build a hypothetical Markov chain that is reversible, and also converges to the target distribution. Then, we quantified the distance between our algorithm's output and the target distribution by using this hypothetical chain as a bridge to establish the total complexity. Our quantum algorithms exhibit polynomial speedups in terms of both dimension and precision dependencies when compared to the best-known classical algorithms.

We study the following characterization problem. Given a set $T$ of terminals and a $(2^{|T|}-2)$-dimensional vector $\pi$ whose coordinates are indexed by proper subsets of $T$, is there a graph $G$ that contains $T$, such that for all subsets $\emptyset\subsetneq S\subsetneq T$, $\pi_S$ equals the value of the min-cut in $G$ separating $S$ from $T\setminus S$? The only known necessary conditions are submodularity and a special class of linear inequalities given by Chaudhuri, Subrahmanyam, Wagner and Zaroliagis. Our main result is a new class of linear inequalities concerning laminar families, that generalize all previous ones. Using our new class of inequalities, we can generalize Karger's approximate min-cut counting result to graphs with terminals.

In 1986, Flagg and Friedman \cite{ff} gave an elegant alternative proof of the faithfulness of G\"{o}del translation $(\cdot)^\Box$ of Heyting arithmetic $\bf HA$ to Shapiro's epistemic arithmetic $\bf EA$. In \S 2, we shall prove the faithfulness of $(\cdot)^\Box$ without using stability, by introducing another translation from an epistemic system to corresponding intuitionistic system which we shall call \it the modified Rasiowa-Sikorski translation\rm . That is, this introduction of the new translation simplifies the original Flagg and Friedman's proof. In \S 3, we shall give some applications of the modified one for the disjunction property ($\mathsf{DP}$) and the numerical existence property ($\mathsf{NEP}$) of Heyting arithmetic. In \S 4, we shall show that epistemic Markov's rule $\mathsf{EMR}$ in $\bf EA$ is proved via $\bf HA$. So $\bf EA$ $\vdash \mathsf{EMR}$ and $\bf HA$ $\vdash \mathsf{MR}$ are equivalent. In \S 5, we shall give some relations among the translations treated in the previous sections. In \S 6, we shall give an alternative proof of Glivenko's theorem. In \S 7, we shall propose several (modal-)epistemic versions of Markov's rule for Horsten's modal-epistemic arithmetic $\bf MEA$. And, as in \S 4, we shall study some meta-implications among those versions of Markov's rules in $\bf MEA$ and one in $\bf HA$. Friedman and Sheard gave a modal analogue $\mathsf{FS}$ (i.e. Theorem in \cite{fs}) of Friedman's theorem $\mathsf{F}$ (i.e. Theorem 1 in \cite {friedman}): \it Any recursively enumerable extension of $\bf HA$ which has $\mathsf{DP}$ also has $\mathsf{NPE}$\rm . In \S 8, we shall propose a modified version of \it Fundamental Conjecture \rm $\mathsf{FC}$ ($\mathsf{FS} \Longrightarrow \mathsf{F}$) proposed by the author as $\Delta_0$-Fundamental Conjecture. In \S 9, I shall give some discussions and my philosophy.

We consider functions $f: \mathbb{Z} \to \mathbb{R}$ and kernels $u: \{-n, \cdots, n\} \to \mathbb{R}$ normalized by $\sum_{\ell = -n}^{n} u(\ell) = 1$, making the convolution $u \ast f$ a "smoother" local average of $f$. We identify which choice of $u$ most effectively smooths the second derivative in the following sense. For each $u$, basic Fourier analysis implies there is a constant $C(u)$ so $\|\Delta(u \ast f)\|_{\ell^2(\mathbb{Z})} \leq C(u)\|f\|_{\ell^2(\mathbb{Z})}$ for all $f: \mathbb{Z} \to \mathbb{R}$. By compactness, there is some $u$ that minimizes $C(u)$ and in this paper, we find explicit expressions for both this minimal $C(u)$ and the minimizing kernel $u$ for every $n$. The minimizing kernel is remarkably close to the Epanechnikov kernel in Statistics. This solves a problem of Kravitz-Steinerberger and an extremal problem for polynomials is solved as a byproduct.

We propose a volumetric formulation for computing the Optimal Transport problem defined on surfaces in $\mathbb{R}^3$, found in disciplines like optics, computer graphics, and computational methodologies. Instead of directly tackling the original problem on the surface, we define a new Optimal Transport problem on a thin tubular region, $T_{\epsilon}$, adjacent to the surface. This extension offers enhanced flexibility and simplicity for numerical discretization on Cartesian grids. The Optimal Transport mapping and potential function computed on $T_{\epsilon}$ are consistent with the original problem on surfaces. We demonstrate that, with the proposed volumetric approach, it is possible to use simple and straightforward numerical methods to solve Optimal Transport for $\Gamma = \mathbb{S}^2$.

We consider structured approximation of measures in Wasserstein space $W_p(\mathbb{R}^d)$ for $p\in[1,\infty)$ by discrete and piecewise constant measures based on a scaled Voronoi partition of $\mathbb{R}^d$. We show that if a full rank lattice $\Lambda$ is scaled by a factor of $h\in(0,1]$, then approximation of a measure based on the Voronoi partition of $h\Lambda$ is $O(h)$ regardless of $d$ or $p$. We then use a covering argument to show that $N$-term approximations of compactly supported measures is $O(N^{-\frac1d})$ which matches known rates for optimal quantizers and empirical measure approximation in most instances. Finally, we extend these results to noncompactly supported measures with sufficient decay.

We improve the previously best known upper bounds on the sizes of $\theta$-spherical codes for every $\theta<\theta^*\approx 62.997^{\circ}$ at least by a factor of $0.4325$, in sufficiently high dimensions. Furthermore, for sphere packing densities in dimensions $n\geq 2000$ we have an improvement at least by a factor of $0.4325+\frac{51}{n}$. Our method also breaks many non-numerical sphere packing density bounds in smaller dimensions. This is the first such improvement for each dimension since the work of Kabatyanskii and Levenshtein~\cite{KL} and its later improvement by Levenshtein~\cite{Leven79}. Novelties of this paper include the analysis of triple correlations, usage of the concentration of mass in high dimensions, and the study of the spacings between the roots of Jacobi polynomials.