| 平成２５年度第２回 ELC領域会議
日時 11月 29日，30日
場所：東北大学 青葉山キャンパス 情報科学研究科棟 ２階 大講義室
アクセス情報：下記のサイト参照
http://www.is.tohoku.ac.jp/access/index.html
仙台駅前(西口）バス停から，710, 713, 715, 719 のいずれかに乗り，
情報科学研究科前バス停にて下車．所要時間は，20～40分です．
時刻表: http://www.donto.co.jp/timetable/citybus/bus_d_result.cgi?SW=90&TG=C&BSC=0050052
プログラム
11月29日
12:45～13:00 事務局連絡
13:00～13:50 講演： Benjamin Rossman (NII)
13:50～14:05 休憩
14:05～14:55 講演： 吉田 悠一 (NII)
14:55～15:10 休憩
15:10～16:00 講演： 畑埜 晃平 (九大)
16:10～17:30 総括班会議 (情報科学研究科棟２階 中講義室)
18：30～ 懇親会 居酒屋赤べこ
http://www.hotpepper.jp/strJ000026165/
11月30日
9:30～11:40 ポスターセッション
A01～C03 班までの各班が1件のポスター発表を＊＊必ず＊＊行う．
ここで，各班には，計画班だけでなく，公募班も含まれる．
13:00～13:50 講演： David Avis (京大)
13:50～14:05 休憩
14:05～14:55 講演： 渋谷 哲朗 (東大)
14:55～15:10 休憩
15:10～16:00 講演： 渡辺 治 (東工大)
16:00～16:15 事務局連絡
Benjamin Rossman (NII)
タイトル： Formulas vs. Circuits for Small Distance Connectivity
アブストラクト： We give the first super-polynomial separation in the power
of bounded-depth (unbounded fan-in) boolean formulas vs.
circuits. We consider the problem STCONN(k(n)) of
determining whether or not an n-vertex graph contains a
path of length <= k(n) between two distinguished vertices.
It is well known that STCONN(k(n)) has *circuits* of size
poly(n) and depth log(k). In contrast, we prove that
*formulas* of depth log(k) require size n^Omega(log(k)) for
all k(n) <= loglog(n). As a corollary, this implies a tight lower
bound of Omega(log(k)) on the depth of polynomial-size
circuits for STCONN(k(n)), improving the previous
Omega(loglog(k)) lower bound of Beame, Impagliazzo and
Pitassi [FOCS 1995].
吉田 悠一 (NII)
タイトル： A Characterization of Locally Testable Affine-Invariant
Properties through Decomposition Theorems
アブストラクト： Let P be a property of functions Fp^n → {0, 1} for a fixed
prime p. An algorithm is called a tester for P if, given a query
access to the input function f, with high probability, it accepts
when f satisfies P and rejects when f is “far” from satisfying
P. In this paper, we give a characterization of affine-invariant
properties that are testable with a constant number of
queries. The characterization is stated in terms of
decomposition theorems, which roughly say that any function
can be decomposed into a structured part that is a function
of a constant number of polynomials, and a pseudo-random
part whose Gowers norm is small. We first show an algorithm
that tests whether the structured part of the input function
has a specific form. We then show that an affine-invariant
property is testable with a constant number of queries if and
only if it can be reduced to the problem of testing whether the
structured part of the input function is close to one of a
constant number of candidates.
畑埜 晃平 (九大)
タイトル： メタラウンディングに基づく離散構造のオンライン予測
アブストラクト： 離散構造のオンライン予測問題は，ルーティングやランキング，ス
ケジューリングなど多くの分野に現れる．離散構造の例としては
s-t パス，集合被覆，順列などが挙げられる．予測者の目標は後
から見て最適な固定の離散構造に匹敵する予測をオンラインで
行うことである．この問題に対する汎用的なアプローチは，対応す
るオフライン（近似）離散最適化アルゴリズムをオラクルとして用
いる事である．これをオフライン－オンライン変換と呼ぶ．しかし，
現在知られ ているオフライン－オンライン変換手法は効率的で
はない．そこで本研究では，オフライン近似アルゴリズムが緩和
に基づく場合において，より効率的なオフライン－オンライン変
換手法を提案する．本研究ではメタラウンディングという特殊な
ウンディングを用いる事により，見通しのよい アルゴリズム設
計・解析が可能となった．
David Avis (京大)
タイトル： Exponential bounds for linear programs
アブストラクト： The first part of talk outlines joint work with Hans Tiwary
on finding exponential bounds for the extension complexity
of various NP-hard problems, including restrictions of
MAX_CUT. The second part outlines joint work with Oliver
Friedmann on finding an exponential lower bound on
Cunninham's pivot selection rule for linear programs and
unique sink orientations of hypercubes. Finally I will
discuss briefly some experimental results on a parallel
implementation of reverse search for vertex and
triangulation enumeration, which is joint work with Gary
Roumanis and Yuji Ishikawa.
渋谷 哲朗 (東大)
タイトル： Indexing Protein 3-D Structures for Faster Similarity Search
アブストラクト： Searching for protein structure-function relationships using
three-dimensional (3D) structural coordinates represents
a fundamental approach for determining the function of
proteins with unknown functions. Since protein structure
databases are rapidly growing in size, the development of
a fast search method to find similar protein substructures
by comparison of protein 3D structures is essential. In this
talk, we introduce a new indexing algorithm for fast protein
3-D structure similarity queries which is designed based
on a statistical model of the target 3-D structures. The new
method runs in O(m + N/m^{0.5}) average-case time, after
O(N log N) preprocessing, where N is the database size
and m is the query length. It is about 2 to 50 times faster
than the previous practically best-known O(N) algorithm,
which was also proposed previously by us, even if we
include the preprocessing time. It is almost 20-1000 times
faster than the naive comparison algorithm, according to
experiments on a huge SCOP database.
渡辺 治 (東工大)
タイトル：平面グラフの到達可能性の省スペース計算可能性
アブストラクト： We show that the reachability problem over directed planar
graphs can be solved simultaneously in polynomial time
and sublinear space, more precisely, O(n^{1/2+eps}) space
by using sublinear space algorithm computing a constant
ratio separator of planar graphs. In this talk we explain the
outline of our approach and report and then we report our
recent improvements on both reachability algorithm and
separator algorithm, which leads us to a new O(n^{1/2})
space and polynomial time algorithm for the planar graph
reachability problem. This is a joint work with T. Asano,
D.G. Kirkpatrick, T. Imai, K. Nakagawa, A. Pavan, and
N.V. Vinodchandran.
|