10 citations · 19 across the 11 of their papers we have counts for
16 papers
Undecided State Dynamics with Many Opinions
Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik +2
We study the Undecided-State Dynamics (USD), a fundamental consensus process in which each vertex holds one of decided opinions or the undecided state. We consider both the gos…
3-Majority and 2-Choices with Many Opinions
Nobutaka Shimizu, Takeharu Shiraga
We present the first nearly-optimal bounds on the consensus time for the well-known synchronous consensus dynamics, specifically 3-Majority and 2-Choices, for an arbitrary number o…
Asynchronous 3-Majority Dynamics with Many Opinions
Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik +2
We consider 3-Majority, a probabilistic consensus dynamics on a complete graph with vertices, each vertex starting with one of initial opinions. At each discrete time step,…
Discrete Incremental Voting on Expanders
Colin Cooper, Tomasz Radzik, Takeharu Shiraga
Pull voting is a random process in which vertices of a connected graph have initial opinions chosen from a set of distinct opinions, and at each step a random vertex alters its…
Discrete Incremental Voting
Colin Cooper, Tomasz Radzik, Takeharu Shiraga
We consider a type of pull voting suitable for discrete numeric opinions which can be compared on a linear scale, for example, 1 ('disagree strongly'), 2 ('disagree'), 5…
An analysis of load-balancing algorithms on edge-Markovian evolving graphs
Takeharu Shiraga, Shuji Kijima
Analysis of algorithms on time-varying networks (often called evolving graphs) is a modern challenge in theoretical computer science. The edge-Markovian is a relatively simple and…
Reversible Random Walks on Dynamic Graphs
Nobutaka Shimizu, Takeharu Shiraga
Recently, random walks on dynamic graphs have been studied because of their adaptivity to the time-varying structure of real-world networks. In general, there is a tremendous gap b…
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga
Real networks are often dynamic. In response to it, analyses of algorithms on {\em dynamic networks} attract more and more attentions in network science and engineering. Random wal…
Quasi-majority Functional Voting on Expander Graphs
Nobutaka Shimizu, Takeharu Shiraga
Consider a distributed graph where each vertex holds one of two distinct opinions. In this paper, we are interested in synchronous voting processes where each vertex updates its op…
Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
Nobutaka Shimizu, Takeharu Shiraga
This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the \emph{Best-of-two} and the \emph{Best-of-…
Discrepancy Analysis of a New Randomized Diffusion Algorithm
Takeharu Shiraga
For an arbitrary initial configuration of discrete loads over vertices of a distributed graph, we consider the problem of minimizing the {\em discrepancy} between the maximum and m…
Dispersion processes
Colin Cooper, Andrew McDowell, Tomasz Radzik +2
We study a synchronous dispersion process in which particles are initially placed at a distinguished origin vertex of a graph . At each time step, at each vertex occupie…
Fast plurality consensus in regular expanders
Colin Cooper, Tomasz Radzik, Nicolás Rivera +1
Pull voting is a classic method to reach consensus among vertices with differing opinions in a distributed network: each vertex at each step takes on the opinion of a random ne…
The Cover Time of Deterministic Random Walks for General Transition Probabilities
Takeharu Shiraga
The deterministic random walk is a deterministic process analogous to a random walk. While there are some results on the cover time of the rotor-router model, which is a determinis…
Total Variation Discrepancy of Deterministic Random Walks for Ergodic Markov Chains
Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima +1
Motivated by a derandomization of Markov chain Monte Carlo (MCMC), this paper investigates deterministic random walks, which is a deterministic process analogous to a random walk.…
Deterministic Random Walks for Rapidly Mixing Chains
Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima +1
The rotor-router model is a deterministic process analogous to a simple random walk on a graph. This paper is concerned with a generalized model, functional-router model, which imi…