We obtain lower bounds on degree and additive complexity of real polynomials approximating the discrete logarithm in finite fields of even characteristic. These bounds complement earlier results for finite fields of odd characteristic.

We prove asymptotic equipartition properties for simple hierarchical structures (modelled as multitype Galton-Watson trees) and networked structures (modelled as randomly coloured random graphs). For example, for large n, a networked data structure consisting of n units connected by an average number of links of order n / log n can be coded by about H × n bits, where H is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical...

We prove asymptotic equipartition properties for simple hierarchical structures (modelled as multitype Galton-Watson trees) and networked structures (modelled as randomly coloured random graphs). For example, for large n, a networked data structure consisting of n units connected by an average number of links of order n / log n can be coded by about H × n bits, where H is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical...

The convergence rate of the expectation of the logarithm of the first return time $R_n$, after being properly normalized, is investigated for ergodic Markov chains. I. Kontoyiannis showed that for any β > 0 we have $log\left[R_n\left(x\right)P_n\left(x\right)\right]=o\left(n^{\beta }\right)$ a.s. for aperiodic cases and A. J. Wyner proved that for any ε >0 we have $-(1+\epsilon )logn\le log\left[R_n\left(x\right)P_n\left(x\right)\right]\le loglogn$ eventually, a.s., where $P_n\left(x\right)$ is the probability of the initial n-block in x. In this paper we prove that $E[log{R}_{(L,S)}-(L-1)h]$ converges to a constant depending only on the process where $R_{(L,S)}$ is the modified first return time with...