Via a Dirichlet form extension theorem and making full use of two-sided heat kernel estimates, we establish quenched invariance principles for ran- dom walks in random environments with a boundary. In particular, we prove that the random walk on a supercritical percolation cluster or among random conductances bounded uniformly from below in a half-space, quarter-space, etc., converges when rescaled diffusively to a reflecting Brownian motion, which has been one of the important open problems in this area. We establish a similar result for the random conductance model in a box, which allows us to improve existing asymptotic estimates for the relevant mixing time. Furthermore, in the uniformly elliptic case, we present quenched invariance prin- ciples for domains with more general boundaries.

No abstract uploaded!

In this paper, we show that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $\sqrt{n}$. This result is best possible, and improves a logarithmic lower bound shown by Chung, F\"uredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

An open subset$D$of$R$^{$d$},$d≧2$, is called Poissonian iff every bounded harmonic function on the set is a Poisson integral of a bounded function on its boundary. We show that the intersection of two Poissonian open sets is itself Poissonian and give a sufficient condition for the union of two Poissonian open sets to be Poissonian. Some necessary and sufficient conditions for an open set to be Poissonian are also given. In particular, we give a necessary and sufficient condition for a Greenian$D$to be Poissonian in terms of its Martin boundary.

No abstract uploaded!