Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

DOI： 10.4230/LIPIcs.ICALP.2025.97

researchmap

Other Link： https://dblp.org/db/conf/icalp/icalp2025.html#HiraharaS25

Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

DOI： 10.1145/3717823.3718244

researchmap

Other Link： https://dblp.org/rec/conf/stoc/2025

Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

DOI： 10.1145/3618260.3649751

researchmap

Publishing type：Research paper (scientific journal)   Publisher：Wiley  

Abstract

Consider an ‐vertex graph where each vertex holds one of two distinct opinions. We are interested in the consensus time of synchronous voting processes, where each vertex is allowed to update its opinion according to a predefined commonly local updating rule. This article proposes a general class of voting processes called quasi‐majority functional voting and gives upper and lower bounds of the consensus time. Our results cover many previous results on specific processes, for example, best‐of‐two (a.k.a. 2Choices) and best‐of‐three (a.k.a. 3Majority), as special cases. Our key ingredient is a nonlinear extension of the expander mixing lemma, which enables us to estimate expected and variance changes in opinions of quasi‐majority functional voting on expander graphs.

DOI： 10.1002/rsa.21224

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

DOI： 10.1145/3564246.3585189

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Wiley  

Abstract

This paper discusses random walks on edge‐changing dynamic graphs. We prove general and improved bounds for mixing, hitting, and cover times for a random walk according to a sequence of irreducible and reversible transition matrices with the time‐invariant stationary distribution. An interesting consequence is the tight bounds of the lazy Metropolis walk on any dynamic connected graph. We also prove bounds for multiple random walks on dynamic graphs. Our results extend previous upper bounds for simple random walks on dynamic graphs and give improved and tight upper bounds in several cases. Our results reinforce the observation that time‐inhomogeneous Markov chains with an invariant stationary distribution behave almost identically to a time‐homogeneous chain.

DOI： 10.1002/rsa.21164

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

DOI： 10.1109/focs54457.2022.00058

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

DOI： 10.11540/bjsiam.32.1_5

researchmap

Language：English   Publishing type：Part of collection (book)   Publisher：Society for Industrial and Applied Mathematics  

DOI： 10.1137/1.9781611976465.8

Scopus

researchmap

Language：English   Publishing type：Part of collection (book)   Publisher：Society for Industrial and Applied Mathematics  

DOI： 10.1137/1.9781611976465.140

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Wiley  

DOI： 10.1002/rsa.20992

researchmap

Other Link： https://onlinelibrary.wiley.com/doi/full-xml/10.1002/rsa.20992

Publishing type：Research paper (international conference proceedings)   Publisher：Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

DOI： 10.4230/LIPIcs.ICALP.2020.97

researchmap

Other Link： https://dblp.uni-trier.de/db/conf/icalp/icalp2020.html#ShimizuS20

Language：English   Publishing type：Research paper (scientific journal)   Publisher：The Electronic Journal of Combinatorics  

Let $\mathrm{AD}(G_{n,d})$ be the average distance of $G_{n,d}$, a random $n$-vertex $d$-regular graph.
For $d=(\beta+o(1))n^{\alpha}$ with two arbitrary constants $\alpha\in(0,1)$ and $\beta>0$, we prove that $|\mathrm{AD}(G_{n,d})-\mu|<\epsilon$ holds with high probability for any constant $\epsilon>0$, where $\mu$ is equal to $\alpha^{-1}+\exp(-\beta^{1/\alpha})$ if $\alpha^{-1}\in\mathbb{N}$ and to $\lceil\alpha^{-1}\rceil$ otherwise.
Consequently, we show that the diameter of the $G_{n,d}$ is equal to $\lfloor\alpha^{-1}\rfloor+1$ with high probability.

DOI： 10.37236/8705

researchmap

Publishing type：Part of collection (book)   Publisher：Society for Industrial and Applied Mathematics  

DOI： 10.1137/1.9781611975031.126

researchmap

Publishing type：Research paper (international conference proceedings)   Publisher：IEEE  

DOI： 10.1109/nocs.2016.7579335

researchmap

researchmap

researchmap

Event date： 2023.2

researchmap

Event date： 2022.8

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Event date： 2022.6

Language：Japanese  

researchmap

researchmap

Event date： 2020.8

Language：Japanese  

researchmap

Event date： 2020.2

Language：Japanese  

researchmap

Language：Japanese  

researchmap

Language：English  

researchmap

Language：Japanese  

researchmap