Ryuhei Mori

Interests

• Quantum information: Foundation of quantum mechanics by information processing, nonlocality, generalized probabilistic theories, quantum computation.
• Information theory: Low-density parity-check codes, belief propagation, graph covers, polar codes.
• Computer science: Constraint satisfaction problems, fully polynomial-time approximation scheme for #P-complete problems, holographic transformation, quantum computation.
• Statistical physics: The Bethe approximation, cluster expansions, partition function zeros, replica method.

Publications

Preprints

• R. Ito and R. Mori, “Lower bounds on the error probability of multiple quantum channel discrimination by the Bures angle and the trace distance,” Jul. 2021. [arXiv]

Journal papers

1. M. Norimoto, R. Mori, and N. Ishikawa, “Quantum speedup for higher-order unconstrained binary optimization and MIMO maximum likelihood detection,” IEEE Trans. Commun., vol.71, no.4, pp.1926–1939, Apr. 2023. [arXiv] [DOI]
2. K. Shimizu and R. Mori, “Exponential-time quantum algorithms for graph coloring problems,” Algorithmica, vol.84, 3603–3621, Jun. 2022. [DOI]
3. R. Mori, “Periodic Fourier representation of Boolean functions,” Quantum Inf. Comput., vol.19, no.5&6, pp.0392–0412, May 2019. [DOI]
4. R. Mori, “Better protocol for XOR game using communication protocol and nonlocal boxes,” Quantum Inf. Comput., vol.17, no.15&16, pp.1261–1276, Dec. 2017. [DOI]
5. R. Mori, “Three-input majority function as the unique optimal function for the bias amplification using nonlocal boxes,” Phys. Rev. A, vol.94, 052130, Nov. 2016. [published version] [DOI]
6. R. Mori, “Loop calculus for non-binary alphabets using concepts from information geometry,” IEEE Trans. Inf. Theory, vol.61, no.4, pp.1887–1904, Apr. 2015. [accepted version] [DOI]
7. R. Mori and T. Tanaka, “Source and channel polarization over finite fields and Reed-Solomon matrices,” IEEE Trans. Inf. Theory, vol.60, no.5, pp.2720–2736, May 2014. [accepted version] [DOI]
8. S.H. Hassani, R. Mori, T. Tanaka, and R. Urbanke, “Rate-dependent analysis of the asymptotic behavior of channel polarization,” IEEE Trans. Inf. Theory, vol.59, no.4, pp.2267–2276, Apr. 2013. [DOI]
9. R. Mori, T. Tanaka, K. Kasai, and K. Sakaniwa, “Effects of single-cycle structure on iterative decoding of low-density parity-check codes,” IEEE Trans. Inf. Theory, vol.59, no.1, pp.238–253, Jan. 2013. [accepted version] [DOI]
10. R. Mori and T. Tanaka, “Performance of polar codes with the construction using density evolution,” IEEE Commun. Lett., vol.13, no.7, pp.519–521, Jul. 2009. [DOI]

Conference papers

1. Y. Kondo, R. Mori, and R. Movassagh, “Quantum supremacy and hardness of estimating output probabilities of quantum circuits,” FOCS 2021, pp.1296–1307, 2022. [arXiv] [DOI]
2. A. Glos, M. Kokainis, R. Mori, and J. Vihrovs, “Quantum speedups for dynamic programming on n-dimensional lattice graphs,” MFCS, LIPIcs, vol.202, pp.50:1–50:23, 2021. [arXiv] [DOI]
3. A. Bostan and R. Mori, “A simple and fast algorithm for computing the N-th term of a linearly recurrent sequence,” SIAM SOSA, pp.118–132, Jan. 11–12, 2021. [arXiv] [DOI]
4. K. Shimizu and R. Mori, “Exponential-time quantum algorithms for graph coloring problems,” LATIN, LNCS, vol.12118, Springer, Cham, pp.387–398, 2020. [DOI]
5. P.K. Kothari, R. Mori, R. O'Donnell, and D. Witmer, “Sum of squares lower bounds for refuting any CSP,” ACM/SIGACT STOC, Montreal, Canada, pp.132–145, Jun. 19–23, 2017. [DOI]
6. R. Mori and D. Witmer, “Lower bounds for CSP refutation by SDP hierarchies,” APPROX/RANDOM, Paris, France, LIPIcs, vol.60, pp.41:1–41:30, Sep. 7–9, 2016. [DOI]
7. N. Shimizu and R. Mori, “Average shortest path length of graphs of diameter 3,” IEEE/ACM NOCS, Nara, Japan, Aug. 31–Sep. 2, 2016. [DOI]
8. R. Mori, “Holographic transformation, belief propagation and loop calculus for generalized probabilistic theories,” 2015 IEEE ISIT, Hong Kong, pp.1099–1103, Jun. 14–19, 2015. [DOI]
9. R. Mori and T. Tanaka, “Central approximation in statistical physics and information theory,” 2012 IEEE ISIT, Cambridge, MA, pp.1652–1656, Jul. 1–6, 2012. [DOI]
10. S.H. Hassani, N. Macris, and R. Mori, “Near concavity of the growth rate for coupled LDPC chains,” 2011 IEEE ISIT, St. Petersburg, Russia, pp.356–360, Jul. 31–Aug. 5, 2011. [DOI]
11. R. Mori, “Connection between annealed free energy and belief propagation on random factor graph ensembles,” 2011 IEEE ISIT, St. Petersburg, Russia, pp.2016–2020, Jul. 31–Aug. 5, 2011. [DOI]
12. R. Mori and T. Tanaka, “Non-binary polar codes using Reed-Solomon codes and algebraic geometry codes,” 2010 IEEE ITW, Dublin, Ireland, Aug. 30–Sep. 3, 2010. [DOI]
13. T. Tanaka and R. Mori, “Refined rate of channel polarization,” 2010 IEEE ISIT, Austin, TX, pp.889–893, Jun. 13–18, 2010. [DOI]
14. R. Mori and T. Tanaka, “Channel polarization on q-ary discrete memoryless channels by arbitrary kernels,” 2010 IEEE ISIT, Austin, TX, pp.894–898, Jun. 13–18, 2010. [DOI]
15. R. Mori and T. Tanaka, “Performance and construction of polar codes on symmetric binary-input memoryless channels,” 2009 IEEE ISIT, Seoul, Korea, pp.1496–1500, Jun. 28–Jul. 3, 2009. [DOI]
16. R. Mori, T. Tanaka, K. Kasai, and K. Sakaniwa, “Finite-length analysis of irregular expurgated LDPC codes under finite number of iterations,” 2009 IEEE ISIT, Seoul, Korea, pp.2497–2501, Jun. 28–Jul. 3, 2009. [DOI]
17. R. Mori, K. Kasai, T. Shibuya, and K. Sakaniwa, “Asymptotic gaps between BP decoding and local-MAP decoding for low-density parity-check codes,” 2008 5th Int. Symp. Turbo Codes and Related Topics, Lausanne, Switzerland, pp.162–167, Sep. 1–5, 2008. [DOI]
18. R. Mori, K. Kasai, T. Shibuya, and K. Sakaniwa, “Asymptotic bit error probability of LDPC codes for the binary erasure channel with finite number of iterations,” 2008 IEEE ISIT, Toronto, Canada, pp.449–453, Jul. 6–11, 2008. [DOI]

Other manuscripts

1. R. Mori, “Average length of cycles in rectangular lattice,” 2017. [arXiv]
2. R. Mori and O. Watanabe, “Peeling algorithm on random hypergraphs with superlinear number of hyperedges,” 2015.
3. R. Mori, T. Koshiba, O. Watanabe, and M. Yamamoto, “Linear programming relaxations for Goldreich's generators over non-binary alphabets,” 2014.
4. R. Mori, “Holographic transformation for quantum factor graphs,” 2014.
5. R. Mori and T. Tanaka, “New generalizations of the Bethe approximation via asymptotic expansion,” 2012 IEICE SITA, Oita, Japan, Dec. 11–14, 2012.
6. R. Mori and T. Tanaka, “Statistical mechanical analysis of low-density parity-check codes on general Markov channel,” 2011 IEICE SITA, Iwate, Japan, Nov. 29– Dec. 2, 2011.

Biography

• Apr. 2023– , Current position.
• Jan. 2015– Mar. 2023, Assistant Professor at Tokyo Institute of Technology.
• Apr. 2013– Dec. 2014, Postdoctoral Fellow at Tokyo Institute of Technology.
• Apr. 2010– Mar. 2013, Ph.D. in Informatics, Kyoto University, Kyoto, Japan.
• Apr. 2008– Mar. 2010, Master of Informatics at Graduate School of Informatics, Kyoto University, Kyoto, Japan.
• Apr. 2000– Mar. 2008, Bachelor of Engineering at Tokyo Institute of Technology, Tokyo, Japan.

Talk slides

1. “Lower Bounds for CSP Refutation by SDP Hierarchies” in APPROX/RANDOM, Paris, France, Sep. 9, 2016.
2. “Holographic transformation, belief propagation and loop calculus for generalized probabilistic theories” in ISIT, Hong Kong, Jun. 16, 2015.
3. “New generalizations of the Bethe approximation via asymptotic expansion” in SITA, Oita, Japan, Dec. 13, 2012.
4. “Statistical mechanical analysis of low-density parity-check codes on general Markov channel” in SITA, Iwate, Japan, Nov. 30, 2011.
5. “Growth rate of spatially coupled LDPC codes” in SCW, Tokyo, Japan, Feb. 9, 2011.
6. “Non-binary polar codes using Reed-Solomon codes and algebraic geometry codes” in ITW, Dublin, Ireland, Aug. 31, 2010.
7. “Finite-length analysis of irregular expurgated LDPC codes under finite number of iterations” in ISIT, Seoul, Korea, Jul. 3, 2009.

Toy programs

1. Demonstration of channel polarization by SVG (Updated at 11 Dec. 2010, available for Firefox, Opera and WebKit)