開催日時	2015年 5月29日（金）～ 5月30日（土）
開催場所	東京工業大学 田町キャンパス キャンパス・イノベーションセンター東京 １階 国際会議室

プログラム
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- ]　懇親会
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 Sensor Networks 講演資料	Korman Matias (NII)
	[13:25-13:50] 解空間のパラメータ化解析による計算困難性と容易性の解明 講演資料	伊藤　健洋 (東北大)
	[13:50-14:15] 計算量的仮定に基づくノンユニバーサル量子計算の研究－ＳＢＱＰと多項式階層 講演資料	森前　智行 (群馬大)
	[14:15-14:25]　事務局連絡

講演概要

Deterministic Random Walks on Finite Graphs
by 来嶋 秀治(九州大学)

数え上げ困難な（#P-hard）問題に対して，1980年代後半から，マルコフ連鎖モンテカルロ(MCMC）法を中心とする様々な乱択近似計算法が開発されてきた一方，決定性の近似アルゴリズムの開発は，近年の重要な挑戦課題になっている．本発表ではMCMC法の脱乱択化へのアプローチとして，決定性ランダムウォークを紹介する．ロータールーターモデル（あるいはPropp機械とも呼ばれる）はグラフ上のランダムウォークに似た決定性の過程である．本発表では，これを一般化し，無理数の推移確率をも模倣する関数ルーターモデルを扱う．関数ルーターモデルと対応するマルコフ連鎖の「分布」について議論し，マルコフ連鎖の混交時間（mixing time）を使って単一頂点誤差の上界を与える．

列挙に対するアルゴリズム設計戦略
by 宇野 毅明(NII)

列挙アルゴリズムに対する研究は、構造的、あるいは計算的なアプローチに基づくものが多く、数理的アプローチを多く取る最適化型のアルゴリズムに対する研究と比べると少し味付けが異なるような感覚を覚えることと思う。この講演では、その中でもまた少し異質な、計算的なアプローチに基づくアルゴリズムの設計戦略について話をしたい。具体的には、遅延時間を短くする方法を２つ、それと計算量を小さくする方法を１つ、両方ともアルゴリズムデザイン的なアプローチからのものである。

論理式の探索と自動合成による計算限界解析
by ジョーダン　チャールズハロルド(北大)

最近は形式検証や機械学習で論理式の探索と自動合成に関する研究が増えている。そこで、形式論理と計算量クラスとの関係や、様々な論理の標準系などを用いる。ここでは、このような応用をunifyする論理式の探索と自動合成について一般的なモデルを紹介する。特にグラフなどの関係ストラクチャーだけではなく、metafiniteストラクチャーについて考える。また、応用などで必要なソルバや大規模な計算機への対応について紹介する。

パラメータ化計算に関する未解決問題の調査と探求による計算複雑さ解明
by 宇野 裕之(大阪府大)

本課題は, パラメータ化計算分野において提示される大小さまざまな未解決問題に着目し,幅広い調査や整理とともに過去の研究で自身が得た未解決問題との間に有機的な関連を見出し,それらを解決することにより計算複雑さ解明への突破口を見出すことを目指す. パラメータ化計算分野の未解決問題として現時点で注目するものとしては, たとえば平面的有向グラフにおける最長路問題に対する劣指数時間アルゴリズムや，辺グラフ枝削除問題に対する高速固定パラメータアルゴリズムなどがある．

公募班テーマ紹介「分散並列計算と逐次計算における計算限界導出技法の融合と深化」
by 泉 泰介(名工大)

分散計算における計算複雑性の理論は、種々の特徴的な要因により逐次計算における複雑性理論とは異なる形で発展を遂げてきたが、両者をより高次な視点から考察し、共通の困難性を見いだすような視点からの研究はあまり進んでいない。このような状況を打破するため、本研究では特に分散並列計算をある種の情報欠落計算の一種と位置づけ、逐次計算における同種のパラダイムとの間で共通する困難性の本質を括り出すことを目標とする。本発表ではこのような研究の方向性に対する現状の俯瞰，また研究課題として取り組んでいく具体的なテーマ等を紹介する．

非線形整数計画問題の組合せ構造解析による計算限界の解明
by 塩浦 昭義(東工大)

私の研究課題では，整数格子点上で定義される非線形な関数（離散関数）が与えられ，それを最小化する整数ベクトルを求める，という非線形整数計画問題を扱う．本研究課題では，離散関数の多面体構造に注目し，効率的に最小化可能な離散関数のクラスを，その凸閉包関数の多面体構造によって特徴付けることを目的とする．本発表では，この課題に関連するこれまでの研究成果，および今後の方針について説明する．

有向木詰め込み問題に対するアルゴリズム
by 小林佑輔(筑波大学)

有向木詰め込みに関する Edmonds の定理は，互いに辺を共有しない有向木の最大個数がある種の最小カット値と等しいことを示すものであり，この最大最小定理に基づいて有向木詰め込みに関する様々な最適化問題のアルゴリズムが与えられている．近年，Edmonds の定理やアルゴリズムの様々な方向への一般化，抽象化が研究されており，組合せ最適化問題に対する多面体的なアプローチの適用範囲が徐々に拡がっている．本講演では，有向木詰め込みに関する既存研究について紹介した後，さらなる拡張に関する成果について紹介する．なお，講演内容の一部は Kristof Berczi氏，Tamas Kiraly氏との共同研究に基づくものである．

一般の凸錐を用いた拡張定式化と一般確率論における通信複雑度: 計算量理論に基づく量子力学の特徴付けへ向けて
by森 立平(東工大)

線形関数を目的関数に持つ0-1最適化問題Pについてその実行可能解それぞれを頂点として持つ多面体上の線形関数最適化が元の問題Pを厳密に解く一方、その多面体の表現に必要な不等式の数は一般的に変数の数に関して指数関数的に増大する。近年 P vs NP 問題へのアプローチの一つとしてNP困難である特定の0-1線形関数最適化問題に対応する多面体の表現の最小サイズを「多面体の複雑度」とみなし、その下界を評価する研究が盛んである。線形不等式制約を用いた表現における多面体の複雑度について研究が進んでいる一方で一般の凸錐制約を用いた表現を扱う研究はまだあまりなされていない。最近 Fiorini達は「ハミルトン閉路多面体を含む大きな多面体のクラス(多面体のクラスにおけるNPの類似とでも言うべきもの)について常に完全正値錐制約を用いた多項式サイズの表現が存在する」ことを示した。また多面体の複雑度と一般確率論における通信複雑度の等価性より「量子力学の特徴付けに通信複雑度を用いること」を提案した。本発表では上記のFiorini達の結果及び一般確率論(量子力学を単純な要請から特徴付けることを目的とする数理物理の分野)について紹介する。Fiorini達の提案に関連して「計算量理論を一般確率論への要請として用いること」を考察する。また発表者による関連研究として古典グラフィカルモデル上のいくつかのテクニック(ホログラフィック変換、確率伝搬法、ループ計算)の一般確率論への一般化を簡単に紹介する。

符号理論における計算限界の解明
by 安永　憲司 (金沢大)

本研究では、誤り訂正符号化技術における計算限界の解明を目的とする。特に、計算量制限通信路に対して訂正能力の可能性と限界を明らかにすることを目指す。可能性を探る方向として、暗号理論で発展してきた漏洩耐性暗号技術や難読化技術を用いることで、これまでに示されていなかった誤り訂正の可能性および明示的構成法を示すことを目指す。限界を探る方向として、計算量理論や暗号理論で発展してきたブラックボックス分離技法を用いることで、効率的な訂正の不可能性を示すことを目指す。

Time-Space Trade-off algorithms for Sensor Networks
by Korman Matias (NII)

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.

解空間のパラメータ化解析による計算困難性と容易性の解明
by伊藤 健洋(東北大学)

本研究では，解空間の連結性を問う「解の遷移問題」をパラメータ化計算量の観点から研究する．解の遷移問題とは，基となる問題の実行可能解が2 つ与えられたとき，その間を段階的に遷移できるか判定する問題である．本研究では，主に解のサイズをパラメータに用いて，遷移問題の解空間をパラメータ化解析する．PSPACE 完全である遷移問題では，その解空間の直径（遷移にかかる最短ステップ数の最悪値）は超多項式長となるが，本研究ではパラメータにどのように依存した直径になるのか，より詳細な解析を与える．

BQPのちょっと下とちょっと上
by 森前　智行(群馬大)

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