講演概要

Formulas vs. Circuits for Small Distance Connectivity
by Benjamin Rossman (NII)

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].

A Characterization of Locally Testable Affine-Invariant Properties through Decomposition Theorems
by 吉田 悠一 (NII)

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.

メタラウンディングに基づく離散構造のオンライン予測
by 畑埜 晃平 (九大)

離散構造のオンライン予測問題は，ルーティングやランキング，スケジューリングなど多くの分野に現れる．離散構造の例としてはs-t パス，集合被覆，順列などが挙げられる．予測者の目標は後から見て最適な固定の離散構造に匹敵する予測をオンラインで行うことである．この問題に対する汎用的なアプローチは，対応するオフライン（近似）離散最適化アルゴリズムをオラクルとして用いる事である．これをオフライン－オンライン変換と呼ぶ．しかし，現在知られ ているオフライン－オンライン変換手法は効率的ではない．そこで本研究では，オフライン近似アルゴリズムが緩和に基づく場合において，より効率的なオフライン－オンライン変換手法を提案する．本研究ではメタラウンディングという特殊なウンディングを用いる事により，見通しのよい アルゴリズム設計・解析が可能となった．

Exponential bounds for linear programs
by avid Avis (京大)

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
by 渋谷 哲朗 (東大)

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.

平面グラフの到達可能性の省スペース計算可能性
by 渡辺 治 (東工大)

We show that the reachability problem over directed planargraphs 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.