Abstract:
We study a discrete Laplace operator $\Delta$ on percolation subgraphs of an infinite graph. The ball volume is assumed to grow at most polynomially. We are interested in the behavior of the integrated density of states near the lower spectral edge. If the graph is a Cayley graph we prove that it exhibits Lifshitz tails. If we merely assume that the graph has an exhausting sequence with positive $\delta$-dimensional density, we obtain an upper bound on the integrated density of states of Lifshitz type.

Abstract:
We study algorithmic randomness and monotone complexity on product of the set of infinite binary sequences. We explore the following problems: monotone complexity on product space, Lambalgen's theorem for correlated probability, classification of random sets by likelihood ratio tests, decomposition of complexity and independence, Bayesian statistics for individual random sequences. Formerly Lambalgen's theorem for correlated probability is shown under a uniform computability assumption in [H. Takahashi Inform. Comp. 2008]. In this paper we show the theorem without the assumption.

Abstract:
We compute the limiting distributions of the lengths of the longest monotone subsequences of random (signed) involutions with or without conditions on the number of fixed points (and negated points) as the sizes of the involutions tend to infinity. The resulting distributions are, depending on the number of fixed points, (1) the Tracy-Widom distributions for the largest eigenvalues of random GOE, GUE, GSE matrices, (2) the normal distribution, or (3) new classes of distributions which interpolate between pairs of the Tracy-Widom distributions. We also consider the second rows of the corresponding Young diagrams. In each case the convergence of moments is also shown. The proof is based on the algebraic work of the authors in \cite{PartI} which establishes a connection between the statistics of random involutions and a family of orthogonal polynomials, and an asymptotic analysis of the orthogonal polynomials which is obtained by extending the Riemann-Hilbert analysis for the orthogonal polynomials by Deift, Johansson and the first author in [BDJ].

Abstract:
Second order asymptotics of fixed-length source coding and intrinsic randomness is discussed with a constant error constraint. There was a difference between optimal rates of fixed-length source coding and intrinsic randomness, which never occurred in the first order asymptotics. In addition, the relation between uniform distribution and compressed data is discussed based on this fact. These results are valid for general information sources as well as independent and identical distributions. A universal code attaining the second order optimal rate is also constructed.

Abstract:
A network belongs to the monotone separable class if its state variables are homogeneous and monotone functions of the epochs of the arrival process. This framework contains several classical queueing network models, including generalized Jackson networks, max-plus networks, polling systems, multiserver queues, and various classes of stochastic Petri nets. We use comparison relationships between networks of this class with i.i.d. driving sequences and the $GI /GI /1/1$ queue to obtain the tail asymptotics of the stationary maximal dater under light-tailed assumptions for service times. The exponential rate of decay is given as a function of a logarithmic moment generating function. We exemplify an explicit computation of this rate for the case of queues in tandem under various stochastic assumptions.

Abstract:
The survival problem for a diffusing particle moving among random traps is considered. We introduce a simple argument to derive the quenched asymptotics of the survival probability from the Lifshitz tail effect for the associated operator. In particular, the upper bound is proved in fairly general settings and is shown to be sharp in the case of the Brownian motion in the Poissonian obstacles. As an application, we derive the quenched asymptotics for the Brownian motion in traps distributed according to a random perturbation of the lattice.

Abstract:
In this paper we study spectral properties of adjacency and Laplace operators on percolation subgraphs of Cayley graphs of amenable, finitely generated groups. In particular we describe the asymptotic behaviour of the integrated density of states (spectral distribution function) of these random Hamiltonians near the spectral minimum. The first part of the note discusses various aspects of the quantum percolation model, subsequently we formulate a series of new results, and finally we outline the strategy used to prove our main theorem.

Abstract:
We consider 4-dimensional space-times which are asymptotically flat at spatial infinity and show that, in the first order framework, action principle for general relativity is well-defined \emph{without the need of infinite counter terms.} It naturally leads to a covariant phase space in which the Hamiltonians generating asymptotic symmetries provide the total energy-momentum and angular momentum of the space-time. We address the subtle but important problems that arise because of logarithmic translations and super-translations both in the Langrangian and Hamiltonian frameworks. As a forthcoming paper will show, the treatment of higher dimensions is considerably simpler. Our first order framework also suggests a new direction for generalizing the spectral action of non-commutative geometry.

Abstract:
Here we present in a single essay a combination and completion of the several aspects of the problem of randomness of individual objects which of necessity occur scattered in our texbook "An Introduction to Kolmogorov Complexity and Its Applications" (M. Li and P. Vitanyi), 2nd Ed., Springer-Verlag, 1997.

Abstract:
We consider the Hamiltonian of a system of three quantum mechanical particles on the three-dimensional lattice $\Z^3$ interacting via short-range pair potentials. We prove for the two-particle energy operator $h(k),$ $k\in \T^3$ the two-particle quasi-momentum, the existence of a unique positive eigenvalue $z(k)$ lying below the essential spectrum under assumption that the operator $h(0)$ corresponding to the zero value of $k$ has a zero energy resonance. We describe the location of the essential spectrum of the three-particle discrete Schr\"{o}dinger operators $H(K)$,$K$ the three-particle quasi-momentum by the spectra of $h(k), k\in \T^3.$ We prove the existence of infinitely many eigenvalues of H(0) and establish for the number of eigenvalues $N(0,z)$ lying below $z<0$ the asymptotics \begin{equation*}\label{asimz} \lim\limits_{z \to -0}\frac{N(0,z)}{|\log |z||}=\frac{\lambda_0}{2\pi}, \end{equation*} where $\lambda_0$ a unique positive solution of the equation $$ \lambda = \frac{8 \sinh \pi\lambda /6}{\sqrt 3 \cosh \pi\lambda/2}.$$ We prove that for all $ K \in U_\delta^0(0),$ where $U_\delta^0(0)$ some punctured $\delta >0$ neighborhood of the origin, the number $N(K,0)$ of eigenvalues the operator $H(K)$ below zero is finite and satisfy the asymptotics \begin{equation*}\label{asimk} \lim\limits_{|K| \to 0}\frac{N(K,0)}{|\log |K||}=\frac{\lambda_0}{\pi}. \end{equation*}