Complexity Seminar
Complexity Seminar とは
Complexity Theory やアルゴリズムに関する Seminar で，１９９５年の
春から東工大と電通大で毎月１回ずつ行なっています．
毎回，講演者 1 人が，
最新の結果の説明や，
今考えていることの説明をゼミ形式で発表する，
というものです．
今のところ，戸田さん，武永さん，渡辺，が世話役になって運営しています．
メイリングリスト
Complexity Seminar のメイリングリストを作成し，
メイリングリストに登録されている方々に，
毎回，案内を出しています．
参加されたい方は，watanabe(at)cs.titech.ac.jp までどうぞ．
今年の発表
過去の発表者と発表内容
- 99.11.17: Ryuhei Uehara
(abstract).
- 99.10.22: Osamu Watanabe
(abstract).
- 99.6.28: UEC Theoretical Computer Science Day
(announce,
program).
- 99.6.4: Crasmaru Marcel
(abstract).
- 99.4.21: Ryuhei Uehara
The number of connected components in graphs and its applications
(abstract).
- 99.3.30: Carlos Domingo
A tutorial on reinforcement learning
(abstract,
slide (gziped ps),
references (text)).
- 99.3.9: Yoshinori Takei
Construction of exactly min-wise independent permutation families
(abstract).
- 99.2.19: Tatsuie Tsukiji
PAC learning of general Boolean concepts
with irrelevant attributes
(abstract).
- 99.1.29: Toru Hasunuma
Page Numbmer of de Bruijn and Kautz digraphs
(abstract).
- 98.11.20: Zhi-Zhong Chen
Topological inference: Known results and open problems
- 98.10.9: Mitsuo Motoki
Unique solution instance generation
for the 3-satisfiability (3SAT) problem
(abstract).
- 98.5.22: Kouichi Yamazaki
On approximation intractability of the path-distance-width problem
(abstract).
- 98.4.21: Osamu Watanabe
An application of the monopolist game to weak learning
(abstract).
- 98.3.2: Paul Vitanyi
Introduction to Kolmogorov Complexity
(abstract).
- 97.11.13: Watanabe-ken
B4 thesis presentation by Yamamoto
(abstract).
- 97.10.28: Seinosuke Toda
Graph Accessibility Problem
(abstract).
- 97.10.9,10: Complexity Workshop
(abstract).
- 97.6.12: R"udiger Reischuk
Average Case Circuit Complexity
(abstract,
manuscript1 (gzipped ps file),
manuscript2 (gzipped ps file)).
- 97.5.29: Osamu Watanabe
Hard Instance Geneartion for SAT
(abstract).
- 97.4.17: Takayuki Nagoya
On Simon's Recognition Algorithm of Interval Graphs
(abstract).
- 97.3.28: Denis Therien
An Algebraic Point of View on Circuit Complexity
(abstract).
- 97.3.13: Ryuhei Uehara
A Measure of Parallelization for the Lexicographically First
Maximal Subgraph Problem
(abstract,
manuscript (gzipped ps file)).
- 97.3.13: Kouichi Yamazaki
It is Hard to Know when Greedy is Good for Finding Independent Sets
(abstract,
manuscript (gzipped ps file)).
- 96.11.21: Kazuyuki Amano
Approximation Method and its Limitation
(abstract,
manuscript (gzipped, in Japanese),
manuscript (gzipped))
- 96.10.18: Tatsuie Tsukiji
DNF is PAC Learnable in Quasi-Polynomial Time
(abstract)
- 96.9.9: Ricardo Baeza-Yates
Fast approximate string matching
(abstract,
manuscript (gzipped))
- 96.6.29: Tao Jiang
Optimal information gathering on the internet
with time and cost constraints
(abstract)
- 96.6.27: Ryumei Okamoto
On relationships between statistical zero-knowledge proofs
(abstract,
manuscript (gzipped))
- 96.4.25: Keisuke Tanaka
On pursuit-evansion problem on grids (extended survey)
(abstract,
manuscript (gzipped))
- 96.1.25: Watanabe-ken
B4 thesis presentation by Watanabe-ken's students
(abstract)
- 95.11.9: Tatsuie Tsukiji
On Shifting Networks over Parity Gates
(abstract)
- 95.10.19: Zhi-Zhong Chen
Practical Approximation Schemes for Maximum Induced-Subgraph Problems
on K_3,3-free or K_5-free graphs
(abstract)
- 95.9.20: Feng Bao
Finite Automata Public Key Cryptosystem
(abstract)
- 95.7.5: Kouichi Yamazaki
On critical Graphs
(abstract)
- 95.6.8: Ryuhei Uehara
Complexity Classes Characterized by Semi-Random Sources
(abstract,
manuscript (gzipped))
- 95.5.18: Zhi-Zhong Chen (Tokyo Denki Daigaku)
Improved Parallel Approximation of Shortest Superstrings
(abstract)
- 95.4.6: Zhi-Zhong Chen (Tokyo Denki Daigaku)
Improved Parallel Approximation of Shortest Superstrings
(abstract)