陳 致中 (Zhi-Zhong Chen)
Date of birth: (秘密)
1: 経歴
専門分野
 
アルゴリズムと計算量の理論(Theory of Algorithms and Complexity)
学歴
工学学士: 西北電訊工程学院(現 西安電子科技大学)(1985年)
工学修士: 電気通信大学(1989年)
博士(工学): 電気通信大学(1992年)
職歴
1992年
4月
-1994年
3月
三重大学工学部情報工学科助手
1994年
4月
-1997年
9月
東京電機大学理工学部数理学科専任講師
1997年
10月
-2006年3月東京電機大学理工学部数理科学科助教授
2006年
4月
-2008年3月東京電機大学理工学部数理科学科教授
2008年
4月
-現在東京電機大学理工学部情報システムデザイン学系教授
 
2: 海外研究歴
1996年9月1997年8月University of California at Berkeley客員研究員(C. H. Papadimitriouと共同研究)
2000年7月2000年9月University of California at Riverside客員研究員(T. Jiangと共同研究)
2002年7月2002年9月 University of Alberta客員教授(G.-H. Linと共同研究)
2004年7月2004年9月 City University of Hong Kong高級研究員(L. Wangと共同研究)
2007年8月2007年9月 City University of Hong Kong高級研究員(L. Wangと共同研究)
2008年2月2008年4月 City University of Hong Kong高級研究員(L. Wangと共同研究)
2009年8月2009年9月 City University of Hong Kong高級研究員(L. Wangと共同研究)
2010年8月2010年9月 City University of Hong Kong高級研究員(L. Wangと共同研究)
2011年2月2011年3月 City University of Hong Kong高級研究員(L. Wangと共同研究)
2011年8月2011年9月 City University of Hong Kong高級研究員(L. Wangと共同研究)
2012年2月2012年3月 City University of Hong Kong高級研究員(L. Wangと共同研究)
3: 褒賞
平成10年度山下記念研究賞(情報処理学会)
第2回LA/EATCS-Japan発表論文賞(2003年)
 
4: 所属学会
ISRN Combinatorics: Editor
電子情報通信学会ソサイエティ論文誌: 査読委員
LAシンポジウム会員
 
5: 代表的な論文
Reducing Randomness via Irrational Numbers,
SIAM Journal on Computing, Vol. 29, No. 4, pp. 1247-1256, 2000.

この論文で多項式等価性判定問題(2つの多変数多項式P(x,y,...,z)と Q(x,y,...,z)が与えられて,PとQの値が変数x,y,...,zの値に依存せず いつも同じか否かを判定する問題)を考える.この問題で,PとQは必ずしも 展開形で与えられなく,むしろ変数行列の行列式などの形で与えられる. この問題は他の問題に応用が多いが,効率的な解法がまだ知られていない. 一方,この問題を解く効率的な確率アルゴリズムが古くから知られてきた. 本論文で,多項式等価性判定問題を解く新しい確率アルゴリズムを提案し, それの使う乱数の桁数が従来のより遥かに小さいことを示す. この論文の斬新なアイディアは無理数の近似をうまく使い, 無理数の近似をよくすればするほど正しい判定を下す確率を上げる ことができるところにある.
[補足:本論文の発表後,他の研究者はこの論文の成果に刺激されて, 素数判定問題を解く多項式時間アルゴリズムの設計に成功して ビッグニュースになった.]

Map Graphs, Journal of the ACM, Vol. 49, No. 2, pp. 127-138, 2002.
地理情報システムの理論研究でトポロジカル推論問題が研究されてきた. この問題において,2次元図形間のトポロジカル関係(たとえば, 「包含関係」とか「隣接関係」)が与えられて, これらの図形とその間の関係を実現する地図を作成できるか否かを決定 しなければならない.この問題を解くアルゴリズムが存在するか否か ですら分かっていなかった.本論文で,普通の地図で一番よく見られる 「隣接関係」と「非隣接関係」に着目し,この2つの関係しか許さない 場合を考え,この特別な場合を解くアルゴリズムが存在することを示す.
[補足:本論文の発表後,他の研究者はこの論文の成果に刺激されて, トポロジカル推論問題を解くアルゴリズムが存在することを示した.]

Finding Double Euler Tours of Planar Graphs in Linear Time,
SIAM Journal on Computing, Vol. 31, No. 4, pp. 1255-1285, 2002.

本論文で,CMOS(相補型金属酸化物半導体)VLSI回路の設計に関連した 基本的な問題である平面グラフの二重双対オイラー路問題を考える. この問題において,平面グラフGが与えられて,いかにしてGを平面に 埋め込み,埋め込んだあとのGとその双対グラフG'にそれぞれオイラー路 PとP'が存在してPとP'が互いに双対であるようにするかを決定しなければ ならない.この問題を解く多項式時間アルゴリズムが存在するか否かは 未解決であった.本論文で,平面グラフ上で定義された2つの演算の 深い代数的性質を解明して更にそれを活用することによって, この問題を解く最適なアルゴリズムを提案する.
 
6: 現在の研究テーマ
バイオインフォマティクス(Bioinformatics):
生物学における計算困難な問題を,数学とコンピュータの知識を使って解こうとする. 具体的に現在は,生物系統樹の構築およびDNAとタンパク質の解析で現れる計算困難な 問題の効率的なアルゴリズムの開発に興味を持っている.設計したアルゴリズムを 数学的に解析してその良さを理論的に評価するだけではなく,実際にプログラミング言語 でプログラムに実装してから実際のデータを与えてその性能を計測して評価する.

離散アルゴリズム(Discrete Algorithms):
離散的な構造を持つ問題(たとえば,グラフや文字列などの上で 定義された問題)を解くためのアルゴリズムのこと.その設計で, 対象となる問題の深い構造を見出したり,最適なデータ構造を 使ったりするのがポイント.

近似アルゴリズム(Approximation Algorithms):
世の中に役立つ問題の多くは最適化問題(optimization problems). 最適化問題において,多数の可能な解(feasible solutions)の中 から最適な解(optimal solutions)を1つ求める必要がある. しかし残念ながら,ほとんどの最適化問題において,最適解を求める 効率的な方法が存在しそうにない(理論的な根拠がある). 近似アルゴリズムは,(必ずしも最適ではないが)最適に近い解 (近似解という)を効率よく求めるアルゴリズムのこと. 速く解けることが分かっている問題をうまく利用して, 速く解けそうにない問題の近似解を速く計算することが 近似アルゴリズムの設計のポイント.

確率アルゴリズム(Randomized Algorithms):
その実行中で乱数(random numbers)を生成できてかつ乱数の出方に 依存して異なる計算を進められるアルゴリズムのこと. 確率アルゴリズムが実行毎に違う解を出したり, 正しくない解を出したりする可能性がある.しかし, よい確率アルゴリズムは1に近い確率で正しい解を出す. 従来のアルゴリズムで速く解けるか否かまだ分かっていない問題で, 確率アルゴリズムで素早く解けてしまう問題がたくさん知られている. これらの確率アルゴリズムは大抵シンプルでコーディングしやすい. 一方,確率アルゴリズムの解析には高度な数学の知識が必要.

並列アルゴリズム(Parallel Algorithms):
複数個のプロセッサを持つ計算機(いわゆる並列計算機)上で 実行されるアルゴリズムのこと.1個のプロセッサを持つ計算機上で t時間かかる問題を,並列計算機上で遥かにより速く(たとえば, log t 時間で)解きたいのが目的.解きたい問題をいかにして いくつかの互いに独立したほぼ同じサイズの部分問題に分割するか は並列アルゴリズムの設計のポイント.

構造的計算量(Structural Complexity):
計算問題をその計算量に基づいていくつかのクラスに分類して,クラス間の関係や 各クラスの性質と構造などについて研究する.解きやすい問題はなぜ解きやすいのか, 解きにくい問題はなぜ解きにくいのか,...などの理論的根拠を与えるのが目的.