Papers

We investigate secure communication over a classical multiple-access wiretap channel (MAC-WTC), specifically exploring the benefit of shared entanglement between the transmitters. Under the strict semantic security criterion, we derive an achievable rate region and a regularized expression for the secrecy capacity. We further establish a single-letter upper bound on the secure capacity of the MAC-WTC with entangled transmitters. Our results demonstrate that entanglement strictly enlarges the secrecy capacity of MAC-WTC compared to sharing only classical correlated randomness, a finding we illustrate using a pseudo-telepathy game example. Finally, we establish new strong soft-covering lemmas for the output statistics of multipleaccess channels (MACs) with entangled transmitters. Our results generalize existing results for non-entangled systems.

In secure distributed matrix multiplication, a user wishes to compute the product of two matrices with the assistance of servers, in such a way that any $T$ colluding servers learn nothing about either matrix. Degree tables are a combinatorial tool for constructing polynomial codes for this problem and underlie several state-of-the-art schemes, including $\mathsf{GASP}_r$, $\mathsf{GASP}_{r,s}$, and $\mathsf{DOG}_{r,s}$. We introduce a periodic-gap framework for constructing degree tables that contains these three families as special cases and leads to two new constructions, $\mathsf{SHIFT}_{r,s}$ and $\mathsf{COVER}_r$. We determine their exact recovery thresholds and show that, in many cases, they outperform the current state of the art. We also prove a new lower bound on the recovery threshold of ordinary integer degree tables. In the balanced case, in which the partitioning parameters and the security parameter are equal, we sharpen this bound to match $\mathsf{SHIFT}_{r,s}$ up to lower-order terms, showing that it is asymptotically optimal among degree-table constructions.

In this paper, we investigate the constrained capacity of discrete Fourier transform (DFT)-precoded faster-than-Nyquist (FTN) signaling over frequency-selective channels with finite-alphabet inputs. With a cyclic prefix (CP) and cyclic suffix (CS), the FTN and multipath induced intersymbol interference (ISI) is decomposed into parallel eigenchannels, whose gains are jointly determined by the folded FTN spectrum and the channel frequency response. Based on this decomposition, we derive the constrained capacity for finite-alphabet constellations and formulate a mismatched decoding achievable information rate for DFT-precoded FTN signaling without CP/CS, quantifying the finite-block rate loss caused by imperfect diagonalization. We find that even under mismatched decoding, FTN significantly improves upon Nyquist transmission.

Bivariate bicycle (BB) codes of Bravyi et al.~\cite{Bravyi2024} are quantum low-density parity-check codes with weight-$6$ checks, exemplified by $[[144,12,12]]$ with $kd^2/n=12$. We develop the algebraic structure theory of BB-type codes with weight-$8$ checks (weight-$4$ generator polynomials) and use it, together with an exactly validated search pipeline, to construct and certify new codes. We prove an exact dimension formula $k=2\dim R/(A,B)$ (forcing even $k$), a $4\ell m$-element symmetry group on generator pairs, an $X/Z$ distance equality $d_X=d_Z$, and a family of subgroup-coset kernel vectors giving rigorous distance upper bounds and a design rule for high-distance constructions; all distances are computed exhaustively by a cross-validated bit-mask verifier. At $n=144$ the pipeline returns a census of $53$ codes whose strongest members surpass the BB benchmark: $[[144,6,d\ge 15]]$ exceeds the benchmark distance $12$ (certified $d\ge 15$), $[[144,10,12]]$ reaches it with weight-$8$ checks, and $[[144,16,10]]$ encodes a third more logical qubits at $kd^2/n=11.11$ ($7.4\%$ below benchmark) while decoding no worse. At $n=72$, $[[72,14,8]]$ attains $kd^2/n=12.44$—more than twice the same-length BB code—and decodes better; a circuit-level memory experiment places our weight-$8$ codes at $\approx 0.1\%$ pseudo-threshold versus $\approx 0.4\%$ for the BB reference under an identical model, quantifying the threshold cost of the heavier checks. All structural statements are verified numerically on the whole census.

Let $C \le \mathbb{F}_q^n$ be a uniformly random $\mathbb{F}_q$-linear code of rate $1 - h_q(\rho) - \varepsilon$, and let $L^*(C,\rho)$ be the least $L$ such that every Hamming ball of relative radius $\rho$ contains at most $L$ codewords of $C$. That $L^* = \Theta_{q,\rho}(1/\varepsilon)$ has been known since work of Guruswami, Håstad and Kopparty and of Guruswami and Narayanan. Guruswami, Li, Mosheiff, Resch, Silas and Wootters proved that the constant in front of $1/\varepsilon$ is at least $h_q(\rho)$ for all $q$, along with an upper bound special to $q = 2$ which narrowed $L^*$ to within three consecutive integers in that case. But for $q \ge 3$ no upper bound with the correct constant was known. We determine $L^*$ for every prime power $q$. Let $\zeta := h_q(\rho)/\varepsilon$. For every sufficiently small $\varepsilon$, with probability $1-o(1)$ over the choice of $C$, $$L^*(C,\rho) = \lceil \zeta \rceil,$$ unless the fractional part of $\zeta$ is at most $q^{-\Omega_{q,\rho}(\zeta)}$, in which case $L^*(C,\rho)$ is $\lfloor \zeta \rfloor$ or $\lfloor \zeta \rfloor + 1$. By the threshold characterization of random linear codes due to Mosheiff, Resch, Ron-Zewi, Silas and Wootters, both bounds reduce to a two-sided estimate of a single quantity $V(q,L,\rho)$, where $1-V(q,L,\rho)$ is the threshold rate for $(\rho,L)$-list-decodability. We prove for all large $L$: $$h_q(\rho)(1 + 1/L) - q^{-\Omega_{q,\rho}(L)} \le V(q,L,\rho) \le h_q(\rho)(1 + 1/L).$$ The upper bound rests on a new entropy inequality for sparse random vectors under pairwise non-proportional linear constraints, proved with the Erdős-Rado sunflower lemma. The lower bound is an exact analysis of the distribution introduced by Guruswami, Li, Mosheiff, Resch, Silas and Wootters.

Sparse Bayesian learning is widely used for sparse linear inverse problems, yet its large-system stationary behavior remains poorly understood because all variance hyperparameters are estimated from the same data. We study classical sparse Bayesian learning, formulated as evidence maximization (type-II maximum likelihood), for underdetermined linear models with sensing matrices having independent and identically distributed Gaussian entries, Gaussian measurement noise, and an unknown deterministic signal sequence. Hyperparameter reoptimization induces a nonvanishing feedback term: a typical coordinate obeys a reoptimization-corrected scalar Gaussian law whose signal coefficient is governed by the normalized adaptive response rather than the frozen resolvent trace. A one-coordinate leave-one-out construction gives an exact conditional Gaussian law, which is transferred to a selected full stationary branch without assuming asymptotic closeness of the reduced and full stationary vectors. Combining this law with the Karush–Kuhn–Tucker conditions of the evidence objective yields a generally set-valued scalar relation and three branchwise large-system consistency relations. If the model noise variance is jointly estimated by evidence maximization, interior joint stationarity yields an exact finite-dimensional equality between the normalized residual energy and normalized resolvent trace. When the limiting signal law has nonzero mass at zero, this identity further yields a parameter-free asymptotic chi-square null law. Under an additional differentiability condition on the selected scalar branch, the large-system characterization also gives a closed relation for the reconstruction error of the posterior mean. The analysis is stationary-point based and permits multiple stationary branches.

Sequential sounding in UAV fluid-antenna systems (FASs) provides additional spatial information but delays transmission, causing earlier channel observations to age. This paper addresses the resulting information–freshness tradeoff by jointly determining where to probe and when to stop under blockwise hardware constraints. A dynamic Karhunen–Loève estimator aligns asynchronous measurements with the transmission state, covariance information gain selects feasible probe locations, and an age-discount identity with a local one-more-slot condition characterizes the covariance-level balance between information and freshness. Paired simulations show that temporal alignment recovers most of the lower-tail reliability lost by static stacking, covariance-aware probing ranks highest numerically among the evaluated policies, and optimized one-slot sounding becomes statistically competitive with two-slot alternatives at the highest tested mobility. Within the evaluated schedule family, increasing mobility shifts the competitive operating region toward shorter scans, supporting joint probe-placement and sounding-duration design.

In this paper, we study the performance of algebraic geometry (AG) codes against adversarial insertion-deletion (insdel) errors. The half-Singleton bound states that an $[n,k]_q$ linear code can correct at most $n-2k+1$ insdel errors. It was recently proven that random Reed-Solomon codes approach this bound. However, these constructions require the field size $q$ to grow linearly with the code length $n$. We overcome this barrier by extending the probabilistic analysis of general linear insdel codes to AG codes. We demonstrate that curves with many rational points allow for nearly optimal codes over significantly smaller alphabets. We prove the following main asymptotic results: (1) For general smooth complete curves of fixed genus, random AG codes are nearly optimal, that is, they can correct $(1-\varepsilon)n-2k$ insdel errors with high probability over linear-sized fields ($q=\Theta(n)$). (2) By utilizing Hermitian curves, we achieve this optimality over sublinear fields of size $q=\Theta(n^{2/3})$, breaking the linear field size barrier. (3) Using asymptotically optimal García-Stichtenoth towers, we prove the existence of random AG codes that approach the half-Singleton bound with high probability over fields of size $q=2^{O_R(1/\varepsilon^2)}$, independent of $n$.

We study the Tsallis-to-Kullback–Leibler (KL) limit for entropy-regularized optimal transport with nonnegative bounded continuous costs. Fixing the regularization parameter $\varepsilon > 0$, we first derive an exact variational reformulation of Tsallis-regularized optimal transport in terms of the Tsallis information projection onto the set of couplings. The formula isolates an explicit correction term and thereby explains why, unlike in the KL case, the regularized transport problem and the corresponding information projection problem do not coincide exactly. We also establish existence and uniqueness for the Tsallis information projection. We then prove, with respect to the narrow topology, the $\Gamma$-convergence of the Tsallis-regularized functionals to the KL-regularized functional as $q\downarrow1$, together with narrow convergence of their unique minimizers. Finally, we obtain explicit error estimates of order $O(q-1)$ for both the regularized optimal transport values and the associated information projection values. These results quantify the passage from Tsallis regularization to the classical KL setting and clarify the relation between entropic regularization and information projection for $1 < q \leq 2$.

This paper introduces LQ8, an open-source weak-signal digital mode for amateur radio that completes structured two-way contacts in 4 transmissions (60 s), achieving a 1.50x speedup over canonical 6-transmission exchanges (90 s) and 1.25x over 5-transmission RR73 exchanges (75 s) while preserving complete bidirectional exchange of Maidenhead grid locators, signal reports, and mutual acknowledgments. By replacing fixed-width message-type headers with variable-length prefix codes matched to physical-layer bit budgets, LQ8 packs the answering station's grid locator and measured signal report into a single 77-bit reply. In multi-station pileup operations, LQ8 confirms up to two answering stations simultaneously within a single-carrier 50.0 Hz transmission with a 0.0 dB RF power-splitting penalty, achieving a peak rate of 240 QSOs/h in continuous pileup (4x over single-carrier FT8; 480 QSOs/h dual-carrier) while retaining -21.0 dB SNR sensitivity. The protocol family also defines three extended profiles (LQ16, LQ4, and LQ2) tailored for extreme sensitivity, VHF/UHF contesting, and fast-burst channels.

Cooperative MSR codes are a kind of storage codes which enable optimal-bandwidth repair of any $h\geq2$ node erasures in a cooperative way, while retaining the minimum storage as an $[n,k]$ MDS code. Each code coordinate (node) is assumed to store an array of $\ell$ symbols, where $\ell$ is termed as sub-packetization. To address the disk IO (input/output) capability, a cooperative MSR code is said to have optimal-access property, if during node repair, the amount of data accessed at each helper node meets a lower bound on this quantity. In this paper, we focus on reducing the sub-packetization level of optimal-access cooperative MSR codes. We propose new constructions of optimal-access cooperative MSR codes through two methods. At first, we propose a direct explicit construction by designing its parity-check matrix. Such parity-check matrix is built by repeatedly employing two crucial parity-check matrices as building blocks. Secondly, we propose a generic transformation framework. Starting from an arbitrary $[n+d-k,d]$ MDS scalar code, one can derive a final cooperative MSR code by systematically applying two basic transformations. Both approaches yield $(n,k,\ell=\delta^m)$ optimal-access cooperative MSR codes with $\delta=d-k+h$ and $m=\binom{n}{h}-\lfloor\frac{n}{\delta}\rfloor(\binom{\delta}{h}-1)$. Compared with the state of the art (with $\ell=\delta^{\binom{n}{h}}$), the derived codes can reduce the sub-packetization $\ell$ by a fraction of $1/\delta^{\lfloor\frac{n}{\delta}\rfloor(\binom{\delta}{h}-1)}$, where $\delta=d-k+h$. Moreover, we also show that some previous code structures of optimal-access cooperative MSR codes and optimal-access MSR codes with $h=1$ are included as special cases of our transformation construction. At last, we note that all of the constructions are built over a finite field of linear size $\geq n+d-k$.

Large-scale multiple-input multiple-output (MIMO) detection is fundamental to modern wireless networks but constrained by performance-complexity trade-offs. Existing detectors, whether classical or learning-based, often fall short in either scalability or generalizability across heterogeneous scenarios. To overcome these limitations, we introduce a wireless-native graph foundation model (GFM) tailored for large-scale MIMO detection. The proposed GFM employs a physics-informed hybrid architecture, integrating the local correlation extraction of message passing neural networks with the global attention of graph Transformers, encoding the physical interference patterns from the expectation propagation algorithm. Via extensive pre-training, this synergy enables the learning of a general-purpose detection mapping scalable across antenna dimensions and channel conditions. For rapid downstream deployment, parameter-efficient fine-tuning is leveraged to adapt the GFM to specific non-ideal system regimes with minimal overhead. To enhance inference efficiency, a mixture-of-experts mechanism is embedded at downstream deployment to dynamically activate only the necessary sub-modules. Evaluations show that the proposed GFM consistently outperforms classical detectors and advanced data-driven baselines in accuracy, configuration generality, and cross-scenario transferability across various challenging zero-shot and few-shot conditions.

We present a machine-checked Lean~4 formalization of Dong and Yang's classification of optimal finite-length $(n,4)$ binary block codes for binary symmetric channels. The formalization was developed mainly by feeding the paper's proofs to an AI tool. To establish correctness, the authors verified the main theorem statements in Lean and the accepted axioms. This note discusses the corrections and simplifications made to the AI-generated formalization, and records discrepancies found in the paper during the formalization. The Lean code is available at https://github.com/shhyang/n4code_lean.

A communication system must choose error protection and decoding effort as channel conditions change. A Bayesian bandit encoder (BBE) uses receiver feedback to learn which transmission configuration to select. We study a receiver that decodes by guessing error patterns, using Guessing Random Additive Noise Decoding (GRAND). We extend BBE's selection component to 1,008 code and decoder configurations by learning shared performance patterns offline and updating their weights online. Decoder noise models remain fixed. On a six-configuration training-selected shortlist, sharing reduces accumulated utility loss by 33.5% relative to independent learning. A fixed training-selected configuration matches the shared learner that searches the full catalog. After channel changes, the pruned shared learner first meets a near-optimal selection criterion in 88.5% of events by 2,000 packets, compared with 54.2% for pruned independent learning with the same discounting. The results support combining sharing and pruning for configuration selection, although packet losses remain high for the tested codes under severe noise.

The $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-additive codes are subgroups of $\mathbb{Z}_2^{\alpha_1}\times\mathbb{Z}_4^{\alpha_2}\times\mathbb{Z}_8^{\alpha_3}$. A $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-linear Hadamard code is a Hadamard code which is the Gray map image of such a code. A recursive construction of $\mathbb{Z}_2\mathbb{Z}_4\mathbb{Z}_8$-additive Hadamard codes $\mathcal H^{t_1,t_2,t_3}$, with all $\alpha_i\neq0$, $t_1\geq1$, $t_2\geq0$, and $t_3\geq1$, is known, as are the linearity and kernel of the corresponding codes $H^{t_1,t_2,t_3}$ of length $2^t$. Their rank, however, was not known in closed form. In this paper, we determine $rank(H^{t_1,t_2,t_3})$ for every admissible triple and obtain an explicit closed formula. The proof computes the dimension of the space spanned by the binary coordinate functions of the code, viewed as Boolean functions of the binary digits of the message. We then use the rank formula, together with the known kernel dimension, to classify the family as far as these two invariants allow. The only pairs of distinct types of the same length sharing both invariants are $\bigl(H^{1,2,t-6},H^{2,0,t-5}\bigr)$ for $t\geq7$ and $\bigl(H^{2,2,t-9},H^{3,0,t-8}\bigr)$ for $t\geq10$. Consequently, the number of distinct pairs $(r,k)$ among the codes of length $2^t$ is $\lfloor(t^2+6)/12\rfloor$ for $3\leq t\leq6$, $\lfloor(t^2+6)/12\rfloor-1$ for $7\leq t\leq9$, and $\lfloor(t^2+6)/12\rfloor-2$ for $t\geq10$. Thus, rank and kernel dimension classify the family completely if and only if $3\leq t\leq6$. We also determine all coincidences with the $\mathbb{Z}_4$-, $\mathbb{Z}_2\mathbb{Z}_4$-, and $\mathbb{Z}_8$-linear Hadamard codes of the same length: there is exactly one infinite family with the first two, namely $H^{2,1,t-7}$ and $H^{5,t-9}$ for $t\geq10$, and exactly five families with the $\mathbb{Z}_8$-linear codes.

We introduce LatentGamma, a differentiable operator on the unit cube $[0,1]^M$ designed as a smooth surrogate of Tarski's immediate consequence operator $\TP$ associated with a definite Horn program $P$ on $M$ atoms. The operator is built as a five-stage composition combining sigmoidal gating, softmax routing, and a residual update that enforces monotonicity by construction. We establish four theoretical results. First, the iterated sequence is coordinate-wise non-decreasing and bounded by $\ind$, hence converges to a fixed point of LatentGamma; the operator itself is lattice-monotone on $[0,1]^M$. Second, our constructive expressivity theorem shows that for every definite Horn program $P$ there exists a closed-form parameter assignment $\theta^*(P)$ and an explicit time bound $T_{\max}(P)$ such that the iterated sequence exactly reproduces $\TPinf(F_0)$ for every initial fact set $F_0$ throughout the window $[D(P, F_0), T_{\max}(P)]$, where $D(P, F_0) \leq M$ is the derivation depth. The window $T_{\max}$ is large in practice ($\geq 10^5$ for sparse programs) and reflects the finite-time nature of computation by smooth sigmoidal gates. Third, the oracle is robust to Gaussian noise on its body and head logits, with explicit non-asymptotic bounds. Fourth, we prove a matching information-theoretic lower bound on the parameter count. We provide a complete numerical validation on programs ranging from $M = 33$ to $M = 504$ atoms: oracle accuracy reaches $1.0000$ on $2000$ test cases with zero false-positive and false-negative rates, and the empirical noise tolerance $\sigma_{\max}$ scales precisely as the union bound $RM \cdot \Phi(-10/\sigma_\eta)$ predicts.

In this paper, we develop and analyze techniques for recovering a linear image $Bx$ of an unknown signal $x$ from indirect noisy observation $\omega=Ax+\xi$. It is a priori known that $x\in \cX$, a given convex compact set, and that $x$ is $s$-sparse—has at most $s$ nonvanishing entries. The proposed estimates belong to a large family of recovery routines by $\ell_1$-minimization. However, unlike the classical result describing performance of such estimates, we do not make any special (and hard to check) assumptions about the sensing matrix $A$ such as nullspace or Restricted Isometry condition and the like. As a consequence, parameters of the estimates and the upper bounds on their risks are not available in a closed analytic form, but are delivered instead by efficient computation as solutions to explicit convex optimization problems.

We study the problem of low-rank matrix recovery from linear measurements via the global nonconvex landscape of a low-rank factored formulation of the matrix LASSO (nuclear-norm–regularized least-squares). If the landscape is benign, that is, has no bad local optima, then practical and scalable algorithms can compute good statistical estimates. Previous state-of-the-art landscape guarantees have typically assumed that the linear measurement operator has the restricted isometry property, that is, the operator is approximately an isometry over all low-rank matrices. This is an unrealistic assumption for many applications; in particular, when the individual measurement matrices are themselves low-rank, we typically have poor upper isometry constants. To overcome this, we establish new guarantees of a benign landscape under a weaker isometry condition: rather than requiring upper isometry over all low-rank matrices, we only require it over the linear low-rank tangent space to the low-rank ground truth matrix. To illustrate the utility of this result, we apply it to the problem of matrix recovery from random rank-one linear measurements; via high-probability concentration bounds on the random measurement operator, we prove a novel landscape guarantee with statistically near-optimal sample complexity and recovery error.

Finite training reduces the output signal-to-interference-plus-noise ratio (SINR) of an adaptive beamformer, and a natural question is how much of this loss is unavoidable. This paper determines this question, providing a beamforming counterpart of the Cramér–Rao bound in spectral estimation. An exact identity expresses the SINR loss as a bounded function of the error in the clairvoyant minimum-variance distortionless-response (MVDR) weight. It yields a local asymptotic minimax lower bound over all measurable data-dependent beamforming rules, including biased and irregular rules. The first-order coefficient is $\tr(\Mb\Jb_{\rm eff}^{-1})$, where $\Jb_{\rm eff}$ describes the information in the training data and $\Mb$ measures the sensitivity of the output SINR. Matching constructions determine this coefficient in two complex-Gaussian models. For an $N$-sensor uniform linear array with $K$ distinct point interferers and $2K+1\le N$, a data-driven split one-step beamformer attains the coefficient $C_\theta\le K$ at every interior scene of a fixed compact regular parameter set. For unrestricted covariance matrices, sample matrix inversion (SMI) attains the coefficient $N-1$ through the classical Reed–Mallett–Brennan law. The difference quantifies the first-order value of finite-source structure. Geometric formulas and numerical results describe the dependence on interference power and array geometry, and the finite-sample departure near a weak-source boundary.

We present Cadence, an error-bounded lossy compressor for numeric time series pairing a 330M-parameter time-series foundation model (Google TimesFM-3) with an adaptive arithmetic coder, guaranteeing $|\hat{x}_t-x_t|\le\tau$ on every sample. One negative result constrains the design space: for lossless coding a foundation model is worth nothing, because bits saved are logarithmic in predictor accuracy, $\Delta b=\log_2(\mathrm{MAE_{old}}/\mathrm{MAE_{new}})$. So the $1.51\times$ advantage TimesFM-3 holds over a 32-tap linear predictor buys 0.60 bits of 20.28, a median gain of +0.03%. Error-bounded coding escapes this at one point: once a forecast lands inside the band the residual index is zero and the sample nearly free. Cadence contributes: (1) an adaptive range coder with context-modelled binarization, beating xz/zstd on real indices by 9.7% (15/15) and reversing a finding from a general-purpose back end; (2) a determinism result – predictions are not bit-identical across batch sizes, and no PyTorch configuration repairs this, forcing group size and execution device into the container format; and (3) domain localization on corpora postdating any plausible training cutoff. On 49 EIA-930 balancing-authority demand series (2026) Cadence gains 13.3% over the best of six classical predictors, and 28.3% on 50 MTA ridership series (2026): 21.4% median over 297 series-tolerance pairs, winning all 297. Against downsampling, what time-series databases deploy for retention, its guaranteed worst-case error is $28$–$56\times$ tighter at equal size. End-to-end, once the context bootstrap is paid for, gains run from 6.8% at six months of hourly data to 15.1% asymptotically. Attempting to falsify the domain claim on SDRBench, theory predicts failure and delivers: -0.8% median, 0 of 27 pairs gaining. Three further negative results and eight retracted claims are reported in full.

For any permutation of a nontrivial finite abelian group, the differential uniformity is at least two; permutations attaining this bound are called almost perfect nonlinear (APN). We construct three infinite classes of APN permutations on the cyclic group $\mathbb{Z}_n$ using Singer cycles, binomials inducing projective permutations, and completed reciprocals combined with parity and quadratic characters. The respective domain orders are $q+1$ for prime powers $q>2$, $(3^d-1)/2$ for integers $d\ge2$, and $2p$ for primes $p>5$ with $p\equiv5\pmod6$. Each class contains an infinite subclass of composite orders outside the standard forms $r-1$, $r-2$, $r-3$, and $r-4$, where $r$ is a prime power. These forms arise in the Welch–Costas, Panario–Sakzad–Stevens–Wang, and Golomb constructions. To the best of our knowledge, these are the first infinite APN constructions on $\mathbb{Z}_n$ reported since 2011 that yield infinitely many composite orders outside these standard forms.

We give a unified hidden-derivative framework for list decoding and mutual correlated agreement of ordinary Reed–Solomon codes over prime fields, on arbitrary prescribed evaluation sets. For every fixed slack $\gamma>0$, every sufficiently large block length $n$, every prime $q\ge n$, and every dimension $1\le k\le(1-\gamma)n$, a deterministic algorithm finds all codewords within relative distance $1-k/n-\gamma$ in $q^{O_\gamma(1)}$ time. The final list has size $n^{O_\gamma(1)}$, independently of $q$. Both statements extend to bounded-input-list recovery, with constants depending additionally on the input-list bound. For every fixed curve degree $\ell$, at most $n^{O_{\gamma,\ell}(1)}$ parameters on a curve $f_0+zf_1+\cdots+z^\ell f_\ell$ admit a nearby codeword whose exact agreement support is not a maximal jointly explained support of the coefficient words. For lines this gives MCA error $n^{O_\gamma(1)}/q$, with no proximity loss. The interpolation stage reparameterizes and optimizes the hidden-derivative construction of Brakensiek, Chen, Putterman, Zhang, and Zheng; differential root enumeration uses Kopparty's algorithm. We then prove that a specialization-safe differential equation has a cover by constant-dimensional varieties of polynomial cumulative degree, outside polynomially many parameter values. Intersecting these varieties with equations from the full agreement support yields both the field-size-independent list bound and exact-support MCA.

Belief propagation with quantum messages (BPQM) is a quantum algorithm that decodes classical codes transmitted over classical–quantum channels. It realizes optimal decoding on tree factor graphs over pure-state classical-quantum channels. However, this tree-based analysis does not ensure vanishing block-error probability for LDPC Tanner graphs with cycles. In this work, we construct a two-stage BPQM decoder for random $q$-ary LDPC codes over symmetric $q$-ary pure-state channels, where $q$ is prime, and prove that its ensemble-average block-error probability vanishes as the blocklength $N$ tends to infinity. For regular ensembles with $d_v\geq3$, fidelity bounds yield double-exponential decay of the average symbol-error probability throughout the BPQM success region. We apply depth-$\ell$ BPQM to coordinates with tree neighbourhoods and treat the remaining coordinates as erasures. With a suitable $\ell=\Theta(\log\log N)$, a noncommutative union bound controls the BPQM decoding errors, while the minimum-distance property guarantees erasure recovery. We also extend the analysis to finite-support irregular ensembles. These results are relevant to quantum algorithms based on Regev's reduction, where coherent decoding uncomputes a codeword register. Decoded quantum interferometry (DQI) uses a closely related Fourier-based framework that reduces sparse max-LINSAT optimization problems to LDPC decoding problems on pure-state channels. Our results justify the use of BPQM in the decoding step of DQI and of coding-theoretic algorithms based on Regev's reduction whenever the code is drawn from one of the random LDPC ensembles analyzed here and the induced memoryless symmetric pure-state channel lies in the BPQM success region. Curiously, our numerical results indicate that DQI+BPQM achieves a satisfaction ratio that closely matches that of simulated annealing.

We consider a fully connected gossip network of $n$ nodes that track a binary continuous-time Markov source through a strategic sender transmitting updates under a communication budget at a rate that depends on the source state. The receivers exchange packets through gossip and decide whether to follow the sender. We model this interaction as a Stackelberg game and analyze it through a stochastic hybrid systems (SHS) framework. We prove that the sender's budget constraint binds at every interior optimum, reducing its problem to a one-dimensional search on the budget line. When the sender pushes its preferred state at the higher rate, the receivers gossip at the highest available rate. Gossip has no direction of its own and works against the asymmetry in the sender's policy rather than reinforcing it. We prove that an optimistic Stackelberg equilibrium exists, and that it is unique and explicitly characterized whenever a policy on the strategic half of that line is feasible at the gossip cap. Monte Carlo simulations agree with the analytical recursion.

Families of sequences with low mutual aperiodic crosscorrelation assist the design of systems for multi-user asynchronous communications and multiple-input multiple-output radar. The crosscorrelation demerit factor of a pair of sequences is the sum of the squared magnitudes of their crosscorrelation values at every shift when the sequences are normalized to unit Euclidean norm, and the merit factor is the reciprocal of the demerit factor. For each positive integer $\ell$, we endow the $2^{2 \ell}$ pairs of binary sequences of length $\ell$ with uniform probability measure and study the distribution of their crosscorrelation demerit factors. Sarwate showed that the mean value is always $1$ regardless of length $\ell$. We develop a method for finding an exact formula for the $p$th central moment (for any positive integer $p$) as a function of $\ell$. Formulae for the variance and third central moment ($p=2$ and $3$) are then obtained by hand calculations, while the fourth through sixth central moments are obtained by computer-assisted calculations. Our theory also shows that all the central moments must be strictly positive for $p\geq 2$ and $\ell \geq 3$.

We give a necessary and sufficient condition for the existence of power-one sequential tests in an i.i.d. composite testing problem. A level-\(\alpha\) test with power one against every alternative exists if and only if the alternatives are separated from the null by a countable family of finite-block events. We provide other equivalent conditions using randomized fixed-sample tests, bounded finite-block scores, e-processes, reduced-filtration test supermartingales, and a countable cover whose finite-block weak-$*$ closed convex hulls are positively separated in total variation. As a bonus, the constructive proof yields tests have pointwise expected sample size \(O_Q(\log(1/\alpha))\). Exactly the same conditions also characterize i.i.d.\ change detectability under optional-horizon average-run-length control: for every \(\eta>0\), they are equivalent to an alarm family \((T_\gamma)_{\gamma\ge1}\) satisfying \(\Prob_{P^\infty}(T_\gamma\le\sigma)\le \E_{P^\infty}\sigma/\gamma\) for every null law and every stopping time \(\sigma\). In fact, when these conditions hold, we can construct a single e-detector such that every null-law average run length lies between \(\gamma\) and \((1+\eta)\gamma+1\), and having robust Lorden delay \(O_Q(\log\gamma)\).

We study state tomography when each measurement acts on at most $k$ fresh copies and no quantum memory is retained between blocks. We prove a lower bound matching the upper bound in [arXiv:2510.07788]. Thus the copy complexity of estimating an arbitrary $d$-dimensional state to trace distance $\epsilon$ is, up to absolute constant factors, $\max\{d^3/(\sqrt{k}\epsilon^2),d^2/\epsilon^2\}$ for every $k$ and all sufficiently small $\epsilon$. This removes the earlier restriction that $k$ be small as a function of the accuracy. The lower bound applies to arbitrary measurements within each block and adaptive choices between blocks. The lower bound already applies in a small neighborhood of any state whose smallest eigenvalue is of order $1/d$, even when the center is known. The main ingredient is a uniform Fisher information bound for one measurement block that depends only on the smallest eigenvalue of the state. The proof avoids the perturbative expansion responsible for the restriction in [arXiv:2402.16353]. Fano's inequality for metric balls and a log-Sobolev comparison between mutual and Fisher information then reduce the adaptive protocol to this block bound [arXiv:1607.00550, arXiv:1902.08582].

We consider the problem of minimizing error in quantized matrix multiplication $C=AB$. Scalar quantization of the factors introduces rounding errors whose scale depends on the maximum absolute entries – the ranges – of their rows and columns. These ranges determine the quantization grid steps. To reduce the error, we optimize over product-preserving transformations that alter the factor ranges and grid steps without changing $C$. Specifically, we seek the smallest leading expected squared error over invertible inner changes of basis and orthogonal outer rotations. Under independent, zero-mean subtractive dither noise on an unbounded lattice, we prove the output-only bound $E_{\rm lead} \ge (c_A+c_B)/K \Vert AB\Vert_*^2$, where $K$ is the inner dimension, $c_A$ and $c_B$ are normalized noise variances, and $\Vert AB\Vert_*$ is the nuclear norm. The bound is tight: an SVD-aligned Hadamard construction attains the infimum whenever a Hadamard matrix of order $K$ exists, including every power of two, while an SVD-aligned DCT construction is within a factor of two for every $K$. Without outer rotations, Gram-matrix balancing minimizes factorization energy, and finite-set flattening achieves the bound within $C\log(K(m+n))$. For power-of-two $K$, conditional expectations deterministically select the Hadamard signs in $O((m+n)K^2)$ exact-real operations. Synthetic experiments verify both constructions and illustrate the tradeoff between regularization and conditioning. These results characterize the full-gauge optimum and quantify the cost of preserving row and column indices.

Estimating a low-dimensional subspace shared across noisy data matrices is a fundamental problem in multi-view matrix estimation. We study this problem under the two-view JIVE model, where each data matrix contains shared and view-specific low-rank components. We demonstrate that standard plug-in subspace intersection, including AJIVE, suffers from a second-order bias caused by direction-dependent leakage of the empirical singular vectors. We propose bias-corrected subspace intersection (BCSI), which removes this bias before estimating the shared subspace. We establish finite-sample risk bounds for BCSI that accommodate unequal view dimensions, signal strengths, and view-specific ranks and require no condition-number assumptions on the signal matrices. When the shared and view-specific ranks are comparable, these bounds match our minimax lower bounds up to universal constants. The resulting minimax rate contains a new second-order term, arising from quadratic leakage perturbations relative to the shrinking spectral gap when the view-specific subspaces are nearly aligned. This term is absent from previous JIVE minimax lower bounds. Numerical experiments demonstrate the advantage of BCSI over AJIVE when the leakage bias is pronounced. Along the way, we establish a nonasymptotic concentration result for the bias-corrected leakage Gram matrix of a rectangular spiked matrix, which may be of independent interest.

Let $C$ be an $[n,k]_q$ maximum distance separable (MDS) code with $4\le k\le q-3$, and suppose that it has a $2$-transitive permutation automorphism group. In this paper we show that $n\le q+1$, so the MDS conjecture holds for this class of codes.