2016.12.22
NII Winter Festa

ELC: Exploring the Limits of Comp.
私たちの目標新学術領域 「計算限界解明」
科研費新学術領域 H24 ～ H28
多面的アプローチの統合による計算限界の解明

領域代表
渡辺 治（東京工業大学）

目標：計算限界の解明への確かな道筋
Clay 数学研究所

21世紀の7 大数学問題の１つ

百年の計コンピュータの黎明期からの未解決問題① 新たな段階へ

確かな研究の道筋 ② 新たな道を築く

障害や問題点を解決し，新たな段階へと進む

将来性の高い質の良い道を築く

今がその時機
我々ならば可能計算限界の解析技法が研ぎ澄まされてきた 2000年～

数理科学の様々な分野の研究者を組織化できる目標：計算限界の解明への確かな道筋
なぜ計算限界？

① 新たな段階へ

確かな研究の道筋 ② 新たな道を築く

障害や問題点を解決し，新たな段階へと進む

将来性の高い質の良い道を築く

今がその時機
我々ならば可能計算限界の解析技法が研ぎ澄まされてきた 2000年～

数理科学の様々な分野の研究者を組織化できる

なぜ「計算限界」？
なぜ計算？
情報を形にできるからコンピュータに載せる
人類が初めて 「情報」を様々な角度から見ることが可能となった

なぜ「計算限界」？
なぜ計算？
情報を形にできるからなぜ計算限界？
計算を真に理解するため４年半やって．．．．
計算の理解を深める
計算の目標
おもしろいことがわかってきた！ 様々なアルゴリズム

なぜ「計算限界」？
なぜ計算？
情報を形にできるからなぜ計算限界？
計算を真に理解するため

２０１７年３月１１日（土）東工大田町キャンパス
国際会議場（駅から１分）

４年半やって．．．．
計算の理解を深める
おもしろいことがわかってきた！

是非，おいで下さい
知的好奇心にお応えできますELC プレゼンター
芦田 亮
石山 一樹
大舘 陽太
玉置 卓
森富 賢一郎

東京工業大学東京大学
北陸先端科学技術大学院大学
京都大学
九州大学

長尾 篤樹
電気通信大学 ＥＬＣ ＰＤ
Christian Engels東京工業大学 ＥＬＣ ＰＤ
Mohit Garg
東京工業大学 ＥＬＣ ＰＤSPARSIFICATION OF GRAPHSKEEPING REACHABILITY
Tokyo Institute of Technology
School of computing

Ryo AshidaSparsification
Cyclic ordered graphGadget graph

1

10→22
12→1 2→1
1→2

10→21→INF• Vertices lie on a circumference of a circle• Cyclic ordered graph with edge-level• There is no edge outside a circle• Keep reachability between vertices on the• Assume that there are vertices at intersections of rimedges

Application• Planar graph reachability problem• Small graph separator

small separator
separator

高次元直交領域探索問題のための簡潔データ構造
東京大学大学院

石山 一樹定兼 邦彦

問題設定
d 次元空間の n 点集合 P と直交領域 Q に対してreporting

Q に含まれる P の点を列挙する

counting

Q に含まれる P の点の数を答える
P が与えられる

Q

データ構造を構築 小さく
counting

4

Q が与えられる
クエリに答える速く高次元直交領域探索問題のための簡潔データ構造
東京大学大学院

石山 一樹

定兼 邦彦

主結果
データ構造 空間kd-treedR

spacereportingO(n) words

O(n(d¡1)/d + k)

dKDW-tree [n] dn lg n + o(n lg n) bits

O((n(d¡2)/d + k) lg n)(d¡2)/dO((n+ k) lg n/ lg lg n)提案手法 [U ]d dn lg U + o(n lg※n)d bits(¸ 3) は定数，k は列挙する点の数● 簡潔データ構造である

空間計算量● KDW-tree を改善

漸近的に一致情報理論的下界提案手法で U = n として KDW-tree と比較
空間計算量は一致．クエリ時間計算量は改善．

最長増加部分列 対

省

発表者: 大舘 陽太 (ELC A03, JAIST)
共著者: 清見 礼，小野 廣隆，Pascal Schweitzer
省
入力 読込 専用

格納

出力 書

込 専用

出力

使

作業用

小動機
入力

巨大小成果 (ISAAC 2014)

n + O(log n)(ELC A03) 清見，小野，大舘，Schweitzer，多項式時間省

最長増加部分列DFS
2016 年 12 月 22–23 日

1/2

最長増加部分列 対
本研究

省

目的

最長増加部分列発見

省

設計[10, 11, 6, 7, 15, 5, 8, 9, 2, 4, 12, 14, 1, 13, 3]Theorem (C.L. Mallows 1973)
O(n log n)，O(n log n) 時間

Theorem (今回 結果)√O( n · log n)(ELC A03) 清見，小野，大舘，Schweitzer，O(n3.5 log n) 時間

省

最長増加部分列

2016 年 12 月 22–23 日

2/2

Beating Brute Force for Systems of
Polynomial Equations over Finite Fields
Suguru Tamaki (Kyoto U.)

joint work with

Daniel Lokshtanov, Ramamohan Paturi, Ryan Williams, Huacheng Yu(U. Bergen) (U. California, San Diego) (Stanford U.) (Stanford U.)

有限体𝑭𝑭𝒒𝒒 上の𝒏𝒏変数連立𝒅𝒅次方程式系

入力 𝑑𝑑次多項式 𝑃𝑃1 , 𝑃𝑃2 , … , 𝑃𝑃𝑚𝑚 ∈ F𝑞𝑞 [𝑥𝑥1 , 𝑥𝑥2 , … , 𝑥𝑥𝑛𝑛 ]出力 𝑎𝑎 ∈ F𝑞𝑞𝑛𝑛 s.t. 𝑃𝑃1 𝑎𝑎 = 𝑃𝑃2 𝑎𝑎 = ⋯ = 𝑃𝑃𝑚𝑚 𝑎𝑎 = 0
例 [𝑞𝑞 = 3, 𝑛𝑛 = 4, 𝑑𝑑 = 5, 𝑚𝑚 = 2]
𝑃𝑃1 = 2𝑥𝑥12 𝑥𝑥22 𝑥𝑥3 + 𝑥𝑥32 𝑥𝑥4 , 𝑃𝑃2 = 𝑥𝑥1 𝑥𝑥2 + 𝑥𝑥22 + 1
𝑎𝑎 = 2,2,1,1

𝑑𝑑 ≥ 2 のとき ∃𝜀𝜀 > 0, 𝑞𝑞 (1−𝜀𝜀)𝑛𝑛 時間で解けるか未解決

有限体F𝑞𝑞 上の𝑛𝑛変数連立𝑑𝑑次方程式系
𝑑𝑑 ≥ 2 のとき ∃𝜀𝜀 > 0, 𝑞𝑞 (1−𝜀𝜀)𝑛𝑛 時間で解けるか未解決
本研究の結果
条件

計算時間

𝑞𝑞 = 𝑑𝑑 = 2𝑞𝑞 = 2, 𝑑𝑑 > 220.8765𝑛𝑛

𝑞𝑞 = 𝑝𝑝𝑘𝑘 , log 𝑝𝑝 < 4𝑒𝑒𝑒𝑒𝑒𝑒
𝑞𝑞 = 𝑝𝑝𝑘𝑘 , log 𝑝𝑝 ≥ 4𝑒𝑒𝑒𝑒𝑒𝑒(𝑒𝑒 = 2.718 … はネイピア数)

21−𝑞𝑞

𝑛𝑛

1𝑛𝑛5𝑑𝑑1𝑛𝑛
1−200𝑑𝑑𝑞𝑞log 𝑞𝑞𝑒𝑒𝑒𝑒𝑒𝑒−𝑘𝑘𝑘𝑘ノルム制約付き行列分解に基づいた
行列補完問題に対する汎化誤差の導出
森富 賢一郎1・畑埜 晃平1,2・瀧本 英二1（1:九州大学, 2:理研AIP）

協調フィルタリング問題

𝑋

1

1

2

3

4

5

0.7

0.2

0.9

0.8

0.70.7?

0.9

0.1

0.3

0.5

0.2

0.9

0.3?

0.5

0.7

0

0.3

0.7

235?

0.90.8?

0.1?

0.5?

0.704𝑋• ユーザーの振舞いは少数の典型ユーザの凸結合• ノルム制約付きの行列分解でモデル化

𝒳=𝑋

＝

𝑈

典型ユーザーの結合係数

×

クラシック
ジャズ

J-POP

ロック

演歌

𝑉T

典型ユーザーの振舞い

アニソン

•

ユーザー数 𝑁 , アイテム数 𝑀 , ランク 𝐾

𝒳=
協調フィルタリング問題

𝑋＝𝑈×

𝑉T

主結果 (1)

𝑋 の各行が𝑉 の凸結合

汎化誤差の上界 𝑂

𝑀𝐾+𝑁 log 𝐾
𝑇

一般化

ノルム制約付きNMF
一般化

ノルム制約付き行列分解

応用

比較評価情報に基づいた
協調ランキング問題

主結果 (2)
汎化誤差の上界 𝑂

𝐾𝑀 log 𝑀+𝑁 log 𝐾𝑇

Two Problems on Interval Graphs
Christian Engels1

Rémy Belmonte2

Tómas Magnússon3

1: Tokyo Institute of Technology, 2: University of Electro-Communications, 3:
Rejkavik University

Thursday 22nd December, 2016

Problem 1Cluster Deletion
Let G = (V , E ) be a graph, delete the minimum number of edges
E 0 such that G 0 = (V , E − E 0 ) has the property such that every
connected component is a clique (of possible size 1 or 2).
k-TreeStart with a complete graph of size k + 1. Repeatedly add vertices
in such a way that every vertex has exactly k neighbors that form ak + 1 clique.
Question
Let G be a k-Tree. Construct the Cluster Deletion where theminimal amount of edges are removed where G and k is part ofthe input.

Problem 2Improper Coloring
We call a coloring col(V ) : V → N for a given graph G = (V , E )having impropriety l ifmax #{u ∈ V | col(u) = col(v )} = l.
v ∈VInterval Graph
Let {S1 , . . . , Sn } be a set of intervals. Then we define the intervalgraph to be defined by
V = {v1 , . . . , vn } and E = {{vi , vj } | Si ∩ Sj 6= ∅}. We call G aunit interval graph if S1 , . . . , Sn have the same length.
Question
Decide if a given unit interval graph has a coloring of impropriety lusing k colors.

SET MEMBERSHIP WITH A FEW BIT PROBES

MOHIT GARGTOKYO INSTITUTE OF TECHNOLOGY
December 22, 2016
WINTER FESTA

THE PROBLEM[m]

Universe: {1,2,…,m} = [m].
S
Set: S⊆[m] with at most n elements.
x|S| ≤ nQueries: Is x∈S?
Task: Represent S in memory as a bit vector,
so that membership queries can be answered using afew bit probes.
s(m,n,t) = minimum number of bits of storage required
for the representation so that queries can be answeredby making t adaptive probes (sequential).
sN(m,n,t) = minimum number of bits of storage required
for the representation so that queries can be answeredby making t non-adaptive probes (parallel).

RESULTS: OLD & NEW
Previous Best
Twoadaptive
probesThree
non-adaptiveprobes

For n < lg mmnlg((lgm) / n)O()lgmn ≥ 16 lgm
mn
Ω()
lgm

New1−

14n+1

1−

1⎢⎣n/ 4 ⎥⎦O(mΩ(m))Ω( mn)For majority decoding
11−cn

Ω(m)

(also for 20 out of 22
types of functions)N. Alon, U. Feige: On the power of two, three and four probes, SODA 09
M. Garg, J. Radhakrishnan: Set membership with a few bit probes, SODA 15
M. Garg, J. Radhakrishnan: Set membership with non-adaptive bit-probes, STACS 17