Selected Publications
List of Contents
Refereed Journals/Conferences
Quantum Computing

Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams
Seiichiro Tani.
Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT),
pp. 36:1–36:19, vol. 162, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl–LeibnizZentrum für Informatik, 2020.
[DOI]

Sumcheckbased delegation of quantum computing to rational server.
Yuki Takeuchi, Tomoyuki Morimae, Seiichiro Tani.
To appear at the 16th Annual Conference on Theory and Applications of Models of Computation (TAMC 2020).

Impossibility of blind quantum sampling for classical client
Tomoyuki Morimae, Harumichi Nishimura, Yuki Takeuchi, and Seiichiro Tani.
Quantum Information & Computation, pp.793–806, vol. 19, no. 9&10, 2019.
[URL]

Improved Quantum MulticollisionFinding Algorithm
Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani, and Keita Xagawa
Proc. 10th International Conference on PostQuantum Cryptography (PQCrypto 2019),
pp. 350–367, vol. 11505 of LNCS, Springer, 2019.
[DOI]

Impossibility of Classically Simulating OneCleanQubit Model with Multiplicative Error
Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani.
Physical Review Letters, vol. 120, p.200502, May, 2018.
[DOI]

arXiv:1409.6777v2
(entitled with ``Impossibility of Classically Simulating OneCleanQubit Computation'')
 Power of uninitialized qubits in shallow quantum circuits.
Yasuhiro Takahashi and Seiichiro Tani.
Proc. 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), pp. 57:1–57:13, 2018.
[DOI]
 Oral presentation at 18th Asian Quantum Information Science Conference (AQIS 2018), Nagoya, Japan, Sep., 2018.
 arXiv:1608.07020
 A Fast Exact Quantum Algorithm for Solitude Verification.
Seiichiro Tani.
Quantum Information & Computation, vol.17, no. 1&2, pp. 15–40, 2017.
[link]

Power of Quantum Computation with Few Clean Qubits.
Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani.
Proc. the 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), 13:1–13:14, 2016.
[DOI]

Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable.
Yasuhiro Takahashi, Seiichiro Tani, Takeshi Yamazaki, and Kazuyuki Tanaka.
Quantum Information & Computation,
vol. 16 , no. 3&4, pp. 251–270, 2016.

Quantum Query Complexity of Almost All Functions with Fixed OnSet Size.
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, and Shigeru Yamashita.
Computational Complexity, vol. 25, Issue 4, pp. 723–735, 2016.
[DOI].
 A rewritten version of Sec.5 in
arXiv:0908.2468: "Average/Worstcase Gaps of Quantum Query Complexities by OnSet Size"

Quantum Algorithms for Finding Constantsized Subhypergraphs.
François Le Gall, Harumichi Nishimura, and Seiichiro Tani.
Theoretical Computer Science, vol. 609 (Part 3), pp. 569–582, 2016
[DOI].
(Selected Papers of COCOON 2014)

Proc. the 20th International Computing and Combinatorics Conference (COCOON 2014), pp. 429–440, vol. 8591 of LNCS, 2014.
[DOI]
[Slide].

arXiv:1310.4127.

The 18th Conference on Quantum Information Processing, poster presentation
[Abst]
[Slide].

Simpler Exact Leader Election via Quantum Reduction.
Hirotada Kobayashi, Keiji Matsumoto and Seiichiro Tani.
Chicago Journal of Theoretical Computer Science, vol. 2014, article 10.
[DOI]

arXiv:1001.5307
with the title ``Computing on Anonymous Networks''
[Slide].

A very preliminary version:
``Brief Announcement: Exactly Electing a Unique Leader is not Harder than Computing Symmetric Functions on Anonymous Quantum Networks''.
Proc. ACM Symposium on Principles of Distributed Computing
(PODC 2009).
[DOI]
[Slide]
 Collapse of the Hierarchy of ConstantDepth Exact Quantum Circuits.
Yasuhiro Takahashi and Seiichiro Tani.
Computational Complexity, vol. 25, Issue 4, pp. 849–881, 2016.
[DOI]

Proc. IEEE Conference on Computational Complexity (CCC 2013),
pp. 168–178, 2013.
[DOI].

arXiv:1112.6063.

Reconstructing Strings from Substrings with Quantum Queries.
Richard Cleve, Kazuo Iwama, François Le Gall, Harumichi Nishimura, Seiichiro Tani, Junichi Teruyama, and Shigeru Yamashita.
Proc. 13th Scandinavian Symposium and Workshops on Algorithm Theory
(SWAT 2012), pp. 388–397, 2012.
[DOI]

Exact quantum algorithms for the leader election problem.
Seiichiro Tani, Hirotada Kobayashi and Keiji Matsumoto.
ACM Transactions on Computation Theory,
4(1):Article 1, 2012
[DOI]
 An extended version of Sec. 3 of
the paper
in Proc.
22nd Symposium on Theoretical Aspects of Computer Science
(STACS 2005), pp. 581–592, 2005.
[DOI]
[Draft]
[Slide]
(or
arxiv:0712.4213).
 Talk at the 8th Workshop on Quantum Information Processing, MIT, USA, 2005.

Compression of View on Anonymous Networks — Folded View —.
Seiichiro Tani.
IEEE Transactions on Parallel and Distributed Systems,
vol. 23, no.2, pp.255–262, 2012.
[DOI]
[Draft
(IEEE copyright notice)]
[Slide (Talk at MinatoPJ)].
 This paper is a fully rewritten version of Sec. 5 of
arxiv:0712.4213
,
with additional results, simplified proofs and figures.
 The results are classical, but they were used in quantum algorithms
(see
here
or
there).

Quantum Addition Circuits and Unbounded FanOut.
Yasuhiro Takahashi, Seiichiro Tani and Noboru Kunihiro.
Quantum Information & Computation,
vol. 10 , no. 9&10, pp. 872–890, 2010.
[link]

The quantum query complexity of certification.
Andris Ambainis, Andrew. M. Childs, François Le Gall, and Seiichiro Tani.
Quantum Information & Computation. vol. 10, no. 3&4, pp. 181–189.
[link]

The oneway communication complexity of subgroup membership.
Scott Aaronson, François Le Gall, Alexander Russell, and Seiichiro Tani.
Chicago Journal of Theoretical Computer Science, Article 6, 2011.
[DOI]

arXiv:0902.3175 (with old title ``The oneway communication complexity of group membership'').

Quantum Query Complexity of Boolean Functions with Small OnSets.
Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, and Shigeru Yamashita.
Proc. 19th International Syposium on Algorithms and Computation
(ISAAC 2008), pp. 907–918, 2008.
[DOI]
[Draft]
[Slide].

Experimental demonstration of quantum leader election in linear optics.
Yuta Okubo, XiangBin Wang, YunKun Jiang, Seiichiro Tani and Akihisa Tomita.
Physical Review A, 77, 032343 (2008).
[DOI]

Claw finding algorithms using quantum walk.
Seiichiro Tani.
Theoretical Computer Science (Selected Papers of MFCS 2007), 410(50):5285–5297, 2009.
[DOI]

Proc. 32nd International Symposium on Mathematical Foundations of Computer Science
(MFCS 2007)
.
[DOI]

arXiv:0708.2584.

Multiparty quantum communication complexity with routed messages.
Seiichiro Tani, Masaki Nakanishi and Shiger Yamashita.
IEICE Transactions on Information and Systems,
vol. E92D, no. 2, pp. 191–199, 2009.
[DOI]

Proc. 14th International Computing and Combinatorics Conference
(COCOON 2008), pp. 180–190, 2008.
[DOI]
[Draft]
[Slide].

Quantum leader election via exact amplitude amplification.
Seiichiro Tani, Kobayashi and K. Matsumoto.
ERATO conference on Quantum Information Science
(EQIS 2005), pp. 11–12, 2005.
[Abst]
[Draft]
[Slide].
Ordered Binary Decision Diagrams

The complexity of the optimal variable ordering problems of shared binary decision diagrams.
Seiichiro Tani, Kiyoharu Hamaguchi and Shuzo Yajima.
IEICE Transactions on Information and Systems, vol. E79D, no. 4, pp. 271–281, 1996.

A preliminary version in
Proc. 4th International Syposium on Algorithms and Computation
(ISAAC 1993), pp.389–398, 1993.
[DOI]

Technical Report 9306, Department of Information Science, University of Tokyo, 1993.

Technical Report 930009, Department of Information Science, Kyoto University, 1993.

Computing the Tutte polynomial of a graph of moderate size.
Kyoko Sekine, Hiroshi Imai and Seiichiro Tani.
Proc. 6th International Syposium on Algorithms and Computation
(ISAAC 1995), pp. 224–233, 1995.
[DOI]

Technical Report 9506, Department of Information Science, University of Tokyo, 1995.

Outputsize sensitiveness of OBDD construction through maximal independent set problem.
Kazuyoshi Hayase and Kunihiko Sadakane.
Proc. First International Computing and Combinatorics Conference
(COCOON 1995), pp. 229–234, 1995.
[DOI]

A reordering operation for an ordered binary decision diagram and an extended framework for combinatorics of graphs.
Seiichiro Tani and Hiroshi Imai.
Proc. 5th International Syposium on Algorithms and Computation
(ISAAC 1994), pp.575–583, 1994.
[DOI]
Network Protocols

Flexcastによる段階的導入に優れたマルチキャストシステムの設計と実装
(Design and implementation of multicast routers based on cluster computing.)
Takeru Inoue, Seiichiro Tani, Hirokazu Takahashi, Shinichi Minato, Toshiaki Miyazaki, and Kan Toyoshima.
IEICE Transactions on Information and Systems, vol. J88D1, no. 2, pp. 272–291, 2005.

Proc. 11th International Conference on Parallel and Distributed Systems
(ICPADS 2005)(in English), Vol. 1, pp.328–334, IEEE, 2005.
[DOI]

WideArea Multicasting based on Flexcast: Toward the Ubiquitous Network.
Takeru Inoue, Seiichiro Tani, Katsuhiro Ishimaru, Shin'ichi Minato and Toshiaki Miyazaki.
Proc. Fifth AsiaPacific Symposium on Information and Telecommunication Technologies (APSITT 2003), pp.301–306, 2003.
[Draft]

An approach to adaptive network.
Shinya Ishihara, Toshiaki Miyazaki, Atsushi Takahara, Seiichiro Tani.
IEICE Transactions on Information and Systems, vol. E85D, no. 5, pp. 839–846, 2002.

Yet Another Active Network Environment Towards Adaptive Network Infrastructure
Toshiaki Miyazaki, Noriyuki Takahashi, Takahiro Murooka, Seiichiro Tani, and Masashi Hashimoto
Proc. IEICE The First International Workshop on Active Network Technologies and Applications (ANTA2002), pp.63–68, Tokyo, March 25–26 2002.
 Multicast as a traffic variance smoother for IP streaming service.
Satoru Ohta, Seiichiro Tani and Toshiaki Miyazaki.
Proceedings of the 10th Telecommunication Network Strategy and Planning Symposium (Networks 2002), pp.105–110, 2002.
[Draft]

Adaptive stream multicast based on IP unicast and dynamic commercial attachment mechanism: An active network implementation.
Seiichiro Tani, Toshiaki Miyazaki and Noriyuki Takahashi.
Proc. IFIPTC6 Third International Working Conference on Active Networks.
(IWAN 2001), pp.116–133, 2001.
[DOI]
[Slide]

Virtual BUS: A network technology for setting up distributed resources in your own computer.
Toshiaki Miyazaki, Atsushi Takahara, Shinya Ishihara, Seiichiro Tani, Takahiro Murooka, Tomoo Fukazawa, Mitsuo Teramoto, and Kazuhiro Matsuhiro.
Proc. International Parallel Distributed Processing Symposium (IPDPS 2000), pp.535–540, IEEE, 2000.
[DOI]

Virtual BUS: A simple implementation of an effortless networking system based on PVM.
Shinya Ishihara, Seiichiro Tani and Atsushi Takahara.
Proc. 6th European PVM/MPI Users' Group Meeting
(PVM/MPI 1999), pp.461–468, 1999.
[DOI]

Virtual BUS: An easytouse environment for distributed resources.
Atsushi Takahara, Seiichiro Tani, Shinya Ishihara, Toshiaki Miyazaki, Mitsuo Teramoto, and Tomoo Fukazawa.
Proc. Conference on Local Computer Networks
(LCN 1999), pp.62–70, IEEE, 1999.
[DOI]
[Draft
(IEEE copyright notice)]
Miscellaneous

A randomized online algorithm for the file caching problem.
Seiichiro Tani and Toshiaki Miyazaki.
IEICE Transactions on Information and Systems, vol. E86D, no. 4, pp. 686–697, 2003.

A design framework for online algorithms solving the object replacement problem.
Seiichiro Tani and Toshiaki Miyazaki.
IEICE Transactions on Information and Systems, vol. E84D, no. 9, pp. 1135–1143, 2001.

Efficient path selection for delay testing based on path clustering.
Seiichiro Tani, Mitsuo Teramoto, Tomoo Fukazawa, and Kazuhiro Matsuhiro.
Journal of Electronic Testing (JETTA),
vol. 15, no. 1/2, pp. 75–85, 1999.
[DOI]
(Selected Papers of IEEE VTS 1998),

Proc. 16th IEEE VLSI Test Symposium
(VTS 1998), pp. 188–193, 1998.
[DOI]
Technical Reports (unpublished papers)
Theses

Bachelor thesis (1993):
The Complexity of the Optimal Variable Ordering Problems of a Shared Binary Decision Diagram
(in Japanese),
supervised by Prof. Shuzo Yajima,
for B.E. in information science from Kyoto University, Japan.
 Master thesis (1995):An Extended Framework of Ordered Binary Decision Diagrams for Combinatorial Graph Problems,
supervised by Prof. Hiroshi Imai,
for M.S. in computer science from the University of Tokyo, Japan.
 Partly published as
"A reordering operation for an ordered binary decision diagram and an extended framework for combinatorics of graphs",
Proc. 5th International Syposium on Algorithms and Computation
(ISAAC 1994), pp.575–583, 1994.
[DOI]

Ph.D. dissertation (2006):
A Study of Algorithms for Efficient MultiPoint Communication in Autonomous Distributed Networks
(pdf),
supervised by
Prof. Hiroshi Imai and refereed by
Prof. Masahito Hayashi (Univ. Tokyo), Prof. Yutaka Ishikawa (Univ. Tokyo), Prof. Hiro Ito (Kyoto Univ.), Prof. Kazuhisa Makino (Univ. Tokyo), Prof. Reiji Suda (refereeinchief, Univ. Tokyo)
for Ph.D. in computer science from the University of Tokyo, Japan.
IEEE Copyright Notice
@2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.