-
xhl_kogitsune
- 1926
- 0
- 0
- 0
-
- いいね！0
kinaba
@kinaba
#air_STACS 2人ゲームで、交互に文字をappendしあって、特定の文法にマッチするものが作れたら先手が勝ち、外せたら後手が勝ち、という無限ゲームの必勝法は「カウンタ1個＋有限状態オートマトンで受理できる言語」の場合でももっと一般の文脈自由言語並に難しいことの証明、
2012-03-01 23:48:13
kinaba
@kinaba
#air_STACS だそうだ。これも詳しくないので新規性度合いよくわからん。恐ろしそうな部分はだいたい既存研究の成果がそのまま引っ張れているだけなのであまり恐ろしくなかった。こけ脅し気味である。
2012-03-01 23:49:59
Takayuki Kihara
@tri_iro
非決定的ビュッキ・オートマトンで受理可能なω-言語はΣ^1_1だから、それでゲームやったらΣ^1_1-決定性で、そりゃ0^#の存在と同値になるよねって当たり前な気がしてきた。いや、実時間ビュッキ・オートマトンの定義よく知らないから本当に当たり前かどうか知らないけど。
2012-03-02 00:38:49
Takayuki Kihara
@tri_iro
@kinaba 決定的ビュッキ・オートマトンの場合だとΠ^0_2決定性なので、当然ZFCというか二階算術の部分体系で証明できる話になるため、一応、real timeという部分がかなり影響を与えているんだなあということで、ちゃんと読めばもしかしたら自明じゃないかもしれません。かも。
2012-03-02 00:58:56
Takayuki Kihara
@tri_iro
@airobo 確か誰かがビュッキ、ビュッキと呼んでいたのでそれを真似していただけで、本当の発音が何であるかは謎です。
2012-03-02 01:12:04
YOSHIDA Yuichi
@oxy
何故かstacsが流行っているが，これアルゴリズムの話とプログラミング言語の話と両方あって読者層が広いからかな．それだとICALPも流行りそう．
2012-03-01 23:49:49
kinaba
@kinaba
やりましょう RT (via @oxy) 何故かstacsが流行っているが，これアルゴリズムの話とプログラミング言語の話と両方あって読者層が広いからかな．それだとICALPも流行りそう．
2012-03-01 23:52:30
Ikegami Daisuke
@ikegami__
#air_STACS Randomized Communication Complexity for Linear Algebra Problems over Finite Fields : アイデア次第では線形代数だけで論文書ける好例です
2012-03-01 23:07:36
kinaba
@kinaba
#air_STACS Aliceが行列Aを持っててBobが行列Bを持ってるときにA+Bの行列式を計算するrandomized/quantum communication complexity！なにかフーリエ変換ぽいことしてからやりとりすると下限達成っぽくなるらしい
2012-03-02 00:21:28
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Communication Complexity: Aliceたんがx∈X, Bobがy∈Yを持っている時にf: X×Y→Zに対してf(x,y)を計算するときにAliceとBobの間の通信量。リア充め… #air_STACS
2012-03-02 00:28:35
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
んで、今回はそのrandomized/quantum版(確率εの失敗を許容)で、有限体F_p上のn×n行列のsingularity判定をするのにΩ(n^2 log p)かかるという話。証明詳細不明。 #air_STACS
2012-03-02 00:30:06
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
これは全部通信せいということなんだろうか? 少なくともオーダーは落ちないという話だよね。quantum/randomizeしてもチート的にオーダー減らないのがすごいのかなぁ?(よく分からない #air_STACS
2012-03-02 00:31:13
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Distribution of the number of accessible states in a random deterministic automaton: n状態k種文字の有限オートマトンの集合(n^{nk}要素)からランダムに #air_STACS
2012-03-02 00:13:18
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
取ってきた時に始状態からreachableな状態の個数の平均と分散がv_k n, σ_k sqrt(n) に収束する(v_k, σ_kはkにより決まる定数)という話。まぁ、ガウス分布っぽくなるといわれてもふーん #air_STACS
2012-03-02 00:14:53
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
って感じだけど、それを利用してランダムに全要素reachableなオートマトン生成アルゴリズム(平均O(n^1.5)とか、サイズに誤差あってもいいなら平均O(n)とか)提案してるのでそっちがメイン? #air_STACS
2012-03-02 00:15:52
kinaba
@kinaba
#air_STACS 「n頂点、全頂点出次数k」のグラフをランダムに作ったとき頂点1から到達可能な頂点の個数の分布は？→こういうGaussianになります、というパラメタを求めていた。これを使って、無駄な部分のないオートマトンのランダム生成などに応用している
2012-03-02 00:12:33
kinaba
@kinaba
#air_STACS ちょうど昨日趣味でオートマトンのenumerationなど書いてたので便利そうな感じがした（詳細は読んでない疲れてきた
2012-03-02 00:13:34
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
左セッション、Variable time amplitude amplification and quantum algorithms for linear algebra problems: 量子計算で連立線形方程式とかの計算量改善。 #air_STACS
2012-03-02 00:38:42