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 a lower bound for Pauli Manipulation Detection (PMD) codes, a class of quantum codes that detect every Pauli error with high probability. Our lower bound reveals the first trade-off between the error parameter and the coding rate. Specifically, we show that everyq-ary PMD code of lengthnand coding rateRmust satisfyR≤ 1 – 2/nlogq(1/ε)+o(1), where ε is the error parameter.

Abstract This paper studies the cardinality of codes correcting insertions and deletions. We give improved upper and lower bounds on code size. Our upper bound is obtained by utilizing the asymmetric property of list decoding for insertions and deletions and can be seen as analogous to the Elias bound in the Hamming metric. Our non-asymptotic bound is better than the existing bounds when the minimum Levenshtein distance is relatively large. The asymptotic bound exceeds the Elias and the MRRW bounds adapted from the Hamming-metric bounds for the binary and the quaternary cases. Our lower bound improves on the bound by Levenshtein, but its effect is limited and vanishes asymptotically.

In this work, we study the problem of list decoding of insertions and deletions. We present a Johnson-type upper bound on the maximum list size. The bound is meaningful only when insertions occur. Our bound implies that there are binary codes of rate Ω(1) that are list-decodable from a 0.707-fraction of insertions. For any τI≥ 0 and τD∈ [0, 1), there exist q-ary codes of rate Ω(1) that are list-decodable from a τI-fraction of insertions and τI-fraction of deletions, where q depends only on τIand τ . We also provide efficient encoding and decoding algorithms for list-decoding from τI-fraction of insertions and τ -fraction of deletions for any τI≥ 0 and τD∈ [0, 1). Based on the Johnson-type bound, we derive a Plotkin-type upper bound on the code size in the Levenshtein metric.

Abstract This paper explores the possibilities and limitations of error correction by the structural simplicity of error mechanisms. Specifically, we consider channel models, called samplable additive channels, in which (i) errors are efficiently sampled without the knowledge of the coding scheme or the transmitted codeword; (ii) the entropy of the error distribution is bounded; and (iii) the number of errors introduced by the channel is unbounded. For the channels, several negative and positive results are provided. Assuming the existence of one-way functions, there are samplable additive errors of entropy nε for ε∈(0,1) that are pseudorandom, and thus not correctable by efficient coding schemes. It is shown that there is an oracle algorithm that induces a samplable distribution over {0,1}n of entropy m=ω(logn) that is not pseudorandom, but is uncorrectable by efficient schemes of rate less than 1−m/n−o(1). The results indicate that restricting error mechanisms to be efficiently samplable and not pseudorandom is insufficient for error correction. As positive results, some conditions are provided under which efficient error correction is possible.

List decoding of insertions and deletions is studied. A Johnson-type upper bound on the maximum list size is derived. The bound is meaningful only when insertions occurred. The result implies that there are binary codes that are potentially list-decodable from a 0.707-fraction of insertions in polynomial time. For non-binary code, for any constant r > 0, there are codes over constant-sized alphabets that achieve a constant list size for a list-decoding radius that is r times larger than the code length. Based on the Johnson-type bound, a Plotkin-type upper bound on the code size in the Levenshtein metric is also derived.

We present a protocol compiler of rational secret-sharing that converts any rational secret-sharing protocol to a protocol with an expected constant-round reconstruction. Our compiler can be applied to protocols for synchronous channels, and preserves a strict Nash equilibrium of the original protocol. Combining with an existing protocol, we obtain the first expected constant-round protocol that achieves a strict Nash equilibrium with the optimal coalition resilience ⌈n2⌉−1⁠, where n is the number of players. Our compiler can be extended to one that preserves the immunity to unexpectedly behaving players. For any constant m≥1⁠, we obtain an expected constant-round protocol that achieves a Nash equilibrium with the optimal coalition resilience ⌈n2⌉−m−1 in the presence of m unexpectedly behaving players. The protocol also achieves a strict Nash equilibrium. As a negative result, we show that if an expected constant-round protocol has immunity m>0⁠, then it cannot achieve a strict Nash equilibrium with the coalition resilience 2. Thus, our protocol with immunity achieves the optimal coalition resilience with respect to both Nash and strict Nash equilibrium.

We study the correctability of efficiently samplable errors. Specifically, we consider samplable additive-error channels, where unbounded-weight errors are sampled by a polynomial-time algorithm, and added to the channel input in an oblivious way. Assuming the existence of one-way functions, there are samplable distributions Z over {0, 1}nwith entropy nεfor 01-(m+log(1-ε))/n. Finally, we observe that small-biased distributions are not correctable by high-rate codes, and hence there is a small-biased Z with entropy m that is not correctable for rate R > 1-m/n+(2 log n+O(1))/n. To derive these results, we use relations between error-correcting codes and other notions such as data compression and randomness condensers.

The error correction capability of binary linear codes with minimum distance decoding, in particular the number of correctable/uncorrectable errors, is investigated for general linear codes and the first-order Reed–Muller codes. For linear codes, a lower bound on the number of uncorrectable errors is derived. The bound for uncorrectable errors with a weight of half the minimum distance asymptotically coincides with the corresponding upper bound for Reed–Muller codes and random linear codes. For the first-order Reed–Muller codes, the number of correctable/uncorrectable errors with a weight of half the minimum distance plus one is determined. This result is equivalent to deriving the number of Boolean functions of$m$variables with nonlinearity$2^{m-2}+1$. Themonotone error structureand its related notionslarger halfandtrial set, which were introduced by Helleseth, Kløve, and Levenshtein, are mainly used to derive the results.

A lower bound on the number of uncorrectable errors of weight half the minimum distance is derived for binary linear codes satisfying some condition. The condition is satisfied by some primitive BCH codes, extended primitive BCH codes, Reed-Muller codes, and random linear codes. The bound asymptotically coincides with the corresponding upper bound for Reed-Muller codes and random linear codes. By generalizing the idea of the lower bound, a lower bound on the number of uncorrectable errors for weights larger than half the minimum distance is also obtained, but the generalized lower bound is weak for large weights. The monotone error structure and its related notion larger half and trial set, which are introduced by Helleseth, Kløve, and Levenshtein, are mainly used to derive the bounds.

Some methods to determine the local weight distribution of binary linear codes are presented. Two approaches are studied: A computational approach and a theoretical approach. For the computational approach, an algorithm for computing the local weight distribution of codes using the automorphism group of the codes is devised. In this algorithm, a code is considered the set of cosets of a subcode, and the set of cosets is partitioned into equivalence classes. Thus, only the weight distributions of zero neighbors for each representative coset of equivalence classes are computed. For the theoretical approach, relations between the local weight distribution of a code, its extended code, and its even weight subcode are studied. As a result, the local weight distributions of some of the extended primitive Bose-Chaudhuri-Hocquenghen (BCH) codes, Reed-Muller codes, primitive BCH codes, punctured Reed-Muller codes, and even weight subcodes of primitive BCH codes and punctured Reed-Muller codes are determined

Relations between the local weight distributions of a binary linear code, its extended code, and its even weight subcode are presented. In particular, for a code of which the extended code is transitive invariant and contains only codewords with weight multiples of four, the local weight distribution can be obtained from that of the extended code. Using the relations, the local weight distributions of the (127, k) primitive BCH codes for k les 50, the (127, 64) punctured third-order Reed-Muller, and their even weight subcodes are obtained from the local weight distribution of the (128, k) extended primitive BCH codes for k les 50 and the (128, 64) third-order Reed-Muller code. We also show an approach to improve an algorithm for computing the local weight distribution proposed before