The Spectral Theory of Amenable Actions and Invariants of Discrete Groups

Let G denote a semisimple group, a discrete subgroup, B=G/P the Poisson boundary. Regarding invariants of discrete subgroups we prove, in particular, the following:(1) For any -quasi-invariant measure on B, and any probablity measure on , the norm of the operator () on L ²(B,) is equal to (), where is the unitary representation in L ²(X,), and is the regular representation of .(2) In particular this estimate holds when is Lebesgue measure on B, a Patterson–Sullivan measure, or a -stationary measure, and implies explicit lower bounds for the displacement and Margulis number of (w.r.t. a finite generating set), the dimension of the conformal density, the -entropy of the measure, and Lyapunov exponents of .(3) In particular, when G=PSL₂() and is free, the new lower bound of the displacement is somewhat smaller than the Culler–Shalen bound (which requires an additional assumption) and is greater than the standard ball-packing bound.We also prove that ()=_G() for any amenable action of G and L ¹(G), and conversely, give a spectral criterion for amenability of an action of G under certain natural dynamical conditions. In addition, we establish a uniform lower bound for the -entropy of any measure quasi-invariant under the action of a group with property T, and use this fact to construct an interesting class of actions of such groups, related to 'virtual' maximal parabolic subgroups. Most of the results hold in fact in greater generality, and apply for instance when G is any semi-simple algebraic group, or when is any word-hyperbolic group, acting on their Poisson boundary, for example.     

Design of Stacked Self-Healing Rings Using a Genetic Algorithm

Ring structures in telecommunications are taking on increasing importance because of their self-healing properties. We consider a ring design problem in which several stacked self-healing rings (SHRs) follow the same route, and, thus, pass through the same set of nodes. Traffic can be exchanged among these stacked rings at a designated hub node. Each non-hub node may be connected to multiple rings. It is necessary to determine to which rings each node should be connected, and how traffic should be routed on the rings. The objective is to optimize the tradeoff between the costs for connecting nodes to rings and the costs for routing demand on multiple rings. We describe a genetic algorithm that finds heuristic solutions for this problem. The initial generation of solutions includes randomly-generated solutions, complemented by seed solutions obtained by applying a greedy randomized adaptive search procedure (GRASP) to two related problems. Subsequent generations are created by recombining pairs of parent solutions. Computational experiments compare the genetic algorithm with a commercial integer programming package.     

Discrete Series Characters for GL(n, q)

The discrete series characters of the finite general linear group GL(n, q) are expressed as uniquely defined integral linear combinations of characters induced from linear characters on certain subgroups Hd, n of GL(n, q). The coefficients in these linear combinations are determined (for all n, q) by a family of polynomials r(T) Z[T] indexed by the set of all partitions .     

Studying the Complexity of Global Verification for NP-Hard Discrete Optimization Problems

This paper examines the complexity of global verification for MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, and Traveling Salesman Problem. These results are obtained by adaptations of the transformations that prove such problems to be NP-complete. The class of problems PGS is defined to be those discrete optimization problems for which there exists a polynomial time algorithm such that given any solution , either a solution can be found with a better objective function value or it can be concluded that no such solution exists and is a global optimum. This paper demonstrates that if any one of MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, or Traveling Salesman Problem are in PGS, then P=NP.     

Une approche transformationnelle a l'algebre universelle

In this paper we propose an axiomatization of the notion of system of terms of a theory by means of which we obtain a representation of equational classes (or varieties) of algebras. We define analgebraic transformational system (S.T.A.) as a quadruple (T,v,S,+) satisfying the axioms, where T is a set containing the variables v(n), n, and having operators S(): TT, . In addition there are operations Q⁺ on T commuting with the operators. A notion of morphism between S.T.A. 's is defined to obtain the category which is shown to be equivalent to the dual of the category of equational classes. In the last section we establish the equivalence between and Lawvere's category of algebraic theories in which every definable constant is present.

---

---

Extrait de la Thèse de doctorat de l'auteur, Université de Montréal, 1971.     

Complete problems withL-samplable distributions

The average case complexity classes P, L-samplable and NL, L-samplable are defined. We show that Deterministic Bounded Halting is complete for P, L-samplable and that Graph Reachability is complete for NL-samplable, both problems with a universal logspace samplable distribution.     

Threshold theorems for a stochastic model of an epidemic with natural immunization

A stochastic model of an epidemic is investigated, taking account of the removal of ill members of the population (by death, by recovery with immunization, by isolation) and natural immunization. Limiting distributions are found for the size of the epidemic, the number immunized ₁, and their sum, under the assumption that the original number of susceptible individuals n and the number of ill individuals m , while n 1,n ₀< , where and are the coefficients for the contraction of the disease and of immunization respectively.Translated from Matematicheskie Zametki, Vol. 8, No. 3, pp. 385–392, September, 1970.     

On equivalence of rearrangements of the Haar system in dyadic Hardy and BMO spaces

H={h ₁,I } — , . : , I ¦(I)¦=¦I¦, ¦I¦ — I. H H ={h _(I),I} . , , . L ^p .

---

---

Dedicated to Professor B. Szökefalvi-Nagy on his 75th birthday

---

This research was supported in part by MTA-NSF Grants INT-8400708 and 8620153.     

Interpolation and best polynomial approximation in the domain ofp-adic integers

, , . , . Lip

---

---

The authors are indebted to Professor R. Bojanic for his valuable remarks and suggestions, especially for the simplification of the proof of Theorem 4.     

On the Discrete Spectrum of a Family of Differential Operators

We consider a family A of differential operators in L ²(²) depending on a parameter 0. The operator A formally corresponds to the quadratic form

Strong formulations for mixed integer programming: A survey

We attempt to motivate and survey recent research on the use of strong valid inequalities and reformulation to solve mixed integer programming problems.     

OnU ϕ-sets of trigonometric integrals

, (t) >0 E(–, +),E<, , ¦f(t)¦ (t) xE, f(t)=0 (–, +).     

Notes on best constants in some Sobolev inequalities

, . .     

On aU-set for multiple Walsh series

m- (m2) , - , .     

On the Cesàro summability of orthogonal sequences

(C, ). , . 0<<1. 1) - ( _k ), _k =a _k , (C, ), . 2) , , (C, ) ; _k = =¦a _k ¦.     

A Class of Global Optimization Problems as Models of the Phase Unwrapping Problem

Let I={(i,j) i=1, 2,..., N ₁, j=1, 2,..., N ₂} and let U=U_i,j, (i,j)I be a discrete real function defined on I. Let []₂ be modulus 2, we define W:I , ) as follows W=[U]₂. The function U will be called phase function and the function W will be called wrapped phase function. The phase unwrapping problem consists in recovering U from some knowledge of W. This problem is not well defined, that is infinitely many functions U correspond to the same function W, and must be `regularized' to be satisfactorily solvable. We propose several formulations of the phase unwrapping problem as an integer nonlinear minimum cost flow problem on a network. Numerical algorithms to solve the minimum cost flow problems obtained are proposed. The phase unwrapping problem is the key problem in interferometry, we restrict our attention to the SAR (Synthetic Aperture Radar) interferometry problem. We compare the different formulations of the phase unwrapping problem proposed starting from the analysis of the numerical experience obtained with the numerical algorithms proposed on synthetic and real SAR interferometry data. The real data are taken from the ERS missions of the European Space Agency (ESA).     

Optimizing constrained subtrees of trees

Given a treeG = (V, E) and a weight function defined on subsets of its nodes, we consider two associated problems. The first, called the rooted subtree problem, is to find a maximum weight subtree, with a specified root, from a given set of subtrees.The second problem, called the subtree packing problem, is to find a maximum weight packing of node disjoint subtrees chosen from a given set of subtrees, where the value of each subtree may depend on its root.We show that the complexity status of both problems is related, and that the subtree packing problem is polynomial if and only if each rooted subtree problem is polynomial. In addition we show that the convex hulls of the feasible solutions to both problems are related: the convex hull of solutions to the packing problem is given by pasting together the convex hulls of the rooted subtree problems.We examine in detail the case where the set of feasible subtrees rooted at nodei consists of all subtrees with at mostk nodes. For this case we derive valid inequalities, and specify the convex hull whenk 4.Research supported in part by Nato Collaborative Research Grant CRG 900281, Science Program SC1-CT91-620 of the EEC, and contract No 26 of the programme Pôle d'attraction interuniversitaire of the Belgian government.     

Convex Separable Minimization Subject to Bounded Variables

A minimization problem with convex and separable objective function subject to a separable convex inequality constraint and bounded variables is considered. A necessary and sufficient condition is proved for a feasible solution to be an optimal solution to this problem. Convex minimization problems subject to linear equality/linear inequality constraint, and bounds on the variables are also considered. A necessary and sufficient condition and a sufficient condition, respectively, are proved for a feasible solution to be an optimal solution to these two problems. Algorithms of polynomial complexity for solving the three problems are suggested and their convergence is proved. Some important forms of convex functions and computational results are given in the Appendix.     

Orthogonal systems invariant under an automorphism

, , - ( ) . , - , ( ) .     

Limites dégénérées de séries discrètes, formes automorphes et variétés de Griffiths–Schmid: le cas du groupe U (2, 1)

Let G be an inner anisotropic form of an unitary group of 3 variables over Q, such that G_RU(2,1), and be an automorphic representation of G(A) whose archimedean component is a degenerate limit of discrete series; such a never occurs in the cohomology (coherent or étale) of a Shimura variety. We show that however it does appear in the coherent cohomology of some line bundle over an associated Griffiths-Schmid variety. Moreover we study cup products between such cohomology classes and some other automorphic cohomology classes and we prove some non-vanishing results.