Information Theory
See recent articles
Showing new listings for Tuesday, 17 November 2026
- [1] arXiv:2611.18798 [pdf, html, other]
-
Title: A proof of the Eskenazis--Nayar--Tkocz conjecture on entropy maximization for cube projectionsComments: 20 pages, 1 figureSubjects: Information Theory (cs.IT); Probability (math.PR)
We complete the Eskenazis--Nayar--Tkocz conjecture: among the one-dimensional projections of the uniform measure on a cube, differential entropy is maximized precisely in directions with equal coordinate magnitudes. Pang proved the conjecture in every dimension at least $150$. We prove the remaining dimensions using polynomial entropy bounds in dimensions three through six and exact certificates for derivatives of the logarithm of the diagonal projection density. The proof uses integer arithmetic and certified one-dimensional integration. We also derive quantitative stability estimates and determine the optimal asymptotic coefficient of a linear stability bound. The source code and the outputs of all finite verifications accompany the paper.
- [2] arXiv:2611.18942 [pdf, other]
-
Title: Surrogate Symbols in Wireless CommunicationsComments: 23 pages. Submitted to the IEEE Open Journal of the Communications SocietySubjects: Information Theory (cs.IT)
Co-channel interference (CCI), caused by the inevitable aggressive channel reuse in dense deployments, remains a critical bottleneck for current and future wireless communication systems. In this paper, we address this bottleneck in an N-co-channel wireless communications network of single-antenna transmitters and receivers. The limiting case of this problem leads to a novel "thought experiment": If each receiver's own desired channel link is simultaneously completely blocked, can a Maximum Likelihood Detection at each receiver still recover its transmitted symbol? In the traditional way of thinking, the answer is no: The receiver obtains nothing but co-channel interference (CCI) plus thermal noise, and a receiver-side phase rotation cannot help, since there is no desired signal to align. Given only the channel matrix H -- and no knowledge of the transmitted symbols -- can the transmitters' phases be chosen so that the received signal becomes "almost" the desired symbol at every receiver? We show that the answer is yes. We first develop the underlying framework for the general case (nonzero own-channel link case), turning classical co-channel systems into a novel discrete phase-optimization problem, "Game of Phases: Surrogate Symbol Optimization", and present two algorithms, "Minimum Phased-Interference Power algorithm (MiPIP)" and "Maximum Phased-Interference Support (MaPRIS)". We then show that the MaPRIS resolves the thought experiment: it converts hostile CCI into an "almost" desired symbol even when the own desired channel link is zero, yielding the counter-intuitive result that higher CCI variance yields higher SINR. Extensive simulation results confirm the findings. The gain promised by the proposed algorithms comes on top of any other CCI reduction techniques as our framework here is based on a bottom-line baseband model.
- [3] arXiv:2611.18947 [pdf, html, other]
-
Title: Joint Channel Estimation, Data Detection, and Phase Noise Tracking in Massive MIMO SystemsSubjects: Information Theory (cs.IT)
Communication over multiple-input multiple-output (MIMO) systems is degraded by phase noise (PN) arising from imperfect local oscillators, with PN becoming more severe at higher carrier frequencies. Existing methods either rely on linearized Kalman-filter approaches or apply variational Bayes (VB) only to individual stages, such as data detection under a static phase prior, or channel estimation alone, leaving no unified framework that tracks an evolving PN process consistently across pilot and data transmission. This paper develops such a framework for uplink massive MIMO. Specifically, we first propose VB-Tracking, which employs von Mises priors and coordinate-ascent VB inference to jointly estimate the channel and track the transmit and receive PN trajectories during the pilot phase without linearization. We then propose VB-Detecting for joint data detection and phase tracking by absorbing the transmit PN into a composite transmit variable. Using a sequentially propagated von Mises predictive prior, the composite variable admits an exact closed-form posterior. Finally, we propose VB-Refining, which periodically re-estimates the channel during data transmission using the soft posterior moments of reliably detected transmit symbols as virtual pilots. We show that VB-Detecting scales linearly in the number of users, receive antennas, constellation size, and iterations. Simulations against EKF-EP, EKF-ZF, and JED baselines show that VB-Tracking, VB-Detecting, and VB-Refining together achieve lower channel NMSE and symbol error rate, with the performance gap widening at high SNR and under severe PN.
- [4] arXiv:2611.19070 [pdf, html, other]
-
Title: New constructions of optimal Ferrers diagram rank-metric codes for quasi-block monotone Ferrers diagramsSubjects: Information Theory (cs.IT)
Constant dimension subspace codes (CDCs) have become an important object in coding theory due to their applications in random network coding. The paper is devoted to constructing optimal Ferrers diagram rank-metric codes for block Ferrers diagrams, which play a crucial role in the multilevel construction of CDCs. Let \(\mathbb{F}_q\) be the finite field with \(q\) elements of characteristic \(p\), \(P\) be a power of \(p\), and \(e\) be a positive integer. Let \(L=\mathbb F_{q^{eP}}\) and \(\sigma\) be the Frobenius \(\mathbb F_q\)-automorphism of \(L\), set \(N=\sigma^e-\mathrm{id}\). Based on the multiplicative property of the kernel filtration of the nilpotent map \(N\), we construct optimal Ferrers diagram rank-metric codes for block monotone diagrams. Specifically, considering \(n \times l\) Ferrers diagrams, we prove that optimal codes always exist for block monotone diagrams when \(n = eP\). Furthermore, by employing puncturing on columns, we prove that optimal codes also always exist for block strictly monotone diagrams, removing the restriction \(n = eP\). Consequently, optimal codes always exist for block upper triangular diagrams, specifically for maximum sum-rank distance (MSRD)-constructible block diagram pairs, which generalizes the corresponding results in \cite{neri2024,calderini2026}, in which the rank distance or the characteristic is restricted. Furthermore, by employing both puncturing and shortening on columns, we prove that optimal codes always exist for quasi-block strictly monotone diagrams, thereby generalizing the corresponding results in \cite{pratihar2023, zhang2019}. The optimal codes constructed in this paper will potentially be beneficial to the further construction of CDCs.
- [5] arXiv:2611.19269 [pdf, html, other]
-
Title: Entropy-Based and Quadratic Conditional Innovation Metrics for Informed Dynamic Scheduling of Belief-Propagation Decoding for LDPC CodesComments: 25 pages, 18 figures, 3 tablesJournal-ref: Entropy 2026, 28, 1246Subjects: Information Theory (cs.IT)
We propose two enhanced conditional innovation (CI) metrics for informed dynamic scheduling (IDS) in belief-propagation (BP) decoding of LDPC codes. The CI-based residual BP (CIRBP) algorithm uses the CI metric to guide the selection of the variable node (VN) to be updated and has been shown to outperform several existing IDS-based BP decoders, especially at the early decoding stage. However, the original CI metric uses only the absolute difference between the current and precomputed posterior probabilities and does not separately account for the reliability associated with each probability. By reformulating the CI metric relative to the decision boundary, we separate each posterior probability into its decision side and a linear-distance term reflecting reliability. Replacing the latter with the binary entropy complement yields the proposed entropy-based CI (E-CI) metric. Moreover, the proposed quadratic CI (Q-CI) metric is derived from the leading quadratic term in the local expansion of the entropy complement, avoiding the logarithmic operations required for direct E-CI evaluation. We apply both proposed metrics to the CIRBP decoder and its node-wise variant. Numerical results show that the proposed metrics generally provide lower frame error rates than the original CI metric, with their relative advantages depending on the code and decoding procedure.
- [6] arXiv:2611.19305 [pdf, html, other]
-
Title: Fundamental Limits of Statistical Watermarking for LLMs with Fixed and Optimizable Common RandomnessSubjects: Information Theory (cs.IT); Cryptography and Security (cs.CR)
Watermarking has emerged as an important technique for distinguishing AI-generated text from human-written text. However, most existing work is primarily empirical, relies on ad hoc watermarking designs, and lacks a fundamental understanding of the performance limits. In this paper, we propose a unified theoretical framework for statistical watermarking of large language models (LLMs), casting the problem as an independence test between generated text and common randomness and jointly designing the watermarking embedder and the detector. Our objective is to maximize detection power while controlling the worst-case false positive rate (FPR) and limiting distortion to text quality. A central focus of our framework is the design of the common randomness, which plays a critical role in both watermark embedding and detection. We characterize the fundamental limits of statistical watermarking under both fixed and optimizable common randomness. Our results show that optimizing the common randomness does not improve the fundamental limits: the best achievable performance is the same as that with fixed common randomness. Nevertheless, common randomness design remains highly important because it can substantially simplify detector design. In particular, with optimizable common randomness, a fixed, deterministic, and model-agnostic detector can achieve optimal performance. We further study a practical setting with fixed uniform common randomness and a fixed deterministic detector, and characterize its performance gap relative to the optimizable case, thereby demonstrating the practical value of optimizable common randomness.
- [7] arXiv:2611.19619 [pdf, html, other]
-
Title: On the boomerang spectrum of the APN power function $x^{q+2}$ over $\F_{q^2}$Subjects: Information Theory (cs.IT); Number Theory (math.NT)
We study the boomerang spectrum of the almost perfect nonlinear power function $x^{q+2}$ over $\F_{q^2}$, where $q$ is an odd prime power with $q\equiv1\pmod6$. The connection of Pal and Stănică between boomerang entries and $(-1)$-differential entries reduces the problem to counting roots of a single equation. We determine the complete contribution from nonzero parameters in $\F_q$. For parameters outside $\F_q$, we obtain a quintic over $\F_q$ in terms of the parameter's trace and norm, with a separate formula when the trace is zero. We exclude the entry four when $q\equiv1\pmod{12}$ and characterize its occurrence when $q\equiv7\pmod{12}$ through a repeated-root parametrization and a residual cubic. We also evaluate the first nonsubfield moment and an aggregate quadratic-character sum, and prove a Weil bound for each nonzero trace. Explicit secant and residual-cubic formulas express the second, third, and fourth falling-factorial moments as finite sums. Once the size-four frequency is known, these moments recover all remaining frequencies through a nonsingular five-dimensional system. A closed-form evaluation of the nonsubfield distribution remains open.
- [8] arXiv:2611.19627 [pdf, html, other]
-
Title: A Recursive Construction of Perfect and Odd Perfect Sequences of Unbounded Length over the Unit QuaternionsSubjects: Information Theory (cs.IT); Combinatorics (math.CO)
We give a recursive construction, with closed-form index functions, of perfect and odd perfect periodic autocorrelation sequences over the eight simple unit quaternions $\Qe=\{\pm1,\pm i,\pm j,\pm k\}$ in every length $2^n$. The sequences are built, as in the recursive perfect array construction of Blake, from \emph{twisted periodic extensions}: a short sequence continued with period $M$ up to a right factor $u\in\Qe$. Over roots of unity the twists cannot be regenerated by a one-dimensional recursion, consistently with Mow's conjecture; over $\Qe$ we show that no single sequence of length $M\not\equiv0\pmod 4$ carries a twist $\pm i,\pm j$ or $\pm k$ either, but that \emph{pairs} of sequences whose $i$- and $(-i)$-twisted autocorrelations are complementary do. These $i$-pairs behave exactly like Golay pairs: they double under interleaving with a right factor $j$ in place of a sign, every Golay pair of length $n$ gives an $i$-pair of length $2n$, and they exist in length $6$ where no Golay pair exists. An $i$-pair of length $M$ interleaves to an odd perfect sequence of length $4M$, and a perfect and an odd perfect sequence of length $M$ interleave to a perfect sequence of length $4M$ with the array orthogonality property for the divisor $2$. The $i$-pairs of length $2^t$ are $x^{(t)}_{r,a}=j^{w_t(r,a)}$, where $w_t(r,a)$ counts the changes in the bit string formed by $r$ and the binary digits of $a$, and the odd perfect sequence of length $2^{t+2}$ is $y^{(t)}_{2a+r}=j^{w_t(r,\,a\bmod 2^t)}\, i^{(1-2r)\lfloor a/2^t\rfloor}$. The construction also gives odd perfect sequences over $\Qe$ in every length $24\cdot2^s$ and perfect sequences in every length $6\cdot4^s$.
- [9] arXiv:2611.19729 [pdf, html, other]
-
Title: Exact Redundancy under Average and Almost-Sure Distortion ConstraintsSubjects: Information Theory (cs.IT)
We characterize the exact redundancy of lossy source coding under average and almost-sure distortion constraints. For general source and output alphabets, we establish the asymptotic redundancy coefficients under suitable regularity conditions. Under the average distortion constraint, the coefficient is half of the minimum probability that an output reveals information about the source, among all rate-distortion optimal channels. Under the almost-sure distortion constraint, the coefficient is either $1/2$ or $1$, depending on whether the $D$-tilted information is constant or not. Both converse results follow from a common change-of-measure inequality. Finally, we verify the required conditions under both distortion requirements always hold for finite alphabets.
- [10] arXiv:2611.19749 [pdf, html, other]
-
Title: Gaussian mass inequalities for latticesComments: 50 pagesSubjects: Information Theory (cs.IT); Number Theory (math.NT)
The Gaussian mass of a lattice is the evaluation of its theta series at a real nome and is relevant to lattice coding for the wiretap Gaussian channel. The ratio of the Gaussian mass of stable lattices to the Gaussian mass of the integer lattice was conjectured to be $\le 1$ (Regev et al., 2024). Kominers proved this bound recently for lattices obtained by Construction~A from binary self-dual codes. Building on Kominers' bound, we establish corresponding inequalities on average for Construction~$A_4$ lattices obtained from free self-dual quaternary codes and for Construction~$A_6$ lattices obtained from self-dual senary codes. We also prove the strict Gaussian-mass inequality for extremal unimodular lattices of both Type~II and Type~I. The Type~I result uses the Rains--Sloane definition of extremality. Its proof combines a universal theta truncation with an exact inversion of the shadow coefficients, and a Gaussian inequality for translated lattices. In addition, we obtain an averaging bound over the genus of Type~II lattices, and extend the binary Construction~A inequality to Siegel theta series of arbitrary genus, with further quaternary results under conditions on the residue code.
- [11] arXiv:2611.19833 [pdf, html, other]
-
Title: Error-correcting codes without parity-check bitsSubjects: Information Theory (cs.IT)
We are developing a new approach to the problem of error correction in communication channels, in which the input sequence is transformed in such a way that the interdependence of symbols increases significantly. Then, after the sequence is transmitted over the channel, this property is used for error correction, so that the residual error rate is significantly reduced. A natural example of its application is the transmission of binary sequences whose entropy (per symbol) is less than one, since in this case the length of the transmitted sequence remains constant during encoding and decoding.
An algorithm has been developed to implement the maximum likelihood method, in which the encoding and decoding times are linear. This algorithm was used to experimentally investigate its effectiveness on popular channel models, and it was found that there are certain sets of parameters for which the proposed method is quite effective. - [12] arXiv:2611.19959 [pdf, html, other]
-
Title: Sparse Rotatable Arrays (SRAs) for Cell-Free MIMO: Network-Wide Design of Antenna Activation and Panel OrientationSubjects: Information Theory (cs.IT)
This paper investigates a sparse rotatable array (SRA)-enabled cell-free multiuser multiple-input multiple-output (MIMO) system. Under a network-wide antenna activation budget, distributed access points (APs) select active antenna elements from their installed arrays and adjust panel orientations, enabling joint control of sparse array apertures and antenna directivity. To avoid frequent hardware reconfiguration in response to instantaneous channel variations, we formulate a two-timescale stochastic optimization problem to maximize the expected minimum-user rate. Long-term antenna activation and panel orientations are optimized based on user spatial distributions and statistical channel state information (CSI), while short-term precoders adapt to instantaneous CSI. Under line-of-sight (LoS) propagation, we derive the optimal single-user antenna allocation, characterize the two-user max-min signal-to-interference-plus-noise ratio (SINR) and establish conditions for discrete activation and panel rotation to attain the continuous-position benchmark, and obtain a closed-form multi-AP zero-forcing (ZF) allocation benchmark under a continuous antenna-count relaxation. For the general mixed-integer nonconvex stochastic problem, we develop an alternating algorithm based on sample-average approximation (SAA), integrating uplink-downlink (UL-DL) duality for short-term precoding, weighted minimum mean-square error (WMMSE) surrogates for panel-orientation optimization, and multi-start greedy search for antenna activation. Numerical results demonstrate that the proposed design outperforms the fixed-array benchmark, improves all-user service reliability with fewer active antennas, and adapts effectively to nonuniform user spatial distributions.
- [13] arXiv:2611.19996 [pdf, html, other]
-
Title: The ordered sum-rank metric and linearized multiplicity codes: NRT meets sum-rankSubjects: Information Theory (cs.IT)
In this work, we introduce linearized multiplicity codes, which are a common generalization of linearized Reed--Solomon codes and univariate multiplicity codes. We also introduce the ordered sum-rank metric, which is a common generalization of the sum-rank metric and the Niederreiter-Rosenbloom-Tsfasman (NRT) metric (or ordered Hamming metric). We provide a Singleton bound for the ordered sum-rank metric and show that linearized multiplicity codes attain it. That is, they are maximum ordered sum-rank distance (MOSRD) codes. We introduce the support lattice for the ordered sum-rank metric and study duality, support distributions and weight distributions of MOSRD codes. We also show that MOSRD codes are ordered MDS, dually quasi MSRD and, under some divisibility conditions, MSRD (and thus MDS). For linear MOSRD codes, we give lower bounds on the field extension degree by the number of matrix columns, and upper bounds on the block length by the base field size. We conclude by showing that linearized multiplicity codes attain such bounds exactly in almost all cases, and the same growth order in all cases.
- [14] arXiv:2611.20243 [pdf, html, other]
-
Title: Achievable Information Rate for FTN under a Reduced Complexity BCJR ReceiverSubjects: Information Theory (cs.IT); Signal Processing (eess.SP)
The capacity of faster-than-Nyquist (FTN) signaling in additive white Gaussian noise (AWGN) channels has been established and is achieved by Gaussian inputs. However, the capacity of FTN signaling with finite-constellations is not yet fully characterized. The achievable information rate (AIR) provides a lower bound on this constrained capacity by quantifying the rate supported by a specified input distribution and receiver. This paper investigates the AIR of FTN signaling with finite constellations using full-state and reduced-state Bahl-Cocke-Jelinek-Raviv (BCJR) receivers, with bidirectional decision feedback incorporated into the reduced-state receiver. Especially, the detection problem is formulated in a reproducing kernel Hilbert space (RKHS), where a geometric foundation is established to understand FTN under severe time packing. The formulation establishes that the Ungerboeck metric remains valid even when the noise covariance is singular. We further characterize detection errors geometrically using RKHS distances between competing sequences. We also study outage probability for reduced-state detection, which occurs when AIR is zero, in addition to deriving the zero-AIR outage criterion for reduced-state detection. Unlike ISI-free Nyquist signaling, reduced-state FTN detection can retain residual ISI that causes the receiver to assign excessive confidence to incorrect symbols, leading to outage even at high signal-to-noise ratio (SNR). Our results confirm both the spectral efficiency gains and the feasibility of FTN systems employing finite constellations and realistic receiver architectures.
- [15] arXiv:2611.20279 [pdf, other]
-
Title: Functional Information, Optimal Channel Simulation and Lossy Source CodingSubjects: Information Theory (cs.IT)
We characterize, within a constant number of bits, the minimum achievable rate for several one-shot coding problems, such as channel simulation and lossy source coding. The basis of our work is a new information measure between random variables $X, Y$ that we call the functional information $I_F(X \to Y)$. We show that this quantity characterizes the minimum one-shot rate $R^*(X \to Y)$ of channel simulation, in which a sample $Y \sim P_{Y \mid X}$ is communicated in the presence of common randomness: $I_F(X \to Y) \leq R^*(X \to Y) < I_F(X \to Y) + 1.45$. For the achievability result, we construct an explicit code using the Poisson functional representation.
Using these results, we develop new bounds for one-shot variable-rate lossy source coding: given some distortion measure $\Delta$, we use $I_F(X \to Y)$ to define the functional rate-distortion function $R_F$. Then, letting $R_O$ denote the one-shot operational rate-distortion function with private encoder randomness and distortion measure $\Delta$, we make use of our channel simulation result to show that $R_F(D) \leq R_O(D) < R_F(D) + 2.45$ at every positive distortion level $D$.
Finally, we generalize our channel simulation result by introducing the Rényi $\alpha$-functional information $I_{F, \alpha}(X \to Y)$ and show that it characterizes the minimum Arimoto-Rényi conditional entropy for channel simulation, ${R^*_\alpha(X \to Y)}$, associated with the Campbell cost: ${I_{F, \alpha}(X \to Y) \leq R^*_{\alpha}(X \to Y) \leq I_{F, \alpha}(X \to Y) + O(1/\alpha)}$. - [16] arXiv:2611.20492 [pdf, html, other]
-
Title: Weighted Sum-Rate Optimization of Near-Field STAR-RIS-Aided ISAC Systems Under Hardware ImpairmentsSubjects: Information Theory (cs.IT)
This paper investigates weighted sum-rate (WSR) optimization for a simultaneously transmitting and reflecting reconfigurable intelligent surface (STAR-RIS)-assisted multi-user multiple-input multiple-output (MIMO) integrated sensing and communication (ISAC) system operating under the energy splitting (ES) protocol. A hybrid propagation model is considered, where the base station (BS)-STAR-RIS channel follows far-field propagation, whereas the STAR-RIS-user channels are modeled using near-field spherical wavefronts. Practical hardware impairments (HWIs), including STAR-RIS phase perturbations and signal-dependent additive distortion at the BS and user equipment (UEs), are incorporated into the system model. Under this framework, the WSR maximization problem is formulated subject to radar beampattern, quality-of-service, transmit-power, and STAR-RIS ES constraints. The resulting problem is highly non-convex due to the coupling among the active beamformers, passive STAR-RIS coefficients, and HWI-dependent signal-to interference-plus-noise ratio expressions. An alternating optimization (AO)-based successive convex approximation framework is developed to iteratively solve the active and passive beamforming subproblems. Numerical results demonstrate stable convergence of the proposed algorithm and consistent WSR improvement over direct-link transmission. Besides, severe HWIs also lead to WSR saturation in the high transmit-power regime, whereas stringent sensing constraints reduce communication throughput. Increasing the STAR-RIS aperture and the number of BS antennas improves the achievable WSR, although the performance gain becomes limited under strong hardware distortion.
- [17] arXiv:2611.20804 [pdf, html, other]
-
Title: A Recursive Construction of Perfect Arrays of Every Shape $2^{a_1}\times\cdots\times2^{a_d}$ over the Unit QuaternionsSubjects: Information Theory (cs.IT); Combinatorics (math.CO)
We extend the recursive construction of perfect and odd perfect sequences over the simple unit quaternions $\Qe=\{\pm1,\pm i,\pm j,\pm k\}$ of Blake to arrays of any dimension. The three operations of that construction act on one direction of an array at a time, and are valid whenever the array is periodic in the remaining directions. Starting from a perfect array $P$ of shape $M_2\times\cdots\times M_d$ they give perfect arrays of shape $2^a\times M_2\times\cdots\times M_d$ for every $a\ge0$, with explicit index functions and with the array orthogonality property for the divisor $2$ in the lifted direction; from $a=5$ on these arrays are, in general, Kronecker products of a sequence with $P$ in neither order. Applied direction by direction, the construction gives perfect arrays over $\Qe$ in every shape $2^{a_1}\times\cdots\times2^{a_d}$, and in every shape $2^{a_1}\times\cdots\times2^{a_{d-1}}\times N$ for which a perfect sequence of length $N$ over $\Qe$ exists. The contrast with the binary alphabet is sharp: a perfect binary array of shape $2^{a_1}\times\cdots\times2^{a_d}$ exists only when $\sum a_k$ is even and $\max a_k\le\frac12\sum a_k+1$, by a theorem of Jedwab and Kraemer on Menon difference sets in abelian $2$-groups, whereas over $\Qe$ there is no constraint on the shape. We also show that, unlike the one-dimensional case, single arrays carrying a non-central twist do exist in two dimensions, and determine where the one-dimensional non-existence argument breaks.
- [18] arXiv:2611.20824 [pdf, html, other]
-
Title: Network-Native DNN Architecture Synthesis for Distributed InferenceSubjects: Information Theory (cs.IT); Distributed, Parallel, and Cluster Computing (cs.DC)
Distributed deep neural network (DNN) inference typically follows a model-first paradigm, in which a predefined DNN is partitioned and deployed over a physical network. On irregular communication-computation topologies, however, this approach can create transmission bottlenecks and leave distributed resources underutilized. This paper reverses this perspective and asks: given a physical network, what kind of DNN can it naturally support? To answer this question, we propose a network-native DNN architecture synthesis paradigm in which the physical network topology directly defines inter-node neural dependencies. Neural computation is allocated across nodes under communication, computation, storage, synchronization, and latency constraints. We establish structural properties of the synthesis problem and develop linear programming (LP)-based Architecture Synthesis (LPAS), an efficient topology-guided algorithm that produces a feasible architecture with a computable bound on suboptimality. Experiments on physical networks of different sizes show that LPAS achieves relative gaps below 0.6% to the LP-derived upper bound, with substantially lower runtime than direct mixed-integer LP optimization on larger networks. Under matched network deadlines, the network-native architectures activate more compute nodes and utilize a larger proportion of available model-storage capacity than the model-first baseline. After training, the network-native models achieve higher classification accuracy across all evaluated dataset-precision settings, with the average gain of up to 10.69%. This network-native design paradigm thus turns the physical network from a deployment constraint into an architecture design primitive.
- [19] arXiv:2611.20863 [pdf, html, other]
-
Title: Practical Semantic Communication for General-Purpose Networks: Compression of High-Dimensional Embeddings Under QuantizationSubjects: Information Theory (cs.IT); Machine Learning (cs.LG)
This paper introduces a practical framework for semantic communication over wireless channels, focusing on the compression of high-dimensional embeddings under quantization and channel errors. Building upon a relaxed Gaussian Information Bottleneck (GIB) model, the approach provides analytical solutions for task-relevant information preservation, even with non-Gaussian targets. The framework relaxes traditional Gaussian assumptions, enabling effective compression for discrete and complex data such as text embeddings. It derives closed-form gradients for optimizing the compression matrix and establishes bounds linking continuous representations to discrete, noisy system performance. Comprehensive experiments on text classification tasks demonstrate that the proposed method outperforms task-agnostic quantization-based compression methods, maintaining high semantic fidelity at low bit budgets per embedding. The approach offers a scalable, interpretable, and resource-efficient solution for deploying semantic communication in general-purpose networks.
- [20] arXiv:2611.20914 [pdf, html, other]
-
Title: Analysis and Design of Spatially Coupled LDPC Codes for Pulsed-Jamming-Resilient Space TelemetrySubjects: Information Theory (cs.IT)
Jamming is a major threat to space telemetry downlinks, which operate under severe power and bandwidth constraints. This paper develops a jamming-aware analysis and design framework for protograph-based spatially coupled low-density parity-check (SC-LDPC) codes. For pulsed jamming with jamming state information (JSI) at the receiver, we derive a two-state protograph-based extrinsic information transfer (PEXIT) recursion that tracks the messages originating from clean and jammed symbols separately and merges them at the check nodes through a mutual-information-matched Gaussian approximation. For non-interleaved pulsed jamming, we map each pulse realization, through the serialization of the lifted codeword, to a profile of jammed fractions over the variable-node types, and we prove that, under random lifting, this profile determines the local channel-state statistics. The resulting position-dependent thresholds are the objective of a constrained differential-evolution search over protographs, coupling memories, and edge spreadings. At different code rates, the designed ensembles are compared with the Consultative Committee for Space Data Systems (CCSDS) accumulate, repeat-by-4, and jagged accumulate (AR4JA) LDPC codes whose block length matches the SC-LDPC constraint length, with longer AR4JA codes whose block length is comparable with the size of the sliding window decoder, and with non-optimized SC-LDPC codes. Under pulsed jamming with random pulse positions and with JSI, the ensembles designed over random pulse realizations, decoded through sliding window decoding, reach a bit error rate of $10^{-4}$ at lower signal-to-noise ratios than all the benchmarks.
- [21] arXiv:2611.21006 [pdf, html, other]
-
Title: The Exact Optimal Delivery Scheme for the Cyclically $L$-Separated Placement in Multi-Access Coded CachingSubjects: Information Theory (cs.IT)
This paper investigates the $(K, L, M, N)$ multi-access coded caching (MACC) system introduced by Hachem et al. The system consists of a server storing $N$ equal-sized files, $K$ cache nodes, each with a storage capacity of $M$ files, and $K$ users, each accessing $L$ consecutive cache nodes in a cyclic wrap-around topology. The server transmits coded information to the users via an error-free capacitated broadcast channel, such that each user obtains its own requested file as a combination of the server transmission and the accessible caches' content. Our objective is to minimize the worst-case transmission load over all possible user demands. First, for the cyclically $L$-separated placement, we derive a new converse bound using the acyclic index coding bound. By carefully counting all valid cache supports, the proposed converse improves upon an existing bound for the same placement. We then develop a linear coded caching scheme based on a novel determinant-based interference alignment strategy, which achieves the new converse bound exactly. Exploiting the determinant structure of a random generating matrix (each of whose columns corresponds to one user), this scheme simultaneously aligns interference across all users into low-dimensional subspaces, while preserving the decodability of their desired packets. Furthermore, by averaging acyclic index coding bounds over cyclic user permutations, we derive a general converse bound applicable to arbitrary uncoded cache placements. By combining the proposed scheme with memory sharing, we demonstrate that the achievable transmission load is within a factor of two of the global bound under uncoded placement. Finally, theoretical and numerical comparisons demonstrate that the proposed scheme generally achieves a strictly lower load than existing schemes.
- [22] arXiv:2611.21190 [pdf, html, other]
-
Title: Linear Network Coding for Sum All-Reduce over Ring NetworksSubjects: Information Theory (cs.IT)
Sum All-Reduce is a fundamental collective communication primitive in which each node holds a local vector and every node must recover the componentwise sum of all vectors. In distributed training, this operation is often implemented over a ring topology using a reduce--multicast scheme. We study sum All-Reduce on directed rings via linear network coding, which includes reduce--multicast as a special case. We give a necessary and sufficient feasibility condition in terms of the coding matrices. For a ring with $N\geq 3$ nodes and unit-capacity links, where each node holds a vector containing $K$ symbols, we prove that the number of time units $T$ required by any feasible linear code satisfies $T\ge\max\bigl\{K+N-2,\ \lceil\frac{2(N-1)}{N}K\rceil\bigr\}$, giving a rate $K/T$ of at most $N/(2(N-1))$. The bound is tight over every field. When $K\ge N$, an interleaved reduce--multicast code achieves the bound; when $K<N$ and $K$ divides $N$, a reduce--partial-multicast code does. When $K<N$ and $K$ does not divide $N$, no coordinate-wise code---in particular, no reduce--multicast code---achieves the bound, while an explicit linear network code does.
- [23] arXiv:2611.21238 [pdf, html, other]
-
Title: Recursive Spectral Graph Partitioning Coding for Index Assignment in Semantic CommunicationsSubjects: Information Theory (cs.IT); Signal Processing (eess.SP)
Transmitting quantized semantic embeddings over a bit-flip channel requires a binary mapping that minimizes expected reconstruction distortion. The classical Binary Switching Algorithm (BSA) ($\mathcal{O}(K^3 \log K)$ for $K$ centroids) yields locally optimal assignments but ignores hierarchical bit significance, making it incompatible with Unequal Error Protection (UEP). We propose Recursive Spectral Graph Partitioning (RSGP), which recursively bisects the centroid affinity graph along the Fiedler eigenvector so that early bits separate semantically distant groups while later bits refine local structure. RSGP runs in $\mathcal{O}(K^3)$ with no iterative outer loop, and is the only method studied to show a systematic positive UEP gain: protecting early bits over later ones improves accuracy for RSGP, while being neutral or harmful for unstructured assignments. Experiments on the Banking77 dataset and the Massive Text Embedding Benchmark (MTEB) confirm that RSGP consistently matches or exceeds BSA accuracy across codebook sizes and error profiles.
- [24] arXiv:2611.21275 [pdf, html, other]
-
Title: Optimal Ordering-Free Two-Dimensional Insdel Reed-Solomon Codes via Cross-RatiosComments: 16 pagesSubjects: Information Theory (cs.IT)
Insertion-deletion (insdel) codes correct synchronization errors. By the half-Singleton bound, an ${[n,2]}_q$ code has minimum insdel distance at most $2n-4$. The smallest field size of two-dimensional Reed--Solomon (RS) codes attaining this bound is $\Theta(n^3)$. Unlike the minimum Hamming distance, the minimum insdel distance of an RS code depends on the ordering of its evaluation points. An evaluation set is called ordering-free if every ordering of its points gives an RS code attaining the half-Singleton bound. In this paper, we first show that for $n\ge6$ every ${[n,2]}_q$ code attaining the half-Singleton bound is an RS code, and hence $q\ge\binom{n}{3}+2$. Secondly, we show that an ordering-free evaluation set with $n\ge6$ points in $\mathbb{F}_q$ satisfies $n<q^{1/3}+2$, and that it has at most $r+1$ points if $q=r^3$ for a prime power $r\ge3$. Finally, by using cross-ratios, we construct an ordering-free evaluation set with $r+1$ points in $\mathbb{F}_{r^3}$ for every prime power $r$. Hence, the bound $r+1$ is attained for $r\ge3$. Moreover, the constructed set is even robust against permutations combined with insdel errors.
- [25] arXiv:2611.21359 [pdf, html, other]
-
Title: K-out-of-N Oblivious Transfer over Erasure Channels: Capacity and ReductionsComments: Submitted to IEEE Transactions on Information TheorySubjects: Information Theory (cs.IT); Cryptography and Security (cs.CR)
We study $K$-out-of-$N$ oblivious transfer (OT) between a server and a client over a discrete memoryless channel, under an honest-but-curious model. The client must retrieve $K$ out of $N$ messages stored by the server while learning nothing about the remaining $N-K$ messages, and the server must not learn the client's selection. For a binary erasure channel (BEC) with parameter $\epsilon$, we show that the $K$-out-of-$N$ OT capacity is $\min\Big(\frac{K\epsilon}{N-K},1-\epsilon\Big)$. This characterization generalizes the known capacity results for $1$-out-of-$2$ OT and for $1$-out-of-$N$ OT when $\epsilon\ge\tfrac{N-1}{N}$. We also investigate OT reductions, specifically, we show that constructing a $K$-out-of-$N$ OT protocol from repeating $K$ times an optimal $1$-out-of-$N$ OT protocol can be suboptimal, but we also identify certain ranges of $\epsilon$ and $M < N$ for which a $1$-out-of-$N$ OT protocol can be optimally realized via the repetition of a $1$-out-of-$M$ OT protocol.
Finally, we discuss extensions of our results to a generalized erasure channel (GEC). - [26] arXiv:2611.21395 [pdf, html, other]
-
Title: The Sample Complexity of Channel CodingComments: 31 pages, 3 figuresSubjects: Information Theory (cs.IT); Statistics Theory (math.ST)
We introduce a new framework for the study and evaluation of the fundamental limits of channel coding, emphasizing genuinely nonasymptotic results. The {\em channel coding sample complexity} $n^*({\cal W},\epsilon)$ of a channel ${\cal W}$ is defined as the smallest blocklength at which it is possible to transmit information through that channel with error probability below $\epsilon$ and at a rate at least as high as that given by an appropriate constraint also in terms of $\epsilon$. This formulation follows analogous developments in statistics, computer science and, more recently, in lossless source coding. For any discrete memoryless channel we derive nonasymptotic bounds on the sample complexity, with explicit constants. These bounds show that the sample complexity is characterized not by the usual channel capacity, but by the channel's Augustin--Csiszár capacity of order $1/2$, which coincides with the cutoff rate as well as with the channel's Sibson capacity of order $1/2$. The proof is partly based on a new channel-coding one-shot converse in terms of hypothesis testing. We also examine extensions of the sample complexity framework to general target rates. Moreover, we derive corresponding results for the sample complexity of the additive white Gaussian noise channel with a quadratic power constraint. Their proof relies on new, explicit upper bounds on the best achievable error probability, which may be of independent interest.
- [27] arXiv:2611.21477 [pdf, html, other]
-
Title: Knowledge Fermentation: Learning from Shared Variation in Few-Shot ClassificationSubjects: Information Theory (cs.IT)
A classifier built from a handful of labeled examples knows where each class sits in feature space but not how it varies, which is why prototype rules and linear probes overfit in the low-data regime. Knowledge Fermentation (KF) recovers this second-order knowledge by letting classes exchange what they know about variation. Residuals around class prototypes act as carriers; the variance of each direction is measured on classes that took no part in estimating it, and directions above the level of the surrounding medium define a structured noise that acts on a linear classifier as a closed-form change of geometry. A convex objective trains the classifier at a noise strength calibrated on the distances between prototypes, and unlabeled examples, when available, join as carriers in repeated rounds. We prove that the held-out variances are unbiased for the directions on which they are measured, that the fermented map never expands a direction, and that damping caused by wrong assignments limits itself. On 14 datasets from vision and language and 8 frozen encoders, with all constants fixed, KF is on par with the best of six tuned inductive baselines. With unlabeled carriers it raises one-shot accuracy from 52.4% to 65.8% on average and attains the highest average accuracy among nine transductive methods, significantly so on vision encoders, while information maximization stays ahead on sentence encoders. Controlled studies attribute the gain to the task-level geometry and show that it grows with the within-class variation that the classes of a task share.
- [28] arXiv:2611.21547 [pdf, html, other]
-
Title: Fundamental Tradeoffs in Sampling, Transmission and Information Freshness: Instantaneous FeedbackSubjects: Information Theory (cs.IT); Networking and Internet Architecture (cs.NI); Systems and Control (eess.SY)
We study a time-slotted generate-at-will status-update system over an erasure channel with transmission success probability $q$, subject to average sampling- and transmission-rate constraints $f_s$ and $f_r$, respectively. The sampler-transmitter pair jointly decides whether to idle, retransmit a stale packet, or replace it with a fresh sample. We derive a universal lower bound on the optimal average age of information, analyze a class of stationary randomized policies, and obtain an optimal policy within this class that provides a $4$-approximation guarantee. The joint problem reduces to the sampling-constrained problem when $f_s\leq qf_r$ and the transmission-constrained problem when $f_s\geq f_r$. For $qf_r<f_s<f_r$, we formulate a constrained Markov decision process (CMDP) and introduce the class $\bar{\Pi}$ of $(W,R)$ policies, where $W$ specifies a waiting threshold for transmission and $R$ specifies a packet-replacement threshold. We prove that, for every choice of Lagrange multipliers, the corresponding Lagrangian-relaxed Markov decision process admits an optimal policy in $\bar{\Pi}$. We then formulate a linear program (LP) over distributions of $(W,R)$ policies and prove that choosing a policy according to an optimal LP solution yields an optimal CMDP policy. Moreover, there exists an optimal LP solution assigning positive probability to at most three $(W,R)$ policies. Since $\bar{\Pi}$ is countably infinite, for every $\epsilon>0$ we construct a finite subset $\bar{\Pi}_{\epsilon}\subset\bar{\Pi}$ and show that the LP restricted to this set yields an $\epsilon$-optimal policy. Finally, we derive a stronger pair of lower bounds by considering systems with only the sampling-rate or transmission-rate constraint. Using these bounds, we construct a policy randomizing among four $(W,R)$ policies with a $2$-approximation guarantee for $qf_r<f_s<f_r$.
New submissions (showing 28 of 28 entries)
- [29] arXiv:2611.18625 (cross-list from stat.ML) [pdf, html, other]
-
Title: Ensemble Bounds for Pairwise Dissimilar Decomposition of Deterministic DatasetsComments: Accepted for publication in Springer Proceedings in Mathematics and Statistics, QEDS conference, Ranchi, IndiaSubjects: Machine Learning (stat.ML); Information Theory (cs.IT); Machine Learning (cs.LG)
In this paper, we study reduced similarity decompositions of \emph{deterministic} datasets using redundancy graphs and obtain \emph{ensemble} bounds for the minimum size of such constrained decomposition. We consider batch decompositions that reduce similarity \emph{across} batches and use the Lovász local lemma to obtain bounds for the minimum size of a decomposition with a given pairwise dissimilarity. We then consider unique batch decomposition with a given relaxation parameter and obtain upper and lower ensemble bounds for the minimum size. Throughout, we use Binomial random graphs to obtain the desired ensemble bounds, by conditioning on the number of similar \emph{pairs} of data points.
- [30] arXiv:2611.18650 (cross-list from cond-mat.dis-nn) [pdf, html, other]
-
Title: Random matrix discrepancy -- CLuP algorithm and parametric RDT approachSubjects: Disordered Systems and Neural Networks (cond-mat.dis-nn); Information Theory (cs.IT); Machine Learning (cs.LG); Probability (math.PR)
We study information-theoretic and algorithmic aspects of random matrix discrepancy in proportional regime. The problem amounts to finding $\kappa=\min_{\x\in\mB^n}\|\sum_{i=1}^{n}\bar{A}_i\x_i\|_2$, where $\bar{A}_i\in\mR^{d\times d}$ is a collection of $n$ iid GOE matrices, $\mB^n$ are vertices of the unit cube in $\mR^n$, and $\alpha=\lim_{n\rightarrow \infty}\frac{n}{d^2}$ is a proportionality constant.
Strong progress is made in several directions: (i) We develop a Random duality theory (RDT) framework and utilize its a lifted variant to establish lower bounds on $\kappa$, which precisely match the bounds obtained via the first moment in [81]. (ii) To address analytical challenges, we propose a negative Hopfield model as a proxy for implementation of a fully lifted RDT. On the 2nd lifting level, this model fits remarkably well between the information-theoretic lower bounds from [81] and the algorithmic upper bounds from [38]. (iii) On the 3rd and 4th lifting levels, parametric RDT concepts predict a sizeable computational gap for lower $\kappa$ values in the proxy model. Extending proxy information-theoretic fitting to algorithmic suggests a similar computational gap for matrix discrepancy in low $\kappa$ regime, aligning with [73]. (iv) We design a Controlled Loosening Up (CLuP) algorithm for matrix discrepancy. Its performance strongly matches our analytical results -- closely approaching information-theoretic predictions in lower $\alpha$ ranges (indicating a small or nonexistent computational gap) and following the proxy model's algorithmic predictions in higher $\alpha$ ranges (indicating a sizeable computational gap).
Both the information-theoretic and algorithmic predictions match the corresponding phenomenologies of the symmetric binary perceptron (SBP) vector analogue in the entire $\alpha\in(0,\infty)$ range [1,2,14,31,51,92,111]. - [31] arXiv:2611.18907 (cross-list from math.CO) [pdf, html, other]
-
Title: The Walsh spectrum of the Dobbertin APN functionComments: 27 pagesSubjects: Combinatorics (math.CO); Information Theory (cs.IT)
APN functions yield the best resistance to differential attacks when used as a building block of a block cipher. APN functions induced by monomials over finite fields have received particular interest both for their simplicity and their unique properties. A key property of APN functions is their linearity, which has been determined for all known APN monomials outside of the Dobbertin APN monomials. In this paper, we close this gap and determine the complete Walsh spectrum and in particular the linearity of the Dobbertin APN monomial, answering a problem that has been open for more than 20 years. Using known connections, our result also yields the asymptotically largest Sidon sets in elementary abelian $2$-groups constructed so far as well as binary linear codes of minimum distance $5$ that are almost optimal.
- [32] arXiv:2611.18958 (cross-list from cs.AI) [pdf, other]
-
Title: Dual-Stage Channel-Posterior Integration for MLM-Aided Token CommunicationsComments: 6 pages, 5 figures, This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessibleSubjects: Artificial Intelligence (cs.AI); Information Theory (cs.IT); Signal Processing (eess.SP)
Token transmission over conventional digital modulation is vulnerable to channel impairments, leading to bit errors that cause received tokens to become contextually inconsistent. This paper proposes a receiver-side dual-stage channel-posterior integration framework for masked language model (MLM)-aided token reconstruction. In the proposed framework, the receiver detects unreliable token positions from channel reliability and constructs a vocabulary-level channel-posterior. In particular, within the receiver, Posterior-Weighted Input Embedding (PWE) injects this posterior into the MLM input, while Adaptive Output Logit Fusion (AOF) reuses it at the output with a channel-adaptive weight. Consequently, multiple unreliable tokens can be reconstructed in a single bidirectional MLM inference without retransmission, transmitter-side encoding, or additional MLM training. Experiments over noisy channels show up to a $67.2$\% improvement in cosine similarity over context-only MLM reconstruction, with consistent gains across different MLM architectures and existing language-model-aided methods.
- [33] arXiv:2611.19062 (cross-list from math.ST) [pdf, html, other]
-
Title: Log-optimal two-sample testing by bettingComments: 55pgsSubjects: Statistics Theory (math.ST); Information Theory (cs.IT); Methodology (stat.ME); Machine Learning (stat.ML)
For each standard Borel observation space, we construct a single anytime-valid two-sample procedure that is asymptotically log-optimal for every pair of unknown probability laws and every limiting ratio of diverging sample sizes, including zero and infinity. For independent balanced pairs, the optimal log-wealth rate is $2\JS(P,Q)$, where $\JS$ is the Jensen--Shannon divergence. Unequal sizes yield weighted Jensen--Shannon information and the one-sample limit $\log W(n_1,n_2)/n_2\to\KL(Q\|P)$ when $n_1/n_2\to\infty$. Refining finite partitions and logarithmic-loss learning with measurable characteristic kernels provide universal constructions. Our main contribution is the generality of our construction, and its connections to classical batch efficiency notions. Practical implementations allow continuous classifier fine-tuning, as demonstrated on finite alphabets, Gaussian data, and handwritten digits.
- [34] arXiv:2611.19192 (cross-list from eess.IV) [pdf, html, other]
-
Title: Zero-shot diffusion image compression with sectioned codebooks and one channel codeComments: 14 pages, 6 figures, 7 tablesSubjects: Image and Video Processing (eess.IV); Information Theory (cs.IT); Signal Processing (eess.SP)
Zero-shot diffusion codecs such as Turbo-DDCM compress images without any training. In each coded step, the encoder selects noise vectors from one codebook and transmits a single index for the selected set. We propose sectioned codebooks. A coded step is divided into sections, and each section has its own large codebook and transmits its best vector as a short field of bits. A model based on order statistics quantifies how well the bits of a step are used and predicts the gain of sectioned codebooks from measurements of Turbo-DDCM alone. Fast Walsh-Hadamard transforms make sections of $2^{20}$ vectors practical. At equal bits, sectioned codebooks improve the PSNR of Turbo-DDCM by 0.18 to 0.51 dB on three datasets, improve LPIPS and DISTS, and save 16 to 21% of the bits at equal PSNR. Codecs that are robust to channel errors by design are usually compared only with unprotected codecs. We compare them, at equal total bits, with a codec protected by one channel code. With one BCH code, the sectioned codec outperforms all reported results of Robust Turbo-DDCM and BitFlat on two datasets, by up to 7.74 dB at the highest bit error rate. At the lowest bit error rate its margin over BitFlat is only 0.08 to 0.16 dB. When the code fails, the receiver can still decode the fields as received. Additional experiments cover burst errors and packet loss, and all observed gains of robust codecs stay within a limit derived from the channel capacity.
- [35] arXiv:2611.19566 (cross-list from cs.LG) [pdf, html, other]
-
Title: Bellman Residual Bracketing: Resolving the Sample Complexity of Discounted and Average-Reward RLSubjects: Machine Learning (cs.LG); Information Theory (cs.IT); Optimization and Control (math.OC); Probability (math.PR); Machine Learning (stat.ML)
We study the sample complexity of the empirical planning or plug-in approach for reinforcement learning (RL) with a generative model. We show the discounted plug-in approach finds an $\varepsilon$-optimal policy with $O(SA (1-\gamma)^{-3} \varepsilon^{-2} \log(SA/\delta))$ samples, where $S, A, \gamma, \delta$ are the state and action sizes, discount factor, and failure probability, respectively. In the average-reward setting, we show that discounted plug-in and direct (undiscounted) plug-in achieve $O(SAH\varepsilon^{-2}\log(SA/\delta))$ and $O(SAD\varepsilon^{-2}\log(SA/\delta))$ complexities, respectively, where $H$ upper-bounds the optimal bias span and $D$ is the diameter. Combining with our lower bounds for nonadaptive generative models, these results resolve the minimax sample complexity of discounted RL and average-reward RL --- in both the span- and diameter-based classes --- up to constant factors. Our main technical contribution is a novel Bellman residual bracketing technique which improves the efficiency of prior absorbing-MDP-based concentration analyses.
- [36] arXiv:2611.20058 (cross-list from eess.SP) [pdf, html, other]
-
Title: SWAN-Rx: Efficient and Bandwidth-Scalable Neural Reception for MIMO-OFDMComments: This work has been submitted to IEEE for possible publicationSubjects: Signal Processing (eess.SP); Information Theory (cs.IT); Machine Learning (cs.LG)
We present a Scalable Windowed Axial-attention Neural Receiver (SWAN-Rx) for multiple-input multiple-output orthogonal frequency-division multiplexing (MIMO-OFDM) systems. The receiver improves reception accuracy and reduces forward-pass computation while supporting frozen-weight reuse across bandwidth allocations and channel conditions. It combines a common resource-element representation of received observations and pilot context with alternating time-axis and local frequency-axis attention. Shared parameters and relative positional information permit soft detection across allocation lengths without inference-time parameter updates. At fixed subcarrier spacing, model configuration, and symbol count, bounded frequency neighborhoods give linear growth of forward-pass computation with bandwidth. Evaluations compatible with the 5G New Radio physical layer reuse weights trained on four physical resource blocks (PRBs) at up to 273 PRBs and on unseen channels. At the training bandwidth, SWAN-Rx achieves lower pre- and post-decoding bit error rates than the implemented three-step neural receiver (NRX) and DeepRx-MIMO baselines, with 16.9% and 39.7% fewer parameters and 56.3% and 35.7% fewer forward-pass operations, respectively. The same weights achieve lower pre-decoding error rates than these baselines throughout the evaluated bandwidth-extrapolation and 16-PRB channel-transfer tests, with an estimated 0.4-0.9 dB signal-to-noise ratio reduction relative to NRX at a pre-decoding error rate of $10^{-2}$ in the 16-PRB tests.
- [37] arXiv:2611.20554 (cross-list from math.CO) [pdf, html, other]
-
Title: $L$-systems on the large Witt designComments: 14 pagesSubjects: Combinatorics (math.CO); Information Theory (cs.IT)
Let $L=\{0,1,2,3,4,8\}$, associated with the large Witt design $S(5,8,24)$, and let $m(n,24,L)$ be the maximum size of a family of $24$-element subsets of an $n$-element set whose distinct members have intersection sizes in $L$. We prove that there are positive constants $c,C,n_0$ such that, for every $n\geq n_0$, \[ cn^{316/63}\leq m(n,24,L)\leq Cn^{169/29}. \] We also obtain similar results for the systems associated with $S(4,7,23)$, $S(3,6,22)$, and $S(3,4,14)$. The upper bounds follow from a non-Shannon information inequality and disprove conjectures of Kupavskii and Terekhov. The lower bounds follow from an algebraic construction for arbitrary Steiner systems.
- [38] arXiv:2611.21389 (cross-list from quant-ph) [pdf, html, other]
-
Title: Vanishing Relative Distance of Uniformly Random CSS LDPC Codes Built from Permutation MatricesComments: 17 pages, 1 figureSubjects: Quantum Physics (quant-ph); Information Theory (cs.IT)
Classical random regular low-density parity-check codes can have minimum distance growing linearly with block length. We study CSS check matrices formed as full $J\times L$ arrays of arbitrary $P\times P$ permutation matrices, sampled uniformly subject to commutation. For fixed column weight $J\ge3$ and fixed even row weight $L>2J$, we prove that the relative minimum distance converges to zero in probability as $P\to\infty$, with block length $n=LP$. We analyze the weight enumerators that count all nontrivial logical representatives after excluding stabilizers. A coefficientwise lower bound shows that, at every fixed relative weight $0<\alpha<1$ along even-weight sequences, exponentially many such representatives exist with high probability. Their typical and mean counts have exponent lower bound $h_2(\alpha)/2$, where $h_2$ is the binary entropy function. We compare this bound with the classical LDPC and dense CSS mean weight-distribution exponents. The existence, with high probability, of a logical operator below every fixed target weight $\delta n$ yields the distance conclusion.
- [39] arXiv:2611.21500 (cross-list from quant-ph) [pdf, html, other]
-
Title: Exponential Quantum Memory Advantage for Late-Graph Smoothness and Spectral EstimationComments: 19 pages, 8 figuresSubjects: Quantum Physics (quant-ph); Information Theory (cs.IT); Signal Processing (eess.SP)
Graph signal processing tests how smoothly the decisions of next-generation massive sensor networks with $N$ nodes vary over their neighbour graph. Memory becomes the bottleneck when the neighbour graph arrives only after data erasure, a late-graph setting motivated by dispersed sensor networks and telemetry. We analyse three collection scenarios, reliable rounds, continuous broadcast and ordered capture, and test the Dirichlet energy $\mathcal E_G=\mathbf z^{\mathsf T}\mathbf L\mathbf z/N$ of the fused decision map $\mathbf z\in\{\pm1\}^N$, with late-graph Laplacian $\mathbf L$, against two thresholds. Hidden Matching uses $O(\log N)$ qubits on fused bits, but in reliable rounds and continuous broadcast, where nodes report $b$ sub-bits separately, a classical record buffer before it uses $O(N b)$ bits; classical methods need $\Omega(\sqrt N)$ bits in the worst case. The recently introduced Quantum Oracle Sketching builds quantum oracles from random data streams without storing them. We combine coherent loading of separately reported sub-bits, exact in reliable rounds and by Quantum Oracle Sketching in continuous broadcast, with nonlinear fusion and Hidden Matching readout. The register count $R$ does not grow with $N$, and the memory is $O(\log N)$ logical qubits and classical bits, at fixed $b$, graph bounds, thresholds and error targets: an exponential memory advantage over every classical receiver and over Hidden Matching with that buffer. We prove unbiasedness in reliable rounds, preparation bounds in continuous broadcast, classical lower bounds and, for a planner-supplied multi-hop coefficient stream, spectral error bounds. Broadcast simulations match analytic averages at $N=1024$, without resolved bias growth up to $N=2^{20}$. Fault-tolerant hardware, gate rates and, in continuous broadcast, report counts remain open.
- [40] arXiv:2611.21549 (cross-list from math.OA) [pdf, html, other]
-
Title: Axioms for relative entropyComments: 27 pagesSubjects: Operator Algebras (math.OA); Information Theory (cs.IT); High Energy Physics - Theory (hep-th); Mathematical Physics (math-ph)
For normal states of arbitrary von Neumann algebras, we characterize positive finite multiples of Araki relative entropy among non-degenerate divergences. The axioms are monotonicity under normal unital completely positive maps, tensor additivity, superadditivity for product second states, and separate lower semicontinuity in the predual norm. Alternatively, a conditional-expectation identity replaces the two tensor assumptions. The proof uses order bounds and asymptotic estimates on tensor powers. An appendix proves the known analytic estimates needed here, using standard modular theory and Haagerup L^p spaces. We also obtain the corresponding characterization in the C* algebraic setting.
Cross submissions (showing 12 of 12 entries)
- [41] arXiv:2405.06121 (replaced) [pdf, html, other]
-
Title: Secure Distributed Matrix Multiplication with PrecomputationRyann Cartor, Rafael G. L. D'Oliveira, Salim El Rouayheb, Daniel Heinlein, David Karpuk, Freeman Slaughter, Alex SprintsonComments: 16 pages, 4 figures, 2 tablesSubjects: Information Theory (cs.IT)
We consider secure distributed matrix multiplication, in which a user computes the product of two matrices with the help of honest-but-curious servers, any $T$ of which may collude. Using the outer-product partition, the matrices are split into $K$ and $L$ blocks and hidden by random masks. Assuming the user has precomputed the products of the random matrices, we develop methods that use this precomputation to reduce the number of servers required.
Polynomial codes are designed through degree tables, whose distinct entries count the servers. We show that precomputation can reduce the minimum number of servers by designing degree tables specifically for this setting. For Gap Additive Secure Polynomial (GASPr) codes, we give a precise formula and show that it is monotone in the chain length $r$, so only the extremes GASP_small and GASP_big matter. We also prove lower bounds attained by GASP_small in several regimes. Consequently, any fraction of colluding servers below one can be tolerated, compared to the threshold of one half without precomputation, and the order of the total computational complexity decreases when the colluders are a fixed fraction of the servers. We show that no existing construction uses fewer servers than the better of GASP_small and GASP_big once the mask products are precomputed.
We introduce Gap-Reduced Additive Secure Polynomial (GRASP) codes, which retain a single interval for the mask degrees while selecting the information degrees carefully. For $K = T = 4$ and every $L \geq 3$, we give an explicit GRASP code that uses one fewer server than every GASPr code and is within two servers of optimal. For large $T$, the configuration becomes an integer packing problem independent of $T$, and the number of servers saved by GRASP over GASPr grows quadratically in $K$ and $L$. - [42] arXiv:2504.02299 (replaced) [pdf, html, other]
-
Title: Asymmetric graph alignment and the phase transition for asymmetric tree correlation testingJournal-ref: Jakob Maier, Laurent Massouli\'e, Asymmetric graph alignment and the phase transition for asymmetric tree correlation testing. Math. Stat. Learn. 9 (2026), no. 3/4, pp. 247 to 335Subjects: Information Theory (cs.IT); Data Structures and Algorithms (cs.DS)
Graph alignment - identifying node correspondences between two graphs - is a fundamental problem with applications in network analysis, biology, and privacy research. While substantial progress has been made in aligning correlated Erdős-Rényi graphs under symmetric settings, real-world networks often exhibit asymmetry in both node numbers and edge densities. In this work, we introduce a novel framework for asymmetric correlated Erdős-Rényi graphs, generalizing existing models to account for these asymmetries. We conduct a rigorous theoretical analysis of graph alignment in the sparse regime, where local neighborhoods exhibit tree-like structures. Our approach leverages tree correlation testing as the central tool in our polynomial-time algorithm, MPAlign, which achieves one-sided partial alignment under certain conditions.
A key contribution of our work is characterizing these conditions under which asymmetric tree correlation testing is feasible: If two correlated graphs $G$ and $G'$ have average degrees $\lambda s$ and $\lambda s'$ respectively, where $\lambda$ is their common density and $s,s'$ are marginal correlation parameters, their tree neighborhoods can be aligned if $ss' > \alpha$, where $\alpha$ denotes Otter's constant and $\lambda$ is supposed large enough. The feasibility of this tree comparison problem undergoes a sharp phase transition since $ss' \leq \alpha$ implies its impossibility. These new results on tree correlation testing allow us to solve a class of random subgraph isomorphism problems, resolving an open problem in the field. - [43] arXiv:2511.06882 (replaced) [pdf, other]
-
Title: Rate-Optimal Streaming Codes Under an Extended Delay Profile for Three-Node Relay Networks With Burst ErasuresComments: There is a flaw in the proof of the main result (Theorem 4, Section V). The proposed code construction fails to achieve the claimed rate optimality under the burst erasure and delay model. This manuscript is withdrawn to avoid incorrect conclusions being citedSubjects: Information Theory (cs.IT)
This paper investigates streaming codes for three-node relay networks under burst packet erasures with a delay constraint $T$. In any sliding window of $T+1$ consecutive packets, the source-to-relay and relay-to-destination channels may introduce burst erasures of lengths at most $b_1$ and $b_2$, respectively. Let $u = \max\{b_1, b_2\}$ and $v = \min\{b_1, b_2\}$. Singhvi et al. proposed a construction achieving the optimal rate when $u\mid (T-u-v)$. In this paper, we present an extended delay profile method that attains the optimal rate under a relaxed constraint $\frac{T - u - v}{2u - v} \leq \left\lfloor \frac{T - u - v}{u} \right\rfloor$ and it strictly cover restriction $u\mid (T-u-v)$. %Furthermore, we demonstrate that the optimal rate for streaming codes is not achievable when $0< T-u-v<v$ under the convolutional code framework.
- [44] arXiv:2603.11714 (replaced) [pdf, html, other]
-
Title: Performance Analysis of Discrete-Phase Fluid Reconfigurable Intelligent Surface-Enabled Index ModulationPeng Zhang, Jian Dang, Miaowen Wen, Ziyang Liu, Kai-Kit Wong, Chen Zhao, Huaifeng Shi, Zaichen ZhangSubjects: Information Theory (cs.IT)
Fluid reconfigurable intelligent surfaces (FRIS) combine the position reconfigurability of fluid antennas (FA) with the phase control suburbs of reconfigurable intelligent surfaces (RIS). In this paper, we propose fluid-port-selected receive index modulation (FPS-RIM), which uses fluid-port selection as an additional spatial degree of freedom. Two operating modes are considered: FPS-RIM index-only (FPS-RIM-IO), which conveys information through the receive-antenna index, and FPS-RIM symbol-augmented (FPS-RIM-SA), which additionally conveys a constellation symbol. Under finite-resolution phase control, the active port and its quantized phase are jointly determined by the post-quantization in-phase component. A low-complexity Top-$L$ detector retains the receive-index candidates with the largest received energies and performs joint detection over the reduced candidate set. For spatially correlated FRIS cascaded channels, we derive selection-aware joint moments that account for phase quantization, fluid-port selection, and overlapping port selections between receive-index states. Correlated Gaussian distance models and quadratic-form Laplace transforms are then used to obtain unconditional pairwise error probabilities and a union-bound bit error rate expression. Numerical results show that fluid-port selection improves the error performance over conventional RIS schemes and that the proposed detector approaches maximum-likelihood performance with a moderate list size. The analytical results closely follow the simulations.
- [45] arXiv:2604.13511 (replaced) [pdf, html, other]
-
Title: Phase transition in compressed sensing using log-sum penalty and adaptive smoothingComments: 26 pages, 6 figuresSubjects: Information Theory (cs.IT); Disordered Systems and Neural Networks (cond-mat.dis-nn)
In many real-world problems, recovering sparse signals from underdetermined linear systems remains a fundamental challenge. Although $\ell_1$ norm minimization is widely used, it suffers from estimation bias that prevents it from reaching the Bayes-optimal reconstruction limit. Nonconvex alternatives, such as the log-sum penalty, have been proposed to promote stronger sparsity. However, maintaining their algorithmic stability is challenging. To address this challenge, we introduce an adaptive smoothing strategy within an approximate message passing framework to mitigate algorithmic instability. Furthermore, we evaluate the typical exact-recovery threshold for Gaussian measurement matrices using the replica method and state evolution. The results indicate that the adaptive method achieves exact recovery over a broader region than $\ell_1$-norm minimization, although metastable states hinder the attainment of the information-theoretic limit.
- [46] arXiv:2605.06710 (replaced) [pdf, other]
-
Title: Information-theoretic Limits of Learning and EstimationSubjects: Information Theory (cs.IT); Machine Learning (cs.LG); Statistics Theory (math.ST)
Information theory plays a central role in establishing fundamental limits on what any learning or estimation algorithm can -- and cannot -- achieve, regardless of computational power. This draft provides an introduction to these connections. We begin by introducing concentration inequalities along with the notions of covering and packing in metric spaces, and the associated concept of metric entropy. These tools are essential for our analysis. We then introduce the learning-theoretic framework and derive upper bounds on generalization error in terms of metric entropy, Rademacher complexity, and the VC dimension, as well as mutual information and relative entropy. Finally we discuss the minimax estimation framework and establish lower bounds on minimax risk using Fano's inequality, yielding bounds in terms of relative entropy and covering and packing numbers.
A significantly revised and augmented version of this manuscript will appear as two chapters in the forthcoming third edition of Cover and Thomas's Elements of Information Theory. For questions, please contact abbas@ee.this http URL. - [47] arXiv:2605.26163 (replaced) [pdf, html, other]
-
Title: Adversarial Water-Filling: Theory, Algorithms, and a Domain-Specific Wireless Foundation ModelComments: Published in IEEE Journal of Selected Topics in Signal ProcessingJournal-ref: IEEE Journal of Selected Topics in Signal Processing. Print ISSN: 1932-4553. Online ISSN: 1941-0484Subjects: Information Theory (cs.IT); Machine Learning (cs.LG); Optimization and Control (math.OC)
Competitive resource allocation problems over frequency and space can be formulated as a minimax interaction between transmit power and worst-case interference. This formulation naturally arises in multi-operator low Earth orbit (LEO) satellite spectrum sharing, where transmissions from competing constellations interfere in real-time. Under Gaussian channels, the corresponding power-allocation problem admits a convex-concave formulation with a unique saddle point. Discrete constellations yield generally nonconvex mercury/water-filling formulations. In this paper we propose the adversarial water-filling (AWF) problem with corresponding theory and algorithms for these settings. In addition, we develop a domain-specific wireless foundation model for AWF to learn the AWF search dynamics. The architecture incorporates permutation-invariant channel representations, a constraint-aware graph neural network (GNN) with sparse message passing, and global latent variables capturing the low-dimensional water level implied by the AWF optimality. Through learned projected extragradient iterations, the model approximates stationary solutions of the constrained minimax problem arising under mercury/water-filling. We further establish projected-stationarity/Karush-Kuhn-Tucker consistency and conditional local convergence of the learned AWF dynamics under local regularity and stability conditions. Experiments demonstrate empirical generalization across unseen problem sizes, constraint structures, discrete constellations, and channel-weighted objectives, while achieving a median speedup exceeding one order of magnitude over Mirror-Prox on matched instances at comparable first-order solution quality. The related code can be found at this https URL.
- [48] arXiv:2606.06307 (replaced) [pdf, html, other]
-
Title: A Spherical Stochastic Geometry Framework for Patrol-Based HAPs Network: Coverage and Energy Efficiency AnalysisSubjects: Information Theory (cs.IT)
This paper develops a stochastic geometry framework for high-altitude platform station (HAP) networks in which platforms execute cyclic patrol trajectories anchored to designated service regions. We introduce two small-circle ring point-process models on the spherical Earth. In the small-circle ring Poisson Cox process (SCR-PCP), platforms form one-dimensional Poisson point processes on localized patrol rings, whereas in the small-circle ring binomial cluster process (SCR-BCP), each ring contains a fixed number of uniformly distributed platforms. We establish the isotropy of both models and derive spatial statistics, including the distributions of the nearest-anchor, nearest-ring, and nearest-HAP distances, together with the serving-ring angle distribution. Building on these results, we derive coverage probability expressions under nearest-visible-HAP association by decomposing aggregate interference into same-ring and other-ring components and characterizing their conditional Laplace transforms. To account for the flight dynamics of patrol-based HAPs, we integrate a steady circular flight propulsion model with the communication analysis and introduce a coverage energy efficiency (CEE) metric. This yields a necessary optimality condition for an interior energy-optimal patrol radius that balances coverage performance against the propulsion cost of circular flight. Numerical results reveal fundamental differences between intensity-driven (SCR-PCP) and finite-fleet (SCR-BCP) deployments and demonstrate that patrol geometry, platform density, and cruising velocity should be jointly considered to achieve energy-efficient HAP operation.
- [49] arXiv:2606.08750 (replaced) [pdf, html, other]
-
Title: New Codes from Cyclic and Negacyclic Codes of Even Length over $\mathbb{Z}_4$Subjects: Information Theory (cs.IT); Combinatorics (math.CO)
This paper uses theoretical results previously established in the literature to design search algorithms to find new linear codes over $\mathbb{Z}_4$ from cyclic and negacyclic codes of even length. As a result of these searches, we have found 2500 new cyclic codes and 730 negacyclic codes. These new codes exhibit improved parameters compared to previously known codes. Additionally, we have obtained binary quantum codes with good parameters from such $\mathbb{Z}_4$ codes.
- [50] arXiv:2607.16983 (replaced) [pdf, html, other]
-
Title: Transmit Coefficients and Receive Combining Vector Design for OTA-FL with Imperfect CSISubjects: Information Theory (cs.IT); Systems and Control (eess.SY)
Over-the-air (OTA) computation has recently gained significant attentions as an effective approach to enhance the communication efficiency of wireless federated learning (FL). By enabling simultaneous transmission and aggregation of local model updates, OTA-FL can substantially reduce both latency and bandwidth consumption. However, a key challenge lies in the imperfect aggregation of global models caused by channel state information (CSI) uncertainty, which introduces distortion to the final learning performance. To address this issue, we study the long-term mean squared error (MSE) minimization problem for OTA-FL under imperfect CSI conditions. Through convergence analysis, we establish an upper bound for the time-averaged MSE, thereby revealing the effect of aggregation errors accumulated throughout multiple communication rounds on the overall training performances. Based on this analysis, an optimization framework is developed to minimize the long-term MSE via the joint design of (i) transmit coefficients at the local devices and (ii) receive combining vectors at the parameter server (PS). Since this alternating optimization approach requires non-causal CSI, a Lyapunov-based optimization method is further introduced to handle causal CSI scenarios. By incorporating virtual queues to characterize long-term energy consumption, the proposed method effectively decouples temporal dependencies and allows transmit coefficients to be optimized based on the causal CSI of each aggregation round. Comprehensive evaluations on Fashion-MNIST, CIFAR-10 and CIFAR-100 datasets have demonstrated that the proposed algorithms can significantly reduce the degradation of test accuracy caused by imperfect CSI. Comparisons with other benchmark schemes further verify the superiority of our proposed algorithms.
- [51] arXiv:2608.02760 (replaced) [pdf, html, other]
-
Title: Speculative Successive Cancellation Decoding of Polar CodesComments: 12 pages, 10 figures, submitted to IEEE for possible publicationSubjects: Information Theory (cs.IT); Signal Processing (eess.SP)
Polar codes achieve channel capacity as block length increases, but this asymptotic advantage comes at the cost of decoding speed: the conventional \ac{SC} algorithm is inherently sequential, which limits its practicality for high-throughput applications. This work addresses that limitation by introducing the \emph{\ac{Spec-SC}} framework, which incorporates speculative execution into the \ac{SC} decoding process. While \ac{sp-node}-based decoders enable partial parallelism for specific, predefined structures, \ac{Spec-SC} extends this capability by permitting parallel execution in general nodes that do not match any \acs{sp-node} pattern. A built-in verification mechanism ensures that this speculation does not compromise decoding correctness. Simulation results show that \ac{Spec-SC} achieves the same \acs{BER} and \acs{FER} performance as conventional \ac{SC} decoding, while reducing the average number of sequentially traversed nodes by up to $69\%$ for a polar code of length $N=4096$. A cycle-level analysis further shows that, for $\Pc(4096,3584)$ at $5\,\mathrm{dB}$, a heterogeneous four-core configuration achieves a $1.57\times$ decoding speedup using a total of $2944$ processing lanes, representing a $43.75\%$ increase over the $N_{\mathrm{lane}}=2048$ one-core \ac{SC} baseline. The speedup increases to $2.5\times$ at $7\,\mathrm{dB}$, demonstrating the increasing effectiveness of speculation at higher $\EbNo$. These results demonstrate that \ac{Spec-SC} enables additional algorithm-level parallelism beyond conventional \ac{sp-node}-based decoding, motivating its further investigation for high-throughput and high-reliability communication systems. achieve, paving the way for speculative hardware decoder implementations.
- [52] arXiv:2608.09115 (replaced) [pdf, html, other]
-
Title: Quantum Bicycle LDPC Codes with High $kd^2/n$ from Divisor-Driven SearchComments: v3: corrected the entry for the code [[90,16,7]] in Table I and added one line to the AcknowledgmentSubjects: Information Theory (cs.IT); Quantum Physics (quant-ph)
Bicycle (two-block circulant) quantum low-density parity-check (LDPC)codes include some of the best known small quantum codes, yet their design has relied on group-algebra formulations in which the dimension and distance are accessible only through matrix computation. We show that in the cyclic case the construction collapses into the polynomial ring $\F_2[x]/(x^{l}-1)$: self-orthogonality is automatic, the quantum dimension is read off from a polynomial gcd, and the minimum distance is certified exactly through the Calderbank correspondence to additive codes over $\F_4$, turning code search into an algebraically pre-filtered enumeration that reaches parameter regimes poorly covered by existing tables. A computer search based on this framework recovers the short codes $[[42,12,4]]_2$ and $[[62,12,4]]_2$ and produces a family of codes with competitive figure of merit $kd^2/n$, including $[[66,20,7]]_2$ with $kd^2/n=14.85$, above the bivariate bicycle code $[[144,12,12]]_2$ ($kd^2/n=12$) at less than half the block length, together with $[[46,2,8]]_2$, $[[66,2,9]]_2$, $[[66,4,8]]_2$, $[[66,6,8]]_2$ and, at $n=90$, $[[90,16,7]]_2$, $[[90,18,6]]_2$, $[[90,20,6]]_2$. An exhaustive census at $n=48$ delineates the boundary of this picture: we exhibit a $[[48,10,6]]_2$ code from a minimal $48$-element group (the Aydin--Tamo--Barg realization uses $72$ elements), and prove that distance $5$ forces a stabilizer-rank loss, which excludes $[[48,10,5]]_2$ from the weight-$8$ symmetric coset family. The framework thus opens a systematic route to bicycle-type quantum LDPC codes beyond the reach of group-theoretic searches, and identifies exactly where genuinely coset-theoretic phenomena begin.
- [53] arXiv:2608.27909 (replaced) [pdf, html, other]
-
Title: Low-Altitude Fluid Antenna Network with Multi-Agent Reinforcement LearningComments: Accepted by IEEE Communications MagazineSubjects: Information Theory (cs.IT); Artificial Intelligence (cs.AI)
Low-altitude wireless networks (LAWNs) integrate terrestrial and aerial platforms to provide ubiquitous communication, sensing, and localization services for unmanned aerial vehicles (UAVs) and electric vertical takeoff and landing (eVTOL) aircraft. However, dynamic air-ground and air-air channels, abrupt blockages, and heterogeneous interference hinder the realization of this goal. Nevertheless, fluid antenna (FA), a cutting-edge multiple-input multiple-output (MIMO) technique, overcomes these challenges by reconfiguring antenna positions to unlock additional spatial degrees-of-freedom. In this paper, towards bringing low-altitude FA networks into reality, we study the fast and high-performance FA reconfiguration for low-altitude FA networks with multi-agent reinforcement learning (MARL). Specifically, we present an electromagnetic digital twin (EM-DT)-assisted MARL framework. To fill the sim-to-real gap, we introduce a two-stage transfer learning framework. Our case study shows that joint FA positions and beamforming optimization can enhance the system sum-rate by 118.5%, compared to the fixed position baseline. This gain comes from the dynamic millisecond timescale reconfiguration of FA arrays and the adaptive steering of beams toward aerial users with mobility.
- [54] arXiv:2609.05771 (replaced) [pdf, other]
-
Title: Moments of crosscorrelation demerit factors of binary sequencesComments: 32 pagesSubjects: Information Theory (cs.IT); Discrete Mathematics (cs.DM); Signal Processing (eess.SP); Combinatorics (math.CO); Probability (math.PR)
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$.
- [55] arXiv:2609.18352 (replaced) [pdf, html, other]
-
Title: Information Spectrum Methods for Multiple-Access Channels--Part I: $\varepsilon$-Capacity Regions in the Mixed Gaussian CaseComments: 30 pages, 3 figuresSubjects: Information Theory (cs.IT)
We study the {\epsilon}-capacity regions of mixed multiple-access channels (MACs) with general mixture and cost constraints by the information spectrum method. The starting point is a general formula for the {\epsilon}-capacity region of general MACs with cost constraint, together with the random-coding and converse lemmas from which it is derived. For the quasi-static fading Gaussian MAC, with random fading coefficients and noise variance, we show that the {\epsilon}-capacity region is the {\epsilon}-outage capacity region, which gives the latter a Shannon-theoretic operational meaning. The direct part follows from the general formula, and the converse part from the strong converse property of the Gaussian MAC, which is stronger than the {\epsilon}-strong converse, applied to each component. The {\epsilon}-capacity regions coincide in all four scenarios of availability of channel state information (CSI), and the results extend to K users. With CSI at both terminals, variable-rate coding enlarges the 0-capacity region to the polymatroid whose rank function is the average of those of the components. For mixed MACs with general components and a countable parameter space, CSI at the receiver alone never enlarges the {\epsilon}-capacity region, and the region with CSI at the transmitters is given by an information spectrum formula; unlike the Gaussian case, the regions with and without CSI at the transmitters may differ. For uncountable parameter spaces, only the formula for the region with CSI at both terminals survives in general. Parts II and III treat finite-alphabet mixed MACs and the strong converse for the K-user Gaussian MAC, respectively.
- [56] arXiv:2610.10235 (replaced) [pdf, html, other]
-
Title: Beyond LLM-GA: Secure Fluid Antenna Systems with ReEvo-Designed Memetic AlgorithmComments: Accepted by WCSP 2026Subjects: Information Theory (cs.IT); Artificial Intelligence (cs.AI)
Fluid antenna systems (FASs) offer significant spatial flexibility, yet securing them against eavesdropping is critical for practical FAS deployment in military, satellite, and internet-of-things networks. Although large language model (LLM)-assisted genetic algorithms (LLM-GAs) can address this secure FAS port selection problem, whether further algorithmic improvement is possible warrants deeper investigation. To this end, we propose a memetic algorithm based on reflective evolution (ReEvo). Unlike the state-of-the-art LLM-GAs, which design only crossover or mutation operators with an LLM, our algorithm leverages an LLM to evolve dedicated crossover, mutation, and local-search operators offline. These operators are then embedded into a memetic search framework, thereby obviating any online LLM queries during execution. Simulation results at equal generation counts demonstrate that our proposed algorithm achieves a higher secure sum-rate than the conventional GA and the state-of-the-art LLM-GAs.
- [57] arXiv:2610.26396 (replaced) [pdf, other]
-
Title: The Exhaustive Peres Transform: Extraction and Universal CodingAur{é}lien Garivier (UMPA-ENSL, MC2)Subjects: Information Theory (cs.IT)
Run to exhaustion, Peres's iteration of von Neumann's procedure yields a bijection of {0,1}^N that splits every string into fair bits and a residual. The residual is self-delimiting and determines the number of ones, so the fair bits are exactly uniform given the residual under every exchangeable law. Each residual one accounts for a power of two of the weight of the input, and the residual of every input of length N has fewer than sqrt(3) N^0.793 ones. This sparsity gives a short proof, with an explicit remainder, that the fair bits per symbol tend almost surely to the entropy for Bernoulli sources and every finite alphabet. The Bernoulli likelihood factorises along the recursion, and code B, which codes the residual at plug-in biases, has the length of the two-part code. Code G gamma-codes the gaps of the residual, with no estimate and no arithmetic coder: on every string its length is at most the logarithm of the type class plus O(N^0.793 log N). What is more, a concatenation of J pieces costs its piecewise empirical entropy plus a term that is sublinear when J = o(N), without the cuts being sent. After a Burrows-Wheeler transform of the reversed string, both codes are universal for stationary ergodic sources: code B through a context tree of growing depth, with regret O(2^k log N) against Markov sources of order k, and code G with no tree, competing on every individual sequence with the empirical conditional entropy of every order. For laws invariant under permutations inside the pieces of a partition, the fair bits not mixed across the pieces are exactly uniform given everything else; after the BWT, the fair bits of every stationary source fall short of their length by o(N) bits of entropy, with an exponential tail for Markov sources. Experiments measure the finite-length price of these guarantees.
- [58] arXiv:2610.34377 (replaced) [pdf, html, other]
-
Title: Minimum Extension Degrees for Reed-Solomon Codes:Exact Values and a Quadratic TransitionComments: 34 pagesSubjects: Information Theory (cs.IT)
We study the minimum extension degree of Reed-Solomon codes admitting exact linear repair of every failed coordinate from any $d$ surviving coordinates at the cut-set bound. Write $s=d-k+1$, and let $Q_s(n)$ be the minimum product of $n$ pairwise coprime integers, each at least $s$. We locate the transition for the formula $sQ_s(n)$ near $n=d^2$: for every fixed $0<\varepsilon<1$ and sufficiently large $d$, the formula is exact up to $(1-\varepsilon)d^2$, whereas strict improvement is possible at every length at least $(1+\varepsilon)d^2$, uniformly over the base field and code dimension. The lower bound follows from an inequality for the cost of residual prime powers; the upper bound follows from an existing affine-plane construction. We also show that the full-helper coordinate-count bound is attained over sufficiently large base fields. Finally, nonlinear repair at cut-set equality induces linear repair over the prime field. Thus the degree bounds over that field remain valid, and the same transition holds when the repair base field is prime.
- [59] arXiv:2611.00082 (replaced) [pdf, html, other]
-
Title: Applying Changes to LDPC Codes by Using 3-Induced Matchings and EigenvaluesComments: Minor revisions and an additional figureSubjects: Information Theory (cs.IT); Combinatorics (math.CO)
The 2-switch operation for reducing the number of short cycles in Tanner graphs of LDPC codes has been utilized in some works. If this operation is appropriately applied to a 2-induced matching in a bipartite graph, then it surely preserves the bipartiteness of the graph. With a 2-induced matching, we have only one choice for applying this type of change to the graph. Using 3-induced matchings creates more potential and flexibility to apply certain changes to the Tanner graph. We present a necessary and sufficient condition for the existence of a 3-induced matching in bipartite graphs with girth at least 6. A 3-induced matching helps us to have more choices for applying a change to a bipartite graph while surely preserving the bipartiteness of the graph and keeping the degree sequences unchanged. Among all changes that we consider, we select the best change for reducing the number of cycles of length 6. The eigenvalues of subgraphs are used to reach a 3-induced matching, and a condition in some steps can be checked to ensure that the subgraph has at least one 3-induced matching. We present some numerical results regarding the steps at which the condition that guarantees the existence of a 3-induced matching is checked.
- [60] arXiv:2611.11461 (replaced) [pdf, html, other]
-
Title: Sharp Rates for Optimal Recovery of Bandlimited Functions from Localized OversamplingComments: 26 pages, 2 figures. Expanded discussion of earlier work on one-sided recovery; added an extrapolation remark and contour figures; corrected the abstract and notation and streamlined proofs. The main sharp recovery estimates are unchangedSubjects: Information Theory (cs.IT); Classical Analysis and ODEs (math.CA)
It is well-known that one can recover a function $f$ bandlimited to $[-\delta,\delta]$ ($0<\delta<\pi$) from its finite oversampling data $f(j),-n+1\le j\le n$, with an approximation error exponentially decaying to zero as $n$ tends to infinity. Various regularized Shannon sampling formulas have been proposed to achieve such exponential approximation. A recent sinh regularized formula achieved so far the best rate $$ O(\frac1{\sqrt{n}}\exp(-(\pi-\delta)n)). $$ We establish that the optimal recovery algorithm in the worst-case scenario achieves an approximation error $\rho_{n,\delta}$ satisfying $$ \frac{c_*}{\sqrt{n}}(\tan\frac\delta 4)^{2n+1/2}\le \rho_{n,\delta}\le \frac{C_*}{\sqrt{n}}(\tan\frac\delta 4)^{2n+1/2}, 0<\delta\leq\pi, n\geq1, $$ where $c_*,C_*$ are explicit positive constants independent of $n$ and $\delta$. This result identifies the best possible exponential rate to reconstruct bandlimited functions from two-sided finite oversampling data. In other words, $$ \rho_{n,\delta} \asymp \frac{\sqrt{\tan\frac\delta 4}}{\sqrt{n}}\exp(-c_\delta(\pi-\delta)n), $$ where $c_\delta$ is strictly decreasing on $(0,\pi]$ and $$ \lim_{\delta\to\pi^-}c_\delta=1,\ \lim_{\delta\to 0^+}c_\delta=+\infty. $$ For one-sided sample data $f(j)$, $-n+1\le j\le 0$, we also obtain the sharp approximation order of optimally recovering function values on $[0,1]$: $$ \rho_{n,\delta}^-\asymp \sqrt{\delta/\pi}\sin^n(\delta/2),\ 0<\delta<\pi,\ n\ge1, $$ which improves the celebrated result of H. J. Landau on extrapolation of bandlimited functions.
- [61] arXiv:2611.15128 (replaced) [pdf, html, other]
-
Title: Affine Combiners for Reed-Solomon Proximity GapsSubjects: Information Theory (cs.IT); Computational Complexity (cs.CC); Cryptography and Security (cs.CR)
Reed-Solomon proximity gaps establish soundness guarantees for protocols that test received words through random combinations. For length-$n$ codes over $\mathbb{F}_q$, classical scalar combiners achieve error $O(n/q)$ in the unique-decoding regime, with larger known bounds near the Johnson radius.
We prove smaller error bounds using affine combiners, which combine two received words $f,g$ as $f(x)+(\alpha+\beta x)g(x)$, where $\alpha,\beta$ are independent uniform elements of $\mathbb{F}_q$. For output degree bound $d=\rho n$, fixed $\rho\in(0,1)$ and $0<\eta<1-\sqrt{\rho}$, and sufficiently large block length $n$, we prove mutual correlated agreement (MCA) with one coordinate of agreement loss at threshold $A=\lceil(\sqrt{\rho}+\eta)n\rceil$, with error $O_{\rho,\eta}\left(\frac{1}{q}+\frac{n^2}{q^2}\right)$. The result holds over arbitrary evaluation domains in every finite field, including prime and binary extension fields. The agreement threshold can approach the Johnson threshold, beyond unique decoding.
For $q\ge n^2$, our error is $O_{\rho,\eta}(1/q)$, an asymptotic factor-$n$ separation from scalar combiners: we prove that their worst-case MCA error is $\Omega_{\rho,\eta}(n/q)$ at the same agreement threshold and with the same one-coordinate loss. We also prove that affine combiners incur worst-case error $\Omega_{\rho,\eta}(n/q)$ when no agreement loss is allowed. Thus one coordinate of agreement loss is necessary for our guarantee; this relaxation of standard MCA reduces the guaranteed common agreement fraction by at most $1/n$. We also extend the result to $k$-variate Reed-Muller codes on subfield grids, obtaining MCA error $O_{\rho,\eta,k}(q^{-k})$ for fixed $\rho,\eta,k$, sufficiently large $n$, and $q\ge n^{k+1}$, with agreement loss $n^{1-1/k}$. - [62] arXiv:2611.16653 (replaced) [pdf, html, other]
-
Title: Information Spectrum Methods for Multiple-Access Channels --Part II : $\varepsilon$-Capacity Regions in the Mixed Finite-Alphabet CaseComments: 27 pages, 2 figuresSubjects: Information Theory (cs.IT)
In a nonergodic channel such as a slowly fading link, the channel law is drawn once and held fixed for the whole codeword, and the relevant performance measure is the $\varepsilon$-capacity. We study the $\varepsilon$-capacity regions of two-user mixed multiple-access channels (MACs) with finite alphabets, additive cost constraints and an arbitrary mixing measure. The direct parts are derived from a single information spectrum formula; the converse parts use, in addition, Fano's inequality and Ahlswede's strong converse applied to each component. Without knowledge of the realized component, we prove a single-letter inner bound for every $0\le\varepsilon<1$, in which one input serves all components; for $\varepsilon=0$ it is tight, and the capacity region is given by the essential infima of the component mutual informations. We prove a single-letter outer bound, the outage region, in which each component may use its own input; it holds with or without channel state information (CSI) at either terminal, and it is the $\varepsilon$-capacity region when the encoders know the component and the parameter space is countable. Both bounds coincide, in all four CSI scenarios, for well-ordered mixed MACs, which include degradedly ordered families and mixtures with a common optimal input, such as mixed additive MACs. Without CSI the outer bound can be strictly loose, and the no-CSI $\varepsilon$-capacity region for $0<\varepsilon<1$ remains open in general. Finally, we extend Ahlswede's strong converse to $K$ users with cost constraints and show that most of these results extend to $K$-user mixed MACs.
- [63] arXiv:2611.16664 (replaced) [pdf, html, other]
-
Title: Information Spectrum Methods for MUltiple-Access Channels--Part III : The Strong Converse in the $K$-User Gaussian CaseComments: 13 pages, 0 figuresSubjects: Information Theory (cs.IT)
This paper, Part III of a series, treats $K$-user multiple-access channels (MACs). Its starting point is a pair of fundamental lemmas, a random-coding lemma of Feinstein type and a converse lemma of Verdú--Han type, which are the $K$-user extensions of the two lemmas underlying Han's information spectrum approach to the general two-user MAC. From them we derive the capacity region of the general $K$-user MAC with cost constraint and show that it contains the polymatroid capacity region of the $K$-user Gaussian MAC. We then prove, by an elementary information spectrum calculation that adapts a diffuse--exceptional subspace decomposition used in recent second-order converses for the Gaussian MAC, that for every subset $\cS$ of users and every independent input satisfying the power constraints, the conditional information spectral-sup rate of the $K$-user Gaussian MAC does not exceed $\frac12\log(1+P_\cS/N)$, where $P_\cS$ is the total power of the users in $\cS$, with a probability bound that does not depend on the input. Consequently, the strong converse for the $K$-user Gaussian MAC, in the sense that the error probability tends to one for every rate tuple outside the capacity region, follows directly from the converse lemma, without the wringing technique and without hypothesis-testing meta-converses. This strong converse was first established by Fong and Tan, whose per-blocklength bounds yield it, through wringing and quantization. It is the key ingredient in the converse parts of the coding theorems for mixed Gaussian MACs in Part I, where the $\varepsilon$-strong converse would not suffice.
- [64] arXiv:2506.16250 (replaced) [pdf, html, other]
-
Title: Graph-Cover-based Characterization of the Bethe Partition Function of Double-Edge Factor GraphsComments: arXiv admin note: substantial text overlap with arXiv:2412.05942Subjects: Quantum Physics (quant-ph); Information Theory (cs.IT)
For standard factor graphs (S-FGs), whose local functions are nonnegative-real valued, a popular approximation of the partition function is given by the Bethe approximation, which is also known as the Bethe partition function. Vontobel gave a combinatorial characterization of the Bethe partition function with the help of graph covers. The proof of this characterization heavily relied on the method of types.
In this paper, we study double-edge factor graphs (DE-FGs), whose local functions are complex valued and satisfy certain positive-semidefinite constraints. DE-FGs and their partition functions are particularly relevant to quantum information processing. Approximating the partition function of a DE-FG is more difficult than approximating the partition function of an S-FG because the DE-FG partition function is a sum of complex values rather than nonnegative-real values.
We develop a Bethe approximation of the partition function of a DE-FG based on sum-product-algorithm (SPA) fixed points. However, one cannot directly apply the method of types to prove a similar graph-cover-based combinatorial characterization of the Bethe partition function as in the case of S-FGs.
Despite this, we establish such a combinatorial characterization for a class of DE-FGs that satisfy an easily checkable condition. Towards proving this characterization, we apply a suitable loop-calculus transform (LCT) to DE-FGs. Originally, the LCT was introduced by Chertkov and Chernyak as a special linear transform for S-FGs and later extended by Mori. Our proposed LCT is applicable to both S-FGs and DE-FGs and generalizes prior versions by handling zero-valued SPA fixed-point message components, which are common in DE-FGs.
Supported by numerical results, we conjecture that the graph-cover-based combinatorial characterization of the Bethe partition function holds more broadly for DE-FGs. - [65] arXiv:2512.24860 (replaced) [pdf, html, other]
-
Title: Approximate Computation via Le Cam SimulabilitySubjects: Statistics Theory (math.ST); Computational Complexity (cs.CC); Information Theory (cs.IT)
We propose a decision-theoretic framework for computational complexity, complementary to classical theory: moving from syntactic exactness (Turing / Shannon) to semantic simulability (Le Cam). While classical theory classifies problems by the cost of exact solution, modern computation often seeks only decision-valid approximations. We introduce a framework where "computation" is viewed as the efficient simulation of a target statistical experiment within a bounded risk distortion (Le Cam deficiency).
We formally define computational deficiency ($\delta_{\text{poly}}$) and use it to construct the complexity class LeCam-P (Decision-Robust Polynomial Time), characterizing problems that may be syntactically hard but semantically easy to approximate. We show that classical Karp reductions can be viewed as zero-deficiency simulations, and that approximate reductions correspond to bounded deficiency. Furthermore, we establish the No-Free-Transfer Inequality, showing that strictly invariant representations inevitably destroy decision-relevant information. This framework offers a statistical perspective on approximation theory, bridging the gap between algorithmic complexity and decision theory. - [66] arXiv:2601.18879 (replaced) [pdf, html, other]
-
Title: Multivariate Multicycle Codes for Complete Single-Shot DecodingSubjects: Quantum Physics (quant-ph); Information Theory (cs.IT)
We introduce multivariate multicycle (MM) codes, a Koszul-complex formulation of abelian multicycle (AMC) codes, which are multidimensional scalar lifted-product codes over a finite abelian group algebra, that unifies bivariate bicycle, multivariate bicycle, abelian two-block group algebra, generalized bicycle, trivariate tricycle, and toric codes. MM codes are Calderbank-Shor-Steane (CSS) codes defined from length-$(t+1)$ chain complexes, and for $t\geq4$ they possess metachecks for both types of checks, which can be used for single-shot decoding. We offer a framework that facilitates the construction of long-length chain complexes through the use of the Koszul complex. In particular, obtaining explicit boundary maps (parity check and metacheck matrices) is particularly straightforward in our approach. We also determine when an MM code encodes logical qubits, count the independent check relations not generated by its metachecks, and show that middle-degree codes with even $t$ have equal $X$ and $Z$ distances. This simple but very general parameterization of codes permitted us to efficiently perform a numerical search, where we identify several MM code candidates with high rates and high code distances. Examples of new codes with parameters $[[n,k,d]]$ include $[[96,12,8]]$, $[[144,12,12]]$, $[[486,24,12]]$, $[[630,70,9]]$, and $[[648,60,9]]$. For selected codes, we report confinement profiles and study single-shot and few-shot decoding under phenomenological and circuit-level noise. Our codes also include explicit collapsed 5D through 9D instances, and our 5D instances have check weights lower than those of recent small instances of quantum Tanner codes.
- [67] arXiv:2604.06974 (replaced) [pdf, html, other]
-
Title: The Gaussian data assumption does not always lead to the largest Cramér-Rao boundSubjects: Signal Processing (eess.SP); Information Theory (cs.IT)
This lecture note addresses the common misconception that the Gaussian distribution always yields the largest Cramér-Rao Bound (CRB). We show that this property only holds under restrictive conditions: specifically, when the mean and covariance parameters are decoupled in the Fisher Information Matrix (FIM), when the parameter of interest lies in the mean vector and when there are no additive nuisance parameters. Beyond this framework, we provide counterexamples demonstrating that non-Gaussian distributions can produce larger CRB.
- [68] arXiv:2611.04863 (replaced) [pdf, html, other]
-
Title: Geometric Obstructions and Sharp Genus Dependence in LCD ScalingsComments: All comments are welcomeSubjects: Algebraic Geometry (math.AG); Information Theory (cs.IT)
We study the least pole order of a rational function whose nonzero evaluations scale a prescribed code to a Euclidean LCD code. A residue-one differential yields an obstruction for odd-dimensional one-point AG codes in characteristic two: for $C=C_L(D,aQ)$ with $0\le a<n$ and odd dimension, the threshold is at least $n+2g-a-1$. The obstruction uses alternating Gram matrices and does not require the scaled code to be self-orthogonal. For the dimension-three codes $C_L(D,(r+1)Q)$ on Hermitian curves over $\F_{r^2}$, $r=2^e\ge4$, we obtain \[ n+2g-r-2\le\tau_D(C;Q)\le n+2g-3. \] Consequently the leading genus contribution is asymptotically sharp even in dimension three. On the elliptic curve $y^2+y=x^3$ over $\F_4$, we prove the exact dimension-three threshold $6$ by an explicit multiplier. For repetition codes on the Hermitian family, the threshold equals the general interpolation bound $n+2g-1$. The upper bounds use information sets and hold for $q>3k$, and for $q>2k$ in characteristic two.
- [69] arXiv:2611.06470 (replaced) [pdf, html, other]
-
Title: How many sorted projections determine any n points in k dimensions?Comments: 30 pages, 5 figures. v2: added word "any" to title, improved a bound following comment from ZM26, added three small special cases, removed unicode from an anc file, and added a statement about deep setsSubjects: Combinatorics (math.CO); Discrete Mathematics (cs.DM); Information Theory (cs.IT); Machine Learning (cs.LG)
Let $d_1,\dots,d_m$ be directions in $\mathbb{R}^k$, where $k\ge 2$. A multiset $X$ of $n$ points of $\mathbb{R}^k$ projects to the $m$ multisets of numbers $\{\{x\cdot d_j : x\in X\}\}$, or equivalently to the $m$ sorted lists of these numbers. How many directions are needed for these projections to determine every multiset of $n$ points? Two simple bounds are known in every dimension: more than $(k-1)\log_2 n$ directions are always needed, and $(k-1)n+1$ directions in general position always suffice. In the plane much more is known: Matousek, Privetivy and Skovron showed that almost every choice of $O(\log n \log\log n)$ directions suffices. Whether anything similar holds in higher dimensions was left open by Dym, Wellershoff, Tsoukanis, Levy and Balan. We observe that two lemmas of Hair and Sahai, proved for list recovery of random linear codes, answer that question, and by tightening their argument we show that in every dimension almost every choice of $(4k-2)\ln(2n)\ln(k\log_2 2n)+k+1$ directions suffices. For $k\le 10$ this beats the linear bound once $n$ is larger than about 100: for example, 144 directions suffice for multisets of 1000 points in the plane, and an exact computation lowers this to 133. Letting some of the random blocks in their argument fail removes a factor $\log k$: almost every choice of $O(k\log n\log\log n)$ directions suffices, uniformly in $k$ and $n$. We also show that $2k-1$ directions never determine three points, so that the logarithmic lower bound is not tight; that every $m$ directions in the plane fail on some pair of multisets of size $O(1.65^m)$, improving the bound $O(1.80^m)$ of Matousek, Privetivy and Skovron; and that for each $k$, $m$ and $n$, either almost every choice of $m$ directions works or almost none does.