Showing 2020Show all
3 papers · 1 filter
cs.CC2020
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
Shuichi Hirahara, Nobutaka Shimizu
In this paper, we seek a natural problem and a natural distribution of instances such that any -time algorithm fails to solve most instances drawn from the distribution…
math.PR2020
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…
math.PR2020
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…