We study the Undecided-State Dynamics (USD), a fundamental consensus process in which each vertex holds one of k decided opinions or the undecided state. We consider both the gossip model and the population protocol model. Prior work established tight bounds on the consensus time of this process only for the regime k=O(n/(log⁡n)2) (for the population protocol model) and k = O((n/log n)1/3) (for the gossip model), often under restrictive assumptions on the initial configuration.

The linear problem specified by an n × n matrix M over a finite field is the problem of computing the product of M and a given vector x. We present optimal error-tolerant random self-reductions (also known as worst-case to average-case reductions) for all linear problems: Given a linear-size circuit that computes M x on an ε-fraction of inputs x for a positive constant ε, we construct a randomized linear-size circuit that computes M x for all inputs x with high probability. This resolves the open problem posed by Asadi, Golovnev, Gur, Shinkar, and Subramanian (SODA’24), who presented quantum n1.5-time random self-reductions for all linear problems. Somewhat surprisingly, we also demonstrate the quantum advantage of their quantum reduction over classical uniform algorithms, by proving that any classical subquadratic-time random self-reduction requires the advice complexity of Ω(log(1/ε) · logn), as long as the field size is at most 1/ε. We complement this advice complexity lower bound by presenting (1) a random self-reduction with the optimal advice complexity of O(log(1/ε) · logn) and (2) a uniform random self-reduction over a large finite field.

A central goal in average-case complexity is to understand how average-case hardness can be amplified to near-optimal hardness. Classical results such as Yao’s XOR lemma establish this principle for Boolean functions, but these techniques typically apply only to artificially constructed functions, rather than to natural computational problems. In this work, we extend hardness amplification beyond the Boolean setting and extend the XOR Lemma to the sum of functions over the finite field Fp, where p is a prime. Specifically, we show that if a function f ∶ {0,1}n → Fp fails to be computed on at least a δ-fraction of inputs, then the k-wise sum f+k(x1,…,xk) = f(x1) + ⋯ + f(xk) becomes almost optimally unpredictable: no efficient algorithm can compute it with success probability exceeding 1 + ε/p for suitable parameters k,δ,ε. Our proof is based on the pseudo-average-min entropy characterization of unpredictability due to Zheng (2014) and Vadhan and Zheng (2012), which we simplify and quantitatively refine to make the dependence of the circuit blow-up on all parameters fully explicit.

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).

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 of opinions. In synchronous consensus dynamics, we consider an n-vertex complete graph with self-loops, where each vertex holds an opinion from {1,..., k}. At each discrete-time round, all vertices update their opinions simultaneously according to a given protocol. The goal is to reach a consensus, where all vertices support the same opinion. In 3-Majority, each vertex chooses three random neighbors with replacement and updates its opinion to match the majority, with ties broken randomly. In 2-Choices, each vertex chooses two random neighbors with replacement. If the selected vertices hold the same opinion, the vertex adopts that opinion. Otherwise, it retains its current opinion for that round.

We consider 3-Majority, a probabilistic consensus dynamics on a complete graph with n vertices, each vertex starting with one of k initial opinions. At each discrete time step, a vertex u is chosen uniformly at random. The selected vertex u chooses three neighbors v1, v2, v3 uniformly at random with replacement and takes the majority opinion held by the three, where ties are broken in favor of the opinion of v3. The main quantity of interest is the consensus time, the number of steps required for all vertices to hold the same opinion. This asynchronous version turns out to be considerably harder to analyze than the synchronous version and so far results have only been obtained for k = 2. Even in the synchronous version the results for large k are far from tight. In this paper we prove that the consensus time is for all k. These are the first bounds for all k that are tight up to a polylogarithmic factor.

The planted clique conjecture states that no polynomial-time algorithm can find a hidden clique of size k ≪ √n in an n-vertex Erdős–Rényi random graph with a k-clique planted. In this paper, we prove the equivalence among many (in fact, most) variants of planted clique conjectures, such as search versions with a success probability exponentially close to 1 and with a non-negligible success probability, a worst-case version (the k-clique problem on incompressible graphs), decision versions with small and large success probabilities, and decision versions with adversarially chosen k and binomially distributed k. In particular, we establish the equivalence between the planted clique problem introduced by Jerrum and Kučera and its decision version suggested by Saks in the 1990s. Moreover, the equivalence among decision versions identifies the optimality of a simple edge counting algorithm: By counting the number of edges, one can efficiently distinguish an n-vertex random graph from a random graph with a k-clique planted with probability Θ(k2/n) for any k ≤ √n. We show that for any k, no polynomial-time algorithm can distinguish these two random graphs with probability ≫ k2 / n if and only if the planted clique conjecture holds. The equivalence among search versions identifies the first one-way function that admits a polynomial-time security-preserving self-reduction from exponentially weak to strong one-way functions. These results reveal a detection-recovery gap in success probabilities for the planted clique problem. We also present another equivalence between the existence of a refutation algorithm for the planted clique problem and an average-case polynomial-time algorithm for the k-clique problem with respect to the Erdős–Rényi random graph.

Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. We develop a general framework for proving hardness self-amplification, that is, the equivalence between strong and weak average-case hardness. Using this framework, we prove hardness self-amplification for popular problems, such as matrix multiplication, online matrix-vector multiplication, triangle counting of Erdős–Rényi random graphs, and the planted clique problem. As a corollary, we obtain the first search-to-decision reduction for the planted clique problem in a high-error regime. Our framework simplifies, improves, and unifies the previous hardness self-amplification results.

We consider the question of hardness self-amplification: Given a Boolean function f that is hard to compute on an o (1)-fraction of inputs drawn from some distribution, can we prove that f is hard to compute on a $(\displaystyle \frac{1}{2}-o(1))$-fraction of inputs drawn from the same distribution? We prove hardness self-amplification results for natural distributional problems studied in fine-grained average-case complexity, such as the problem of counting the number of the triangles modulo 2 in a random tripartite graph and the online vector-matrix-vector multiplication problem over $\mathbb{F}_{2}$. More generally, we show that any problem that can be decomposed into "computationally disjoint" subsets of inputs admits hardness self-amplification. This is proved by generalizing the security proof of the NisanWigderson pseudorandom generator, in which case nearly disjoint subsets of inputs are considered. At the core of our proof techniques is a new notion of feasible hard-core set, which generalizes Impagliazzo’s hard-core set [Impagliazzo, FOCS’95]. We show that any weak average-case hard function f has a feasible hard-core set H: any small H-oracle circuit (that is allowed to make queries q to H if $f(q)$ can be computed without the oracle) fails to compute f on a $(\displaystyle \frac{1}{2}-o(1))$-fraction of inputs in H.

In this paper, we seek a natural problem and a natural distribution of instances such that any O(nc–∊) time algorithm fails to solve most instances drawn from the distribution, while the problem admits an nc+o(1)-time algorithm that correctly solves all instances. Specifically, we consider the Ka,b counting problem in a random bipartite graph, where Ka,b is a complete bipartite graph and a and b are constants. Our distribution consists of the binomial random bipartite graphs Bαn,βn with edge density 1/2, where α and β are drawn uniformly at random from {1, …, a} and {1, …, b}, respectively. We determine the nearly optimal average-case complexity of this counting problem by proving the following results. Conditional Tight Worst-Case Complexity. Under the Strong Exponential Time Hypothesis, for any constants a ≥ 3 and ∊ > 0, there exists a constant b = b(a, ∊) such that no O(na–∊)-time algorithm counts the number of Ka,b subgraphs in a given n-vertex graph. On the other hand, for any constant a ≥ 8 and any b = b(n), we can count all Ka,b subgraphs in time bna+o(1). Worst-to-Average Reduction. If there exists a T(n)-time randomized heuristic algorithm that solves the Ka,b subgraph counting problem on a random graph Bαn,βn with success probability 1 — 1/polylog(n), then there exists a T(n)polylog(n)-time randomized algorithm that solves the Ka,b subgraph counting problem for any input with success probability 2/3. Fine-Grained Hardness Amplification. Suppose that there is a T(n)-time algorithm with success probability n–∊ that computes the parity of the number of Ka,b subgraphs in H, where is the disjoint union of k = O(∊ log n) i.i.d. random graphs G1, …, Gk each of which is drawn from the distribution of Bαn,βn. Then there is a T(n)nO(∊)-time randomized algorithm that counts Ka,b subgraphs for any input with success probability 2/3. The central idea behind these results is colorful subgraphs. For the first result, we reduce the k-Orthogonal Vectors problem to the colorful Ka,b detection problem. In the second result, we establish a worst-case-to-average-case reduction for a colorful subgraph counting problem based on the binary-extension technique given by [Boix-Adserà, Brennan, and Bresler; FOCS19]. Then, we reduce colorful Ka,b counting to Ka,b counting. Regarding the third result, we prove the classical XOR lemma and the direct product theorem in the fine-grained setting for subgraph counting problems. The core of the proof is an O(log n)-round doubly-efficient interactive proof system for the colorful subgraph counting problem such that the honest prover is asked to solve polylog(n) instances of the counting problem. The new protocol improves the known interactive proof system for the t-clique counting problem given by [Goldreich and Rothblum; FOCS18] in terms of query complexity.

Real networks are often dynamic. In response to it, analyses of algorithms on dynamic networks attract more and more attention in network science and engineering. Random walks on dynamic graphs also have been investigated actively in more than a decade, where in most cases the edge set changes but the vertex set is static. The vertex sets are also dynamic in many real networks. Motivated by a new technology of the analysis of random walks on dynamic graphs, this paper introduces a simple model of graphs with an increasing number of vertices and presents an analysis of random walks associated with the cover time on such graphs. In particular, we reveal that a random walk asymptotically covers the vertices all but a constant number if the vertex set grows moderately.

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/\sqrt{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)$.

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-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\leq p$. We obtain two main results. First, if $p=ω(\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 $Ω(n)$. By contrast, if $rr^*$, 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.

There is a tight upper bound on the order (the number of vertices) of any d-regular graph of diameter D, known as the Moore bound in graph theory. This bound implies a lower bound D0(n, d) on the diameter of any d-regular graph of order n. Actually, the diameter diam(Gn,d) of a random d-regular graph Gn,d of order n is known to be asymptotically “optimal” as n → ∞. Bollobás and de la Vega (1982) proved that diam(Gn,d) = (1 + o(1)) D0(n, d) = (1 + o(1)) logd–1 n holds w.h.p. (with high probability) for fixed d ≥ 3, whereas there exists a gap diam(Gn,d) – D0(n, d) = Ω(log log n). In this paper, we investigate the gap diam(Gn,d) – D0(n, d) for d = (β + o(1)) nα where α ∊ (0, 1) and β > 0 are arbitrary constants. We prove that diam(Gn,d) = ⌊α–1⌋ + 1 holds w.h.p. for such d. Our result implies that the gap is 1 if α–1 is an integer and d ≥ nα, and is 0 otherwise. One can easily obtain that diam(Gn,d) ≤ ⌊α–1⌋ + 1 holds w.h.p. by using the embedding theorem due to Dudek et al. (2017). Our critical contribution is to show that diam(Gn,d) ≤ ⌊a–1⌋ + 1 holds w.h.p. by the analysis of the distances of fixed vertex pairs.

A network topology with low average shortest path length (ASPL) provides efficient data transmission while the number of nodes and the number of links incident to each node are often limited due to physical constraints. In this paper, we consider the construction of low ASPL graphs under these constraints by using stochastic local search (SLS) algorithms. Since the ASPL cannot be calculated efficiently, the ASPL is not suitable for the evaluation function of SLS algorithms. We first derive an equality and bounds for the ASPL of graphs of diameter 3. On the basis of the simplest upper bound of the ASPL, we propose to use 3Δ + 2□ as the evaluation function for graphs of diameter 3 where Δ and □ denote the number of triangles and squares in a graph, respectively. We show that the proposed evaluation function can be evaluated in O(1) time as the number of nodes and the maximum degree tend to infinity by using some data tables. By using the simulated annealing with the proposed evaluation function, we construct low ASPL regular graphs of diameter 3 with 10 000 nodes.