2013-02-16
_ 出張中に某エヌ氏から紹介された、エドワード・ゴーリー（Edward Gorey）という人の絵本。
The Gashlycrumb Tinies: Or, After the Outing
いつぞやの「ダジャレ数学クラスタ死亡かるた」のときに彼はこの本を連想したらしい。中身を見せてもらったけれども、なんというか、こう…なんとも言い難い味わいの本だったが、ともかく彼がこの本を連想した理由は言葉でなく心で理解した。
[ツッコミを入れる]
_ 色々あって何故か2013年日本ジュニア数学オリンピック予選問題をしばらく眺めていた。これ、どのくらいの予備知識を仮定して解いていいのだろうか。
_ ↑ちなみにこちらがジュニアじゃない方の予選問題。
_ arXiv:math 2012年12月2日分まで、IACR ePrint 2013/048まで確認済み
_ （2/12記：ゲームソフトも扱っている某レンタルビデオ屋さんに行ったらちょうどドラゴンクエストVIIの宣伝をしていた。VIIにはあまり思い入れがないのだが、やはりあの序曲は素晴らしいと再確認した。）
_ （2/12記：間の悪いことに翌日から某〆切当日まで出張なので、出発前に投降投稿を済ませておこうと思ってここ数日酷い勢いで論文を書いていたのだが、この日…というか正確には翌日の朝までかかってようやく論文を書き終えた。翌日…というか数時間も立たないうちに出発という実感がまるでない。
それにしても、「今回はそんなに長くならないだろう」と目論んでいた小ネタでどうして40ページ超の原稿が出来上がるのか小一時間）
_ 研究打ち合わせ終了。今回は、打ち合わせ初日に投入した問題が最終日までに完全に解決されるという極めて珍しい順調ぶりだった。皆さんどうもありがとうございました。
_ で、帰りの電車が積雪にみまわれている（↑との因果関係については何も主張していません）。
_ 出張中に某エヌ氏から紹介された、エドワード・ゴーリー（Edward Gorey）という人の絵本。
The Gashlycrumb Tinies: Or, After the Outing
いつぞやの「ダジャレ数学クラスタ死亡かるた」のときに彼はこの本を連想したらしい。中身を見せてもらったけれども、なんというか、こう…なんとも言い難い味わいの本だったが、ともかく彼がこの本を連想した理由は言葉でなく心で理解した。
_ （2/20記：慶応義塾大学総合政策学部の入試問題の数学で数独が出題されたらしい件のまとめ記事を見た。何というか、出題者がどんな能力を測りたくてこの問題を出したのか意図が不明なので、入試にパズルを出題すること自体の是非は置いておくとしても、入試で出題するという観点では数独は中途半端にメジャーなパズルなのがまずい点だと思う。いくら問題文にルールが記載されているとしても、数独を一度も解いたことのない人と頻繁に解いている人では後者の方が圧倒的に有利である。先程「出題者がどんな能力を測りたくてこの問題を出したのか意図が不明」と書いたが、いくらなんでも、「数学」ではなく「数独」が得意な人を合格させたいという意図ではなかろう。であれば、せめて受験生が誰も（せめて、ごくごく一握りの人以外は）解いたことのないような新種もしくはマイナーなパズルを題材にすべきだったのではないかと思う。）
_ arXiv:math 1月2日分まで、IACR ePrint 2013/087まで確認済み
_ 気になった論文１：On the computational complexity of finding hard tautologies
, Jan Krajicek, http://jp.arxiv.org/abs/1212.1789
It is well-known (cf. K.-Pudlak (1989)) that a polynomial time algorithm finding tautologies hard for a propositional proof system $P$ exists iff $P$ is not optimal. Such an algorithm takes $1^{(k)}$ and outputs a tautology $\tau_k$ of size at least $k$ such that $P$ is not p-bounded on the set of all $\tau_k$'s.
We consider two more general search problems involving finding a hard formula, {\bf Cert} and {\bf Find}, motivated by two hypothetical situations: that one can prove that $\np \neq co\np$ and that no optimal proof system exists. In {\bf Cert} one is asked to find a witness that a given non-deterministic circuit with $k$ inputs does not define $TAUT \cap \kk$. In {\bf Find}, given $1^{(k)}$ and a tautology $\alpha$ of size at most $k^{c_0}$, one should output a size $k$ tautology $\beta$ that has no size $k^{c_1}$ $P$-proof from substitution instances of $\alpha$.
We shall prove, assuming the existence of an exponentially hard one-way permutation, that {\bf Cert} cannot be solved by a time $2^{O(k)}$ algorithm. Using a stronger hypothesis about the proof complexity of Nisan-Wigderson generator we show that both problems {\bf Cert} and {\bf Find} are actually undefined for infinitely many $k$. The results are based on interpreting the Nisan-Wigderson generator as a proof system.
_ 気になった論文２：Freeness of hyperplane arrangements and related topics
, Masahiko Yoshinaga, http://jp.arxiv.org/abs/1212.3523
This is the expanded notes of the lecture by the author in "Arrangements in Pyrenees", June 2012. We are discussing relations of freeness and splitting problems of vector bundles, several techniques proving freeness of hyperplane arrangements, K. Saito's theory of primitive derivations for Coxeter arrangements, their application to combinatorial problems and related conjectures.
_ 気になった論文３：Accumulation points of infinite Coxeter groups of rank 3
, Akihiro Higashitani, Ryosuke Mineyama, Norihiro Nakashima, http://jp.arxiv.org/abs/1212.6617
In this paper, we investigate the limit set of normalized roots of infinite Coxeter groups of rank 3. Moreover, we obtain that the set of such accumulation points coinsides with the closure of the orbit of one point of normalized limit roots.
_ arXiv:math 1月8日分まで、IACR ePrint 2013/095まで確認済み
_ 気になった論文：Tropical cryptography
, Dima Grigoriev, Vladimir Shpilrain, http://jp.arxiv.org/abs/1301.1195
We employ tropical algebras as platforms for several cryptographic schemes that would be vulnerable to linear algebra attacks were they based on "usual" algebras as platforms.
_ 今日は関東すうがく徒のつどいに参加して発表させてもらった。自分以外の３件の発表はみんなわかり易くて面白かったんだけど、自分の発表は結局最後の方がグダグダになってしまったので、もし次の機会があったらもっとちゃんと（というか、初めから板書で発表するつもりで）準備をしないといけないなぁと思った。
ともあれ、久々にとても楽しい数学の時間を過ごせたので、運営の方々にこの場を借りてお礼申し上げます。明日は自分は参加できないけど、トラブルなく楽しい会になるよう祈っています。
_ arXiv:math 1月9日分まで、IACR ePrint 2013/095まで確認済み
_ 「関東つどい」二日目、どうやら中学生（！）の発表者が現れたらしい。私は欠席だったので直接は発表を聞いていないのだけど、発表の中身がどうこう以前にそのやる気と行動力に敬意を抱いた。
_ twitter上でしむらさん（@ta_shim_at_nhn）に教わった話をもとに検索してみたら「TeX数式を含んだ文章のEbraを用いた点訳」という文書を見つけた。興味深いなぁと思いつつ読んでいたのだが、実は1998年に書かれた文書であるらしく、ということは1998年の時点で（実用レベルだったかはともかく）その手の技術が世の中に存在していたわけで、1998年といったら多分自分が人生で一番点訳していた時期なので、今までこの技術のことを知らなかったことに少々衝撃を受けている。
_ arXiv:math 1月9日分まで、IACR ePrint 2013/117まで確認済み
_ 気になった論文１：Notions of Black-Box Reductions, Revisited
, Paul Baecher and Christina Brzuska and Marc Fischlin, http://eprint.iacr.org/2013/101
Reductions are the common technique to prove security of cryptographic constructions based on a primitive. They take an allegedly successful adversary against the construction and turn it into a successful adversary against the underlying primitive. To a large extent, these reductions are black-box in the sense that they consider the primitive and/or the adversary against the construction only via the input-output behavior, but do not depend on internals like the code of the primitive or of the adversary. Reingold, Trevisan, and Vadhan~(TCC, 2004) provided a widely adopted framework, called the RTV framework from hereon, to classify and relate different notions of black-box reductions.
Having precise notions for such reductions is very important when it comes to black-box separations, where one shows that black-box reductions cannot exist. An impossibility result, which clearly specifies the type of reduction it rules out, enables us to identify the potential leverages to bypass the separation. We acknowledge this by extending the RTV framework in several respects using a more fine-grained approach. First, we capture a type of reduction---frequently ruled out by so-called meta-reductions---which escapes the RTV framework so far. Second, we consider notions that are ``almost black-box'', i.e., where the reduction receives additional information about the adversary, such as its success probability. Third, we distinguish explicitly between efficient and inefficient primitives and adversaries, allowing us to determine how relativizing reductions in the sense of Impagliazzo and Rudich (STOC, 1989) fit into the picture.
_ 気になった論文２：Public Key Exchange Using Matrices Over Group Rings
, Delaram Kahrobaei and Charalambos Koupparis and Vladimir Shpilrain, http://eprint.iacr.org/2013/114
We offer a public key exchange protocol in the spirit of Diffie-Hellman, but we use (small) matrices over a group ring of a (small) symmetric group as the platform. This ``nested structure" of the platform makes computation very efficient for legitimate parties. We discuss security of this scheme by addressing the Decision Diffie-Hellman (DDH) and Computational Diffie-Hellman (CDH) problems for our platform.
最近のツッコミ↓
_ @izutetsuya [11月ISECとSCIS2014と2014年3月ISECもよろしくお願いします。]
_ MarriageTheorem [情報ご提供ありがとうございます。（一応個人的メモなので、ISEC研究会は機械振興会館の分だけしか記載していませんでし..]