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 GRAPHS
KEEPING REACHABILITY
Tokyo Institute of Technology
School of computing
Ryo Ashida
Sparsification
Cyclic ordered graph
Gadget graph
1
1
0→2
2
1
2→1 2→1
1→2
1
0→2
1→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 rim
edges
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-tree
d
R
space
reporting
O(n) words
O(n(d¡1)/d + k)
d
KDW-tree [n] dn lg n + o(n lg n) bits
O((n(d¡2)/d + k) lg n)
(d¡2)/d
O
((
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, 𝑑𝑑 > 2
20.8765𝑛𝑛
𝑞𝑞 = 𝑝𝑝𝑘𝑘 , log 𝑝𝑝 < 4𝑒𝑒𝑒𝑒𝑒𝑒
𝑞𝑞 = 𝑝𝑝𝑘𝑘 , log 𝑝𝑝 ≥ 4𝑒𝑒𝑒𝑒𝑒𝑒
(𝑒𝑒 = 2.718 … はネイピア数)
2
𝑞𝑞
𝑞𝑞
1−
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.7
0.7
?
0.9
0.1
0.3
0.5
0.2
0.9
0.3
?
0.5
0.7
0
0.3
0.7
2
3
5
?
0.9
0.8
?
0.1
?
0.5
?
0.7
0
4
𝑋
• ユーザーの振舞いは少数の典型ユーザの凸結合
• ノルム制約付きの行列分解でモデル化
クラシック
ジャズ
J-POP
ロック
演歌
T
𝑉
𝑋
𝒳 = ＝ 𝑈 ×
典型ユーザーの結合係数
典型ユーザーの振舞い
アニソン
•
ユーザー数 𝑁 , アイテム数 𝑀 , ランク 𝐾
T
𝒳 = 𝑉
𝑋
＝ 𝑈 ×
協調フィルタリング問題
主結果 (1)
𝑋 の各行が
𝑉 の凸結合
汎化誤差の上界 𝑂
𝑀𝐾+𝑁 log 𝐾
𝑇
一般化
ノルム制約付き
NMF
一般化
ノルム制約付き
行列分解
応用
比較評価情報に基づいた
協調ランキング問題
主結果 (2)
汎化誤差の上界 𝑂
𝐾𝑀 log 𝑀+𝑁 log 𝐾
𝑇
Two Problems on Interval Graphs
Christian Engels1
Rémy Belmonte2
Tómas Magnússon3
1: Tokyo Institute of Technology, 2: University of Electro-Communications, 3:
Rejkavik University
Thursday 22nd December, 2016
Problem 1
Cluster 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-Tree
Start with a complete graph of size k + 1. Repeatedly add vertices
in such a way that every vertex has exactly k neighbors that form a
k + 1 clique.
Question
Let G be a k-Tree. Construct the Cluster Deletion where the
minimal amount of edges are removed where G and k is part of
the input.
Problem 2
Improper Coloring
We call a coloring col(V ) : V → N for a given graph G = (V , E )
having impropriety l if
max #{u ∈ V | col(u) = col(v )} = l.
v ∈V
Interval Graph
Let {S1 , . . . , Sn } be a set of intervals. Then we define the interval
graph to be defined by
V = {v1 , . . . , vn } and E = {{vi , vj } | Si ∩ Sj 6= ∅}. We call G a
unit interval graph if S1 , . . . , Sn have the same length.
Question
Decide if a given unit interval graph has a coloring of impropriety l
using k colors.
SET MEMBERSHIP WITH A FEW BIT PROBES
MOHIT GARG
TOKYO 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| ≤ n
Queries: Is x∈S?
Task: Represent S in memory as a bit vector,
so that membership queries can be answered using a
few bit probes.
s(m,n,t) = minimum number of bits of storage required
for the representation so that queries can be answered
by making t adaptive probes (sequential).
sN(m,n,t) = minimum number of bits of storage required
for the representation so that queries can be answered
by making t non-adaptive probes (parallel).
RESULTS: OLD & NEW
Previous Best
Two
adaptive
probes
Three
non-adaptive
probes
For n < lg m
mnlg((lgm) / n)
O(
)
lgm
n ≥ 16 lgm
mn
Ω(
)
lgm
New
1−
1
4n+1
1−
1
⎢⎣n/ 4 ⎥⎦
O(m
Ω(m
)
)
Ω( mn)
For majority decoding
1
1−
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
© Copyright 2024 ExpyDoc
