Singular limits for Liouville-type equations on the flat two-torus

We consider the problem $$\begin{aligned} -\Delta u=\varepsilon ^{2}e^{u}- \frac{1}{|\Omega |}\int _\Omega \varepsilon ^{2} e^{u}+ {4\pi N\over |\Omega |} - 4 \pi N\delta _p, \quad \text{ in} {\Omega }, \quad \int _\Omega u=0 \end{aligned}$$ in a flat two-torus $\Omega $ with periodic boundary conditions, where $\varepsilon >0,\,|\Omega |$ is the area of the $\Omega $ , $N>0$ and $\delta _p$ is a Dirac mass at $p\in \Omega $ . We prove that if $1\le m<N+1$ then there exists a family of solutions $\{u_\varepsilon \}_{\varepsilon }$ such that $\varepsilon ^{2}e^{u_\varepsilon }\rightharpoonup 8\pi \sum _{i=1}^m\delta _{q_i}$ as $\varepsilon \rightarrow 0$ in measure sense for some different points $q_{1}, \ldots , q_{m}$ . Furthermore, points $q_i$ , $i=1,\dots ,m$ are different from $p$ .     

Tunneling for a Class of Difference Operators

We analyze a general class of difference operators ${H_\varepsilon = T_\varepsilon + V_\varepsilon}$ on ${\ell^2((\varepsilon \mathbb {Z})^d)}$ where ${V_\varepsilon}$ is a multi-well potential and ${\varepsilon}$ is a small parameter. We decouple the wells by introducing certain Dirichlet operators on regions containing only one potential well, and we shall treat the eigenvalue problem for ${H_\varepsilon}$ as a small perturbation of these comparison problems. We describe tunneling by a certain interaction matrix, similar to the analysis for the Schr?dinger operator [see Helffer and Sj?strand in Commun Partial Differ Equ 9:337–408, 1984], and estimate the remainder, which is exponentially small and roughly quadratic compared with the interaction matrix.     

Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function

In this paper we develop a randomized block-coordinate descent method for minimizing the sum of a smooth and a simple nonsmooth block-separable convex function and prove that it obtains an $\varepsilon $ -accurate solution with probability at least $1-\rho $ in at most $O((n/\varepsilon ) \log (1/\rho ))$ iterations, where $n$ is the number of blocks. This extends recent results of Nesterov (SIAM J Optim 22(2): 341–362, 2012), which cover the smooth case, to composite minimization, while at the same time improving the complexity by the factor of 4 and removing $\varepsilon $ from the logarithmic term. More importantly, in contrast with the aforementioned work in which the author achieves the results by applying the method to a regularized version of the objective function with an unknown scaling factor, we show that this is not necessary, thus achieving first true iteration complexity bounds. For strongly convex functions the method converges linearly. In the smooth case we also allow for arbitrary probability vectors and non-Euclidean norms. Finally, we demonstrate numerically that the algorithm is able to solve huge-scale $\ell _1$ -regularized least squares problems with a billion variables.     

A gaussian estimate for the heat kernel on differential forms and application to the Riesz transform

Let $(M,g)$ be a complete Riemannian manifold which satisfies a Sobolev inequality of dimension $n$ , and on which the volume growth is comparable to the one of ${\mathbb{R }}^n$ for big balls; if there is no non-zero $L^2$ harmonic 1-form, and the Ricci tensor is in $L^{\frac{n}{2}-\varepsilon }\cap L^\infty $ for an $\varepsilon >0$ , then we prove a Gaussian estimate on the heat kernel of the Hodge Laplacian acting on 1-forms. This allows us to prove that, under the same hypotheses, the Riesz transform $d\varDelta ^{-1/2}$ is bounded on $L^p$ for all $1<p<\infty $ . Then, in presence of non-zero $L^2$ harmonic 1-forms, we prove that the Riesz transform is still bounded on $L^p$ for all $1<p<n$ , when $n>3$ .     

An approach to constrained global optimization based on exact penalty functions

In the field of global optimization many efforts have been devoted to solve unconstrained global optimization problems. The aim of this paper is to show that unconstrained global optimization methods can be used also for solving constrained optimization problems, by resorting to an exact penalty approach. In particular, we make use of a non-differentiable exact penalty function ${P_q(x;\varepsilon)}$ . We show that, under weak assumptions, there exists a threshold value ${\bar \varepsilon >0 }$ of the penalty parameter ${\varepsilon}$ such that, for any ${\varepsilon \in (0, \bar \varepsilon]}$ , any global minimizer of P _q is a global solution of the related constrained problem and conversely. On these bases, we describe an algorithm that, by combining an unconstrained global minimization technique for minimizing P _q for given values of the penalty parameter ${\varepsilon}$ and an automatic updating of ${\varepsilon}$ that occurs only a finite number of times, produces a sequence {x ^k } such that any limit point of the sequence is a global solution of the related constrained problem. In the algorithm any efficient unconstrained global minimization technique can be used. In particular, we adopt an improved version of the DIRECT algorithm. Some numerical experimentation confirms the effectiveness of the approach.     

Sharp geometric rigidity of isometries on Heisenberg groups

We prove sharp geometric rigidity estimates for isometries on Heisenberg groups. Our main result asserts that every $(1+\varepsilon )$ -quasi-isometry on a John domain of the Heisenberg group $\mathbb H ^n, n>1,$ is close to some isometry up to proximity order $\sqrt{\varepsilon }+\varepsilon $ in the uniform norm, and up to proximity order $\varepsilon $ in the $L_p^1$ -norm. We give examples showing the asymptotic sharpness of our results.     

Normal generation and \ell ^2-Betti numbers of groups

The normal rank of a group is the minimal number of elements whose normal closure coincides with the group. We study the relation between the normal rank of a group and its first $\ell ^2$ -Betti number and conjecture the inequality $\beta _1^{(2)}(G) \le \mathrm{nrk}(G)-1$ for torsion free groups. The conjecture is proved for limits of left-orderable amenable groups. On the other hand, for every $n\ge 2$ and every $\varepsilon >0$ , we give an example of a simple group $Q$ (with torsion) such that $\beta _1^{(2)}(Q) \ge n-1-\varepsilon $ . These groups also provide examples of simple groups of rank exactly $n$ for every $n\ge 2$ ; existence of such examples for $n> 3$ was unknown until now.     

A mean field model for a class of garbage collection algorithms in flash-based solid state drives

Garbage collection (GC) algorithms play a key role in reducing the write amplification in flash-based solid state drives, where the write amplification affects the lifespan and speed of the drive. This paper introduces a mean field model to assess the write amplification and the distribution of the number of valid pages per block for a class $\mathcal {C}$ of GC algorithms. Apart from the Random GC algorithm, class $\mathcal {C}$ includes two novel GC algorithms: the $d$ -Choices GC algorithm, that selects $d$ blocks uniformly at random and erases the block containing the least number of valid pages among the $d$ selected blocks, and the Random++ GC algorithm, that repeatedly selects another block uniformly at random until it finds a block with a lower than average number of valid blocks. Using simulation experiments, we show that the proposed mean field model is highly accurate in predicting the write amplification (for drives with $N=50{,}000$ blocks). We further show that the $d$ -Choices GC algorithm has a write amplification close to that of the Greedy GC algorithm even for small $d$ values, e.g., $d = 10$ , and offers a more attractive trade-off between its simplicity and its performance than the Windowed GC algorithm introduced and analyzed in earlier studies. The Random++ algorithm is shown to be less effective as it is even inferior to the FIFO algorithm when the number of pages $b$ per block is large (e.g., for $b \ge 64$ ).     

On Extending {\mathcal{A}}-Modules Through the Coefficients

In classical linear algebra, extending the ring of scalars of a free module gives rise to a new free module containing an isomorphic copy of the former and satisfying a certain universal property. Also, given two free modules on the same ring of scalars and a morphism between them, enlarging the ring of scalars results in obtaining a new morphism having the nice property that it coincides with the initial map on the isomorphic copy of the initial free module in the new one. We investigate these problems in the category of free ${\mathcal{A}}$ -modules, where ${\mathcal{A}}$ is an ${\mathbb{R}}$ -algebra sheaf. Complexification of free ${\mathcal{A}}$ -modules, which is defined to be the process of obtaining new free ${\mathcal{A}}$ -modules by enlarging the ${\mathbb{R}}$ -algebra sheaf ${\mathcal{A}}$ to a ${\mathbb{C}}$ -algebra sheaf, denoted ${\mathcal{A}_\mathbb{C}}$ , is an important particular case (see Proposition 2.1, Proposition 3.1). Attention, on the one hand, is drawn on the sub- ${_{\mathbb{R}}\mathcal{A}}$ -sheaf of almost complex structures on the sheaf ${{_\mathbb{R}}\mathcal{A}^{2n}}$ , the underlying ${\mathbb{R}}$ -algebra sheaf of a ${\mathbb{C}}$ -algebra sheaf ${\mathcal{A}}$ , and on the other hand, on the complexification of the functor ${\mathcal{H}om_\mathcal {A}}$ , with ${\mathcal{A}}$ an ${\mathbb{R}}$ -algebra sheaf.     

Convergence rate of the Allen-Cahn equation to generalized motion by mean curvature

We investigate the singular limit, as ${\varepsilon \to 0}$ , of the Allen-Cahn equation ${u^\varepsilon_t=\Delta u^\varepsilon+\varepsilon^{-2}f(u^\varepsilon)}$ , with f a balanced bistable nonlinearity. We consider rather general initial data u ₀ that is independent of ${{\varepsilon}}$ . It is known that this equation converges to the generalized motion by mean curvature ?? in the sense of viscosity solutions??defined by Evans, Spruck and Chen, Giga, Goto. However, the convergence rate has not been known. We prove that the transition layers of the solutions ${u^{\varepsilon}}$ are sandwiched between two sharp ??interfaces?? moving by mean curvature, provided that these ??interfaces?? sandwich at t?=?0 an ${\mathcal O({\varepsilon}|\,{\rm ln}\,{\varepsilon}|)}$ neighborhood of the initial layer. In some special cases, which allow both extinction and pinches off phenomenon, this enables to obtain an ${\mathcal O({\varepsilon}|\,{\rm ln}\,{\varepsilon}|)}$ estimate of the location and the thickness measured in space-time of the transition layers. A result on the regularity of the generalized motion by mean curvature is also provided in the Appendix.     

Admissible closures of polynomial time computable arithmetic

We propose two admissible closures ${\mathbb{A}({\sf PTCA})}$ and ${\mathbb{A}({\sf PHCA})}$ of Ferreira??s system PTCA of polynomial time computable arithmetic and of full bounded arithmetic (or polynomial hierarchy computable arithmetic) PHCA. The main results obtained are: (i) ${\mathbb{A}({\sf PTCA})}$ is conservative over PTCA with respect to ${\forall\exists\Sigma^b_1}$ sentences, and (ii) ${\mathbb{A}({\sf PHCA})}$ is conservative over full bounded arithmetic PHCA for ${\forall\exists\Sigma^b_{\infty}}$ sentences. This yields that (i) the ${\Sigma^b_1}$ definable functions of ${\mathbb{A}({\sf PTCA})}$ are the polytime functions, and (ii) the ${\Sigma^b_{\infty}}$ definable functions of ${\mathbb{A}({\sf PHCA})}$ are the functions in the polynomial time hierarchy.     

On the Neumann problem for PDE’s with a small parameter and the corresponding diffusion processes

The diffusion process in a region ${G \subset \mathbb R^2}$ governed by the operator ${\tilde L^\varepsilon = \frac{\,1}{\,2}\, u_{xx} + \frac1 {2\varepsilon}\, u_{zz}}$ inside the region and undergoing instantaneous co-normal reflection at the boundary is considered. We show that the slow component of this process converges to a diffusion process on a certain graph corresponding to the problem. This allows to find the main term of the asymptotics for the solution of the corresponding Neumann problem in G. The operator ${\tilde L^\varepsilon}$ is, up to the factor ε ^{? 1}, the result of small perturbation of the operator ${\frac{\,1}{\,2}\, u_{zz}}$ . Our approach works for other operators (diffusion processes) in any dimension if the process corresponding to the non-perturbed operator has a first integral, and the ε-process is non-degenerate on non-singular level sets of this first integral.     

[1,1,t]-Colorings of Complete Graphs

Given non-negative integers $r, s,$ and $t,$ an $[r,s,t]$ -coloring of a graph $G = (V(G),E(G))$ is a mapping $c$ from $V(G) \cup E(G)$ to the color set $\{1,\ldots ,k\}$ such that $\left|c(v_i) - c(v_j)\right| \ge r$ for every two adjacent vertices $v_i,v_j, \left|c({e_i}) - c(e_j)\right| \ge s$ for every two adjacent edges $e_i,e_j,$ and $\left|c(v_i) - c(e_j)\right| \ge t$ for all pairs of incident vertices and edges, respectively. The $[r,s,t]$ -chromatic number $\chi _{r,s,t}(G)$ of $G$ is defined to be the minimum $k$ such that $G$ admits an $[r,s,t]$ -coloring. In this note we examine $\chi _{1,1,t}(K_p)$ for complete graphs $K_p.$ We prove, among others, that $\chi _{1,1,t}(K_p)$ is equal to $p+t-2+\min \{p,t\}$ whenever $t \ge \left\lfloor {\frac{p}{2}}\right\rfloor -1,$ but is strictly larger if $p$ is even and sufficiently large with respect to $t.$ Moreover, as $p \rightarrow \infty $ and $t=t(p),$ we asymptotically have $\chi _{1,1,t}(K_p)=p+o(p)$ if and only if $t=o(p).$      

Stability results for the N-dimensional Schiffer conjecture via a perturbation method

Given a eigenvalue $\mu _{0m}^2$ of $-\Delta $ in the unit ball $B_1$ , with Neumann boundary conditions, we prove that there exists a class $\mathcal{D}$ of $C^{0,1}$ -domains, depending on $\mu _{0m} $ , such that if $u$ is a no trivial solution to the following problem $ \Delta u+\mu u=0$ in $\Omega , u=0$ on $\partial \Omega $ , and $ \int \nolimits _{\partial \Omega }\partial _{\mathbf{n}}u=0$ , with $\Omega \in \mathcal{D}$ , and $\mu =\mu _{0m}^2+o(1)$ , then $\Omega $ is a ball. Here $\mu $ is a eigenvalue of $-\Delta $ in $\Omega $ , with Neumann boundary conditions.     

Asymptotic analysis of a second-order singular perturbation model for phase transitions

We study the asymptotic behavior, as ${\varepsilon}$ tends to zero, of the functionals ${F^k_\varepsilon}$ introduced by Coleman and Mizel in the theory of nonlinear second-order materials; i.e., $$F^k_\varepsilon(u):=\int\limits_{I} \left(\frac{W(u)}{\varepsilon}-k\,\varepsilon\,(u')^2+\varepsilon^3(u'')^2\right)\,dx,\quad u\in W^{2,2}(I),$$ where k?>?0 and ${W:\mathbb{R}\to[0,+\infty)}$ is a double-well potential with two potential wells of level zero at ${a,b\in\mathbb{R}}$ . By proving a new nonlinear interpolation inequality, we show that there exists a positive constant k ₀ such that, for k?<?k ₀, and for a class of potentials W, ${(F^k_\varepsilon)}$ ??(L ¹)-converges to $$F^k(u):={\bf m}_k \, \#(S(u)),\quad u\in BV(I;\{a,b\}),$$ where m _k is a constant depending on W and k. Moreover, in the special case of the classical potential ${W(s)=\frac{(s^2-1)^2}{2}}$ , we provide an upper bound on the values of k such that the minimizers of ${F_\varepsilon^k}$ cannot develop oscillations on some fine scale and a lower bound on the values for which oscillations occur, the latter improving a previous estimate by Mizel, Peletier and Troy.     

First-order algorithm with {\mathcal{O}({\rm ln}(1{/}\epsilon))} convergence for {\epsilon}-equilibrium in two-person zero-sum games

We propose an iterated version of Nesterov’s first-order smoothing method for the two-person zero-sum game equilibrium problem $$\min_{x \in Q_1}\max_{y \in Q_2} {x}^{\rm T}{Ay} = \max_{y \in Q_2} \min_{x \in Q_1} {x}^{\rm T}{Ay}.$$ This formulation applies to matrix games as well as sequential games. Our new algorithmic scheme computes an ${\epsilon}$ -equilibrium to this min-max problem in ${\mathcal {O}\left(\frac{\|A\|}{\delta(A)} \, {\rm ln}(1{/}\epsilon)\right)}$ first-order iterations, where δ(A) is a certain condition measure of the matrix A. This improves upon the previous first-order methods which required ${\mathcal {O}(1{/}\epsilon)}$ iterations, and it matches the iteration complexity bound of interior-point methods in terms of the algorithm’s dependence on ${\epsilon}$ . Unlike interior-point methods that are inapplicable to large games due to their memory requirements, our algorithm retains the small memory requirements of prior first-order methods. Our scheme supplements Nesterov’s method with an outer loop that lowers the target ${\epsilon}$ between iterations (this target affects the amount of smoothing in the inner loop). Computational experiments both in matrix games and sequential games show that a significant speed improvement is obtained in practice as well, and the relative speed improvement increases with the desired accuracy (as suggested by the complexity bounds).     

Dimension Reduction for Finite Trees in \varvec{\ell _1}

We show that every $n$ -point tree metric admits a $(1+\varepsilon )$ -embedding into $\ell _1^{C(\varepsilon ) \log n}$ , for every $\varepsilon > 0$ , where $C(\varepsilon ) \le O\big ((\frac{1}{\varepsilon })^4 \log \frac{1}{\varepsilon })\big )$ . This matches the natural volume lower bound up to a factor depending only on $\varepsilon $ . Previously, it was unknown whether even complete binary trees on $n$ nodes could be embedded in $\ell _1^{O(\log n)}$ with $O(1)$ distortion. For complete $d$ -ary trees, our construction achieves $C(\varepsilon ) \le O\big (\frac{1}{\varepsilon ^2}\big )$ .     

LIM is not slim

In this paper LIM, a recently proposed impartial combinatorial ruleset, is analyzed. A formula to describe the $\mathcal G $ -values of LIM positions is given, by way of analyzing an equivalent combinatorial ruleset LIM’, closely related to the classical nim. Also, an enumeration of $\mathcal P $ -positions of LIM with $n$ stones, and its relation to the Ulam-Warburton cellular automaton, is presented.     

Finite groups with \mathbb{P }-subnormal subgroups

A subgroup $H$ of a group $G$ is called $\mathbb{P }$ -subnormal in $G$ whenever either $H=G$ or there is a chain of subgroups $H=H_0\subset H_1\subset \cdots \subset H_n=G$ such that $|H_i:H_{i-1}|$  is a prime for all $i$ . In this paper we study groups with $\mathbb{P }$ -subnormal 2-maximal subgroups, and groups with $\mathbb{P }$ -subnormal primary cyclic subgroups.