MarriageTheoremのこと

_ プレプリント確認状況：arXiv:math 9月9日分まで、IACR ePrint 2012/560まで

_ 気になった論文１：Is Wolfram and Cook's (2,5) Turing machine really universal? (Dominic J. D. Hughes, arXiv:1208.6342)

Wolfram [2, p. 707] and Cook [1, p. 3] claim to prove that a (2,5) Turing machine (2 states, 5 symbols) is universal, via a universal cellular automaton known as Rule 110. The first part of this paper points out a critical gap in their argument. The second part bridges the gap, thereby giving what appears to be the first proof of universality.

_ 気になった論文２：Coxeter Groups are not higher rank Arithmetic Groups (Sandip Singh, arXiv:1208.6569)

Let W be an irreducible finitely generated Coxeter group. The geometric representation of W in GL(V) provides a discrete embedding in the orthogonal group of the Tits form (the associated bilinear form of the Coxeter group). If the Tits form of the Coxeter group is non-positive and non-degenerate, the Coxeter group does not contain any finite index subgroup isomorphic to an irreducible lattice in a semisimple group of R-rank greater or equal to 2.

_ 気になった論文３：Efficiently Extracting Randomness from Imperfect Stochastic Processes (Hongchao Zhou, Jehoshua Bruck, arXiv:1209.0734)

We study the problem of extracting a prescribed number of random bits by reading the smallest possible number of symbols from non-ideal stochastic processes. The related interval algorithm proposed by Han and Hoshi has asymptotically optimal performance; however, it assumes that the distribution of the input stochastic process is known. The motivation for our work is the fact that, in practice, sources of randomness have inherent correlations and are affected by measurement's noise. Namely, it is hard to obtain an accurate estimation of the distribution. This challenge was addressed by the concepts of seeded and seedless extractors that can handle general random sources with unknown distributions. However, known seeded and seedless extractors provide extraction efficiencies that are substantially smaller than Shannon's entropy limit. Our main contribution is the design of extractors that have a variable input-length and a fixed output length, are efficient in the consumption of symbols from the source, are capable of generating random bits from general stochastic processes and approach the information theoretic upper bound on efficiency.

_ 気になった論文４：Minimizing the number of carries in addition (Noga Alon, arXiv:1209.1131)

When numbers are added in base $b$ in the usual way, carries occur. If two random, independent 1-digit numbers are added, then the probability of a carry is $\frac{b-1}{2b}$. Other choices of digits lead to less carries. In particular, if for odd $b$ we use the digits $\{-(b-1)/2, -(b-3)/2,...,...(b-1)/2\}$ then the probability of carry is only $\frac{b^2-1}{4b^2}$. Diaconis, Shao and Soundararajan conjectured that this is the best choice of digits, and proved that this is asymptotically the case when $b=p$ is a large prime. In this note we prove this conjecture for all odd primes $p$.