研究集会情報の変更

* … 必須項目
* 会議名 :
	- 新学術領域 ELC の小規模な研究集会は、「ELC Seminar (講師名)」, 　　  「ELC Mini-Workshop (班名 or テーマ名)」などにしてください。
* Date :	2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 年 -- 1 2 3 4 5 6 7 8 9 10 11 12 月 -- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 日 から　 -- 1 2 3 4 5 6 7 8 9 10 11 12 月 -- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 日 まで
	- 会期が１日の場合は「--月--日まで」で結構です。
	- 会期が未定の場合は「○年○月--日から」で結構です。後日、修正できます。
タグ :	elc
	- 新学術領域 ELC 関連のイベントは、チェックマークを付けてください。
Place :
URL :	本システムで作るページを、研究集会の一次情報源にします。 　　  (小規模な研究集会などで、案内を簡便に作る時は、 　　  こちらにチェックを入れて下さい) 外部のページに、リンクします。 　　  (外部に案内のページを作る予定 (or 主催者が作る予定) で、 　　  まだ無い場合は、空欄で結構です。)
投稿〆切 :	2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 年 -- 1 2 3 4 5 6 7 8 9 10 11 12 月 -- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 日
	- 〆切が不明の場合は、「--月--日」で結構です。
	- 講演会など、そもそも投稿〆切が無い場合も、同様です。
その他の情報 (招待講演など) :
- 招待講演者、プログラム、懇親会の情報、参加の情報等を書いてください。 　　- ELC セミナーやミニワークショップは、講演のホストの先生のお名前を書き加えてください。
領域会議 日時：　5月29，30日 場所：　ELCセンター 　　　　http://www.al.ics.saitama-u.ac.jp/elc/celc/ 　　　　東京工業大学 田町キャンパス　キャンパス・イノベーションセンター　１階 国際会議室 総括班会議 日時：　5月30日　お昼 場所：　ELCセンター 　　　　http://www.al.ics.saitama-u.ac.jp/elc/celc/ 　　　　東京工業大学 田町キャンパス　キャンパス・イノベーションセンター　404号室 プログラム 5月29日 13:00-13:55 「Deterministic Random Walks on Finite Graphs」来嶋 秀治 (九大) 14:10-15:05 「列挙に対するアルゴリズム設計戦略」宇野 毅明 (NII) 15:15-15:30 　事務局連絡 15:30-15:55　(公募班) 「論理式の探索と自動合成による計算限界解析」ジョーダン　チャールズハロルド (北大) 15:55-16:20　(公募班) 「パラメータ化計算に関する未解決問題の調査と探求による計算複雑さ解明」宇野 裕之 (大阪府大) 16:35-17:00　(公募班) 「分散並列計算と逐次計算における計算限界導出技法の融合と深化」泉 泰介 (名工大) 17:00-17:25　(公募班) 「非線形整数計画問題の組合せ構造解析による計算限界の解明」塩浦 昭義 (東工大) 18：00－　　　 懇親会: IL FILO(イルフィーロ) 田町駅より徒歩10分　 　　　　　　　　　　　 　 http://tabelog.com/tokyo/A1314/A131403/13013997/ 　 5,000円　貸切、着席のブッフェスタイル（テラス使用可）飲み放題　　 5月30日 09:15-10:10 「有向木詰め込み問題に対するアルゴリズム」小林 佑輔 (筑波大) 10:25-11:20 「一般の凸錐を用いた拡張定式化と一般確率論における通信複雑度:計算量理論に基づく量子力学の 特徴付けへ向けて」森 立平 (東工大) 11:20-11:45 　(公募班) 「符号理論における計算限界の解明」安永　憲司 (金沢大) 11:50-13:00　 (総括班会議　4階　404号室) 13:00-13:25　 (公募班) 'Time-Space trade-off algorithms for sens'　Korman Matias (NII) 13:25-13:50　 (公募班) 「解空間のパラメータ化解析による計算困難性と容易性の解明」伊藤　健洋 (東北大) 13:50-14:15　 (公募班) 「計算量的仮定に基づくノンユニバーサル量子計算の研究－ＳＢＱＰと多項式階層」 　　　　　　　 森前　智行 (群馬大) 14:15-14:25 事務局連絡 アブストラクト 5月29日 来嶋 秀治(九州大学) タイトル： Deterministic Random Walks on Finite Graphs アブストラクト： 数え上げ困難な（#P-hard）問題に対して，1980年代後半から，マルコフ連鎖モンテカルロ(MCMC）法を中心とする 様々な乱択近似計算法が開発されてきた一方，決定性の近似アルゴリズムの開発は，近年の重要な挑戦課題になっている． 本発表ではMCMC法の脱乱択化へのアプローチとして，決定性ランダムウォークを紹介する． ロータールーターモデル（あるいはPropp機械とも呼ばれる）はグラフ上のランダムウォークに似た決定性の過程である． 本発表では，これを一般化し，無理数の推移確率をも模倣する関数ルーターモデルを扱う． 関数ルーターモデルと対応するマルコフ連鎖の「分布」について議論し，マルコフ連鎖の混交時間（mixing time）を使って 単一頂点誤差の上界を与える． 宇野 毅明(NII) タイトル：「列挙に対するアルゴリズム設計戦略」 アブスト： 列挙アルゴリズムに対する研究は、構造的、あるいは計算的なアプローチに基づくものが多く、数理的アプローチを多く取る 最適化型のアルゴリズムに対する研究と比べると少し味付けが異なるような感覚を覚えることと思う。 この講演では、その中でもまた少し異質な、計算的なアプローチに基づくアルゴリズムの設計戦略について話をしたい。 具体的には、遅延時間を短くする方法を２つ、それと計算量を小さくする方法を１つ、 両方ともアルゴリズムデザイン的なアプローチからのものである。 ジョーダン　チャールズハロルド(北大) タイトル：論理式の探索と自動合成による計算限界解析 アブストラクト： 最近は形式検証や機械学習で論理式の探索と自動合成に関する研究が増えている。 そこで、形式論理と計算量クラスとの関係や、様々な論理の標準系などを用いる。 ここでは、このような応用をunifyする論理式の探索と自動合成について一般的なモデルを紹介する。 特にグラフなどの関係ストラクチャーだけではなく、metafiniteストラクチャーについて考える。 また、応用などで必要なソルバや大規模な計算機への対応について紹介する。 宇野 裕之(大阪府大) タイトル：「パラメータ化計算に関する未解決問題の調査と探求による計算複雑さ解明」　 アブストラクト： 本課題は, パラメータ化計算分野において提示される大小さまざまな未解決問題に着目し, 幅広い調査や整理とともに過去の研究で自身が得た未解決問題との間に有機的な関連を見出し, それらを解決することにより計算複雑さ解明への突破口を見出すことを目指す. パラメータ化計算分野の未解決問題として現時点で注目するものとしては， たとえば平面的有向グラフにおける最長路問題に対する劣指数時間アルゴリズムや， 辺グラフ枝削除問題に対する高速固定パラメータアルゴリズムなどがある． 泉 泰介(名工大) タイトル：公募班テーマ紹介「分散並列計算と逐次計算における計算限界導出技法の融合と深化」 アブストラクト： 分散計算における計算複雑性の理論は、種々の特徴的な要因により逐次計算における複雑性理論とは異なる形で 発展を遂げてきたが、両者をより高次な視点から考察し、共通の困難性を見いだすような視点からの研究はあまり進んでいない。 このような状況を打破するため、本研究では特に分散並列計算をある種の情報欠落計算の一種と位置づけ、 逐次計算における同種のパラダイムとの間で共通する困難性の本質を括り出すことを目標とする。 本発表ではこのような研究の方向性に対する現状の俯瞰，また研究課題として取り組んでいく具体的なテーマ等を紹介する． 塩浦 昭義(東工大) タイトル：非線形整数計画問題の組合せ構造解析による計算限界の解明 アブストラクト： 私の研究課題では，整数格子点上で定義される非線形な関数（離散関数）が与えられ，それを最小化する整数ベクトルを求める， という非線形整数計画問題を扱う． 本研究課題では，離散関数の多面体構造に注目し，効率的に最小化可能な離散関数のクラスを，その凸閉包関数の 多面体構造によって特徴付けることを目的とする． 本発表では，この課題に関連するこれまでの研究成果，および今後の方針について説明する． 5月30日 小林佑輔(筑波大学) タイトル：有向木詰め込み問題に対するアルゴリズム アブストラクト：有向木詰め込みに関する Edmonds の定理は，互いに辺を共有しない有向木の最大個数が ある種の最小カット値と等しいことを示すものであり，この最大最小定理に基づいて有向木詰め込みに関する 様々な最適化問題のアルゴリズムが与えられている． 近年，Edmonds の定理やアルゴリズムの様々な方向への一般化，抽象化が研究されており，組合せ最適化問題に対する 多面体的なアプローチの適用範囲が徐々に拡がっている． 本講演では，有向木詰め込みに関する既存研究について紹介した後，さらなる拡張に関する成果について紹介する． なお，講演内容の一部は Kristof Berczi氏，Tamas Kiraly氏との共同研究に基づくものである． 森 立平(東工大) タイトル：一般の凸錐を用いた拡張定式化と一般確率論における通信複雑度: 計算量理論に基づく量子力学の特徴付けへ向けて アブストラクト： 線形関数を目的関数に持つ0-1最適化問題Pについてその実行可能解それぞれを頂点として持つ多面体上の線形関数最適化が 元の問題Pを厳密に解く一方、その多面体の表現に必要な不等式の数は一般的に変数の数に関して指数関数的に増大する。 近年 P vs NP 問題へのアプローチの一つとしてNP困難である特定の0-1線形関数最適化問題に対応する 多面体の表現の最小サイズを「多面体の複雑度」とみなし、その下界を評価する研究が盛んである。 線形不等式制約を用いた表現における多面体の複雑度について研究が進んでいる一方で一般の凸錐制約を用いた表現を扱う研究は まだあまりなされていない。 最近 Fiorini達は「ハミルトン閉路多面体を含む大きな多面体のクラス(多面体のクラスにおけるNPの類似とでも言うべきもの) について常に完全正値錐制約を用いた多項式サイズの表現が存在する」ことを示した。 また多面体の複雑度と一般確率論における通信複雑度の等価性より「量子力学の特徴付けに通信複雑度を用いること」を提案した。 本発表では上記のFiorini達の結果及び一般確率論(量子力学を単純な要請から特徴付けることを目的とする数理物理の分野) について紹介する。 Fiorini達の提案に関連して「計算量理論を一般確率論への要請として用いること」を考察する。 また発表者による関連研究として古典グラフィカルモデル上のいくつかのテクニック(ホログラフィック変換、 確率伝搬法、ループ計算)の一般確率論への一般化を簡単に紹介する。 安永　憲司 (金沢大) タイトル：符号理論における計算限界の解明 アブストラクト： 本研究では、誤り訂正符号化技術における計算限界の解明を目的とする。 特に、計算量制限通信路に対して訂正能力の可能性と限界を明らかにすることを目指す。 可能性を探る方向として、暗号理論で発展してきた漏洩耐性暗号技術や難読化技術を用いることで、 これまでに示されていなかった誤り訂正の可能性および明示的構成法を示すことを目指す。 限界を探る方向として、計算量理論や暗号理論で発展してきたブラックボックス分離技法を用いることで、 効率的な訂正の不可能性を示すことを目指す。 コルマン・マティアス(NII) Title: Time-Space Trade-off algorithms for Sensor Networks Abstract: In this talk we will discuss relationship between the running time of the algorithms and the amount of available space. Clearly, if we give more resources (say, memory) to any program, we expect it to find the solution faster. We are interested in how much of a reduction will that bring. Say, will the running time of the algorithm halve if we double the available space? Or will it only be reduced by a 10%? We study the exact dependency between these parameters. 伊藤 健洋(東北大学) タイトル： 解空間のパラメータ化解析による計算困難性と容易性の解明 アブストラクト： 本研究では，解空間の連結性を問う「解の遷移問題」をパラメータ化計算量の観点から研究する． 解の遷移問題とは，基となる問題の実行可能解が2 つ与えられたとき，その間を段階的に遷移できるか判定する問題である． 本研究では，主に解のサイズをパラメータに用いて，遷移問題の解空間をパラメータ化解析する． PSPACE 完全である遷移問題では，その解空間の直径（遷移にかかる最短ステップ数の最悪値）は超多項式長となるが， 本研究ではパラメータにどのように依存した直径になるのか，より詳細な解析を与える． 森前　智行(群馬大) タイトル：BQPのちょっと下とちょっと上 アブストラクト： BQPの「ちょっと下」と「ちょっと上」のクラスを調べることにより、 量子計算量の理解を深めるとともに、 古典計算量の研究にもつなげる、というのが本研究の目的である。 １．BQPのちょっと下： 量子回路で使うキュービットの１つを除き全てが古典ランダムビットにおきかわった ような量子回路はDQC1回路と呼ばれている。 DQC1回路が解ける問題のクラスは明らかにBQPではなく、それどころかBPPに 入ってしまうように見える。しかしながら、面白いことに、 DQC1回路の出力確率分布が古典計算機で効率的にサンプルできたら 多項式階層が第二レベルで崩壊することが示された[1,2]。多項式階層の崩壊が ありえないと仮定するならば、このような大きく制限された量子計算モデルでも、 ある意味「古典計算機よりも速い」ということがいえるのである。 ２．BQPのちょっと上： 量子論を拡張した理論の計算量を考えることにより、BQPの理解が深まるとともに、 なぜ量子論は今のような理論体系をしているのかと言う物理的な問題に 計算量の立場からアプローチすることもできる。例えば、ポストセレクションやタイムトラベルが可能で あるような拡張された量子論の計算量はPPやPSPACEになることが 証明されている。しかしながら、PPやPSPACEはBQPのはるか上空にあるため、 もうすこしBQPの「ちょっと上」にある例が欲しいところである。 最近、ポストセレクションにある制限を加えると、PPから、AWPPとWPPの間に 落ちることが示された[3]。AWPPはBQPの現状でベストな上界であるし、BQPはWPPを 含まないと考えられているので、これはBQPの「ちょっと上」の良い例となっている。 [1] TM, Fujii, and Fitzsimons, Physical Review Letters 112, 130502 (2014) [2] Fujii, Kobayashi, TM, Nishimura, Tamate, and Tani, arXiv:1409.6777 [3] TM and Nishimura, arXiv:1502.000