Minimum Description Length Principle in Discriminating Marginal Distributions

2010 Mathematics Subject Classification: 94A17, 62B10, 62F03.

Matricial Model for the Study of Lower Bounds

Let V be an array. The range query problem concerns the design of data structures for implementing the following operations. The operation update(j,x) has the effect vj ← vj + x, and the query operation retrieve(i,j) returns the partial sum vi + ... + vj. These tasks are to be performed on-line. We define an algebraic model – based on the use of matrices – for the study of the problem. In this paper we establish as well a lower bound for the sum of the average complexity of both kinds of operations, and demonstrate that this lower bound is near optimal – in terms of asymptotic complexity.

Classification of Texts' Authorship Using a Regression Model on Compressed Data

2010 Mathematics Subject Classification: 68T50,62H30,62J05.