header

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

第1回

日 時 5月12日 (水) 13:30〜15:00

講演者 Simeon Reich 氏 (The Technion - Israel Institute of Technology, Haifa / Israel)

場 所 W 1008 号室

題 目 Genericity and Porosity in Nonlinear Analysis and Optimization

要 旨

In this lecture I intend to present several recent examples of the generic approach to nonlinear problems. In this approach, instead of considering, for instance, the convergence of an algorithm, one investigates an appropriate space of algorithms equipped with some natural complete metric and shows that convergence does indeed occur for almost all algorithms there. Sometimes one can show that the complement of the good subset is not only of the first category, but is also a sigma-porous set. My intention is to make the lecture accessible to a general audience.

第2回

日 時 6月2日 (水) 13:30〜15:00

講演者 Glenn Shafer 氏 (Rutgers Business School)

場 所 W 1008 号室

題 目 Is everything stochastic?

要 旨

It is always possible, using randomization, to make sequential probability forecasts that will pass any battery of well-behaved statistical tests. This result, which follows directly from von Neumann's minimax theorem once we accept the game-theoretic framework for probability, casts doubt on the conventional understanding of stochasticity.

Reference: “Good sequential probability forecasting is always possible”, by Vladimir Vovk and Glenn Shafer. Working Paper #6 at www.probabilityandfinance.com.

(下平先生より) Shafer先生のご専門は数理ファイナス,ゲーム理論,確率論など広範囲におよび著書も多数 あります.講演者のウェブサイトは http://www.glennshafer.com/ です.

第3回

日 時 7月21日 (水) 13:30〜15:00

講演者 Rene Peralta 氏 (Yale University)

場 所 W 1008 号室

題 目 Multiplicative complexity, fractals, and applications to electronic commerce?

要 旨

The multiplicative complexity of a function is the number of AND gates necessary and sufficient to compute it using the base (AND,XOR,NOT). A powerful class of protocols in electronic commerce have communication cost linearly proportional to the multiplicative complexity of the functions involved. We will explain this relation and then move on to our results on the complexity of symmetric functions. We show that fractals (specifically, Sierpinski's gasket) can be used to bound the complexity of threshold and other important symmetric functions. We conclude the talk by presenting some simple applications and discussing open problems.

This is joint work with Joan Boyar.

第4回

日 時 : 10月6日 (水) 13:30〜15:00

講演者 : Philippe G. LeFloch 氏 (University of Paris 6)

場 所 : W 1008 号室

題 目 : Conservation Laws and Shock Waves

要 旨 :

In this lecture, I will review the well-posedness theory for nonlinear hyperbolic systems of conservation laws. The solutions contain shock waves and are sought in the space of functions of bounded variation. The talk will cover the existence (Glimm), uniqueness (Bressan and LeFloch), and continuous dependence (Bressan, LeFloch, Liu, Yang) of entropy solutions of genuinely nonlinear, conservative systems.

第5回

日 時 : 10月27日 (水) 13:30〜15:00

講演者 : Hosam M. Mahmoud 氏 (George Washington Univ.)

場 所 : W 1008 号室

題 目 : Polya process and random sprouts

要 旨 :

We investigate the Polya process, which underlies an urn of white and blue balls growing in real time. A partial differential equation governs the evolution of the process. For urns with (forward or backward) diagonal ball addition matrix the partial differential equation is amenable to asymptotic solution. In the case of forward diagonal we find a solution via the method of characteristics; the numbers of white and blue balls, when scaled appropriately, converge in distribution to independent Gamma random variables. The method of characteristics becomes a bit too involved for the backward diagonal process, except in degenerate cases, where we have Poisson behavior. In nondegenerate cases, constant limits are found via the method of moments, and matrix formulation involving a Leonard pair.

Moreover, an average-case analysis for all tenable Polya processes, without any constraints, is given. We present applications of the Polya process to the sprout, a random tree growing in real time. The sprout is proposed as a model for the growth of the Internet. The tree size is analyzed via a special associated two-color Polya process. In addition to the usage of this average-case analysis in evaluating sprouts, we also give a heuristic interpretation of the result for Polya urns, which might be a first step toward understanding several nonclassic urn models, as those with nonconstant row sum and those with multiple eigenvalues.

第6回

日 時 : 10月29日 (金) 15:00〜16:00

講演者 : 河内亮周 氏 (東京工業大学)

場 所 : W 1008 号室

題 目 : Computational Distinguishability between Quantum States

要 旨 :

We introduce a distinguishability problem between quantum states as a new underlying problem for computational cryptographic schemes secure against quantum adversaries. The problem is actually a natural generalization of distinguishability problems between probability distributions, which is commonly used in computational cryptography. Specifically speaking, our problem QSCDff is defined as a quantum state computational distinguishability problem between two types of random coset states with a hidden permutation over the symmetric group. In this talk, we show that (i) QSCDff has the trapdoor property; (ii) the average-case complexity of QSCDff completely coincides with its worst-case complexity; (iii) the computational complexity of QSCDff is lower- bounded by the worst-case hardness of the graph automorphism problem. These properties enable us to construct cryptographic systems. Actually, we present cryptographic applications based on the hardness of QSCDff. This is a joint work with T. Koshiba, H. Nishimura, and T. Yamakami.

第7回

日 時 : 11月24日 (水) 15:30〜16:30

講演者 : 松本眞 氏 (広島大学)

場 所 : W 1008 号室

題 目 : 擬似乱数の非統計的検定と符号理論

要 旨 :

擬似乱数とは、サイコロを振ったかのようにデタラメに見える数列のことである。大規模シミュ レーションなどで高速生成が要求される場合は、単純な漸化式で生成する必要があり乱数性が 損なわれることが多い。乱数性の欠陥を捕らえるのに、通常は統計的検定を行う。すなわち擬似 乱数を発生しいくつかずつ組にしてあるテスト関数で変換し、その分布が期待分布から甚だしく ずれているか否かを統計的に検定する。しかし、有限代数などを用いて作られた擬似乱数の場合 には、擬似乱数がつくる分布が符号理論などの代数理論を用いて精密に計算できる場合がある。 その結果、C言語の標準擬似乱数を使ってコイン投げギャンブルをするとどんどんもうかるような 戦略が立てられる。このことを紹介する。

第8回

日 時 : 11月30日 (火) 15:00〜16:00

講演者 : 来嶋 秀治 氏 (東京大学)

場 所 : W 809 号室

題 目 : マルコフ連鎖を用いたサンプリング法

要 旨 :

本発表ではマルコフ連鎖を用いたサンプリング法について述べる。マルコフ連鎖を用いたサンプ リング法は MCMC(マルコフ連鎖モンテカルロ)法、 Gibbsサンプラーといった形で統計物理、 数値積分、画像処理などの多岐にわたる分野に現れる。実用において、マルコフ連鎖の収束の速さ は計算効率と結果の信頼性を議論する上で欠かせない話題である。本発表ではマルコフ連鎖の収束 の速さの算定に関連する話題に触れる。特に、1996年に Propp and Wilson によって提案された CFTP (Coupling From The Past)アルゴリズムを紹介する。このアルゴリズムはLas Vegas 型の乱択アルゴリ ズムで マルコフ連鎖のシミュレーションを工夫することで定常分布に厳密に従うサンプリングを 実現する画期的な手法として注目を集めている。

第9回

日 時 : 12月14日 (火) 16:00〜

講演者 : Wojciech Zajaczkowski 氏 (ポーランド科学アカデミー)

場 所 : W 809 号室

題 目 : Global axially symmetric solutions to the Navier-Stokes equations in a cylinder and with large swirl.

第10回

日 時 : 12月24日 (金) 14:00〜15:00

講演者 : C. Castaing 氏 (Universite Montpellier II)

場 所 : W 1008 号室

題 目 : Some limits results for integrands and Hamiltonians with application to viscosity

第11回

日 時 : 1月26日 (水) 14:00〜15:00

講演者 : Sunyoung Kim 氏 (Ewha Womans University)

場 所 : W 1008 号室

題 目 : Convex relaxation methods for polynomial optimization problems

要 旨 :

Optimization problems with polynomial objective and constraints represent a broad range of applications in science and engineering. The main idea of convex relaxation methods for polynomial optimization problems is to relax nonconvex constraints and objective function with convex ones. Convex relaxation methods such as semidefinite relaxation and sums of squares relaxation have been widely used for successful finding of optimal values. We discuss various convex relaxation methods in view of effectiveness and efficiency in practice.

第12回

日 時 : 2月4日 (金) 13:30〜14:30

講演者 : Magnus M. Halldorsson 氏 (University of Iceland)

場 所 : W 809 号室

題 目 : Graph coloring: From maps to wireless networks and job scheduling

要 旨 :

The four coloring problem was one of the most celebrated problems in modern Mathematics. Although its motivation for coloring maps was never really substantiated, a lot of problems of practical importance depend on graph coloring. We will examine several recent variations of graph coloring along with their applications. In particular, we will look closely at two topics. The first is coloring planar graphs such that common neighbors of a node must also receive different colors. This is motivated by constraints in radio communications, where different neighbors of a node must be assigned different frequencies in order to avoid collisions. The second topic involves generalizations that correspond to situations in the scheduling of dependent tasks. We will consider some variations of this theme with the focus on the application of data migration, where the task is to transfer files and data within a network.

第13回

日 時 : 2月9日 (水) 16:00〜17:00

講演者 : 福田 公明 氏 (EPFL / ETH Zentrum)

場 所 : W 1008 号室

題 目 : Union of convex polytopes: When is it convex? How to wrap it?

要 旨 :

Consider the union $P$ of $k$ convex polytopes $P_1$, $P_2$, ..., $P_k$ in $\R^d$. In this talk, we consider various questions on $P$, some theoretical and others computational. A most natural question is to characterize when the union $S$ is convex. We shall consider two cases, the case where each $P_i$'s are H-polytopes (given as an intersection of halfspaces) and the case where they are V-polytopes (given by their vertices). Some characterizations lead to polynomial algorithms for convexity recognition, while others do not seem to suggest immediate algorithmic consequences.

In the second part, we look at the problem of computing the H-representation of the convex hull of $P$, when each input $P_i$'s are given as H-polytopes. A reverse search algorithm is proposed that runs in time polynomial in the sizes of input and output, under a nondegeneracy assumption.

(The first part is based on joint works with I. Barany, A. Bemporad and F.D. Torrisi. The second part is jointly with T.M. Liebling and C. L\"utolf.)

第14回

日 時 : 2月28日 (月) 15:00〜16:00

講演者 : 藤澤 克樹 氏 (東京電機大学/産業技術総合研究所)

場 所 : W 809 号室

題 目 : グリッド技術を用いたサプライ・チェイン最適化システム

要 旨 :

近年の計算機や通信技術の急速な進歩によって,工学や理学などの多くの分野で大規模な数値計算が 行われていることは良く知られている。最適化問題の分野においても,この数年で想定する問題の規模, 適用する手法, 実問題への適用可能性などの考え方に大きな変化が生じている。本講演ではその一例と してサプライ・チェイン最適化問題を取り上げて解説していく。 我々が開発したサプライ・チェイン最適化のための意思決定支援システムとしては,在庫方策最適化, 安全在庫配置,配送計画,ロジスティクス・ネットワーク設計,収益管理,需要予測,ロットサイズ 決定,スケジューリングなどがある.これらの意思決定支援システムは,すべてWebアプリケーション であり,インターネット経由で使用することが可能である。 本講演では,これらの意思決定支援システムの概要について解説を行う.また最適化問題を実用的な 時間で解くためには多くの計算機資源が必要となるので,クラスタ計算(Cluster Computing)とグリッド 計算(Grid Computing)などの最近注目を集めている並列計算の手法についても触れ、これらの最新技術 をどのように Web アプリケーションに組み込んでいくかについても解説を行う。