We consider the solution of large-scale discrete-time algebraic Riccati equations with numerically low-ranked solutions. The structure-preserving doubling algorithm will be adapted, with the iterates for A not explicitly computed but in the recursive form Ak= A2 k 1 D (1) k

We prove a Harnack inequality for positive harmonic functions on graphs which is similar to a classical result of Yau on Riemannian manifolds. Also, we prove a mean value inequality of nonnegative subharmonic functions on graphs.

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.

Suppose G is a reductive algebraic group, T is a Cartan subgroup of G, N= Norm (T), and W= N/T is the Weyl group. If w W has order d, it is natural to ask about the orders lifts of w to N. It is straightforward to see that the minimal order of a lift of w has order d or 2d, but it can be a subtle question which holds. We first consider the question of when W itself lifts to a subgroup of N (in which case every element of W lifts to an element of N of the same order). We then consider two natural classes of elements: regular and elliptic. In the latter case all lifts of w are conjugate, and therefore have the same order. We also consider the twisted case.