Robust locally testable codes and products of codes

We continue the investigation of locally testable codes, i.e., error‐correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically checkable proofs, we introduce the notion of robust local testability of codes. We relate this notion to a product of codes introduced by Tanner and show a very simple composition lemma for this notion. Next, we show that codes built by tensor products can be tested robustly and somewhat locally by applying a variant of a test and proof technique introduced by Raz and Safra in the context of testing low‐degree multivariate polynomials (which are a special case of tensor codes). Combining these two results gives us a generic construction of codes of inverse polynomial rate that are testable with poly‐logarithmically many queries. We note that these locally testable tensor codes can be obtained from any linear error correcting code with good distance. Previous results on local testability, albeit much stronger quantitatively, rely heavily on algebraic properties of the underlying codes. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Improved bounds for sampling contingency tables

We study the problem of sampling contingency tables (nonnegative integer matrices with specified row and column sums) uniformly at random. We give an algorithm which runs in polynomial time provided that the row sums r_i and the column sums c_j satisfy r_i = Ω(n^3/2m log m), and c_j = Ω(m^3/2n log n). This algorithm is based on a reduction to continuous sampling from a convex set. The same approach was taken by Dyer, Kannan, and Mount in previous work. However, the algorithm we present is simpler and has weaker requirements on the row and column sums. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 135–146, 2002     

Time Asymptotic Behaviour for a One-Velocity Transport Operator with Maxwell Boundary Condition

This paper is concerned with the spectral analysis of a one-velocity transport operator with Maxwell boundary condition in L ₁-space. After a detailed spectral analysis it is shown that the associated Cauchy problem is governed by a C ₀-semigroup. Next, we discuss the irreducibility of the transport semigroup. In particular, we show that the transport semigroup is irreducible. Finally, a spectral decomposition of the solutions into an asymptotic term and a transient one which will be estimated for smooth initial data is given.     

Area orthogonality in normed linear spaces

A new concept of orthogonality in real normed linear spaces is introduced. Typical properties of orthogonality (homogeneity, symmetry, additivity, ...) and relations between this orthogonality and other known orthogonalities (Birkhoff, Boussouis, Unitary-Boussouis and Diminnie) are studied. In particular, some characterizations of inner product spaces are obtained.     

NONLOCAL INITIAL PROBLEM FOR NONLINEAR NONAUTONOMOUS DIFFERENTIAL EQUATIONS IN A BANACH SPACE

The nonlocal initial problem for nonlinear nonautonomous evolution equati-ons in a Banach space is considered. It is assumed that the nonlinearities havethe local Lipschitz properties. The existence and uniqueness of mild solutionsare proved. Applications to integro-differential equations are discussed.The main tool in the paper is the normalizing mapping (the generalizednorm).     

The components of the Wired Spanning Forest are recurrent

 We show that a.s. all of the connected components of the Wired Spanning Forest are recurrent, proving a conjecture of Benjamini, Lyons, Peres and Schramm. Our analysis relies on a simple martingale involving the effective conductance between the endpoints of an edge in a uniform spanning tree. We believe that this martingale is of independent interest and will find further applications in the study of uniform spanning trees and forests. Received: 20 April 2001 / Revised version: 23 July 2002 / Published online: 14 November     

Asymmetric hydrogenation of alkyl(vinyl)thioethers: a promising approach to α-chiral thioethers

This paper describes the enantioselective hydrogenation of vinylthioethers. We show that thioether derivatives of maleic esters can be hydrogenated with full conversion and up to 60% ee, and that α-thioether cinnamic acids can be hydrogenated in 51% ee with modest conversion.     

Recent developments in the statistical processing of textual data

Statisticians are accustomed to processing numerical, ordinal or nominal data. In many circumstances, such as socio-economic, epidemiologic sample surveys and documentary data bases, this data is juxtaposed with textual data (for example, responses to open questions in surveys). This article presents a series of language-independent procedures based upon applying multivariate techniques (such as correspondence analysis and clustering) to sets of generalized lexical profiles. The generalized lexical profile of a text is a vector whose components are the frequencies of each word (graphical form) or ‘repeated segment’ (sequence of words appearing with a significant frequency in the text). The processing of such large (and often sparse) vectors and matrices requires special algorithms. The main outputs are the following: (1) printouts of the characteristic words and characteristic responses for each category of respondent (these categories are generally derived from available nominal variables); (2) graphical displays of the proximities between words or segments and categories of respondents; (3) when analysing a combination of several texts: graphical displays of proximities between words or segments and each text, or between words or segments and groupings of texts. The systematic use of ‘repeated segments’ provides a valuable help in interpreting the results from a semantic point of view.