MarriageTheoremのこと

_ 某所への論文投稿〆切になんとか間に合った。

_ （9/3記：論文提出が済んだので久々にのんびりと休日を過ごした。）

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

_ 気になった論文１：Report on "Mathematical Aspects of P vs. NP and its Variants." (Joshua A. Grochow, Korben Rusek, arXiv:1203.2888)

This is a report on a workshop held August 1 to August 5, 2011 at the Institute for Computational and Experimental Research in Mathematics (ICERM) at Brown University, Providence, Rhode Island, organized by Saugata Basu, Joseph M. Landsberg, and J. Maurice Rojas. We provide overviews of the more recent results presented at the workshop, including some works-in-progress as well as tentative and intriguing ideas for new directions. The main themes we discuss are representation theory and geometry in the Mulmuley-Sohoni Geometric Complexity Theory Program, and number theory and other ideas in the Blum-Shub-Smale model.

_ 気になった論文２：A note on Shannon entropy (Tomasz Sobieszek, arXiv:1203.3322)

We present a somewhat different way of looking on Shannon entropy. This leads to an axiomatisation of Shannon entropy that is essentially equivalent to that of Fadeev. In particular we give a new proof of Fadeev theorem.

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

_ （9/6記：某大学の某学科の某分野のおっかない話を聞いた、ような…）

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

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

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

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

_ 昨日と今日は「関西すうがく徒のつどい」の開催日。次回はどうにかして参加したいものである。

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

_ 気になった論文１：From edge-disjoint paths to independent paths (Serge Gaspers, arXiv:1203.4483)

Let f(k) denote the maximum such that every simple undirected graph containing two vertices s,t and k edge-disjoint s-t paths, also contains two vertices u,v and f(k) independent u-v paths. Here, a set of paths is independent if none of them contains an interior vertex of another. We prove that f(k)=k if k<3, and f(k)=3 otherwise.

_ 気になった論文２：Elements with finite Coxeter part in an affine Weyl group (Xuhua He, Zhongwei Yang, arXiv:1203.4680)

Let $W_a$ be an affine Weyl group and $\eta:W_a\longrightarrow W_0$ be the natural projection to the corresponding finite Weyl group. We say that $w\in W_a$ has finite Coxeter part if $\eta(w)$ is conjugate to a Coxeter element of $W_0$. The elements with finite Coxeter part is a union of conjugacy classes of $W_a$. We show that for each conjugacy class $\mathcal{O}$ of $W_a$ with finite Coxeter part there exits a unique maximal proper parabolic subgroup $W_J$ of $W_a$, such that the set of minimal length elements in $\mathcal{O}$ is exactly the set of Coxeter elements in $W_J$. Similar results hold for twisted conjugacy classes.

_ 各所で「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」という動画が話題になっていたので観てみた。「組合せ爆発（問題のサイズが増えるにつれて、答えの個数が急激に増加する様子）のすごさを教えたい」とのことだが、爆発しているのはむしろ作った人の（中略）ではないだろうか。数学ネタ、しかも数学の素養を必要としないネタでここまで趣深い（←穏当な表現）動画を作れるという、人間と数学の豊かな可能性に感銘を受けた次第。

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

_ MathSciNetの共著者距離を調べるツールは登録なしで使えることに気が付いたので、色々な人との共著者距離を調べているのだけど、今のところ８が最長（パスが無い場合を除く）で、中々二桁の相手が見つからない。

_ CSS2012参加用のメモ（10/30更新）

プログラムはここ

初日：1C1-1→1D1-3、1C2-1→1D2-2→1C2-4（移動大変そう…）

二日目：2D1全部、2C2全部、2C3全部、2C4全部

最終日：どうしようかなー

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

_ 気になった論文：Game arguments in computability theory and algorithmic information theory (Andrej Muchnik, Alexander Shen, Mikhail Vyugin, arXiv:1204.0198)

We provide some examples showing how game-theoretic arguments can be used in computability theory and algorithmic information theory: unique numbering theorem (Friedberg), the gap between conditional complexity and total conditional complexity, Epstein--Levin theorem and some (yet unpublished) result of Muchnik and Vyugin

_ 昨日発売の「数学セミナー」10月号のどこかに出没していますので、よかったら探してみて下さい。

_ 今度は「関東すうがく徒のつどい」が催されるらしい。こうして、数学のプロやセミプロでない方々を中心に数学について語らう場が増えるのは本当に嬉しいことなので、応援したい。

_ Twitterでも似たことを書いたのだけど、研究者を目指している数学科の大学院生には、「数学が」好きな人と、数学の「研究が」好きな人がいるという印象である。前者のタイプの人が数学の職を得られなかった場合にはとても大変なことになるかもしれないが、一方、後者は数学で職が見つからなくても周辺分野の研究者としてやっていける可能性が高いと思われる。

そこで問題になるのが、当の本人であっても、自分がどちらのタイプの人間であるかの見極めがそれほど自明な問題ではないことである。私自身の経験からいっても、特に所謂純粋数学中心の大学院にいると、何となく「前者のタイプでなければならない」という思い込みが形成されやすく、本当は後者のタイプである人が「自分は「数学が」好きなのだ」と思い込んでしまう事例が少なくないのではないか、と推測している。

そのように、本来なら数学自体でなくてもその周辺分野の研究者として活き活きと活動できる素養のある学生さんが、上記のような思い込みから数学のポストを得ることに拘って、結果として「討ち死に」してしまうとしたらそれは非常に悲しいことである。そのようなことが少しでも減るようにと願って止まない。

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

_ 気になった論文１：On the longest length of arithmetic progressions (MinZhi Zhao, Huizeng Zhang, arXiv:1204.1149)

Suppose that $\xi^{(n)}_1,\xi^{(n)}_2,...,\xi^{(n)}_n$ are i.i.d with $P(\xi^{(n)}_i=1)=p_n=1-P(\xi^{(n)}_i=0)$. Let $U^{(n)}$ and $W^{(n)}$ be the longest length of arithmetic progressions and of arithmetic progressions mod $n$ relative to $\xi^{(n)}_1,\xi^{(n)}_2,..., \xi^{(n)}_n$ respectively. Firstly, the asymptotic distributions of $U^{(n)}$ and $W^{(n)}$ are given. Simultaneously, the errors are estimated by using Chen-Stein method. Next, the almost surely limits are discussed when all $p_n$ are equal and when considered on a common probability space. Finally, we consider the case that $\lim_{n\to\infty}p_n=0$ and $\lim_{n\to\infty}{np_n}=\infty$. We prove that as $n$ tends to $\infty$, the probability that $U^{(n)}$ takes two numbers and $W^{(n)}$ takes three numbers tends to 1.

_ 気になった論文２：Density-based group testing (Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, Gábor Wiener, arXiv:1204.1464)

In this paper we study a new, generalized version of the well-known group testing problem. In the classical model of group testing we are given n objects, some of which are considered to be defective. We can test certain subsets of the objects whether they contain at least one defective element. The goal is usually to find all defectives using as few tests as possible. In our model the presence of defective elements in a test set Q can be recognized if and only if their number is large enough compared to the size of Q. More precisely for a test Q the answer is 'yes' if and only if there are at least \alpha |Q| defective elements in Q for some fixed \alpha.

_ 気になった論文３：The minimal degree of permutation representations of finite groups (Oren Becker, arXiv:1204.1668)

In this thesis we study the following property of a finite group G: the minimal number n such that G embeds in Sn. We start with an explicit formula for the number n for abelian groups. Then, we study the behavior of this group property in respect to direct products. Finally, we define and explore the "compression ratio" of a finite group G which measures how much better the best embedding is relative to the embedding given by Cayley's theorem.

_ 気になった論文４：On convex hulls of orbits of Coxeter groups and Weyl groups (Georg Hofmann, Karl-Hermann Neeb, arXiv:1204.2095)

The notion of a linear Coxeter system introduced by Vinberg generalizes the geometric representation of a Coxeter group. Our main theorem asserts that if $v$ is an element of the Tits cone of a linear Coxeter system and $\cW$ is the corresponding Coxeter group, then $\cW v \subeq v - C_v,$ where $C_v$ is the convex cone generated by the coroots $\check \alpha$, for which $\alpha(v) > 0$. This implies that the convex hull of $\cW v$ is completely determined by the image of $v$ under the reflections in $\cW$. We also apply an analogous result for convex hulls of $\cW$-orbits in the dual space, although this action need not correspond to a linear Coxeter system. Motivated by the applications in representation theory, we further extend these results to Weyl group orbits of locally finite and locally affine root systems. In the locally affine case, we also derive some applications on minimizing linear functionals on Weyl group orbits.

_ 気になった論文５：A Secret Sharing Scheme Based on Group Presentations and the Word Problem (Maggie Habeeb, Delaram Kahrobaei, Vladimir Shpilrain, arXiv:1205.0157)

A (t,n)-threshold secret sharing scheme is a method to distribute a secret among n participants in such a way that any t participants can recover the secret, but no t-1 participants can. In this paper, we propose two secret sharing schemes using non-abelian groups. One scheme is the special case where all the participants must get together to recover the secret. The other one is a (t,n)-threshold scheme that is a combination of Shamir's scheme and the group-theoretic scheme proposed in this paper.

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

_ 気になった論文：Some word maps that are non-surjective on infinitely many finite simple groups (Sebastian Jambor, Martin W. Liebeck, E. A. O'Brien, arXiv:1205.1952)

We provide the first examples of words in the free group of rank 2 which are not proper powers and for which the corresponding word maps are non-surjective on an infinite family of finite non-abelian simple groups.

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

_ 気になった論文：On the Structure of Involutions and Symmetric Spaces of Dihedral Groups (Katrina K. A. Cunningham, Tom J. Edgar, Aloysius G. Helminck, Benjamin F. Jones, Hyunju Oh, Rachel Schwell, Jennifer F. Vasquez, arXiv:1205.3207)

We initiate the study of analogues of symmetric spaces for the family of finite dihedral groups. In particular, we investigate the structure of the automorphism group, characterize the involutions of the automorphism group, and determine the fixed-group and symmetric space of each automorphism.

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

_ 気になった論文１：A simplified and generalized treatment of DES related ciphers (Liljana Babinkostova, Alyssa M. Bowden, Andrew M. Kimball, Kameryn J. Williams, arXiv:1205.5613)

This work is a study of DES-like ciphers where the bitwise exclusive-or (XOR) operation in the underlying Feistel network is replaced by an arbitrary group operation. We construct a two round simplified version of DES that contains all the DES components and show that its set of encryption permutations is not a group under functional composition, it is not a pure cipher and its set of encryption permutations does not generate the alternating group. We present a non-computational proof that for n\leq6 the set of n-round Feistel permutations over an arbitrary group do not constitute a group under functional composition.

_ 気になった論文２：Optimal epsilon-biased sets with just a little randomness (Cristopher Moore, Alexander Russell, arXiv:1205.6218)

Subsets of F_2^n that are eps-biased, meaning that the parity of any set of bits is even or odd with probability eps close to 1/2, are useful tools in derandomization. A simple randomized construction shows that such sets exist of size O(n/eps^2), and known deterministic constructions achieve sets of size O(n/eps^3), O(n^2/eps^2), and O((n/eps^2)^{5/4}). Rather than derandomizing these sets completely in exchange for making them larger, we attempt a partial derandomization while keeping them small, constructing sets of size O(n/eps^2) with as few random bits as possible. The naive randomized construction requires O(n^2/eps^2) random bits. We show that this can be reduced to O(n log (n/eps)) random bits. Our construction uses the Legendre symbol and Weil sums, but in a different way than the construction of Alon, Goldreich, Haastad, and Peralta.

_ 気になった論文３：The Discrete Logarithm Problem in Bergman's non-representable ring (Matan Banin, Boaz Tsaban, arXiv:1206.1077)

Bergman's Ring $E_p$, parameterized by a prime number $p$, is a ring with $p^5$ elements that cannot be embedded in a ring of matrices over any commutative ring. This ring was discovered in 1974. In 2011, Climent, Navarro and Tortosa described an efficient implementation of $E_p$ using simple modular arithmetic, and suggested that this ring may be a useful source for intractable cryptographic problems.

We present a deterministic polynomial time reduction of the Discrete Logarithm Problem in $E_p$ to the classical Discrete Logarithm Problem in $\Zp$, the $p$-element field. In particular, the Discrete Logarithm Problem in $E_p$ can be solved, by conventional computers, in sub-exponential time.

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

_ （9/20記：先日、整数論における重要な未解決問題である「ABC予想」が解決されたのではないか、と（数学の話題にしては）大きく報道された。たとえばこのあたりの記事など。ここでは「ABC予想」の詳細は述べないことにするが、どうやら本件の報道を見聞きした方々の中には「暗号技術の危機に繋がるのではないか」と思った方もいたらしい（参考）。

念のため注意しておくと、もし今回の「ABC予想」の解決が実際に正しいと確認されたとしても、そのことで現在広く使われている暗号技術が直ちに危機にさらされるわけではない。もっとも、「将来的な可能性の有無」というレベルの話で言うならば、整数論の知見に基づいて設計されている現代の主要暗号技術の安全性と、同じく整数論の話題である「ABC予想」の間に何らかの関係が見出されることがあり得ないとは言えないが、もしそうなったとしたらそのこと自体が大きな発見として扱われるレベルの話である。というわけで、今回の成果を基に暗号技術が危なくなるという短期的な見通しは無いので、あまり心配しないでいただきたい。）

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

_ 気になった論文：Rationally smooth elements of Coxeter groups and triangle group avoidance (Edward Richmond, William Slofstra, arXiv:1206.5746)

We study a family of infinite-type Coxeter groups defined by the avoidance of certain rank 3 parabolic subgroups. For this family, rationally smooth elements can be detected by looking at only a few coefficients of the Poincar\'{e} polynomial. We also prove a factorization theorem for the Poincar\'{e} polynomial of rationally smooth elements. As an application, we show that a large class of infinite-type Coxeter groups have only finitely many rationally smooth elements. Explicit enumerations and descriptions of these elements are given in special cases.

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

_ 気になった論文１：Enhanced Chosen-Ciphertext Security and Applications (Dana Dachman-Soled and Georg Fuchsbauer and Payman Mohassel and Adam O'Neill, IACR ePrint archive 2012/543)

We introduce and study a new notion of enhanced chosen-ciphertext security (ECCA) for public- key encryption. Loosely speaking, in ECCA, when the decryption oracle returns a plaintext to the adversary, it also provides coins under which the returned plaintext encrypts to the queried ciphertext (when they exist). Our results mainly concern the case where such coins can also be recovered efficiently. We provide constructions of ECCA encryption from adaptive trapdoor functions as defined by Kiltz et al. (EUROCRYPT 2010), resulting in ECCA encryption from standard number-theoretic assumptions. We then give two applications of ECCA encryption: (1) We use it as a unifying concept in showing equivalence of adaptive trapdoor functions and tag-based adaptive trapdoor functions (namely, we show that both primitives are equivalent to ECCA encryption), resolving a main open question of Kiltz et al. (2) We show that ECCA encryption can be used to securely realize an approach to public-key encryption with non-interactive opening (PKENO) suggested by Damg{\aa}rd and Thorbek (EUROCRYPT 2007), resulting in new and practical PKENO schemes quite different from those in prior work. We believe our results indicate that ECCA is an intriguing notion that may prove useful in further work.

_ 気になった論文２：Factoring integer using elliptic curves over rational number field $\mathbb{Q}$ (Xiumei Li, Jinxiang Zeng, arXiv:1207.0274)

For the integer $ D=pq$ of the product of two distinct odd primes, we construct an elliptic curve $E_{2rD}:y^2=x^3-2rDx$ over $\mathbb Q$, where $r$ is a parameter dependent on the classes of $p$ and $q$ modulo 8, and show, under the parity conjecture, that the elliptic curve has rank one and $v_p(x([k]Q))\not=v_q(x([k]Q))$ for odd $k$ and a generator $Q$ of the free part of $E_{2rD}(\mathbb Q)$. Thus we can recover $p$ and $q$ from the data $D$ and $ x([k]Q))$. Furthermore, under the Generalized Riemann hypothesis, we prove that one can take $r

_ 気になった論文３：Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator (Jan Krajíček, arXiv:1207.0393)

For an NP intersect coNP function g of the Nisan-Wigderson type and a string b outside its range we consider a two player game on a common input a to the function. One player, a computationally limited Student, tries to find a bit of g(a) that differs from the corresponding bit of b. He can query a computationally unlimited Teacher for the witnesses of the values of constantly many bits of g(a). The Student computes the queries from a and from Teacher's answers to his previous queries. It was proved by Krajicek (2011) that if g is based on a hard bit of a one-way permutation then no Student computed by a polynomial size circuit can succeed on all a. In this paper we give a lower bound on the number of inputs a any such Student must fail on. Using that we show that there is a pseudo-finite set of hard instances on which all uniform students must fail. The hard-core set is defined in a non-standard model of true arithmetic and has applications in a forcing construction relevant to proof complexity.

_ 気になった論文４：A New Efficient Asymmetric Cryptosystem Based on the Square Root Problem (M. R. K. Ariffin, M. A. Asbullah, N. A. Abu, arXiv:1207.1157)

The square root modulo problem is a known primitive in designing an asymmetric cryptosystem. It was first attempted by Rabin. Decryption failure of the Rabin cryptosystem caused by the 4-to-1 decryption output is overcome efficiently in this work. The proposed scheme (known as the AA_\beta- cryptosystem) has its encryption speed having a complexity order faster than the Diffie-Hellman Key Exchange, El-Gammal, RSA and ECC. It can also transmit a larger data set securely when compared to existing asymmetric schemes. It has a simple mathematical structure. Thus, it would have low computational requirements and would enable communication devices with low computing power to deploy secure communication procedures efficiently.

_ （9/23記：妻が借りてきた「アイスフォレスト」という漫画が面白そうなので読んでみた。フィギュアスケートのアイスダンスが題材という珍しい作品。膝の負傷で本来のジャンプが跳べなくなりスケートから離れていた女子シングルの日本人選手と、とある事情で日本にやってきたカナダ人の男性アイスダンス選手が、これまた事情ありげなフィギュアスケートクラブの男性オーナーによって引きあわされてカップルを組むことになり…といった展開から始まる物語。

全12巻という長さの中で展開がドラマチックに二転三転するので、つい一気に読み進めてしまった。また、作者さんの絵の上手さと熱心な取材に加えて、相当気合の入った監修の方々が付いていたようで、近年の複雑高度化するリフトの描写やアイスダンスならではの繊細な表現、新採点方式の細かいルールやフィギュアスケート界の内部事情に至るまで、アイスダンスの世界やその魅力が見事に描かれていた。漫画ということもあり登場人物の美男美女率がかなり高めなのだが、現実のアイスダンス選手にも現実離れした美貌の持ち主が少なくないので、この点についても全く違和感を覚えなかった（笑）。仮に少女漫画特有（？）の凝った愛憎劇を脇に置いたとしても、フィギュアスケート好きの方なら文句なしに楽しめる作品ではないかと思う。

というか、これだけの作品ならアイスダンスオタの方々には「今更」な有名作なのかもしれないが、私は知らなかったので、今回この作品を読めてよかったなぁと感じている。興味をお持ちの方はぜひ。）

_ 昨日の日記に引き続き、読んだ漫画ネタ。

「ちはやふる」は以前11巻まで読んでいたのだけど、今回は12巻から17巻まで読了。やはりこの作品は素晴らしい。「ヒカルの碁」のときにも感じた「自分もやってみたい感」を喚起する熱さを備えた作品は大好物である。（しかし、実際にやろうとすると「聴覚」＋「暗記」という私のニガテ要素がダブルで要求されるという…）

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

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

_ 気になった論文１：A Clifford algebraic framework for Coxeter group theoretic computations (Pierre-Philippe Dechant, arXiv:1207.5005)

Real physical systems with reflective and rotational symmetries such as viruses, fullerenes and quasicrystals have recently been modeled successfully in terms of three-dimensional (affine) Coxeter groups. Motivated by this progress, we explore here the benefits of performing the relevant computations in a Geometric Algebra framework, which is particularly suited to describing reflections. Starting from the Coxeter generators of the reflections, we describe how the relevant chiral (rotational), full (Coxeter) and binary polyhedral groups can be easily generated and treated in a unified way in a versor formalism. In particular, this yields a simple construction of the binary polyhedral groups as discrete spinor groups. These in turn are known to generate Lie and Coxeter groups in dimension four, notably the exceptional groups D_4, F_4 and H_4. A Clifford algebra approach thus reveals an unexpected connection between Coxeter groups of ranks 3 and 4. We finally discuss how to extend these considerations and computations to the Conformal Geometric Algebra setup.

_ 気になった論文２：Zorn's Lemma- An elementary proof under the Axiom of Choice (Arjun Jain, arXiv:1207.6698)

This article presents an elementary proof of Zorn's Lemma under the Axiom of Choice, simplifying and supplying necessary details in the original proof by Paul R. Halmos in his book, Naive Set Theory. Also provided, is a preamble to Zorn's Lemma, introducing the reader to a brief history of this important maximal principle.

_ 気になった論文３：A 60,000 digit prime number of the form $x^{2} + x + 41$ (Justin DeBenedetto, Jeremy Rouse, arXiv:1207.7291)

Motivated by Euler's observation that the polynomial $x^{2} + x + 41$ takes on prime values for $0 \leq x \leq 39$, we search for large values of $x$ for which $N = x^{2} + x + 41$ is prime. To apply classical primality proving results based on the factorization of $N-1$, we choose $x$ to have the form $g(y)$, chosen so that $g(y)^{2} + g(y) + 40$ is reducible. Our main result is an explicit, 60,000 digit prime number of the form $x^{2} + x + 41$.

_ とある事情で、オセロの学生チャンピオン（だったかな）にして日本ランカーの某氏とお手合わせする機会があったので胸をお借りしてみた。私が現場に行く前から「挑戦者側はパーフェクト負けを逃れれば勝ち」という変則ルールで遊んでいたらしく、私もその流れで。といっても、トップクラスの選手と打てる機会なんてそうそうあるものではないので、強さを肌で感じるためにも、私の側は変則ルールのことは忘れて、無謀にも勝利を目指して大真面目に打ってみた。（まぁ、「全駒だけは逃れよう」と目標設定したところでどうすれば有利になるのかわからないから、どのみち普通に打つしかないのだが。）

で、結果。（当たり前ですが、少ない方が私です。）

（撮影：@Yaruo_Yanai氏）

…つえー（←そりゃそうだ）。超つえー（←そりゃそうだ）。

何というか、こちらも考えに考えて抜け目ない手を打っているつもりなのに、気がつくと八方ふさがりな状況に追い込まれているという、あの不思議な感覚を味わえただけでも対戦してみた甲斐があったなぁと思う。彼にすれば、お遊びかつ無茶なルール設定（実際、感想戦のときに「パーフェクトを狙うために本来の最善手を外した場面があった」と仰っていた）にもかかわらずあの強さだったわけで、やはりトップクラスのプレイヤーの凄みはとんでもないものがあるなぁ、と驚嘆した次第。

あと、これも当然といえば当然なのだが、駒を扱う際の手つきの良さが明らかに際立っていた。オセロの駒をあんなに素早く正確にひっくり返す人なんて初めて見た。

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

_ （9/27記：「暗号用語しりとり」というマニア心溢れる遊びに興じていた。）

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

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

_ 気になった論文１：Lecture notes on NIP theories (Pierre Simon, arXiv:1208.3944)

This text is an introduction to the study of NIP (or dependent) theories. It is meant to serve two purposes. The first is to present various aspects of NIP theories and give the reader the background material needed to understand almost any paper on the subject. The second is to advertise the use of honest definitions, in particular in establishing basic results, such as the so-called shrinking of indiscernibles.

_ 気になった論文２：Strict independence in dependent theories (Itay Kaplan, Alexander Usvyatsov, arXiv:1208.4062)

We investigate the notions of strict independence and strict non-forking in dependent theories, establish basic properties and connections between the two. In particular it follows from our study that strict non-forking is symmetric. Based on this study, we develop notions of weight which characterize NTP2, dependence and strong dependence. Many of our proofs rely on careful analysis of sequences that witness dividing in dependent theories. We prove simple characterizations of such sequences, as well as of Morley sequences which are witnesses. As a by-product of this investigation, we obtain information on types co-dominated by generically stable types. For example, we prove that every Morley sequence in such a type is a witness.

_ 気になった論文３：The size of a formula as a measure of complexity (Lauri Hella, Jouko Väänänen, arXiv:1208.4803)

We introduce a refinement of the usual Ehrenfeucht-Fra\"{\i}ss\'e game. The new game will help us make finer distinctions than the traditional one. In particular, it can be used to measure the size formulas needed for expressing a given property. We will give two versions of the game: the first version characterizes the size of formulas in propositional logic, and the second version works for first-order predicate logic.

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

_ 気になった論文１：Dependence and Independence (Erich Grädel, Jouko Väänänen, arXiv:1208.5268)

We introduce an atomic formula intuitively saying that given variables are independent from given other variables if a third set of variables is kept constant. We contrast this with dependence logic. We show that our independence atom gives rise to a natural logic capable of formalizing basic intuitions about independence and dependence.

_ 気になった論文２：Open and solved problems in infinite combinatorics (Shimon Garti, Saharon Shelah, arXiv:1208.6091)

We list some open problems, concerning the polarized partition relation. We solve a couple of them by showing that for every singular cardinal $\mu$ one can force the strong polarized relation with respect to the pair $\mu^+,\mu$.

_ プレプリント確認状況：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$.