掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

DOI： 10.4230/LIPIcs.ICALP.2025.97

researchmap

その他リンク： https://dblp.org/db/conf/icalp/icalp2025.html#HiraharaS25

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ACM  

DOI： 10.1145/3717823.3718244

researchmap

その他リンク： https://dblp.org/rec/conf/stoc/2025

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ACM  

DOI： 10.1145/3618260.3649751

researchmap

掲載種別：研究論文（学術雑誌）   出版者・発行元：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

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ACM  

DOI： 10.1145/3564246.3585189

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE  

DOI： 10.1109/focs54457.2022.00058

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）  

DOI： 10.11540/bjsiam.32.1_5

researchmap

記述言語：英語   掲載種別：論文集(書籍)内論文   出版者・発行元：Society for Industrial and Applied Mathematics  

DOI： 10.1137/1.9781611976465.8

Scopus

researchmap

記述言語：英語   掲載種別：論文集(書籍)内論文   出版者・発行元：Society for Industrial and Applied Mathematics  

DOI： 10.1137/1.9781611976465.140

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Wiley  

DOI： 10.1002/rsa.20992

researchmap

その他リンク： https://onlinelibrary.wiley.com/doi/full-xml/10.1002/rsa.20992

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Schloss Dagstuhl - Leibniz-Zentrum für Informatik  

DOI： 10.4230/LIPIcs.ICALP.2020.97

researchmap

その他リンク： https://dblp.uni-trier.de/db/conf/icalp/icalp2020.html#ShimizuS20

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

掲載種別：論文集(書籍)内論文   出版者・発行元：Society for Industrial and Applied Mathematics  

DOI： 10.1137/1.9781611975031.126

researchmap

掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：IEEE  

DOI： 10.1109/nocs.2016.7579335

researchmap

researchmap

researchmap

開催年月日： 2023年2月

researchmap

開催年月日： 2022年8月

記述言語：日本語   会議種別：口頭発表（招待・特別）  

researchmap

開催年月日： 2022年6月

記述言語：日本語  

researchmap

researchmap

開催年月日： 2020年8月

記述言語：日本語  

researchmap

開催年月日： 2020年2月

記述言語：日本語  

researchmap

記述言語：日本語  

researchmap

記述言語：英語  

researchmap

記述言語：日本語  

researchmap