Conference Proceedings (Peer-Reviewed)
Optimal Random Self-Reductions for All Linear Problems
Shuichi Hirahara, Nobutaka Shimizu
Symposium on Theory of Computing (STOC 2026)
Average-Case Complexity
Abstract
The linear problem $\calL_M$ for a matrix $M\in\F^{n\times n}$ asks one to compute $Mx$ for a given vector $x\in\F^n$. Given an average-case solver $\calO$ for $\calL_M$ such that \[ \Pr_{x\sim\F^n}[\calO(x)=Mx]\ge\varepsilon, \] can we solve $\calL_M$ correctly on every input with almost the same running time?
This paper presents both positive and negative results on worst-case-to-average-case reductions for this problem.
- First, we present a surprisingly simple worst-case-to-average-case nonuniform reduction that uses $\Theta(n)$ bits of advice.
- Second, if the field size satisfies $p=|\F|>1/\varepsilon+1$, then there exists a uniform worst-case-to-average-case reduction.
- Third, if the field size satisfies $p=|\F|\le1/\varepsilon$, then any worst-case-to-average-case reduction requires $\Omega(\log_p(1/\varepsilon)\cdot\log n)$ bits of advice. Moreover, this lower bound is tight: there exists a worst-case-to-average-case reduction that uses $O(\log_p(1/\varepsilon)\cdot\log n)$ bits of advice.
Hardness Amplification Beyond Boolean Functions
Nobutaka Shimizu, Kenji Yasunaga
Symposium on Theory of Computing (STOC 2026)
Average-Case Complexity
Abstract
We prove an XOR lemma for $\F_p$-valued functions for every prime $p$, using the characterization of weak hardness in terms of pseudo min-average entropy (PAME) due to Zheng (2014) and Vadhan and Zheng (2012). Specifically, if $f\colon\{0,1\}^n\to\F_p$ is hard to compute on more than a $(1+\varepsilon)/p$ fraction of instances for any circuit of size $s$, then \[ f^{+k}\colon (x_1,\dots,x_k)\mapsto f(x_1)+\dots+f(x_k) \] is hard to compute on more than a $(1-\delta)$ fraction of instances for circuits of size $\Omega\!\left(s\cdot\frac{\varepsilon^2}{pk^2\log(k/\varepsilon)}\right)$, where $k=O(p^2\log(p/\varepsilon)/\delta)$. As an application, we present an error-tolerant worst-case-to-average-case nonuniform reduction for triangle counting over Erdős–Rényi graphs.
We also prove a query lower bound for adaptive black-box hardness amplification for $\F_p$-valued functions. This lower bound does not match the upper bound achieved by our XOR-lemma reduction. It is obtained via the framework of Shaltiel and Viola (2010) and Grinberg, Shaltiel, and Viola (2018) by considering a coin problem over $\F_p$. We also present a conceptually simpler proof of the fixed-set lemma using KL-divergence.
3-Majority and 2-Choices with Many Opinions
Nobutaka Shimizu, Takeharu Shiraga
Symposium on Principles of Distributed Computing (PODC 2025)
DOI:10.1145/3732772.3733511 | arXiv:2503.02426
Graph Theory Consensus Dynamics Stochastic Processes
Abstract
This paper presents the first tight bound on the consensus time of 3-Majority and 2-Choices with an arbitrary number of opinions in the parallel gossip model, resolving our seven-year-old private open problem.
The proof relies on multi-step concentration via the Freedman inequality framework developed in our SODA’25 paper. The main technical challenge is that, in the gossip model, all vertices simultaneously update their opinions. As a result, we cannot exploit the locality of updates from the sequential model, which was crucial in our SODA’25 analysis (in martingale terms, the bounded-jump condition is no longer applicable).
We overcome this difficulty by observing that, in each round, all vertices independently choose their next opinion. This observation leads us to introduce the notion of a Bernstein condition, which allows us to transfer concentration bounds from the sequential model to the parallel gossip model.
An Optimal Error-Correcting Reduction for Matrix Multiplication
Shuichi Hirahara, Nobutaka Shimizu
International Colloquium on Automata, Languages, and Programming (ICALP 2025)
DOI: 10.4230/LIPIcs.ICALP.2025.97 | Slide | ECCC
Average-Case Complexity Error-Correcting Code
Abstract
This paper is a follow-up to our STOC’25 paper below, which presents a uniform worst-case-to-average-case and exact-to-approximation reduction for matrix multiplication. Specifically, we show that there exists a randomized oracle algorithm $M^{\calO}$ such that, for any oracle $\calO$ satisfying \[ \Pr_{\substack{A,B\sim\F^{n\times n} \\ i,j\sim[n]}}[\calO(A,B)_{i,j} = (AB)_{i,j}] \ge \frac{1}{|\F|}+\varepsilon, \] the algorithm $M^{\calO}$ satisfies \[ \forall A,B\in\F^{n\times n}, \quad \Pr_{M^{\calO}}[M^{\calO}(A,B)=AB] \ge \frac{2}{3}. \] This oracle algorithm makes only $\Otilde(1)$ queries.
The key idea is to encode matrix multiplication using derandomized direct sum over expander walks, and then apply a recent linear-time approximate list-decoding algorithm for this code due to Jeronimo (2023).
Error-Correction of Matrix Multiplication Algorithms
Shuichi Hirahara, Nobutaka Shimizu
Symposium on Theory of Computing (STOC 2025)
DOI: 10.1145/3717823.3718244 | ECCC | Slide
Average-Case Complexity Error-Correcting Code
Abstract
Given an efficient algorithm $\calO$ that computes an $\alpha$ fraction of the entries of $AB$ for two uniformly random matrices $A,B\sim\F^{n\times n}$, can we design an efficient algorithm that computes all entries of $AB$?
We answer this question affirmatively when $|\F|\ge n/\alpha^2$. Specifically, there exists a randomized oracle algorithm $M^{\calO}$ such that, for any oracle $\calO$ satisfying \[ \Pr_{\substack{A,B\sim\F^{n\times n} \\ i,j\sim[n]}}[\calO(A,B)_{i,j} = (AB)_{i,j}] \ge \alpha, \] the algorithm $M^{\calO}$ satisfies \[ \forall A,B\in\F^{n\times n}, \quad \Pr_{M^{\calO}}[M^{\calO}(A,B)=AB] \ge \frac{2}{3}. \] Moreover, if $\calO$ runs in time $T(n)$, then $M^{\calO}$ runs in time $\Otilde(T(n)\cdot\log|\F|\cdot\log(1/\alpha))$.
We also consider the case where the field size $|\F|$ is constant. We present a nonuniform reduction when $\alpha>1/|\F|+\varepsilon$ (note that outputting a random matrix achieves $\alpha=1/|\F|$, so this bound is nearly tight), and a uniform reduction when $\alpha>2/|\F|+\varepsilon$.
The key idea is to encode matrices using a linear tensor code. Such a code encodes a matrix $C\in\F^{n\times n}$ as \[ LCL^\top \in \F^{N\times N}, \] for a carefully designed matrix $L\in\F^{N\times n}$. Under this encoding, the product $AB$ is mapped to $LABL^\top$, and we obtain a noisy codeword $\widetilde{C}$ that is close to $LABL^\top$ by running the approximation solver on the inputs \[ LA \text{ and } BL^\top. \]
Asynchronous 3-Majority Dynamics with Many Opinions
Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, Takeharu Shiraga
Symposium on Discrete Algorithms (SODA 2025)
DOI: 10.1137/1.9781611978322.140 | arXiv:2503.02426 | Slide
Graph Theory Consensus Dynamics Stochastic Processes
Abstract
This paper bounds the consensus time of 3-Majority in the sequential update model (i.e., at each round, only one randomly chosen vertex updates its opinion), where each vertex holds an opinion from the set $\{1,\dots,k\}$. We prove that the consensus time is $\Otilde(\min(k,\sqrt{n}))$ with high probability for any $2\le k\le n$, using Freedman’s inequality (a Bernstein-type concentration inequality for martingales).
Planted Clique Conjectures Are Equivalent
Shuichi Hirahara, Nobutaka Shimizu
Symposium on Theory of Computing (STOC 2024)
DOI: 10.1145/3618260.3649751 | ECCC | Slide
Average-Case Complexity Graph Theory
Abstract
We study the hardness self-amplification problem for planted clique, for both the search and decision versions. For example, we show that if we can find an $n^{1/2-\alpha}$-clique hidden in the Erdős–Rényi graph $G(n,1/2)$ with success probability $\varepsilon$ in polynomial time, then we can find an $n^{1/2-\alpha-o(1)}$-clique in $G(n,1/2)$ in polynomial time.
As a corollary, we present the first search-to-decision reduction for the planted clique problem in a high-error regime, meaning that any algorithm that decides planted clique with a small advantage can be transformed into a search algorithm with a large success probability.
The core idea of our reductions is to embed an instance of planted clique into a slightly larger Erdős–Rényi random graph and then shrink the graph by taking a random induced subgraph. Correctness follows from the sampler property, via a read-$k$ concentration inequality due to Gavinsky, Lovett, Saks, and Srinivasan (2015).
Hardness Self-Amplification: Simplified, Optimized, and Unified
Shuichi Hirahara, Nobutaka Shimizu
Symposium on Theory of Computing (STOC 2023)
DOI: 10.1145/3564246.3585189 | ECCC | Slide
Average-Case Complexity
Abstract
Hardness amplification is a general technique for turning a problem $\Pi$ that is only weakly hard on average into one that is hard on average with high probability. In hardness self-amplification, the goal is more ambitious: the amplified problem $\Pi'$ is required to be identical to the original problem $\Pi$, unlike classical approaches such as the direct product theorem or the XOR lemma, which inherently modify the problem.
I proved such self-amplification results for several natural computational problems, including matrix multiplication, triangle counting modulo $2$, and the planted clique problem. The unifying idea behind these results is upward self-reduction, which embeds a given instance into a slightly larger random instance. Correctness follows from the fact that the reduction exhibits a sampler property of the bipartite graph specified this embedding.
As a particularly simple example, I obtained an error-tolerant worst-case-to-average-case reduction for matrix multiplication based on the direct product theorem. Despite its simplicity, this reduction already captures many of the key ideas behind self-amplification and remains one of my favorite constructions.
Hardness Self-Amplification from Feasible Hard-Core Sets
Shuichi Hirahara, Nobutaka Shimizu
Foundations of Computer Science (FOCS 2022)
DOI: 10.1109/FOCS54457.2022.00083 | ECCC | Slide
Average-Case Complexity
Abstract
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
Shuichi Hirahara, Nobutaka Shimizu
Symposium on Discrete Algorithms (SODA 2021)
DOI: 10.1137/1.9781611976465.140 | arXiv:2010.05822 | Slide
Average-Case Complexity Graph Theory
Abstract
How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
Shuji Kijima, Nobutaka Shimizu, Takeharu Shiraga
Symposium on Discrete Algorithms (SODA 2021)
DOI: 10.1137/1.9781611976465.8 | arXiv:2008.10837 | Slide
Graph Theory Random Walks
Abstract
Quasi-majority Functional Voting on Expander Graphs
Nobutaka Shimizu, Takeharu Shiraga
International Colloquium on Automata, Languages, and Programming (ICALP 2020)
DOI: 10.4230/LIPIcs.ICALP.2020.97 | arXiv:2002.07411
Graph Theory Consensus Dynamics Stochastic Processes
Abstract
We introduce the notion of quasi-majority functional voting, which is a broad class of consensus dynamics including 3-Majority and 2-Choices, and we bound the consensus time on expander graphs.
Phase Transitions of Best-of-Two and Best-of-Three on Stochastic Block Models
Nobutaka Shimizu, Takeharu Shiraga
International Symposium on Distributed Computing (DISC 2019)
DOI: 10.4230/LIPIcs.DISC.2019.32 | arXiv:1907.12212
Graph Theory Consensus Dynamics Stochastic Processes
Abstract
We consider 3-Majority and 2-Choices (in the synchronous gossip model) on a stochastic block model $G(n,p,q)$. We show that there exists a threshold $\theta\in(0,1)$ such that
- if $q/p>\theta$, then the dynamics converges to consensus within $O(\log n)$ rounds.
- if $q/p<\theta$, then there exists an initial configuration such that the consensus time is exponentially large.
The Diameter of Dense Random Regular Graphs
Nobutaka Shimizu
Symposium on Discrete Algorithms (SODA 2018)
DOI: 10.1137/1.9781611975031.126
Graph Theory Random Graphs
Abstract
Average Shortest Path Length of Graphs of Diameter 3
Nobutaka Shimizu, Ryuhei Mori
Symposium on Networks-on-Chip (NOCS 2016)
DOI: 10.1109/NOCS.2016.7579335 | arXiv:1606.05119
Graph Theory