トップ   差分 バックアップ リロード   一覧 単語検索 最終更新   ヘルプ   最終更新のRSS



日時: 2011年11月25日(金)11:00-12:00

会場: 西8号館W棟8階W809号室

講演者: Ellen Hidemi Fukuda 氏 (State University of Campinas & Kyoto University)

題目: Differentiable exact penalty functions for nonlinear second-order cone programs

要旨: We propose a method to solve nonlinear second-order cone programs (SOCPs), based on a continuously differentiable exact penalty function. The construction of the penalty function is given by incorporating a multipliers estimate in the augmented Lagrangian for SOCPs. Under the nondegeneracy assumption and the strong second-order sufficient condition, we show that a generalized Newton method has global and superlinear convergence. We also present some preliminary numerical experiments.


日時: 2011年9月21日(水)16:30-17:45

会場: 西8号館W棟10階W1008号室

講演者: Johaness Koebler 氏 (Humboldt Univ. at Berlin)

題目: Canonizing interval and circular arc graphs

要旨: We present logspace algorithms for computing canonical representations for interval and special cases of circular arc graphs. As a consequence, the isomorphism and automorphism problems for these graphs are solvable in logspace.


日時: 2011年9月15日(木)16:00-17:30

会場: 西8号館W棟8階W809号室

講演者: Jitamitra Desai 氏 (Nanyang Technological University)

題目: A fractional programming approach for determining the stability number of a graph

要旨: In this talk, a continuous optimization approach for determining the stability number (or independence number) of a graph via a fractional programming formulation is presented. While the problem of finding the independence number of a graph is a well-studied problem in the IP literature, the use of continuous optimization techniques for solving this problem is a relatively new area of research. Using some previously known properties of the stability number, we examine several convexity results of the fractional programming formulation, and prove that the fractional program yields the stability number. Characterizations of the local maxima are described, and tight lower and upper bounds on the stability number are derived. These results are utilized in developing a new global optimization algorithm for solving the fractional programming formulation. Detailed computational results that show the efficacy of this approach along with comparisons to other bounds on the stability number are provided using standard test sets in the literature.


日時: 2011年7月6日(水)14:15-

会場: 西8号館W棟8階W809号室

講演者: 岩田具治 氏(NTTコミュニケーション科学基礎研究所)

題目: 確率モデルに基づくデータマイニング

要旨: NTT コミュニケーション科学基礎研究所にて行ってきた確率モデルに基づくデータマイニング研究(定額制サービスのための推薦,クラス構造の可視化,ソーシャルアノテーションの解析)を紹介する.確率モデルを用いることにより,データに内在する不確実性に対応でき,また,確率論の枠組みに従い,多様な情報を統一的に扱うことができる.


クラス構造の可視化:データをそのクラス構造とともに低次元の可視化空間へ埋め込む非線形次元圧縮手法を紹介する.提案法は,可視化空間において混合正規分布を仮定し,原空間における事後確率と可視化空間における事後確率のKullback-Leibler ダイバージェンスができるだけ小さくなるようにデータとクラスを埋め込む.データ間距離(非類似度) を直接計算しないため,従来法に比べ計算効率がよい.分類済Web ページを用いたクラスラベル付きデータの可視化,手書き文字を用いた分類モデルの可視化,単語群を用いたラベルなしデータの可視化を行い,提案法の有効性を示す.

ソーシャルアノテーションの解析:ソーシャルアノテーションサービスでは,ユーザが任意のタグを付与できるため,しばしば内容に関連しないタグが含まれる.内容に関連するタグを自動的に抽出することにより,情報検索の性能向上や,文書分類や画像認識などの機械学習タスクの精度向上が期待できる.そこで,潜在トピックモデルに基づく内容に関連するタグの抽出法を提案する.提案法では,内容とタグが生成される過程をモデル化し,確率的EMアルゴリズムを用いてモデルを推定することにより,関連するタグを自動的に抽出する.人工データ,および,Web ページと画像を対象とするソーシャルアノテーションサービスのデータを用いて提案法の有効性を示す.


日時: 2011年5月27日(金)16:30-17:45

会場: 西8号館W棟10階W1008号室

講演者: Neil Immerman 氏 (University of Massachusetts Amherst)

題目: P versus NP: Approaches, Rebuttals, and Does It Matter?

要旨: NP contains all those problems that we could efficiently solve if "guessing were free", i.e., all those problems whose solutions we could recognize as correct if they were given to us in an appropriate format and context. We've known since 1971 that a large class of important combinatorial problems including boolean satisfiablity (SAT) are NP complete, i.e, hardest problems in NP. If any of these had a solution in P, then so would all other problems in NP.

How hard is SAT, or any other NP-complete problem? It is well believed that P is not equal to NP and that SAT requires exponential time on some hard instances. However, SAT solvers are now in practical use as general problem solvers, currently working even on instances with a million variables.

I will explain some of these issues, laying out what we do know, what we do not know, and what we hope to understand once the P versus NP question, together with many similar but less famous open questions, are finally resolved. At the same time, this talk will present a survey of descriptive complexity -- the logical approach to compexity that I have been pursuing for years.

連絡先:渡辺治 watanabe(at)is.titech.ac.jp


日時: 2011年5月18日(水)13:30-14:30

会場: 西8号館W棟10階W1008号室

講演者: 梅原雅顕 氏 (東京工業大学 数理・計算科学専攻)

題目: 変曲点を持たない平面閉曲線について




日時: 2011年5月11日(水)16:30-17:45

会場: 西8号館W棟10階W1008号室

講演者: Valentine Kabanets 氏(Simon Fraser Univ., Computing Science)

題目: Direct Product Codes: Decoding and Testing


※ Kabanets 先生は数理計算科学専攻の客員教授として5月〜8月まで滞在され,計算の複雑さの理論(平均時計算量)の講義を行います.(数理計算科学特別講義第三,5月16日より)


Abstract. Given a Boolean function f, and parameter k (natural number), we define f^k to be a function mapping k-tuples of inputs x_1,...,x_k to the k-tuple of values f(x_1),...,f(x_k). If we think of the truth table of f as a message, then the truth table of f^k can be viewed as an encoding of f using the Direct-Product Code. This encoding is useful in complexity and cryptography for hardness amplification: if f is somewhat hard on average to compute by certain efficient algorithms, then f^k is much harder on average to compute by a related class of efficient algorithms.

Over the past several years, together with Impagliazzo, Jaiswal, and Wigderson, we gave tight results about both decodability (actually, list-decodability) and testability of such Direct Product codes. Here decodability is the task: given a corrupted version of f^k, recover (a small list of candidates for) a message close to the original message f. The testability is the task: given an oracle F, decide if F is close to being (approximately equal to) f^k, i.e., if F is a Direct-Product codeword. Somewhat surprisingly, the testability result uses the ideas developed for the decodability result, even though there is no formal connection between these two tasks. Finally, the testability result allows us to prove a version of Parallel Repetition Theorem for certain 2-player games, basically showing that the ability to win in k copies of a game decreases exponentially with k.


日時: 2011年4月27日(水)14:30-15:30

会場: 西8号館W棟8階W809号室

講演者: 一杉裕志 氏 (産業総合研究所産 ヒューマンライフテクノロジー研究部門)

題目: 脳とベイジアンネット