Search Results

Documents authored by Shimizu, Nobutaka

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.97
An Optimal Error-Correcting Reduction for Matrix Multiplication

Authors: Shuichi Hirahara and Nobutaka Shimizu

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We present an optimal "worst-case exact to average-case approximate" reduction for matrix multiplication over a finite field of prime order p. Any efficient algorithm that correctly computes, in expectation, at least (1/p + ε)-fraction of entries of the multiplication A ⋅ B of a pair (A, B) of uniformly random matrices over the finite field of order p for a positive constant ε can be transformed into an efficient randomized algorithm that computes A ⋅ B for all the pairs (A, B) of matrices with high probability. Previously, such reductions were known only in a low-error regime (Gola, Shinkar and Singh; RANDOM 2024) or under non-uniform reductions (Hirahara and Shimizu; STOC 2025).
Cite as

Shuichi Hirahara and Nobutaka Shimizu. An Optimal Error-Correcting Reduction for Matrix Multiplication. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 97:1-97:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hirahara_et_al:LIPIcs.ICALP.2025.97,
  author =	{Hirahara, Shuichi and Shimizu, Nobutaka},
  title =	{{An Optimal Error-Correcting Reduction for Matrix Multiplication}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{97:1--97:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.97},
  URN =		{urn:nbn:de:0030-drops-234742},
  doi =		{10.4230/LIPIcs.ICALP.2025.97},
  annote =	{Keywords: Matrix Multiplication, Error-Correcting Reduction, Average-Case Complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.97
Quasi-Majority Functional Voting on Expander Graphs

Authors: Nobutaka Shimizu and Takeharu Shiraga

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
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 opinion according to a predefined common local updating rule. For example, each vertex adopts the majority opinion among 1) itself and two randomly picked neighbors in best-of-two or 2) three randomly picked neighbors in best-of-three. Previous works intensively studied specific rules including best-of-two and best-of-three individually. In this paper, we generalize and extend previous works of best-of-two and best-of-three on expander graphs by proposing a new model, quasi-majority functional voting. This new model contains best-of-two and best-of-three as special cases. We show that, on expander graphs with sufficiently large initial bias, any quasi-majority functional voting reaches consensus within O(log n) steps with high probability. Moreover, we show that, for any initial opinion configuration, any quasi-majority functional voting on expander graphs with higher expansion (e.g., Erdős-Rényi graph G(n,p) with p = Ω(1/√n)) reaches consensus within O(log n) with high probability. Furthermore, we show that the consensus time is O(log n/log k) of best-of-(2k+1) for k = o(n/log n).
Cite as

Nobutaka Shimizu and Takeharu Shiraga. Quasi-Majority Functional Voting on Expander Graphs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 97:1-97:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{shimizu_et_al:LIPIcs.ICALP.2020.97,
  author =	{Shimizu, Nobutaka and Shiraga, Takeharu},
  title =	{{Quasi-Majority Functional Voting on Expander Graphs}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{97:1--97:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.97},
  URN =		{urn:nbn:de:0030-drops-125042},
  doi =		{10.4230/LIPIcs.ICALP.2020.97},
  annote =	{Keywords: Distributed voting, consensus problem, expander graph, Markov chain}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.32
Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models

Authors: Nobutaka Shimizu and Takeharu Shiraga

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
This paper is concerned with voting processes on graphs where each vertex holds one of two different opinions. In particular, we study the Best-of-two and the Best-of-three. Here at each synchronous and discrete time step, each vertex updates its opinion to match the majority among the opinions of two random neighbors and itself (the Best-of-two) or the opinions of three random neighbors (the Best-of-three). Previous studies have explored these processes on complete graphs and expander graphs, but we understand significantly less about their properties on graphs with more complicated structures. In this paper, we study the Best-of-two and the Best-of-three on the stochastic block model G(2n,p,q), which is a random graph consisting of two distinct Erdős-Rényi graphs G(n,p) joined by random edges with density q <= p. We obtain two main results. First, if p=omega(log n/n) and r=q/p is a constant, we show that there is a phase transition in r with threshold r^* (specifically, r^*=sqrt{5}-2 for the Best-of-two, and r^*=1/7 for the Best-of-three). If r>r^*, the process reaches consensus within O(log log n+log n/log (np)) steps for any initial opinion configuration with a bias of Omega(n). By contrast, if r<r^*, then there exists an initial opinion configuration with a bias of Omega(n) from which the process requires at least 2^{Omega(n)} steps to reach consensus. Second, if p is a constant and r>r^*, we show that, for any initial opinion configuration, the process reaches consensus within O(log n) steps. To the best of our knowledge, this is the first result concerning multiple-choice voting for arbitrary initial opinion configurations on non-complete graphs.
Cite as

Nobutaka Shimizu and Takeharu Shiraga. Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{shimizu_et_al:LIPIcs.DISC.2019.32,
  author =	{Shimizu, Nobutaka and Shiraga, Takeharu},
  title =	{{Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.32},
  URN =		{urn:nbn:de:0030-drops-113397},
  doi =		{10.4230/LIPIcs.DISC.2019.32},
  annote =	{Keywords: Distributed Voting, Consensus Problem, Random Graph}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact