-
xhl_kogitsune
- 1923
- 0
- 0
- 0
-
- いいね！0
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
確率εで成功するアルゴリズムを受け取ると確率1-o(1)で成功するアルゴリズムを返す時、古典計算ではΘ(1/ε)だけど量子計算だとO(1/sqrt(ε))らしい[既存]。それの改良版を提案して、前記の線形代数に使う。 #air_STACS
2012-03-02 00:42:57
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Asymptotic enumeration of Minimal Automata: accessible complete DFAからランダムサンプリングした時の最小DFAの確率とか。そろそろ力尽きてきた #air_STACS
2012-03-02 00:49:33
kinaba
@kinaba
#air_STACS あんまり面白くなかった。n状態k文字DFA適当に作ったときに最小DFAになってる確率はexp(-n^{-k+2}/4)くらいのような感じらしいですよ
2012-03-02 00:33:53
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Trichotomy for Integer Linear Systems Based on Their Sign Patterns: A,b:実数行列及びベクトルが与えられた時、Ax>=b となる0～d-1の整数からなるベクトルxの計算はNP-hard #air_STACS
2012-03-02 00:55:45
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
というのは既知ですが、本研究ではSign Pattern, 即ち行列Aの各要素が負/0/正であるという情報のみから、該当インスタンスが線形で計算できる/弱NP-hard/強NP-hard、に3分類できることを示しました(ｷﾘｯ #air_STACS
2012-03-02 00:57:05
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
何それぱない。minimize Z s.t. 各iについて (Aijが正であるiの個数-Aijが負であるiの個数)αj+(Aijが負であるi,jの個数)<=Z 及び 0<=αj<=1 でZが1未満/1/1より大きい、で三分類らしい。 #air_STACS
2012-03-02 01:00:29
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
あ、ついでにこの判定もlinear timeらしい #air_STACS
2012-03-02 01:02:07
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
正確には「Zが1になるようなインスタンス集合はweak NP-hard」とかそういう定式化だな #air_STACS
2012-03-02 01:07:02
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Compressed Membership for NFA (DFA) with Compressed Labels is in NP (P): SLP(単一文字列のみ生成するCFG)がなんたらorz #air_STACS
2012-03-02 01:17:10
kinaba
@kinaba
#air_STACS SLP (各文法記号に対して１つの規則しかない、特定の文字列１つを表す文脈自由文法) で表現された文字列、だいたいLZ圧縮みたいなもの、に対してラベルがSLP圧縮されたDFAやNFAを走らせる計算量はPやNPとな。
2012-03-02 00:51:18
kinaba
@kinaba
#air_STACS 「え、聴いた瞬間適当にDPっぽくあれそれすれば当たり前だろ」と「そうでもないかな？」が今2周くらいしている。
2012-03-02 00:52:25
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
一日目のセッション終了。Kei Kimura and Kazuhisa Makino, "Trichotomy for Integer Linear Systems Based on Their Sign Patterns" がかっこよかった。 #air_STACS
2012-03-02 01:23:19
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
Chan et al., "Linear-Space Data Structures for Range Mode Query in Arrays" も理解可能だった。(ぉ #air_STACS
2012-03-02 01:24:01
Deprecated: おねーちゃんですよ!⚓/xhl_kogitsune
@xhl_kogitsune
リアルVEE/ASPLOS行く人は映画けいおんの聖地巡礼をしてきてください
2012-03-02 01:37:06