| 日時 | 10月 11日 (火) 9:30 〜 17:30 |
| 会場 | 東京工業大学 大岡山キャンパス西８号館 (W) ８階８０９号室 |
| 東京都目黒区大岡山 2-12-1 (アクセス) |
|
| 世話役 | 垂井淳 (電気通信大学) |
| 内容 | Complexityに関する研究集会を以下のように開催します。 Complexityは広い意味に捉える、未解決問題の説明も歓迎すると スピーカーの方々に伝えてあります。 参加される場合連絡は必要ありません。 都合と興味にあわせた部分参加も全く問題ありません。 特定領域研究と無関係な方や学生さんの参加も全く問題ありません。 是非参加検討ください。 |
| 9:30 -- 10:15 | 索引を用いた文字列検索の計算量と未解決問題 ： 定兼邦彦 (九大) |
| 10:15 -- 10:30 | 休憩 |
| 10:30 -- 11:15 | オラクル同定問題に対する量子質問計算量の幾何的な特徴付け ： 河内亮周 (東工大) |
| 11:15 -- 12:00 | 閉ジャクソンネットワークの正規化定数の近似計算法について ： 来嶋秀治 (東大) |
| 12:00 -- 13:30 | 休憩 |
| 13:30 -- 14:45 | MAX2SAT の Average Case 時間計算量について ： 山本真基 (東工大) |
| 確率伝搬法とその発展形の可能性について ： 渡辺治 (東工大) | |
| 14:45 -- 15:00 | 休憩 |
| 15:00 -- 15:45 | 否定数を log(n+1) に限定した回路計算量の下界について ： 森住大樹 (京大) |
| 15:45 -- 16:30 | 単調DNF式の幾つかの性質について ： 天野一幸 (東北大) |
| 16:30 -- 16:45 | 休憩 |
| 16:45 -- 17:30 | NP neq coNPを証明するには？ (ショートトーク) |
| k-wise almost independent permutations ： 垂井淳 (電通大) |
東工大西８号館 (W) ８０９号室への行き方
大岡山駅を出て左を見れば正門が見えます．我々の建物は西８号 館(E)です．西８号館(E) は新しく立った建物です．本館西側にた っています．本館に向かってあるき，向かって右の新しいビルを 目指して，スロープを下れば入口です．入ったところが (E) 棟３階 です．そのフロアをまっすぐ進むと (W) 棟に入ります．そこのエレ ベータを使って８階に来て下さい．エレベータを出て，まっすぐ進 んだつき当たりが８０９号室です．
文字列中のパタンの検索を高速化するために、あらかじめ索引を付加する手法が とられているが、索引のサイズと検索時間の間にはトレードオフが存在する。 本発表では既存の索引について解説し、検索時間の下限に対する予想を立てる。
オラクル同定問題とは与えられたブラックボックス関数（オラクル）に質問を行 い，候補関数集合の中のどれがオラクルとして与えられているかを同定する問題 である．本講演では候補関数集合の幾何的な特徴に着目して同定に必要な量子質 問計算量について議論する．
閉ジャクソンネットワークの積形式解の正規化定数に対する近似計算法を提案する。 提案するアルゴリズムはマルコフ連鎖モンテカルロ法で、FPRASを与える。 本発表では特にモンテカルロ法に焦点をあて、近似解の精度保証について議論する。
これまでに，MAXSAT および MAX-k-SAT に関する Average-Case 時間計算量の研究は，（筆者の知る限り）全くされていない． （SAT に関してはある．） 本講演では，MAX2SAT 問題を考え，以下のような性質を持つ 例題生成器 RGEN が生成する例題族 F(RGEN)に対して， Average-Case 時間計算量を議論する． 1. RGEN が出力する例題と真理値割り当ての対のほとんど（任意の コンスタントの割合 1-ε）が，例題とその最大充足解の対である． 2. RGEN の生成する例題の大きさは小さい．つまり，2CNF 論理式 の節の数が，変数の数の（εに関する）コンスタント倍である． 3. RGEN が出力する全例題上の MAX2SAT 問題が NP-Hard である． F(RGEN) のほどんど（all but o(1)）が，Local Search タイプの アルゴリズムに弱いことの直感的説明をし，それを示すための 方法について議論する．
統計力学の研究者により再発見され，非常に盛んに研究されて いる確率伝搬法について，それがどの程度まで有効（そう）な のか，他の局所探索法と比べて，どのように違うのか／同じな のか，を，たとえば SAT 問題（とその variation）に絞り，議論 してみたい．
否定数をlog(n+1)に限定した回路における n入力2出力論理関数(PARITY, neg)（ただし，n+1は2の累乗）の 回路計算量の5n-cの下界の証明について紹介し， そこからの発展の可能性に触れる． 否定数をlceil og(n+1) ceil omega(nog(n))，一般の回路における 同等の下界を示したことになることが知られており， 否定数をその数に限定した回路の回路計算量を 調べることは特別な意味を持つ．
DNF式の充足割り当ての個数を数え上げる問題に関係する(可能性のある)， 充足割り当ての個数を最小化/最大化する式の構造に関連する問題について 議論したいと思います．
（この話についての現時点でのアイデア・中身はおおむね以下のみ； 共同研究者募集中） NP neq coNPであるという前提のもとに、このことの証明が どのような方法では無理そうかということを考えたい。 3SATフォーミュラFについて、それが充足不可能であって、かつ、 （普通の数学を展開する公理系としての）ZFでの 充足不可能性の最短証明が長いことを Long(F)と表すことにする。 NP neq coNPであればLong なFが存在する。 （１)あるexplicitなFに対してLong(F)であることを、 （我々にとって自然である）コンスタントまたは 短いサイズの証明で示すことはできない。 そのような証明がないことがLong(F)の主張だから。 （２）２つのexplicitなフォーミュラF1,F2に対して 「Long(F1)orLong(F2)」のコンパクトな証明がないことも 簡単にわかり、少し注意して拡張すればp=poly(n)個に対しても 同様に「Long(F1) or ... or Long(Fp)」のコンパクトな証明が ないことがわかる。 （３）フォーミュラのうまい確率的生成を定義し、 生成されるフォーミュラが確率1/poly(n)で Longになるという証明法に対しても、 complexity-theoretic assumptionのもとでの derandomizationにより、もしそんな証明ができれば 多項式個のF1,...,Fpに対してLong(F1)or...orLong(Fp)であることが 証明できてしまうことになり矛盾するので そんなことはできそうにない、という議論を考えたい。 以上において充足不可能な3SATフォーミュラの代わりに、 たとえば、「root(n)のクリークを持たないn頂点グラフ」を 用いても全く同じ議論となる。
N置換の集合Pは次の性質を持つときk-wise (almost) independentであるという： 任意のk点x1,...,xkに関してpiをPから一様ランダムに選んだときの pi(x1),...,pi(xk)の分布が 完全にランダムな置換のもとでの分布と一致する・ほとんど一致する。 このようなPをkが大きいときもFeistel変換のcompositionによる構成で 生成することができることを示す。 Reingold によるブレークスルー：USTCONN in LogSpace[STOC05]の Reingold-Trevisan-Vadhan[ECCC05]による拡張が以上の問題に応用できるという Kaplan-Naor-Reingold[RANDOM05]の指摘、すなわち、 もとのグラフのexpansion factorを 維持したzig-zag productによるpseudorandom walkの方法の応用についても 簡単に説明し、また、以上の問題に関連する未解決問題のリストを提示する。