# Hiroshi Imai

**Hiroshi Imai**,

a Japanese mathematician, computer scientist and professor at Graduate School of Information Science and Technology, University of Tokyo, and head of the *Imai Laboratory*. His research interests include computational geometry, discrete mathematics, graph theory, computational complexity theory, quantum computation, cryptography and tree search.
Along with Ayumu Nagai, he worked on depth-first Proof-number search applied to Shogi and Othello.

## Contents

# Selected Publications

^{[2]} ^{[3]}

## 1982 ...

- Hiroshi Imai (
**1982**).*Finding Connected Components of an Intersection Graph of Squares in the Euclidean Plane*. Information Processing Letters, Vol. 15, No. 3 - Hiroshi Imai, Takao Asano (
**1983**).*Finding the Connected Components and a Maximum Clique of an Intersection Graph of Rectangles in the Plane*. Journal of Algorithms, Vol. 4, No. 4 - Hiroshi Imai, Takao Asano (
**1984**).*Dynamic Segment Intersection Search with Applications*. FOCS 1984 - Hiroshi Imai (
**1985**).*On combinatorial structures of line drawings of polyhedra*. Discrete Applied Mathematics, Vol. 10, No. 1 - Hiroshi Imai, Takao Asano (
**1986**).*Efficient Algorithms for Geometric Graph Search Problems*. SIAM Journal on Computing, Vol. 15, No. 2 - Hiroshi Imai, Takao Asano (
**1987**).*Dynamic Orthogonal Segment Intersection Search*. Journal of Algorithms, Vol. 8, No. 1 - Hiroshi Imai (
**1988**).*On the convexity of the multiplicative version of Karmarkar's potential function*. Mathematical Programming, Vol. 40, Nos. 1-3^{[4]}

## 1990 ...

- Hiroshi Imai, Kazuo Iwano (
**1990**).*Efficient Sequential and Parallel Algorithms for Planar Minimum Cost Flow*. SIGAL 1990 - Ayumu Nagai, Hiroshi Imai (
**1999**).*Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees*. Proceedings of the Korea-Japan Joint Workshop on Algorithms and Computation - Ayumu Nagai, Hiroshi Imai (
**1999**).*Application of df-pn+ to Othello endgames*. 5th Game Programming Workshop » Othello - Takahiro Ikeda, Hiroshi Imai (
**1999**).*Enhanced A* Algorithms for Multiple Alignments: Optimal Alignments for Several Sequences and k-Opt Approximate Alignments for Large Cases*. Theoretical Computer Science, Vol. 210, No. 2

## 2000 ...

- Tomohiro Yamasaki, Hirotada Kobayashi, Hiroshi Imai (
**2001**).*Two-way Quantum One-counter Automata*. arXiv:cs/0110005 - Jozef Gruska, Hiroshi Imai (
**2001**).*Power, Puzzles and Properties of Entanglement*. MCU 2001 - Ayumu Nagai, Hiroshi Imai (
**2002**).*Proof for the Equivalence Between Some Best-First Algorithms and Depth-First Algorithms for AND/OR Trees*. IEICE transactions on information and systems - Sonoko Moriyama, Ayumu Nagai, Hiroshi Imai (
**2002**).*Fast and Space-efficient Algorithms for Deciding Shellability of Simplicial Complexes of Large Size using h-Assignments*. ICMS 2002 - Tomohiro Yamasaki, Hirotada Kobayashi, Hiroshi Imai (
**2005**).*Quantum versus deterministic counter automata*. Theoretical Computer Science, Vol. 334, No. 1-3 - Hiroshi Imai, Masahito Hayashi (eds.) (
**2006**).*Quantum Computation and Information: From Theory to Experiment*. Springer - Kimikazu Kato, Mayumi Oto, Hiroshi Imai, Keiko Imai (
**2008**).*Computational Geometry Analysis of Quantum State Space and Its Applications*. Generalized Voronoi Diagram 2008

## 2010 ...

- Vorapong Suppakitpaisarn, Masato Edahiro, Hiroshi Imai (
**2010**).*Optimal Average Joint Hamming Weight and Minimal Weight Conversion of d Integers*. IACR Cryptology ePrint Archive, 2010 - Vorapong Suppakitpaisarn, Masato Edahiro, Hiroshi Imai (
**2011**).*Fast Elliptic Curve Cryptography Using Optimal Double-Base Chains*. IACR Cryptology ePrint Archive, 2011 - Vorapong Suppakitpaisarn, Masato Edahiro, Hiroshi Imai (
**2012**).*Fast Elliptic Curve Cryptography Using Minimal Weight Conversion of d Integers*. AISC 2012 - Vorapong Suppakitpaisarn, Hiroshi Imai (
**2014**).*Worst case computation time for minimal joint Hamming weight numeral system.*. ISITA 2014

# External Links

- Home Page of Hiroshi Imai
- Imai Laboratory
- IMAI Hiroshi - School of Science, the University of Tokyo
- Graduate School of Information Science and Technology, The University of Tokyo - Professor Hiroshi Imai