https://twitter.com/kinaba のログ (twilog の方が便利です。)
| #air_STACS 「n頂点、全頂点出次数k」のグラフをランダムに作ったとき頂点1から到達可能な頂点の個数の分布は？→こういうGaussianになります、というパラメタを求めていた。これを使って、無駄な部分のないオートマトンのランダム生成などに応用している | |
| #air_STACS ちょうど昨日趣味でオートマトンのenumerationなど書いてたので便利そうな感じがした（詳細は読んでない疲れてきた | |
| #air_STACS Aliceが行列Aを持っててBobが行列Bを持ってるときにA+Bの行列式を計算するrandomized/quantum communication complexity！なにかフーリエ変換ぽいことしてからやりとりすると下限達成っぽくなるらしい | |
| #air_STACS （次の右のやつが面白そうなのでさっさとそっちが読みたくておざなりになっています | |
| #air_STACS あんまり面白くなかった。n状態k文字DFA適当に作ったときに最小DFAになってる確率はexp(-n^{-k+2}/4)くらいのような感じらしいですよ | |
| 力尽きたので風呂ル | |
| @tri_iro 同じ感想でした＞当たり前な気が。や、細部までちゃんと読んでないですけど | |
| #air_STACS SLP (各文法記号に対して１つの規則しかない、特定の文字列１つを表す文脈自由文法) で表現された文字列、だいたいLZ圧縮みたいなもの、に対してラベルがSLP圧縮されたDFAやNFAを走らせる計算量はPやNPとな。 | |
| #air_STACS 「え、聴いた瞬間適当にDPっぽくあれそれすれば当たり前だろ」と「そうでもないかな？」が今2周くらいしている。 | |
| #air_STACS 「そうでもないかな？」によりはじめた。ふむー。 | |
| #air_STACS おおこれカッコイイ | |
| きたく。今日は #air_STACS 静かだけどまあ第2セッションからやるか。でも今日のはほとんど本気でわからん気配がある | |
| そして宅配ボックスの中にCHR本 http://www.amazon.co.jp/dp/0521877768 と素数全書 http://www.amazon.co.jp/dp/4254111282 ががが。ああありがとうございますすす！！！素数全書の方の贈り主は言及されてた某師ですかね。がんばって読んで面白ネタのネタ元にします！ | |
| あと @zakkas783 に推薦頂いてほしい物リストに投げといたら別方面から頂いた竜の学校は山の上 http://www.amazon.co.jp/dp/4781605451 も最近読んでて楽しかったです感謝。前半の一連の勇者物はちょと不安だったけど天使のや山の話すごく好きですね。あと絵が絶妙なバランスで可愛い | |
| ^^---0------------------000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000----------------- | |
| キーボードの掃除をしてたらちょうど140文字入力されていたのでついEnterを↓ | |
| #air_STACS Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid minor 読んでる。 | |
| #air_STACS 二つ名の三つや四つついてそうな八面六臂の活躍をされてる河原林先生だ | |
| #air_STACS グラフの「ツリーっぽさ」を表すtreewidthという指標(treeなら1、一般にはもっと大きい)がありまして、これに関する重要な定理として「treewidthが十分大きいf(r)くらい大きいならr×rの格子状のグラフをマイナーとして持つ」てのがあって | |
| #air_STACS 平面グラフに限るとその関数f(r)はrの線形関数、みたいなことも知られていて、一般化として禁止マイナーで定義されるグラフに限るとf(r)が線形という定理があるんだけどその線形の比例定数がどんだけデカくなるのか既存の証明では爆発してたのを指数程度で抑えたとな | |
| #air_STACS グラフマイナー理論の成果に大いに乗っかった既存の証明と違って比較的シンプルに直接的に証明を与えている、という成果なので、ちゃんと読めば理解できそうな風に見える（あとで読む） | |
| #air_STACS On separation question for tree languages。無限オートマトンは有限の時と違って最後に止まらないので、状態の間に順位をつけて「無限回出現する状態のうち一番位の高いお方の位」が偶数か奇数かで判定したりするんですけど | |
| #air_STACS 状態のランクを「何ランクに分けるか」と「ランクの個数が偶数か奇数か」で論理式の∀と∃の違いのような表現力の階層が生まれるんですけど、強い階層のオートマトンの排他な受理言語 A と B があったときに弱い階層ので"separte"できるか問題というのがあって | |
| #air_STACS それが文字列の場合について完全に解けてツリーの場合にも半分くらい解けてロジックでの既存の結果のアナロジーにもまっちした結果で嬉しい感じとのことです。これも @tri_iro さんとか方面の目の方を引きそうな感じのお話だ | |
| やばいまったり書いてたら全然ペース追いつけてない | |
| #air_STACS Regular tree languages, cardinality predicates, and addition-invariant FO 文字列やツリーに対する、個数をmodで数えるのも許す一階述語論理（"aの次にbが並ぶパターンが偶数回出現"とか | |
| #air_STACS …の表現力を調べてaddition invariant FOてのと一致したよとかなんとか。正規言語とFOの差は"繰返し"が表現できぬこと、というざっくりした理解があるのですが、modで数えるのはある種の繰返しなのでその辺の繰返し概念の細分理解と言える気がする | |
| #air_STACS Improved bounds on Bipartite Matching on surfaces これはComplexity動物園に出張に行ってきた人が読むと良い系論文ですなあ。ULってなんだっけ… | |
| #air_STACS http://qwiki.stanford.edu/index.php/Complexity_Zoo:U#ul 「非決定性計算なんだけど実はYESに行く分岐は一つしかない」マシンでLOGSPACEで解ける問題のクラス、に二部＆平面グラフの完全マッチングが入るよ、という論文だそうだ。 | |
| 要は「PTIMEアルゴリズムを求めよ」という問題を競うコンテストは多いですが「LOGSPACEアルゴリズム」を競うコンテストも面白いのではないか。「無向グラフと頂点vと頂点uがあります、vとuがconnectedかどうか判定しなさい、はい！」 | |
| @dream_shifter 時間に響くから以外のスペース側中心の都合だと、下回りで「メモリの動的確保も再帰によるスタック消費もしたくない」みたいな状況になって頭を捻ることはあるかもです。普段あまり気にしないとすると、逆に考えてみると新しい発見があって面白いと思うんですよね。 | |
| やる気がだるい | |
| @ikegami__ 今関数型とか圏論が流行ってるノリで15年前のネットの片隅では若者の間でデータ圧縮と情報理論がブームだったのですよー（言い過ぎ。Network codingの論文出たちょい後に五十嵐健夫先生が日記で触れてて面白ーと思って調べて日記書いたはずなのですが見当たらぬ | |
| #air_STACS ここからTCS強度が上がってついていけない感じの論文だらけになってきた…。 | |
| #air_STACS Rumor Spreading: グラフがどう繋がってるか各頂点自分の隣接リストしかわからない状況で各自1ターンに1人ずつ選んで情報伝達できるとして一人が持ってる情報を全体に速く伝えるプロトコル。乱択しないとどうしようもないことは既知なのだけど、 | |
| #air_STACS ノード数nのsublinearオーダの乱択しか使わないで高速に全員に伝達できる初のプロトコルなんだそうだ（いかん本当にabstの内容しか読めてない） | |
| #air_STACS 乱択で互いに独立なハッシュ関数を全ターン用に作って、kターン目に伝達が起きる経路で伝わってきたら1<<kのビットが立ってるようなIDを今のターンのハッシュに書けてでてきた番目の隣接ノードに送る、とかなんとか（ちゃんと読めてるか自信ない）。あらシンプル。 | |
| #air_STACS An Approximation Algorithm for #k-SAT ふごご。なんか凄くストレートなアルゴリズムだけど僕これちゃんと読めてるんだろうか。3-SATの解の個数を誤差ε以内で数えますO(ε^{-2}·1.5366^n)時間で、とな。 | |
| #air_STACS 速いk-SATソルバをサブルーチンとして使って基本的に全探索っぽく(変数x0を偽にしてみてSAT解く、真にしてみて解く、再帰)地道に列挙する。解が少ないときはそれだけ。数が閾値を超えたらランダム割り当てを十分な回数やってパーセンテージに2^nを掛ける！だん！ | |
| #air_STACS この近似アルゴリズムを#2-SATに適用すると既存のexactアルゴリズムより遅いので#2-SATは誰か考えると面白いんじゃないかな～、と書いてある | |
| RSA Conference 2012 Keynote - https://www.youtube.com/watch?v=y5FeJ6DEaJw 見てる。例のRon was wrong, Whit was rightについてRonとWhitがパネルトークしてる。楽しい。 | |
| RSAのRの人「Lenstra(素因数分解のプロ中のプロ)がRSAがヤバいとかいう論文を出したというからついに素因数分解がヤバいのか！！と思ったらそうじゃなかったのである意味安心した」 |