Papers

NVFP4 is an attractive datatype for large language model (LLM) inference, offering compact storage and native tensor-core acceleration. However, preserving accuracy using NVFP4 requires careful quantization. In this work we develop a novel quantization scheme called Optimized Smoothing and Scaling for NVFP4 (OSFP4). For each linear projection it uses a diagonal smoothing matrix whose entries are optimized to minimize the squared matrix-product quantization error under NVFP4, taking into account the rounding procedure that is used (either round-to-nearest, or GPTQ-style successive interference cancellation). This requires performing joint optimization on the smoothing entries as well as the block scales, which is facilitated by analyzing a multiplicative-dither FP4 quantizer instead of the fixed deterministic one. Experiments show that OSFP4 achieves the highest average accuracy among the evaluated competitors in the corresponding quantization settings, while retaining approximately 94-97% of vendor NVFP4 prefill throughput on the measured workloads. Our code is available in https://github.com/neriahbd/OSFP4

This work studies non-linear function computation broadcast (NFCB), in which a sender with access to $N$ datasets $(X_1,\dots,X_N)$ broadcasts a common message to $K$ users, each possessing side information and requesting a function of the datasets. The goal is to minimize the rate required for asymptotically lossless recovery of all demands. We introduce a broadcast graph that jointly captures the source distribution, side information, and demanded functions. Using Körner's characteristic-graph framework, we develop an achievable scheme for arbitrary $K$, general source distributions, and general finite-field demands, including linear, non-separable, and non-linear functions, without restricting the encoding or decoding operations to be linear. We also present a side-information-assisted independent-set scheme and characterize the optimal graph-based achievable rate for compatible functions. For the converse, we derive a multi-letter response-profile bound that strengthens a basic side-information converse, zero-error and asymptotically lossless clique-entropy bounds based on the operational block broadcast graph, and a genie-aided lower bound. For binary NFCB with $N=K$ and side information $X_i$ at user $i$, we characterize the optimal rate in several special cases and bound the worst-case and average additive gaps between the proposed achievable rate and the genie-aided converse for $K=3$ and $K=4$. Finally, three-user examples with Boolean and linear demands illustrate the proposed bounds and show that non-linear encoding can strictly outperform the best scalar and vector linear schemes.

We study cyclic triorthogonal codes in prime dimension $p$, on which a transversal third-level diagonal gate acts as a logical non-Clifford gate. For odd $p$, we use a definition of triorthogonality that does not require self-orthogonality. For cyclic codes of length coprime to $p$, triorthogonality reduces to a sumset condition on the spectral support, which makes exhaustive search feasible: for two natural constructions, we enumerate all maximal codes of this kind for $p=3$ up to length $121$ and $p=5,7$ up to length $96$. For qubits, we prove that a cyclic code of odd length is triply even if and only if it is classically triorthogonal, giving a complete description of triply-even cyclic codes, and we determine all such codes up to length $763$. For qudits, we find codes such as $[[19,1,3]]_3$ and $[[7,1,3]]_7$, which improve on the shortest Reed-Muller and Reed-Solomon codes in both overhead exponent and distillation threshold. The latter is the first member of an infinite family of $[[p,1,2\lfloor p/6\rfloor+1]]_p$ codes.

We consider a generalization of the Gaussian information bottleneck problem to jointly stable variables $X$ and $Y$. Specifically, for $X = Y + A$, where $A$ is stable and independent of $Y$, we find optimal stochastic linear encoders of the form $T = kX + N$, $N$ being stable and independent of $X$. We characterize the linear stable information bottleneck in closed-form and its critical value. Furthermore, we show that, except for the Gaussian case, such stochastic linear encoders are strictly suboptimal, however asymptotically optimal at large compression rate. Our linear solution recovers the Gaussian information bottleneck for jointly Gaussian variables.

We study sparse locally private discrete mechanisms generated by a nonnegative kernel and an input-dependent admissible output support. The support set is intentionally small relative to the ambient alphabet and acts as a mechanism-design parameter. This formulation covers metric-ball supports, sparse exponential mechanisms, sparse staircase mechanisms, sparse randomized response, sparse additive kernels such as Skellam perturbations, and Poisson-binomial-inspired bounded-support channels. We give a general exact characterization of pure and approximate local differential privacy for this sparse-kernel class. Pure local differential privacy forces all supports to coincide, so genuinely input-dependent sparse supports are incompatible with pure privacy. In the approximate regime, the privacy defect decomposes exactly into support leakage and overlap excess loss. We instantiate the formula for several discrete mechanism families. For sparse staircase mechanisms, a shell-ratio condition eliminates overlap excess loss. For graph-metric supports, overlap of metric balls is necessary for nontrivial privacy. For sparse randomized response, the support-leakage term has a closed form in terms of support mismatch. For generic radius-truncated additive kernels and, in particular, sparse Skellam mechanisms, we obtain exact finite-support formulas in terms of the Skellam CDF and an exact Bessel-ratio overlap condition. Numerical evaluations illustrate how support radius and kernel shape separately affect support leakage and overlap excess loss.

The vulnerability and unavailability of global navigation satellite system (GNSS) signals in dense urban environments have motivated the use of low earth orbit (LEO) signals of opportunity (SoOP) for positioning, navigation, and timing (PNT). However, multipath and non-ideal noise can significantly degrade delay–Doppler estimation and, consequently, navigation accuracy. This paper proposes a hybrid generalized likelihood ratio test (GLRT) and off-grid sparse Bayesian learning (SBL) framework for LEO-SoOP navigation under multipath and non-Gaussian, temporally correlated noise. First, a GLRT-based framework is developed, demonstrating reliable detection under ideal Gaussian noise but degraded estimation under heavy-tailed or colored noise and unresolved multipath. Next, an off-grid SBL framework is introduced for high-resolution separation and estimation of line-of-sight (LOS) delay–Doppler parameters. The estimated LOS parameters are subsequently tracked and incorporated into an extended Kalman filter (EKF) to obtain the navigation solution. Simulation results demonstrate that, in urban environments, the proposed method reduces delay RMSE by up to 77% and position RMSE by 88.5% compared with GLRT-based estimation. These results demonstrate the potential of the proposed framework for robust and accurate LEO-SoOP navigation.

An effective Cold-Atom Rydberg Array (CoRA) architecture is investigated, which addresses the fundamental thermal noise limit in classical electromagnetics and intrinsic Doppler broadening as well as photon shot noise in conventional hot-vapor cell-based atomic receivers. However, translating the CoRA-based quantum electrometers into practical wireless communication receivers is bottlenecked by both the macroscopic readout dead-times and nonlinear binomial population counts rather than the additive-Gaussian baseband samples in conventional receivers. To address these critical challenges and facilitate the practicality of the CoRA, in this paper, a subarray scheduling-based spatiotemporal multiplexing (STM) framework is first proposed for gap-free symbol interrogation within an admitted packet. Additionally, a signal detection scheme based on a joint binomial particle smoother (JBPS) is proposed for burst-wise state and data inference. Furthermore, the weak-signal quantum-projection-noise (QPN) limit and the state-averaged finite-alphabet rate are derived for CoRA-assisted wireless communications. Numerical results demonstrate that: 1) The proposed STM-based CoRA scheme resolves the macroscopic temporal bottleneck for continuous signal sampling; 2) The proposed JBPS approach effectively mitigates the nonlinear noise amplification to achieve a lower bit error rate; and 3) Performance analysis reveals a fundamental sensitivity-sustainability tradeoff that increasing the number of atoms effectively suppresses the QPN, but simultaneously reduces the sustainable packet repetition rate.

This paper studies continuous transmissive reconfigurable intelligent surface (CT-RIS)-enabled multiuser downlink communications, where passive beamforming is characterized by a phase function defined over the continuous aperture. We employ a distance-dependent spherical-wave model for the base station (BS)-to-CT-RIS link and introduce a finite-path model based on field-response vectors for the CT-RIS-to-user links. The resulting weighted sum rate maximization problem jointly optimizes the finite-dimensional BS precoders and the infinite-dimensional CT-RIS phase function, giving rise to a mixed finite- and infinite-dimensional non-convex optimization problem. To address this problem, we develop an alternating optimization algorithm that combines a closed-form BS precoder update with a functional phase update derived using the calculus of variations and minorization-maximization. Numerical results demonstrate that the proposed CT-RIS consistently outperforms the considered benchmarks, with the performance gains attributed to spatially continuous phase control and a larger effective receiving area.

In previous work, we established sufficient conditions for recovering geometry and topology from non-random information, demonstrating reconstruction with the Arecibo message. Undeciphered historical records present a related problem: one-way communication without access to their makers' intentions or encoding conventions. Here we extend this framework to the Phaistos Disc, Andean khipu, Rongorongo, Indus inscriptions and the Voynich manuscript, using Egyptian layouts and Arecibo as controls. Algorithmic information dynamics (AID) guides structural perturbations, combining classical information measures, predictive coding, compression and algorithmic-probability-based estimates. Phaistos retains 0.714 bits of excess adjacent-sign mutual information after positional controls; its authentic segmentation lies within a broad information basin, and cross-face boundary prediction achieves AUCs of 0.76 and 0.86. Repetition explains its principal recurrence, while the tested spiral embeddings provide no evidence of additional cross-winding structure. Across several corpora, comparative transfer persists beyond exact shared local pairs. Khipu knot forms distinguish authentic attachments after controlling for degree, depth, fibre and twist (adjusted $p=0.009$); constrained assignment recovers 8.75% of concealed parents against 7.87% expected by chance. Row-alignment tests yield no comparable evidence after correction. Calibrated BDM recovers Arecibo's 23-column width (search-corrected $p=0.005$), while executable controls detect spatial dependence and eliminate it through interventions on the generator. These findings connect information-based structural reconstruction with interventional reasoning, distinguishing recoverable organisation from semantic decipherment.

DNA storage systems retrieve information by randomly sampling synthesized DNA strands, making the number of reads required for successful recovery a fundamental performance measure. This motivates the coverage depth problem: for given code parameters, determine a linear code that minimizes the expected number of randomly sampled columns required to span the entire information space. While MDS codes are known to be optimal whenever they exist, identifying optimal codes in parameter regimes where MDS codes do not exist remains largely open. In this work, we derive a general formula for the expectation in the coverage depth setting, and apply this result to establish the optimality of the $q$-ary simplex code for the parameters that allow its existence. Moreover, we show the optimality of the $q$-ary Hamming code by relating coverage depth to independent sets in the dual code and exploiting log-concavity properties of matroid basis-generating polynomials. We further analyze random linear codes, derive an exact expression for their expected coverage depth, and show that, in the constant-rate regime, their additive gap from the MDS benchmark remains bounded independently of the code length.

The goal of the partial information decomposition (PID) is to quantify the redundant and synergistic information that multiple sources provide about a target. PID has many applications in machine learning, neuroscience, and other fields, but defining and computing it for high-dimensional continuous systems remains challenging. Here, we define a PID for multivariate Gaussian systems based on the Blackwell order, which formalizes when one channel is more informative than another. We prove that Gaussian channels are optimal for extracting both redundant and union information, yielding an intuitive geometric interpretation and an efficient numerical algorithm for the PID. Our union information and synergy coincide with the well-known BROJA measures, and we derive closed-form expressions for both in the case of two sources. We also argue that Blackwell redundancy (which differs from BROJA) is the only existing redundancy measure that satisfies a set of natural desiderata. We demonstrate the scalability of our method on systems with up to a thousand dimensions or sources. Our approach is illustrated on an optimal control problem, where it identifies redundant and synergistic interactions between sensor and memory.

Missing covariates are frequently encountered in supervised learning problems, and classical methods for estimation using such data use carefully chosen imputation schemes for missing data, or likelihood approximations that lead to nonconvex $M$-estimation problems. These methods and their relatives are suitable for scenarios in which the covariate distribution is known, and more broadly, have enjoyed tremendous success in linear models. But even in basic nonlinear problems such as logistic regression in moderate dimensions, such methods can experience drastic failure modes when the covariate distribution is unknown. Motivated by the need for reliable alternatives, we consider the problem of parameter estimation in logistic regression with missing covariates. Crucially, we operate in the assumption-lean setting where the covariate distribution is unknown (but bounded). We design a stochastic approximation method that is based on $Z$-estimation with a novel monotone operator, and establish that our algorithm is computationally efficient and achieves provable signal recovery at parametric rates under the hypothesis that covariates are missing completely at random. Our theory sharply characterizes the $\ell_2^2$ risk of the estimator in terms of the missingness profile, accommodating heterogeneous observation probabilities. Importantly, it shows that our method always outperforms the de facto “complete-case” estimator that ignores observations with any missing data. Even in the setting with homogeneous missingness (in which each covariate is observed independently with probability $q$), our bounds exhibit intricate and nonstandard dependence on $q$ that can yield significant improvements over using only complete cases. We complement our upper bounds with new information-theoretic lower bounds that show that this intricate dependence on $q$ is fundamental in a minimax sense.

We investigate converse bounds on the average decoding error probability in finite-blocklength classical-quantum channel coding. We first present a lower bound for multiple quantum hypothesis testing in terms of pairwise trace distances and derive a corresponding fidelity bound. We then obtain a spectrum-based converse that depends only on the a priori probabilities and spectra of the states. We show that the converse bound remains tight for the quantum depolarizing channel under suitable conditions. For codes with product-state outputs, this converse takes an explicit form involving products of output-state eigenvalues. We apply it to binary codes over the quantum amplitude damping channel using the input states $\vert+\rangle$ and $\vert-\rangle$. For this setting, we also discuss a normal approximation to the spectrum-based converse in the large blocklength regime. In all numerical examples considered, the spectrum-based converse is tighter than the other converse bounds at low noise levels.

We study collective state preparation and channel encoding in fermionic systems under parity superselection and composition governed by the canonical anticommutation relations. For a two-mode Gaussian state $\tau$, we obtain the exact entanglement of formation, $E_{\mathrm F}^{\mathrm{phys}}(\tau^{\otimes m})=\lceil m/2\rceil\log2$ for every $m\geq1$. Two copies have the same formation value as one, violating additivity and strong superadditivity, while regularization halves the single-copy value. For an associated Gaussian channel, we determine the minimum output entropy and Holevo information at every blocklength and prove nonadditivity of both. Together, these results give exact answers to the fermionic counterparts of the four additivity questions associated with Shor and Hastings. One physical use carries no classical information, whereas two uses transmit one bit perfectly. The unassisted classical and zero-error classical capacities both equal one half bit per mode. A sharp finite-block bound gives a strong converse: the decoding success probability vanishes at every rate above capacity. These optimizations cover all physical pure-state decompositions and channel inputs, with Gaussian ensembles and classical codes attaining the optima. The formation and minimum output entropy formulas hold for every Rényi order $\alpha\in(0,\infty]$. We also determine the unassisted quantum and zero-error quantum capacities, both equal to one half logical qubit per mode, and prove a strong converse: entanglement fidelity vanishes at every rate above capacity. For a noisy Gaussian family, we determine the one- and two-copy formation values and prove strict nonadditivity at full rank. For $\tau$, Bell violation under local parity-preserving measurements first appears at three copies.

We study a variant of Schumacher compression. The task asks for the minimal memory cost for compressing many copies of a density matrix with known spectrum and unknown eigenbasis, without preserving its purification. For fixed dimension and distinct positive eigenvalues, we obtain the cost through its additive constant. Achievability uses a generalization of Werner's cloning map to $\mathrm{GL}(d,\mathbb C)$ irreducible representations, with finite trace-distance bounds controlled by highest-weight differences and row gaps. The matching converse follows from a quantitative form of Koashi–Imoto incompressibility for irreducible group orbits under a spectral-gap assumption. We also identify the relation between this quantum minimum description length and universal lossless coding overhead, and its connection to free entropy is explained in a companion letter. We provide a Lean certificate for our proofs.

We study the dimension defect of finitely many subspaces over an arbitrary field. We derive a symmetric, nonrecursive Grassmann-type formula for the dimension of their sum. The formula expresses the total dimension loss through intersections of a distinguished subspace with partial sums of the remaining subspaces, with coefficients determined by the number of subspaces involved. We also show that the formula admits a Shapley-value interpretation for the associated representable polymatroid. Grouping the correction terms by the number of participating subspaces yields a nonnegative dimension-defect profile. We prove that this profile is monotone and identify its successive gaps with the discrete curvatures of the average-rank profile. These gaps give exact remainders in two-sided defect bounds. Equality in either bound holds precisely when the images of the subspaces in the quotient by their common intersection form an internal direct sum. We also give an exact geometric decomposition of the Kinser slack into nonnegative quotient dimensions and characterize equality. Averaging these slacks over permutations and contractions recovers every defect curvature except the final one; additional representability constraints remain in the individual ordered slacks. Weighted and dual formulas accompany the expansion, and entropy analogues express the defect levels and curvatures as averages of mutual and conditional mutual information, respectively.

The no-cloning theorem is a cornerstone result in quantum mechanics that forbids copying of general quantum information. More quantitatively, even given $N$ copies of an unknown state, any channel producing an $(N+1)$-copy state incurs a nonzero trace-distance error on some inputs. Turning this around, one can ask about the sample complexity of approximate $N\rightarrow N+1$ cloning: for a desired small error $\epsilon$, what $N$ suffices? For arbitrary pure states on a Hilbert space $H$, the answer is $N\simeq \dim H/\epsilon$ - astronomically large for most $H$ of interest. What if the input is promised to lie in a structured family? We examine a range of families fundamental to many-body physics and quantum information: $n$-mode fermionic Gaussian and Slater states, $n$-mode bosonic Gaussian states, and qudit phase states. For fermions, we construct optimal cloning channels, reducing the complexity from exponential to polynomial in $n$. For bosonic Gaussian states, we construct an explicit cloner that certifies polynomial complexity, without any constraint on the energy of the state; this channel, however, is not optimal in general. The fermionic and bosonic results follow from a single representation-theoretic framework, which generalizes previous work by Werner and by Chiribella and Yang; it also yields the cloners' unitary implementation. Furthermore, we explain why for many families the cloning complexity is linear in the dimension of the family manifold, via a controlled saddle-point evaluation of the frame potential at high $N$. The same calculation accounts for the analogous scaling of tomography complexity. The above framework does not cover phase states; for these we give an independent construction of a channel with optimal cloning fidelity. Our work complements recent results on cloning stabilizer states.

Learning the Hamiltonian of a many-body system from its dynamics is a central task in quantum science, yet the algorithms with the strongest provable guarantees assume some level of quantum control–fast, arbitrary single-qubit gates interleaved with time evolution, and measurements in arbitrary bases–that is beyond the capabilities of near-term analog quantum simulators. Motivated by analog atom- and ion-based platforms, we study Hamiltonian learning under minimal access models. Uniform state preparation and measurements: We first consider the setting where in every experiment, one can rotate each qubit to the same state, perform short-time evolution, and measure every qubit in the same basis. Surprisingly, we show that for generic 2-local Hamiltonians on any interaction graph, all of the parameters can be reconstructed from such experiments. Computational basis state preparation and measurements: We then consider a similarly constrained setting, but where state preparation and measurement are restricted to the computational basis. For nearest-neighbor Hamiltonians with only Pauli $X/Z$ interactions, a class which captures contemporary Rydberg atom platforms, we show that over 1D and 2D rectangular lattices, all of the parameters can be reconstructed from such experiments up to unavoidable gauges. Our protocols introduce new techniques for solving structured polynomial systems over an extensive number of parameters. Taken together, our results suggest that one can learn a great deal from the dynamics of quantum many-body systems even under the most stringent experimental constraints.

We consider the following data compression problem. Given a string $x \in \{0,1\}^m$ of Hamming weight at most $n$, compress it into a shorter string $y \in \{0,1\}^s$ so that any bit $x_i$ of $x$ can be retrieved without any error using at most $t$ quantum queries to the standard oracle encoding of $y$. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on $m$ except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on $n$.

The information bottleneck (IB) seeks a representation $U$ of a source $X$ that retains as much information as possible about a target $Y$, subject to a constraint on $I(U;X)$. A classical argument shows that it suffices to consider representations with at most $|\mathcal{X}|+1$ symbols, and this bound is known to be tight whenever $|\mathcal{X}| \geq 3$. We show that the binary case behaves differently: if $X$ is binary and $Y$ is finite, then for every joint distribution of $(X,Y)$ and every rate constraint, the IB optimum is attained by a binary $U$. Hence the bound $|\mathcal{U}| \leq |\mathcal{X}|+1$ sharpens to $|\mathcal{U}| \leq |\mathcal{X}|$ for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.

We devise and analyze WLZ, a family of LZ77 encoders whose sliding-window sizes depend on match length: short matches use smaller windows and shorter distance fields, while long matches retain access to distant repetitions. Write $B:=\log_2 W$ for the maximum window $W$. A parsing-transfer bound charges both window restrictions and missed matches, preserving established convergence and finite-input minimax orders, and a sharper block charge proves stationary-ergodic universality of exact greedy WLZ when full-window matching begins at length $o(B)$. A calibrated window schedule never increases minimum token cost relative to a single-window baseline and saves $\Omega(BW^{-\beta})$ in rate on specified iid sources, with $\beta>2$. The remaining gains come from the token code rather than the windows. On a uniform iid source, a growing phrase cap with a cheap length symbol improves redundancy from the $\Omega(\log B/B)$ of the original 1977 fixed-field format, whatever phrase cap it uses, to $O(\log\log B/B)$. Recoding a single-symbol run $(r,1)$ as $(1,r)$, with a logarithmic-cost count $r$ that may exceed the match cap, codes inputs with $O(n^\alpha)$ runs, $0\le\alpha<1$, in $O(n^\alpha\log n)$ bits, versus $\Omega(n)$ for that format with phrase cap $\Theta(\log W)$ and $W=o(n)$. On globally $p$-periodic inputs, Huffman coding the fields of a capped parse with nearest-distance ties reduces the large-file rate from $\Theta(B/W)$ under fixed-width coding to at most $3/W$, including tables and framing. Finally, selection among complete WLZ codes yields an entropy-rate estimator consistent almost surely and in mean, with finite-data error bounds for fixed nonuniform iid sources.

Based on the CRT for polynomial rings, Yang, Zhu, Fu and Xia (ISIT 2026) proposed a compartmented secret sharing scheme for the compartmented access structure with lower bounds, claiming it can be ideal. We exhibit three families of unauthorized subsets that reconstruct the secret. The scheme is therefore insecure, except for a degenerate choice of parameters in which the only authorized subset is the whole participant set. The flaw in the security analysis is that it does not take all published polynomials into account. Similar flaws appear in the same first author's hierarchical schemes (ISIT 2024, 2026).

Entropy-based selection objectives suffer from a fundamental degeneracy: minimizing Shannon entropy $H(p_A)$ rewards confident selection regardless of whether the selected candidate is informative. We address this limitation with the residual entropy $D = H(p_A) - H(p_\beta)$, where $p_\beta$ is induced by candidate trust weights. We prove the exact identity $D = -\mathrm{KL}(p_A\Vert p_\beta) - \Delta$, where $\Delta$ measures whether the score-induced distribution and trust profile favor the same candidates. Boundary cases establish basic safety: under uniform trust, $D\leq0$ automatically, so an equal-trust, non-starving state is never penalized, while at any one-hot limit, $D\to0$ regardless of the selected candidate. For the intermediate regime where selection occurs, we prove that $D\leq0$ when candidate ordering by trust agrees pairwise with ordering by informativeness, and derive a tighter certificate based on the leading candidate's margin over its competitors. These results are independent of the candidate-scoring function and apply to both stationary and dynamically changing information. Experiments with a gradient-based mixture-of-experts router confirm that the ordering conditions can hold during real optimization and show that correct ordering improves downstream performance when candidates are non-interchangeable and selections are used directly rather than averaged. Beyond routing, margin-based reweighting matches or outperforms fixed-strength baselines in a class-imbalance task, while informative selection in a production video-prediction system reduces MSE by approximately 20$\%$ and transfers to a related species. Residual entropy, therefore, provides a safety criterion for selection and a usable signal for deciding when that selection is informative.

In the general probabilistic model of information theory, the signaling dimension of a given communication protocol (or, equivalently, of its state space) is the smallest possible complexity of a classical communication protocol capable of perfectly simulating the given one in terms of input-output correlations. The signaling dimensions of three-, four-, and five-dimensional cross-polytopes have been known to be 3. We give logarithmic lower and upper bounds for the signaling dimensions of higher dimensional cross-polytopes, pinning down the value up to an additive gap of 2. The lower bound shows that the signaling dimension goes to infinity, in contrast to the case of balls and hypercubes.

An important role in the theory of conflict-avoiding codes is played by a quantity involving the multiplicative order of $4$ modulo $d$, with $d$ running over all positive divisors of an odd integer $n$. We establish results on its distribution as $n$ varies over the odd prime numbers, respectively odd integers, using techniques from the study of Artin's primitive root conjecture. We also point out some other interpretations of this quantity, with one of them making a connection with the factorization of $X^n-1$ into irreducibles over the finite field $\mathbb F_2$.

Given a finite Cartesian set $S=X \times Y$ and a decreasing set of monomials $\mathcal M$, we call extremal polynomials for $\mathcal M$ over $S$ those that have the maximum number of zeros in $S$ and whose support belongs to $\mathcal M$. Coordinate factorizations give a family of extremal polynomials; we call them canonical. If $\max(\mathcal M)$, taken with respect to divisibility, is a single monomial, all extremal polynomials are canonical. If $|\max(\mathcal M)|=2$, either all extremal polynomials are canonical, or the problem reduces to the case where $\max(\mathcal M)=\{x^{d_x},y^{d_y}\}$. In the latter case, we prove that the existence of noncanonical extremal polynomials depends on finding families of subsets whose elementary symmetric functions agree. This condition is more restrictive than the classical Prouhet–Tarry–Escott problem, which asks for two sets whose elementary symmetric functions agree. We determine the number of triples $(X, Y, h)$, where $h$ is a quadratic noncanonical extremal polynomial. We apply extremal polynomials to coding theory via minimum-weight codewords.

Omura's lower bound on the probability of correct decoding at rates above capacity has an exponent of sphere packing form. Dueck and Körner refined Omura's argument through a codebook extension step and obtained the exact strong converse exponent. It has been claimed in the literature that the two exponents coincide at all rates, but the argument contains an error. To settle this question, we first show that above a threshold rate, the strong converse exponent follows a straight line of unit slope determined by the Rényi capacity of order infinity. This threshold rate plays the role of a critical rate above capacity, while the order-infinity capacity plays that of a cutoff rate. We then show that the two exponents coincide up to a second threshold rate, which lies above the first, and differ strictly beyond it. Examples include modulo-additive channels, where there is no gap; and the binary erasure channel, where the thresholds and the gap are computed in closed form.

We introduce a framework for multi-bit text watermarking with security defined directly through $f$-divergence from the base language model distribution. Unlike prior approaches that focus on average-key distortion-freeness or a particular statistical distance, our formulation supports general $f$-divergences, including total variation and KL divergence, and enforces the guarantee for each realized key and embedded message. We develop a coding-based watermarking scheme that optimally biases next-token distributions subject to a prescribed divergence budget, and characterize the resulting tradeoff between embedding rate, decoding reliability, and statistical security. Experimentally, we compare our method against prior multi-bit watermarking schemes across modern language models and payload regimes. Our approach achieves substantially lower watermark detectability while maintaining competitive message-recovery performance and generation quality. Our results provide a unified view of secure multi-bit watermarking and recover several commonly used security notions as special cases.

A $k$-substring edit in a sequence first deletes a substring of length at most $k$, and then inserts a sequence of length at most $k$ at the same position. A code that can correct a $k$-substring edit is called a $k$-substring edit code. In this paper, we develop a new localization method and use it to construct a $q$-ary $k$-substring edit correcting code with $\log n+8\log\log n+o(\log\log n)$ bits of redundancy for any fixed $q\ge2$ and $k\ge1$, where $n$ is the code length. For the binary alphabet, this improves upon the redundancy $\log n+16k\log\log n+o(\log\log n)$ obtained by Li et al. When the deleted substring and the inserted sequence have different lengths, we further construct codes with redundancy $\log n+O_{q,k}(1)$, which is optimal up to an additive constant. As corollaries, for all fixed $q\ge2$ and $1\le t\le T$, we obtain $q$-ary $(\le t)$-burst-deletion correcting codes and $(t,T)$-localized deletion correcting codes with redundancies $\log n+O_{q,t}(1)$ and $\log n+O_{q,T}(1)$, respectively. To the best of our knowledge, these are the first constructions attaining optimal redundancy up to an additive constant for these two deletion models over the full range of fixed parameters. For $(\le t)$-burst-deletion correction with $t\ge2$, such redundancy had previously been achieved only for $q=t=2$ by Levenshtein in 1967.

Modeling the channel in a single-antenna fluid antenna system (FAS) using extreme value distributions (EVDs) provides an accurate and tractable framework for FAS performance evaluation. When the objective of FAS channel fitting is outage probability (OP) evaluation, accurate characterization of the low-probability left-tail region becomes crucial, while existing fitting strategies that emphasize global fitting accuracy may fail to capture the critical tail behavior required for precise OP evaluation. In this paper, we propose an OP-oriented channel fitting strategy with a left-tail-sensitive target distribution and fitting criterion. Specifically, a combined EVD (CEVD) is introduced as the target distribution, where a generalized Pareto distribution (GPD) is employed to characterize the left tail and a generalized extreme value (GEV) distribution is used to model the global behavior. Furthermore, a modified mean-square-error (MMSE) criterion is developed, which employs logarithmic-domain errors to enhance sensitivity to left-tail discrepancies. Meanwhile, the evaluation points are constructed via uniform discretization on the logarithm of the cumulative distribution function, ensuring uniform sampling across all probability scales. This mitigates the under-representation of tail errors in the overall MMSE, which cannot be effectively addressed by error amplification alone due to the sparsity of tail samples. Simulation results demonstrate that the proposed fitting strategy significantly improves the OP evaluation accuracy in the ultra-low-OP regime.