Publications

This publication list includes peer-reviewed journal articles, conference proceedings, and preprints in theoretical computer science and mathematics. My research focuses on discrete mathematics and theoretical computer science, particularly random graph theory, consensus dynamics, and computational complexity theory.

Journal Articles (Peer-Reviewed)

  • How Many Vertices Does a Random Walk Miss in a Network with a Moderately Increasing Number of Vertices?
    Shuji Kijima, Nobutaka Shimizu, and Takeharu Shiraga
    MATHEMATICS OF OPERATIONS RESEARCH, 2025
    DOI: 10.1287/moor.2023.0060 | arXiv (2021) | Slide Preliminary version appeared in SODA2021
    Random Walks

  • Quasi-majority Functional Voting on Expander Graphs
    Nobutaka Shimizu and Takeharu Shiraga
    Random Structures & Algorithms, 65(4), pp.613-643, 2024
    DOI: 10.1002/rsa.21224 | arXiv (2022) | Slide Preliminary version appeared in ICALP2020
    Graph Theory Consensus Dynamics Stochastic Processes

  • Reversible Random Walks on Dynamic Graphs
    Nobutaka Shimizu and Takeharu Shiraga
    Random Structures & Algorithms, 63(4), pp.1100-1136, 2023
    DOI: 10.1002/rsa.21164 | arXiv (2022)
    Graph Theory Random Walks

  • Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
    Nobutaka Shimizu and Takeharu Shiraga
    Random Structures & Algorithms, 59(1), pp.96-140, 2021
    DOI: 10.1002/rsa.20992 | Preliminary version appeared in DISC2019 | Slide
    Graph Theory Consensus Dynamics Stochastic Processes

  • The average distance and the diameter of dense random regular graphs
    Nobutaka Shimizu
    The Electronic Journal of Combinatorics, 27(3), 2020
    DOI: 10.37236/9809
    Preliminary version appeared in SODA2018
    Graph Theory Random Graphs

Conference Proceedings (Peer-Reviewed)

  • 3-Majority and 2-Choices with Many Opinions Nobutaka Shimizu, Takeharu Shiraga
    Symposium on Principles of Distributed Computing (PODC 2025)
    DOI:10.1145/3732772.3733511 | arXiv:2503.02426
    Graph Theory Consensus Dynamics Stochastic Processes

  • An Optimal Error-Correcting Reduction for Matrix Multiplication Shuichi Hirahara, Nobutaka Shimizu
    International Colloquium on Automata, Languages, and Programming (ICALP 2025) Theoretical CS Computational Complexity

  • Error-Correction of Matrix Multiplication Algorithms
    Shuichi Hirahara, Nobutaka Shimizu
    Symposium on Theory of Computing (STOC 2025)
    DOI: 10.1145/3717823.3718244 | ECCC TR24-026 | Slide
    Theoretical CS Computational Complexity

  • Asynchronous 3-Majority Dynamics with Many Opinions
    Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, Takeharu Shiraga
    Symposium on Discrete Algorithms (SODA 2025)
    DOI: 10.1137/1.9781611978322.140 | arXiv:2503.02426 | Slide
    Graph Theory Consensus Dynamics Stochastic Processes

  • Planted Clique Conjectures Are Equivalent
    Shuichi Hirahara, Nobutaka Shimizu
    Symposium on Theory of Computing (STOC 2024)
    DOI: 10.1145/3618260.3649751 | ECCC TR24-058 | Slide
    Theoretical CS Computational Complexity Graph Theory

  • Hardness Self-Amplification: Simplified, Optimized, and Unified
    Shuichi Hirahara, Nobutaka Shimizu
    Symposium on Theory of Computing (STOC 2023)
    DOI: 10.1145/3564246.3585189 | ECCC TR23-026 | Slide
    Theoretical CS Computational Complexity

  • Hardness Self-Amplification from Feasible Hard-Core Sets
    Shuichi Hirahara, Nobutaka Shimizu
    Foundations of Computer Science (FOCS 2022)
    DOI: 10.1109/FOCS54457.2022.00083 | ECCC TR22-108 | Slide
    Theoretical CS Computational Complexity

  • Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
    Shuichi Hirahara, Nobutaka Shimizu
    Symposium on Discrete Algorithms (SODA 2021)
    DOI: 10.1137/1.9781611976465.140 | arXiv:2010.05822 | Slide
    Theoretical CS Computational Complexity Graph Theory

  • How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
    Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga
    Symposium on Discrete Algorithms (SODA 2021)
    DOI: 10.1137/1.9781611976465.8 | arXiv:2008.10837 | Slide
    Graph Theory Random Walks

  • Quasi-majority Functional Voting on Expander Graphs
    Nobutaka Shimizu, Takeharu Shiraga
    International Colloquium on Automata, Languages, and Programming (ICALP 2020)
    DOI: 10.4230/LIPIcs.ICALP.2020.97 | arXiv:2002.07411
    Graph Theory Consensus Dynamics Stochastic Processes

  • Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
    Nobutaka Shimizu, Takeharu Shiraga
    International Symposium on Distributed Computing (DISC 2019)
    DOI: 10.4230/LIPIcs.DISC.2019.32 | arXiv:1907.12212
    Graph Theory Consensus Dynamics Stochastic Processes

  • The Diameter of Dense Random Regular Graphs
    Nobutaka Shimizu
    Symposium on Discrete Algorithms (SODA 2018)
    DOI: 10.1137/1.9781611975031.126
    Graph Theory Random Graphs

  • Average Shortest Path Length of Graphs of Diameter 3
    Nobutaka Shimizu, Ryuhei Mori
    Symposium on Networks-on-Chip (NOCS 2016)
    DOI: 10.1109/NOCS.2016.7579335 | arXiv:1606.05119
    Graph Theory Network Theory

Other Publications

  • 動的グラフ上のランダムウォーク (Random Walks on Dynamic Graphs)
    来嶋 秀治, 清水 伸高, 白髪 丈晴
    日本応用数理学会 学会誌「応用数理」, 32(1), pp. 5-15, 2022
    DOI: 10.11540/bjsiam.32.1_5
    Graph Theory Random Walks Survey Paper