Nobutaka Shimizu

According to our database, Nobutaka Shimizu authored at least 20 papers between 2014 and 2026.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2026

Hardness Amplification beyond Boolean Functions.

Nobutaka Shimizu, Kenji Yasunaga

Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

Optimal Random Self-Reductions for All Linear Problems.

Shuichi Hirahara, Nobutaka Shimizu

Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

Undecided State Dynamics with Many Opinions.

Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, Takeharu Shiraga

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2026

2025

Error-Correction of Matrix Multiplication Algorithms.

Shuichi Hirahara, Nobutaka Shimizu

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Asynchronous 3-Majority Dynamics with Many Opinions.

Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, Takeharu Shiraga

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

3-Majority and 2-Choices with Many Opinions.

Nobutaka Shimizu, Takeharu Shiraga

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2025

An Optimal Error-Correcting Reduction for Matrix Multiplication.

Shuichi Hirahara, Nobutaka Shimizu

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

Planted Clique Conjectures Are Equivalent.

Shuichi Hirahara, Nobutaka Shimizu

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

Reversible random walks on dynamic graphs.

Nobutaka Shimizu, Takeharu Shiraga

Random Struct. Algorithms, December, 2023

Hardness Self-Amplification: Simplified, Optimized, and Unified.

Shuichi Hirahara, Nobutaka Shimizu

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

Hardness Self-Amplification from Feasible Hard-Core Sets.

Shuichi Hirahara, Nobutaka Shimizu

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Metropolis Walks on Dynamic Graphs.

Nobutaka Shimizu, Takeharu Shiraga

CoRR, 2021

How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?

Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH.

Shuichi Hirahara, Nobutaka Shimizu

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

The Average Distance and the Diameter of Dense Random Regular Graphs.

Nobutaka Shimizu

Electron. J. Comb., 2020

Quasi-Majority Functional Voting on Expander Graphs.

Nobutaka Shimizu, Takeharu Shiraga

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models.

Nobutaka Shimizu, Takeharu Shiraga

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

2018

The Diameter of Dense Random Regular Graphs.

Nobutaka Shimizu

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2016

Average shortest path length of graphs of diameter 3.

Nobutaka Shimizu, Ryuhei Mori

Proceedings of the Tenth IEEE/ACM International Symposium on Networks-on-Chip, 2016

2014

Some results of multidimensional discrete probability measures represented by Euler products.

Takahiro Aoyama, Nobutaka Shimizu

JSIAM Lett., 2014