Committee 
Date Time 
Place 
Paper Title / Authors 
Abstract 
Paper # 
COMP 
20120427 10:35 
Osaka 
Osaka Prefecture University 
Reconstructing Strings from Substrings with Quantum Queries Richard Cleve (Univ. of Waterloo), Kazuo Iwama (Kyoto Univ.), Francois Le Gall (Univ. of Tokyo), Harumichi Nishimura (Nagoya Univ.), Seiichiro Tani (NTT), Junichi Teruyama (Kyoto Univ.), Shigeru Yamashita (Ritsumeikan Univ.) COMP20122 
This paper investigates the number of quantum queries made
to solve the problem of reconstructing an unknown string fro... [more] 
COMP20122 pp.714 
COMP 
20100422 11:10 
Shiga 
Ritusmeikan University, BiwakoKusatsu Campus 
Averaging Techniques for Competitive Auctions Takayuki Ichiba (Nomura Research Institute), Kazuo Iwama (Kyoto Univ.) COMP20103 
[more] 
COMP20103 pp.1724 
COMP 
20091016 15:25 
Miyagi 
Tohoku University 
An Improved Approximation Lower Bound for Maximum Cardinality Almost Stable Matching Problem Koki Hamada, Shuichi Miyazaki, Kazuo Iwama (Kyoto Univ.) COMP200937 
In the stable marriage problem that allows incomplete preference
lists, all stable matchings for a given instance have ... [more] 
COMP200937 pp.3540 
COMP 
20090526 11:15 
Saitama 
Saitama Univ. 
Designing Quantum Game Strategies from Quantum Communication Protocols Kazuo Iwama (Kyoto Univ.), Harumichi Nishimura (Osaka Pref. Univ.), Rudy Raymond (IBM Japan) COMP200912 
In their recent paper, Cleve , Slofstra, Unger and Upadhyay showed that the $CHSH^{\oplus{n}}$, a natural extension of t... [more] 
COMP200912 pp.2128 
COMP 
20080310 09:30 
Kanagawa 

Approximation Algorithms for the SexEqual Stable Marriage Problem Hiroki Yanagisawa (IBM), Shuichi Miyazaki, Kazuo Iwama (Kyoto Univ.) COMP200755 
The stable marriage problem is a classical matching problem introduced
by Gale and Shapley. It is known that for any i... [more] 
COMP200755 pp.18 
COMP 
20071016 10:40 
Miyagi 
Tohoku Univ. 
NPCompleteness of the Stable Roommates Problem with Triple Rooms Kazuya Okamoto, Shuichi Miyazaki, Kazuo Iwama (Kyoto Univ.) COMP200741 
[more] 
COMP200741 pp.16 
COMP 
20070920 15:15 
Aichi 

The Complexity of the Hajos Calculus on Planar Graphs Yoichi Hanatani (Kyoto Univ.), Takashi Horiyama (Saitama Univ.), Kazuo Iwama, Suguru Tamaki (Kyoto Univ.) COMP200738 
The planar Haj\'os calculus is the Haj\'os calculus with the restriction
that all the graphs that appear in the constr... [more] 
COMP200738 pp.4350 
COMP 
20070629 09:25 
Hokkaido 
Hokkaido University 
Linear Time Enumeration of Isolated Bicliques with Part Size Proportion Bounded by Constants Hiromitsu Miyagawa, Hiro Ito, Kazuo Iwama (Kyoto Univ.) COMP200719 
Problems for finding a maximum bipartite clique and enumerating maximal bipartite cliques for graphs are difficult. Alth... [more] 
COMP200719 pp.916 
COMP 
20061204 16:35 
Aichi 
Nagoya University 
1.875approximation algorithm for the stable marriage problem Naoya Yamauchi, Shuichi Miyazaki, Kazuo Iwama (Kyoto Univ.) 
[more] 
COMP200648 pp.4956 
R 
20060623 13:25 
Tokyo 
KikaiShinkoKaikan Bldg. 
Ｅｆｆｅｃｔ Ｅｖａｌｕａｔｉｏｎ for Hazardous Event Rate by SFF in IEC 61508 Kazuo Iwama (kaiyou university), Tsuneharu Simodaira (InterRisk Research Inst. & Consulting), Yoshinobu Sato, Koichi Suyama (Tokyo Univ. of Marine Science and Technology) 
[more] 
R200615 pp.16 
COMP 
20060623 11:10 
Saitama 
Saitama Univ. 
Reductions for Monotone Boolean Circuits Kazuo Iwama, Hiroki Morizumi (Kyoto Univ.) 
The large class, say {\it NLOG}, of Boolean functions, including 01 Sort and 01 Merge, have an upper bound of $O(n\log... [more] 
COMP200619 pp.1519 
COMP 
20060524 14:10 
Fukuoka 
Kyushu Institute of Technology 
(4,1)Quantum Random Access Coding Does Not Exist Masahito Hayashi (JST), Kazuo Iwama (Kyoto Univ.), Harumichi Nishimura (Osaka Prefecture Univ.), Rudy Raymond (Kyoto Univ.), Shigeru Yamashita (NAIST) 
An (n,1,p)Quantum Random Access (QRA) coding, introduced by Ambainis,
Nayak, Tashma and Vazirani in ACM Symp. on The... [more] 
COMP200614 pp.3338 
COMP 
20060323 09:00 
Tokyo 
The University of ElectroCommunications 
Increasing the Success Probability of PPSZtype Satisfiability Testing Kazuo Iwama, Suguru Tamaki (Kyoto Univ.) 
Recently, [Iwama, Tamaki, SODA04] gave a new worstcase upper bound
for 3SAT by modifying the PPSZtype algorithm in
... [more] 
COMP200563 pp.16 
COMP 
20060323 13:10 
Tokyo 
The University of ElectroCommunications 
[Fellow Memorial Lecture]
Invited Talk as a New Fellow Kazuo Iwama (Kyoto Univ.) 
[more] 

COMP 
20051222 13:00 
Tokushima 
The University of Tokushima 
Transmitting classical information on the quantum network efficiently Kazuo Iwama, Harumichi Nishimura, Rudy Raymond (Kyoto Univ.), Shigeru Yamashita (NAIST) 
The question in this paper is whether the quantum random access (QRA) coding, given by Ambainis et al., on the {\it netw... [more] 
COMP200551 pp.1520 
COMP 
20051222 16:25 
Tokushima 
The University of Tokushima 
MaxStretch Reduction for Tree Spanners Kazuo Iwama (Kyoto Univ.), Andrzej Lingas (Lund Univ.), Masaki Okita (Kyoto Univ.) 
A tree $t$spanner $T$ of a graph $G$ is a spanning tree of $G$ whose
maxstretch is $t$, i.e., the distance between ... [more] 
COMP200556 pp.4955 
R, SSS 
20051216 13:00 
Tokyo 
KikaiShinkoKaikan Bldg. 
* Kazuo Iwama (TUMST), Tsuneharu Simodaira (InterRisk Research Inst. & Consulting), Yoshinobu Sato, Koichi Suyama (TUMST) 
IEC 61508 regulates requirements for the purpose of achievement of functional safety. This is translated into Japanese a... [more] 
R200547 SSS200526 pp.14 
R, SSS 
20051216 13:25 
Tokyo 
KikaiShinkoKaikan Bldg. 
 Kazuo Iwama (TUMST), Tsuneharu Simodaira (InterRisk Research Inst. & Consulting), Yoshinobu Sato, Koichi Suyama (TUMST) 
Unavailability of the redundant system with one repair team has been calcurated by meanas of Markov analysis in general.... [more] 
R200548 SSS200527 pp.510 
COMP 
20051019 09:35 
Miyagi 
Tohoku Univ. 
Automated Competitive Analysis of Online Problems Takashi Horiyama, Kazuo Iwama, Jun Kawahara (Kyoto Univ.) 
In this paper we study the 2Bin Exchangeable Online Knapsack Problem (2EOK)
which is an extension of the 2Bin Removab... [more] 
COMP200545 pp.712 
COMP 
20050520 15:30 
Fukuoka 
Kyushu Univ. 
Improving a local search approximation algorithm for the stable marriage problem Naoya Yamauchi, Shuichi Miyazaki, Kazuo Iwama (Kyoto Univ.) 
We consider the problem of finding a stable matching of maximum size when both ties and unacceptable partners are allowe... [more] 
COMP200515 pp.4551 