Selected Publications

List of Contents

• Refereed Journal/Conference Papers
  • Quantum Computing
  • Ordered Binary Decision Diagrams (OBDDs)
  • Network Protocols
  • Miscellaneous
• Technical Reports (unpublished papers)
• Theses

• 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–Leibniz-Zentrum für Informatik, 2020. [DOI]
  • arXiv:1909.12658
• Sumcheck-based 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).
  • arXiv:1911.04734
• 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]
  • arXiv:1812.03703
• Improved Quantum Multicollision-Finding Algorithm
  Akinori Hosoyamada, Yu Sasaki, Seiichiro Tani, and Keita Xagawa
  Proc. 10th International Conference on Post-Quantum Cryptography (PQCrypto 2019), pp. 350–367, vol. 11505 of LNCS, Springer, 2019. [DOI]
  • arXiv:1911.02822, entitled ''Quantum Algorithm for the Multicollision Problem,'' (superseding arXiv:1811.08097)
  • Cryptology ePrint Archive: Report 2018/1122
• Impossibility of Classically Simulating One-Clean-Qubit 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 One-Clean-Qubit 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]
  • arXiv:1612.05317
• 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]
  • arXiv:1509.07276
• 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.
  • Proc. the 21st International Computing and Combinatorics Conference (COCOON 2015), pp. 223–234, vol. 9198 of LNCS, 2015. [DOI]
  • arXiv:1409.6792.
• Quantum Query Complexity of Almost All Functions with Fixed On-Set 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/Worst-case Gaps of Quantum Query Complexities by On-Set Size"
• Quantum Algorithms for Finding Constant-sized Sub-hypergraphs.
  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 Constant-Depth 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]
  • arXiv:1204.4691.
• 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 Fan-Out.
  Yasuhiro Takahashi, Seiichiro Tani and Noboru Kunihiro.
  Quantum Information & Computation, vol. 10 , no. 9&10, pp. 872–890, 2010. [link]
  • arXiv:0910.2530 .
• 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]
  • arXiv:0903:1291 .
• The one-way 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 one-way communication complexity of group membership'').
• Quantum Query Complexity of Boolean Functions with Small On-Sets.
  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, Xiang-Bin Wang, Yun-Kun Jiang, Seiichiro Tani and Akihisa Tomita.
  Physical Review A, 77, 032343 (2008). [DOI]
  • arXiv:0709.4314.
• 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.
• Multi-party quantum communication complexity with routed messages.
  Seiichiro Tani, Masaki Nakanishi and Shiger Yamashita.
  IEICE Transactions on Information and Systems, vol. E92-D, 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].

• 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. E79-D, 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 93-06, Department of Information Science, University of Tokyo, 1993.
  • Technical Report 93-0009, 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 95-06, Department of Information Science, University of Tokyo, 1995.
• Output-size 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]

• Flexcastによる段階的導入に優れたマルチキャストシステムの設計と実装
  (Design and implementation of multicast routers based on cluster computing.)
  Takeru Inoue, Seiichiro Tani, Hirokazu Takahashi, Shin-ichi Minato, Toshiaki Miyazaki, and Kan Toyoshima.
  IEICE Transactions on Information and Systems, vol. J88-D1, 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]
• Wide-Area Multicasting based on Flexcast: Toward the Ubiquitous Network.
  Takeru Inoue, Seiichiro Tani, Katsuhiro Ishimaru, Shin'ichi Minato and Toshiaki Miyazaki.
  Proc. Fifth Asia-Pacific 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. E85-D, 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. IFIP-TC6 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 easy-to-use 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)]

• A randomized online algorithm for the file caching problem.
  Seiichiro Tani and Toshiaki Miyazaki.
  IEICE Transactions on Information and Systems, vol. E86-D, 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. E84-D, 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]

• Classically Simulating Quantum Circuits with Local Depolarizing Noise.
  Yasuhiro Takahashi, Yuki Takeuchi, Seiichiro Tani.
  arXiv:2001.08373
• Sampling of globally depolarized random quantum circuit
  Tomoyuki Morimae, Yuki Takeuchi, Seiichiro Tani.
  arXiv:1911.02220

• 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.
  • A revised version (in English) is published as "The complexity of the optimal variable ordering problems of shared binary decision diagrams", IEICE Transactions on Information and Systems, vol. E79-D, no. 4, pp. 271–281, 1996. [A preliminary version appeared at Proc. 4th International Syposium on Algorithms and Computation (ISAAC 1993), pp.389–398, 1993. [DOI]]
• 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 Multi-Point 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 (referee-in-chief, Univ. Tokyo) for Ph.D. in computer science from the University of Tokyo, Japan.

IEEE Copyright Notice