Search

Let $\Gamma$ be a finitely generated discrete exact group. We consider operators on $l^2(\Gamma)$ which are composed by operators of multiplication by a function in $l^\infty (\Gamma)$ and by the operators of left-shift by elements of $\Gamma$. These operators generate a $C^*$-subalgebra of $L(l^2(\Gamma))$ the elements of which we call band-dominated operators on $\Gamma$. We study the stability of the finite sections method for band-dominated operators with respect to a given generating system of $\Gamma$. Our approach is based on the equivalence of the stability of a sequence and the Fredholmness of an associated operator, and on Roe's criterion for the Fredholmness of a band-dominated operator on a exact discrete group, which we formulate in terms of limit operators. Special emphasis is paid to the quasicommutator ideal of the algebra generated by the finite sections sequences and to the stability of sequences in that algebra. For both problems, the sequence of the discrete boundaries plays an essential role.

The aim of this paper is to derive Agmon's type exponential estimates for solutions of elliptic systems of partial differential equations on $\sR^n$. We show that these estimates are related with the essential spectra of a family of associated differential operators which depend on the original operator, and with exponential weights which describe the decrease of solutions at infinity. The essential spectra of the involved operators are described by means of their limit operators. The obtained results are applied to study the problem of exponential decay of eigenfunctions of matrix Schr\"{o}dinger, Moisil-Theodorescu, and Dirac operators., Comment: 19 pages

Let $(\cX, \rho)$ be a discrete metric space. We suppose that the group $\sZ^n$ acts freely on $X$ and that the number of orbits of $X$ with respect to this action is finite. Then we call $X$ a $\sZ^n$-periodic discrete metric space. We examine the Fredholm property and essential spectra of band-dominated operators on $l^p(X)$ where $X$ is a $\sZ^n$-periodic discrete metric space. Our approach is based on the theory of band-dominated operators on $\sZ^n$ and their limit operators. In case $X$ is the set of vertices of a combinatorial graph, the graph structure defines a Schr\"{o}dinger operator on $l^p(X)$ in a natural way. We illustrate our approach by determining the essential spectra of Schr\"{o}dinger operators with slowly oscillating potential both on zig-zag and on hexagonal graphs, the latter being related to nano-structures.

In a recent breakthrough, [Bshouty et al., 2005] obtained the first passive-learning algorithm for DNFs under the uniform distribution. They showed that DNFs are learnable in the Random Walk and Noise Sensitivity models. We extend their results in several directions. We first show that thresholds of parities, a natural class encompassing DNFs, cannot be learned efficiently in the Noise Sensitivity model using only statistical queries. In contrast, we show that a cyclic version of the Random Walk model allows to learn efficiently polynomially weighted thresholds of parities. We also extend the algorithm of Bshouty et al. to the case of Unions of Rectangles, a natural generalization of DNFs to $\{0,...,b-1\}^n$.

Maximum likelihood is one of the most widely used techniques to infer evolutionary histories. Although it is thought to be intractable, a proof of its hardness has been lacking. Here, we give a short proof that computing the maximum likelihood tree is NP-hard by exploiting a connection between likelihood and parsimony observed by Tuffley and Steel., Comment: 6 pages; Corrected typos and notational problem

We consider the problem of maximizing the revenue raised from tolls set on the arcs of a transportation network, under the constraint that users are assigned to toll-compatible shortest paths. We first prove that this problem is strongly NP-hard. We then provide a polynomial time algorithm with a worst-case precision guarantee of ${1/2}\log_2 m_T+1$, where $m_T$ denotes the number of toll arcs. Finally we show that the approximation is tight with respect to a natural relaxation by constructing a family of instances for which the relaxation gap is reached., Comment: 38 pages

In a series of recent works, Boyd, Diaconis, and their co-authors have introduced a semidefinite programming approach for computing the fastest mixing Markov chain on a graph of allowed transitions, given a target stationary distribution. In this paper, we show that standard mixing-time analysis techniques--variational characterizations, conductance, canonical paths--can be used to give simple, nontrivial lower and upper bounds on the fastest mixing time. To test the applicability of this idea, we consider several detailed examples including the Glauber dynamics of the Ising model--and get sharp bounds., Comment: 20 pages