Andrea Novero, Mudasir Ahmad Sheikh, Danish Nisar, Saif Khan Mohammed, Michele Zorzi, Robert Calderbank
Delay-Doppler (DD) modulations, such as Zak-transform-based orthogonal time frequency space (Zak-OTFS) modulation, represent the channel as a sparse set of delay and Doppler shifts, which makes them well suited for radar sensing. Sensing with a single DD frame, however, is unambiguous only when the channel spread factor, i.e., the product of the delay and Doppler spreads, is below one. Long-range mobility scenarios, including drones, airplanes, low Earth orbit (LEO) satellites, and underwater acoustic links, typically violate this crystallization condition, so that a single frame aliases the target delays, Doppler shifts, or both. Existing methods add a time-frequency pilot to a conventional DD frame and resolve the aliasing in only one dimension. We propose a frame design that combines multiple DD bases with different delay and Doppler periods, which together cover an overspread channel, on the same bandwidth and frame size. For two frames, we show that modular arithmetic on the wrapped peak positions uniquely recovers each target by pairing the peaks through their common projection and their gains, and we derive the condition under which this pairing is ambiguous. We implement the design with two superimposed Zak-OTFS frames and propose two receivers: dual-frame sensing (DS), which performs the joint detection directly, and DS with cross-pilot cancellation (DS-XC), which additionally cancels the cross-pilot interference, re-estimates the gains by joint least squares, and removes ghost targets. Both receivers keep a detection rate close to one as the spread factor grows, and DS-XC also achieves the lowest false-alarm rate and channel normalized mean squared error (NMSE). In a 100 km drone scenario, DS-XC detects 98% of the targets, compared with 81% for the best baseline, with a complexity that grows near-linearly with the time-bandwidth product for a fixed number of targets.
Nizar Khalfet, Francisco A. Monteiro, Ioannis Krikidis
This paper investigates a quantum relay-assisted free-space optical (FSO) communication system in which a decode-and-forward relay is powered by time-switching optical energy harvesting and forwards the decoded information using displaced squeezed signaling (DSS). To obtain a physically con sistent description of turbulence-induced loss for non-classical signaling, each hop is modeled as a pure-loss bosonic chan nel whose random transmissivity follows a truncated Gamma Gamma law, i.e., the Gamma-Gamma irradiance conditioned on the physically admissible range of a transmittance. Under this channel, coherent states remain pure, whereas squeezed states are mapped to mixed Gaussian states. Under Helstrom-optimal detection, the average error of the coherent hop is derived in exact Laplace-series form. For the DSS hop, we derive the output states, a closed-form Gaussian fidelity with rigorous two sided bounds on the Helstrom error, and prove the existence of a loss-aware optimal photon partition. Furthermore, we prove that optimized squeezing preserves both the turbulence-induced diversity order and the leading asymptotic constant of coherent relaying, so that its benefit is a finite-photon-budget effect, and that an interior throughput-optimal harvesting fraction exists. A covariance-preserving benchmark with an exact series representation yields an analytical upper bound on the achievable throughput whose absolute gap vanishes as the relay photon budget grows. Numerical results based on the exact mixed-state Helstrom error quantify the benefit of squeezing and the regime in which it is useful.
Generative communication uses transmitted information to control stochastic generation at the receiver. A fundamental question is how much source-specific information must be communicated so that outputs generated at the receiver satisfy prescribed fidelity and reliability requirements while preserving the conditional source distribution. We address this question for sources on compact Riemannian manifolds by developing a generative rate-distortion-perception (GRDP) framework without common randomness. We formulate an asymptotic operational GRDP function under a geodesic distortion radius and a failure-probability constraint, and establish its single-letter characterization through an equivalent informational formulation. Furthermore, for the informational formulation with the high-reliability limit, we derive a geometric lower bound determined by the largest source probability mass of a region with bounded geodesic diameter, together with an upper bound based on probabilistic coverings of the source manifold. Small-radius analysis of the lower bound reveals the roles of intrinsic dimension and scalar curvature in the required communication rate. For uniformly distributed sources on compact homogeneous Riemannian manifolds, we prove that the bounds coincide, yielding an exact characterization of the limiting GRDP function. We further specialize this result to unit spheres, obtaining an explicit expression that relates the minimum communication rate to the geodesic distortion radius and intrinsic dimension, revealing that for the $d$-dimensional unit sphere with $d\ge2$, increasing the communication rate by $d$ bits per source symbol can reduce the distortion radius by more than half.
Alireza Goldar, Zhen Qin, Zhihui Zhu, Zhe-Xuan Gong, Michael B. Wakin
Can measurements chosen adaptively, in response to earlier outcomes, be exponentially more informative than measurements fixed in advance? In many quantum settings, adaptivity helps at most polynomially; known exponential advantages require coherent measurements across copies or restricted measurements. We show an exponential advantage measuring one copy at a time, with no quantum memory kept between state copies, even when the nonadaptive learner may perform arbitrary global measurements on each copy. We construct explicit families of multi-qubit states in which a scalar parameter is encoded in one of exponentially many candidate observables, with an auxiliary marker indicating which one. An adaptive protocol identifies the relevant observable and then measures it using only single-qubit measurements and one round of adaptation. At fixed accuracy, it needs logarithmically many copies as the qubit count grows, whereas every nonadaptive protocol needs exponentially many. The same mechanism yields an exponential gap in local asymptotic minimax mean squared error constants, tight up to the exponential base. The states are separable and classical in label-dependent product bases; no entanglement or other nonclassical correlations are required. The gap comes from measurement incompatibility: the candidate observables cannot be measured jointly, so a fixed measurement must divide its information budget among them, while adaptivity selects the informative one. Accordingly, the separation disappears when the candidate observables commute, and cannot occur with fully observed classical samples. Measurement incompatibility thus emerges as a resource for quantum learning, distinct from entanglement and quantum memory, that classical feedback alone can exploit.
Rohan Goyal, Venkatesan Guruswami, Yihang Sun, Mary Wootters
Local Coordinate-wise Linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (2025), capture coding-theoretic properties such as list decoding and list recovery. They showed that every LCL property has the same rate threshold for random linear codes (RLC) and random Reed--Solomon codes (RRS). Brakensiek, Chen, Dhar, and Zhang (2025) extended this to random additive codes. Thus any property of all subspace design codes holds for RLCs and RRS at the same rate. In this work, we improve the probabilistic guarantees in the RRS local equivalence theorem and extend the equivalence to all known subspace design constructions individually. Each such construction, including folded Reed--Solomon codes, has the same LCL threshold as RLC and RRS codes. We apply these results to alphabet-size bounds for curve decoding. Curve decoding, introduced by Goyal and Guruswami (2025) and Carmon et al. (2026), is a row-span-constrained LCL property implying proximity gaps (PG), correlated agreement (CA), and mutual correlated agreement (MCA), relevant to IOPs and SNARKs. Informally, a rate-$R$ code $C \subset \mathbb{F}^n$ is $(\ell,δ,a,b)$-curve decodable if any degree-$\ell$ curve $u:\mathbb{F}\to\mathbb{F}^n$ that is $δ$-close to $C$ on at least $a$ points has at least $b\leq a$ nearby codewords lying on a degree-$\ell$ curve in $C$. Goyal and Guruswami (2025) and Goyal, Guruswami, Sun, and Wootters (2026) established curve decodability for RLC and RRS codes at radius $δ$ approaching $1-R$, but with large alphabets in $\ell$ and $η:=1-R-δ$. Using our improved LCL equivalence and rank-sensitive counting inspired by Goyal and Guruswami (2026), we exponentially improve alphabet requirements while matching the best known values of $(a,b)$. For $\ell=O(1)$, our alphabet-size bounds match the best known for list decoding, and improves results for PG, CA, and MCA.
Chapman, Dinur, and Lubotzky recently introduced the theory of non-commutative error-correcting codes, generalizing classical coding theory to arbitrary groups via $δ$-robust subsets used to detect proper subgroups. Building on this foundation, this paper systematically studies an analogue of random codes for arbitrary groups, exploring the extent to which the classical Gilbert-Varshamov (GV) bound holds in this non-commutative setting. While random universal codes of linear size in free groups are shown to be asymptotically bad, we establish a complete characterization for general families of finite groups. Specifically, a family of finite groups admits good random codes (forming a GV family) if and only if it exhibits uniform polynomial maximal-subgroup growth. Furthermore, we provide explicit quantitative bounds on the rate and optimal distance range based on intrinsic parameters, proving that families of finite solvable groups always form GV families and determining the exact probabilistic rate for direct powers of a fixed finite simple group.
Masoud Kavian, Milad Sefidgaran, Youssef Attia El Hili, Malik Tiomoko, Abdellatif Zaidi
Streaming federated learning (SFL) allows clients to train a shared model from continuously arriving data without retaining large local datasets. Such streams often exhibit temporal dependence, yet its effect on generalization remains poorly understood. In this paper we study the expected generalization gap of the aggregated model when client data follow Markov processes, using information-theoretic and rate-distortion techniques. Our framework accommodates heterogeneous Markovian dynamics across clients and distinguishes temporal dependence from information acquired during local learning. We establish bounds under cross-entropy loss, specializing them to Linear Next-Token Prediction (LNTP) and Self-Attention Next-Token Prediction (SANTP). These results quantify the effects of client count, communication rounds, sample size, data dimension, mixing time, and context length. In particular, they reveal a communication--generalization tradeoff: although frequent aggregation may help optimization, it can weaken generalization guarantees. They also suggest a potential advantage of distributed over centralized streaming learning under a fixed total data budget. Temporal dependence enters through the square root of the mixing time. By analyzing the history-state process, we obtain refined bounds with improved context-length dependence under suitable mixing conditions. Experiments on GPT-style language-model pretraining with TinyStories and real-world time-series forecasting illustrate how collaboration and communication frequency influence generalization under temporal dependence
Joshua Brakensiek, David Conlon, Venkatesan Guruswami, Xiaoyu He, Jiaxi Nie, Maya Sankar, Hung-Hsun Hans Yu
In the study of constraint satisfaction problems (CSPs), the non-redundancy of a relation measures the maximum number of clauses in a CSP instance which can be logically independent. In the last few years, CSP non-redundancy has found a number of applications including in query complexity, sparsification, kernelization and streaming. In this paper, we present a novel technique for upper-bounding the non-redundancy of some relations using locally decodable codes (LDCs) and locally correctable codes (LCCs). More precisely, known limitations on the structure of 2-query LDCs and LCCs can be translated into limitations on the size of certain non-redundant CSP instances. This technique builds on a technique used by Brakensiek and Guruswami [STOC 2025] to bound non-redundancy via techniques from matching vector codes. Using LDCs and LCCs, we give improved upper bounds on non-redundancy of the BCK predicate pioneered by Bessiere, Carbonnel, and Katsirelos [AAAI 2020] as well as its well-studied Boolean variant. We also give the first example of a Boolean predicate whose non-redundancy is provably not of the form $n^{k\pm o(1)}$ for some positive integer $k$.
Let $X$ be a random vector in $\mathbb{F}_2^m$, and let $X'$ be an independent copy. We prove that, for every $\varepsilon>0$, there is a subspace $G$ with $\dim G\le 2^{320(1+\varepsilon)/\varepsilon}H(X)$ such that $H(q_GX)\le(1+\varepsilon)(H(q_GX+q_GX')-H(q_GX))$. In particular, the quotient entropy is at most $(1+\varepsilon)(H(X+X')-H(X))$. The coefficient is independent of the ambient dimension, and its exponential order in $1/\varepsilon$ is necessary. The structural result is a logarithmic rigidity estimate for finite weighted families of laws with averaged subspace entropy sparsity. A common variational quotient controls both a family and its convolution family without decreasing the original family's normalized mean entropy defect. Posterior families preserve averaged sparsity, and a fresh-index argument combines a local-to-global estimate with the entropic Marton theorem to increase the defect ratio at a fixed multiplicative sparsity cost. We also obtain two-input almost-additivity and concentration of moderate-doubling sets on subspace cosets at the same exponential scale. The constants are not optimized.
Shortest-path optimality does not guarantee that a memoryless graph generator preserves a prescribed source-target correspondence. We study whether reordering legal shortest edits can retain this correspondence without changing the pairing, mandatory edits, or sampling budget. Under a common Poisson clock, we establish an exact criterion for endpoint coupling recoverability: the source-blind Markov projection attains the unavoidable clock-error floor if and only if routes to distinct targets do not share graph states. Routes to the same target may merge without sacrificing endpoint fidelity. This characterization leads to an exact finite-state routing formulation and a legality-preserving scheduling procedure with recovery certificates. A marker-free construction demonstrates how shared edge structure can retain source distinctions, while a capacity-constrained family exhibits a sharp separation in paired error between edit orders with identical marginal error. Finally, a target-conditioned aliasing bound connects structural route design to the terminal fidelity of a learned graph-only generator. These results characterize when legal edit ordering can preserve a prescribed coupling under fixed operational costs.
We study the problem of finding the minimum $\mathbb{L}\_2$-norm element in a transportation polytope. It corresponds to minimizing the index of coincidence or maximizing R{é}nyi entropy over joint probability distributions with prescribed marginals. The solution is straightforward under a feasibility condition on the marginals. We make three contributions. First, we decompose the basic solution into a mixture of three interpretable couplings and derive a closed-form sampling procedure, revealing its role as the $\mathbb{L}\_2$-projection of the uniform distribution onto the transportation polytope. Second, we show that the feasibility condition becomes exponentially rare as the number of modalities grows, which highlights the practical necessity of a more general construction. Third, we provide a KKT-based iterative construction of the optimal coupling for arbitrary marginals with explicit Lagrange multipliers.
In this paper, we propose a novel uplink Hybrid Non-Orthogonal Multiple Access (NOMA) architecture assisted by Rydberg Atomic Quantum Receivers (RAQRs) to improve energy efficiency by addressing the physical constraints of atomic sensing. We formulate a joint optimization problem encompassing phase measurements and multi-user power allocation to minimize the total transmit power. This problem is particularly challenging due to the non-linear amplitude-only observations of atomic vapor cells. To decomposes the resulting non-convexity, we develop a hierarchical three-layer decomposition optimization framework that systematically decouples the global problem. The inner layer employs a customized Expectation Maximization-Gerchberg-Saxton (EM-GS) algorithm to resolve phase ambiguity and estimate equivalent channel gains. The middle layer derives closed-form optimal power allocation solutions via Karush-Kuhn-Tucker (KKT) conditions. The outer layer utilizes linear Minimum Mean Square Error (MMSE) detection for high-reliability signal recovery. Simulation results demonstrate the superiority of the proposed framework over conventional RF-based Hybrid NOMA. Notably, the atomic architecture achieves approximately a 93% reduction in total power consumption compared to Orthogonal Multiple Access (OMA) baselines while maintaining strict backward compatibility, thereby laying a solid foundation for practical deployment in next-generation green communication networks.
We study the expected number of random linear observations required to recover a prescribed information symbol. For ensembles with uniformly random supports, independently sampled nonzero coefficients, and uniformly bounded column weights, we prove that the asymptotic normalized expected recovery time is at least $π/4$ under optimal decoding. The result holds over finite or infinite fields and extends the lower bound previously established for binary fully symmetric codes under peeling decoding. For singleton - pair observations, we determine the exact limiting expectation and show that optimal and peeling decoding have the same limit, independently of the field and coefficient distribution. The minimum within this family is approximately $0.793933445$, which explicit constructions attain asymptotically over every fixed finite field.
We prove achievability below the symmetric information rate (SIR) under block maximum a posteriori (MAP) decoding for a fixed-degree MacKay-Neal (MN) socket ensemble on the quaternary insertion-deletion-substitution channel used to model DNA reads. For every integer $\ell\ge4$, the $(\ell,3,3)$ socket ensemble, with one transmitted bit fixed and an independent uniform known offset, has limiting rate $r_\star=6/\ell$ bits per stored nucleotide. If the joint SIR $J_t$ of a fixed number $t$ of reads under independent, uniformly distributed input nucleotides exceeds $r_\star$, the ensemble-average full extended-word block error is $O(1/n)$, and deterministic graph-offset sequences attain the same limiting rate and message-average error bound. This result concerns the discrete rate family $6/\ell$, not arbitrary rates approaching a given SIR. The channel permits arbitrarily many insertions and unbounded drift, with no alignment supplied to the receiver. The proof combines established MN parity and distance estimates with a strict arbitrary-candidate-list bound and a list construction that accounts for hidden output boundaries.
Allowing for small fraction of errors in retrieved stored binary patterns, Hopfield-Hebbian neural network (NN) associative memory dynamics [14] achieves linearly scaled capacity. The famous proportionality constant $α_c\approx 0.14$ is obtained in a large dimensional scenario as the ratio of the number of reliably stored patterns $m$ and the patterns' length $n$ under the assumption that uniformly randomly chosen binary patterns are \emph{independent} among themselves. While such an idealized scenario is now well understood, more practical scenarios with correlated/noisy datasets remaining challenging even for classical statistical mechanics replica approaches. We consider precisely such practical settings where each \emph{archetype} pattern is replaced with $M$ correlated \emph{examples} with parameter $r$ governing the quality of correlation. We develop a powerful Random Duality Theory (RDT) based framework to analyze correlated data and already on the first level of RDT lifting obtain capacity characterizations that remarkably well match behavior exhibited through simulated dynamics. Moreover, characterizations explicitly feature correlation parameters $M$ and $r$, which allows to precisely determine their effects on phase-transitioning behavior of the underlying dynamics. Our results are also a well-fitting complement to the existing literature. Namely, to circumvent challenging statistical mechanics analyses, an alternative combination of spectral and replica methods is considered in [4]. We confirm that [4]'s elegant spectral characterizations are excellent approximations in the low correlated regime. At the same time, we also close the gap in the regimes with higher correlation levels where spectral methods deviate from the practical dynamics performance.
Random access codes (RACs) encode a $q$-ary input string into fewer $q$-ary symbols while allowing any requested input symbol to be recovered with probability above the random-guessing value $1/q$. However, it remains unclear what asymptotic guarantees on compression and recovery probability should be required of RACs. We address this question by introducing the notion of asymptotically good RACs and give two polynomial-time constructions. First, an $[n,k,d]_q$ linear code with $d\ge2$, together with an encoder based on its orthogonal-array property, yields an $(n,n-k)_q$-RAC with worst-case decoding success probability \[ p_{\rm wc}=\frac{1}{q}+\left(1-\frac{1}{q}\right)\frac{d-2}{n}. \] These OA-RACs are asymptotically good whenever the underlying linear codes are, and Garcia--Stichtenoth algebraic-geometry codes give a concrete polynomial-time realization. Second, a direct-sum strategy using OA-RACs derived from $q$-ary Hamming codes and the trivial $(1,1)_q$-RAC yields asymptotically good RAC families at every prescribed RAC rate $R_{\rm RAC}=(n-k)/n\in(0,1)$. Numerical results demonstrate favorable finite-length performance of both constructions.
Adrian Agustin, Xavier Mestre, Carlos Suárez García, Alberto Pellon Sancho
Current wireless communication systems are designed based on channel models obtained under the assumption of far-field operation, where electromagnetic waves can be approximated by a planar wave. In those circumstances, dualpolarized antennas seem to be the optimal solution for maximizing the spectral efficiency. However, the recent research on XLMIMO systems represents a paradigm shift, since communication may take place in the near-field and an additional degree of freedom can be achieved. This work presents a modular, lowcost tripolarized antenna at 2.4 GHz band, that is used to experimentally validate theoretical findings about tripolarized antennas, which are commonly based on orthogonal infinitesimal dipoles. The evaluation is carried out in two indoor scenarios and one outdoor scenario, with transmitter comprising multiple tripolarized antennas and a receiver equipped with a single tripolarized antenna. We show that this type of antenna can increase the number of spatial streams up to three or extend the region where terminals are able to achieve two spatial streams
We construct three binary extremal self-dual codes of length $60$ with weight enumerators for which no binary extremal self-dual codes of length $60$ were previously known to exist. This completes the determination of the weight enumerators that occur for binary extremal self-dual codes of length $60$.
We revisit the Gray-Wyner problem of lossy compression of bivariate Gaussian sources under the quadratic distortion measure and derive the exact second-order asymptotics. Specifically, we first identify the boundary rate tuples using the explicit first-order asymptotics by Yu (TIT 2023) and then characterize the tradeoff among three second-order coding rates subject to a constraint on the joint excess-distortion probability. Our main contribution is the achievability proof, where we derive a covariance shell covering lemma that is analogous to the type covering lemma for the discrete case. In particular, our covering lemma classifies the source sequences into power shell types via their empirical covariance matrix. For each such power shell type, we derive sufficient conditions on the compression rates so that covering within distortion levels are achievable. Finally, asymptotical analysis via the Berry-Esseen theorem yields the desired result.
Sanghyeon Cho, Taewoo Park, Seong-Joon Park, Dae-Young Yun, Hee-Youl Kwak, Sang-Hyo Kim, Yongjune Kim
Universal channel decoders based on transformers-such as the Foundation Error Correction Code Transformer (FECCT)-achieve competitive decoding performance across diverse code families with a single shared backbone, optionally followed by code-specific finetuning. However, the high computational complexity and large parameter footprint of FECCT present substantial obstacles to practical deployment. To address these challenges, we investigate structured pruning for FECCT and propose Spectral-Aligned Pruning (SAP), a structure-aware framework that enables cross-code reuse of structured pruning masks by leveraging the spectrum of the corresponding bipartite graph. SAP is grounded in classical graph analysis of codes: the two algebraically largest adjacency eigenvalues provide compact spectral proxies for degree scale, expansion ratio, and minimum-distance lower bounds. These quantities are directly relevant to decoding performance: degree scale reflects how densely codeword bits and parity checks are connected; expansion ratio influences how information propagates across the bipartite graph; and minimum distance characterizes codeword separation. Based on this connection, SAP uses these two leading eigenvalues as a lightweight code signature for pruning-mask retrieval. Empirically, this two-dimensional signature yields stable library selection equivalent to higher-dimensional spectral signatures in our evaluation. After pruning, SAP uses parameter-efficient low-rank adaptation (LoRA) to recover decoding performance while storing only a small number of additional adapter parameters per code. Experiments across diverse codes show that SAP achieves decoding performance comparable to dedicated per-code pruning, while enabling substantial reductions in computational cost and model memory footprint through kernel-level structured pruning. Code is available at https://github.com/iil-postech/sap.
Binary Iterative Hard Thresholding (BIHT) is a simple, yet effective, greedy method for recovering a sparse vector from one-bit sign measurements. In its original form, BIHT performs a ``gradient-descent'' step, followed by hard thresholding. A convergence analysis of this algorithm was left open in the introductory work of Jacques, Laska, Boufounos, and Baraniuk [IEEE Trans. Inform. Theory (2013)] and has remained unresolved for over a decade, with subsequent sharp analyses studying a normalized variant instead, that additionally projects every iterate onto the unit sphere. This paper resolves that gap and characterizes when per-iterate normalization is algorithmically necessary. In the noiseless setting, we prove a universal, sample-optimal convergence theorem for the original BIHT algorithm. Specifically, with $\widetilde O(s/ε)$ measurements, a deterministic, computable finite-time iterate has directional error at most $ε$, simultaneously for every $s$-sparse unit vector. This matches the optimal sample dependence achieved by normalized BIHT in prior work. Under sign corruptions, we prove a sharp separation. If at most a $τ$ fraction of signs are flipped adversarially, then BIHT, without per-iterate normalization, still reaches the robust error floor at an early iterate with a matching $\widetilde O(s/ε)$ sample complexity rate as its normalized variant. This recovery, however, is not stable. We prove a scalar lower bound showing that any nontrivial corruption pattern, even one that involves only one flipped sign together with one clean sign, forces the iterates to oscillate indefinitely. Consequently, no general last-iterate convergence theorem can hold for BIHT under sign corruptions, while its normalized surrogate provably escapes this instance.
Decentralized networks can learn collision-free periodic transmission schedules, but acquisition can consume much of a finite operating horizon. We characterize acquisition in a reservation protocol for a fixed population of $n$ nodes and a period of $Γ_n\ge n$ slots. Initially, each node attempts independently in each slot with probability proportional to $1/n$. A success reserves a slot that the node reuses every $Γ_n$ slots, retaining it after collisions. Nodes use only their own acknowledgments and small local memory. An exact finite-population Markov reduction, independent of the arrangement of reserved slots, characterizes the time until every node has a distinct reservation. As $n\to\infty$, mean acquisition takes $O(n^2)$ slots when $Γ_n=n$ and $O(n\log n)$ slots when $Γ_n\sim(1+θ)n$, for fixed $θ>0$. With a fixed number $Γ_n-n$ of spare slots, the standard deviation of acquisition time has the same asymptotic order as its mean. If that number diverges while $Γ_n/n$ remains bounded, the ratio of standard deviation to mean tends to zero. A diverging sublinear number of spare slots yields $o(n^2)$ mean acquisition while long-run utilization, the fraction $n/Γ_n$ of slots with successful transmissions, tends to one. Simulations validate these laws and compare acquisition and delivered packets per slot with existing access protocols.
This paper addresses long-range sensing in bistatic low-Earth-orbit integrated sensing and communication (LEO-ISAC). Conventional OFDM sensing fails in LEO-ISAC because millisecond-scale propagation delays destroy the transmitter--receiver symbol alignment and, with multiple targets, make the receive window longer than the transmitted block. We propose a window-grid (WG) processing framework that exploits the known beam-intersection swath to resolve both problems purely at the receiver, leaving the 3GPP symbol structure unmodified: the swath delay span is folded into cyclic-prefix-sized slices, each handled by one WG. With 103.2 MHz bandwidth at bistatic ranges beyond 640 km, simulations demonstrate meter-level ranging of two targets, and 1000 Monte-Carlo trials over random target--satellite geometries show that, with an ephemeris-based satellite-selection rule, every target is detected with a 90th-percentile range error of 2.4 m.
Bounds based on Integral Probability Metrics (IPMs) are ubiquitous in machine learning and statistics, appearing, e.g., in generalization, alignment, fairness, and privacy. IPMs reduce the discrepancy between two distributions to a single worst-case gap between expectations. This compression is costly: for rare events, safety failures, or under-represented groups, IPM-based bounds are loose or vacuous. We introduce a non-linear generalization of IPMs, which we term Integral Probability Boundaries (IPBs). Unlike IPMs, IPBs provide bounds that are tight at the extremes. We derive their basic properties and present algorithms for estimating them in practically relevant settings. We demonstrate the usage of IPBs in both theoretical and practical applications for alignment, judge-free performance estimation, and fairness, where they enable us to obtain sharp bounds on performance and fairness gaps, e.g., 15 p.p. more precise estimates on fairness gaps for rare groups in a realistic generative modeling task, compared to the state of the art.
We define and study burst-covering codes. We provide some general bounds connecting the parameters of a code with its burst-covering radius. We then provide stronger bounds on the burst-covering radius of cyclic codes, by employing linear-feedback shift-register (LFSR) sequences. For the case of BCH codes we prove a bound on pattern frequencies in LFSR sequences, and using this tool, we bound the burst-covering radius of binary primitive BCH codes and Melas codes. We then present an efficient burst-covering algorithm for cyclic codes. Finally, we present a bound on the critical exponent of cyclic codes based on the burst-covering radius.
This paper studies when list-decodability guarantees for error-correcting codes of good distance can go beyond the classical Johnson radius and gives a corresponding efficient list-decoding algorithm for Reed-Solomon codes up to this new radius. The Johnson bound shows that any error-correcting code with distance $δ$ is automatically list-decodable with small list size up to a certain radius $J(δ)$ around any received word $r$. We show that if the received word $r$ is known to have some codewords that are somewhat close to it (we call these ``hints"), then $C$ is list-decodable with small list size up to an even larger radius around $r$. We determine the optimal list-decoding radius in this setting for single and multiple hints over both large and small alphabets and show that this radius is the optimum of a natural convex program. Remarkably, even a single hint that is $(J(δ)-ε)$-close to $r$ improves the list-decoding radius around $r$ to $J(δ)+ε'$. Finally, we give an efficient algorithm, based on the weighted Guruswami-Sudan decoder, that list-decodes Reed-Solomon codes up to this optimal radius.
We prove a new lower bound on the $b$-symbol weight of codewords in dual Melas codes, which is strictly better than known results. We employ a new strategy that translates a pattern counting problem in linear-feedback shift register sequences to a problem on orbits of binary polynomials under a certain action. We use the same techniques to provide an improved lower bound on the burst-covering radius of Melas codes and a new upper bound on the critical exponent of dual Melas codes. We then define a new randomness postulate on (families of) binary sequences, based on the definition of infinite Poisson generic sequences. We conjecture that codewords in the dual Melas code satisfy this postulate, and we show partial progress in establishing this conjecture. We also show how a relaxed version of the problem can be completely resolved, and relate the conjecture to the first part of the paper, giving a justification of why the improved bounds on the $b$-symbol weight were somewhat to be expected.
We show that for every prime power $q$ and $ρ\in(0,1-\frac1q)$ there exists $\varepsilon_0(q, ρ) > 0$ such that for all positive $\varepsilon < \varepsilon_0(q, ρ)$, a random linear code over $\mathbb{F}_q$ of rate $1-h_q(ρ)-\varepsilon$ has list size $\lfloor h_q(ρ)/\varepsilon\rfloor$ or $\lfloor h_q(ρ)/\varepsilon\rfloor+1$ with probability $1-o(1)$. Before this work, the list size was known only up to a constant factor for $q\ge3$, and for $q=2$ it was known to be either $\lfloor h_2(ρ)/\varepsilon\rfloor-1$, $\lfloor h_2(ρ)/\varepsilon\rfloor$ or $\lfloor h_2(ρ)/\varepsilon\rfloor+1$. We also show that the same two-point concentration holds for the list size of random LDPC codes. This follows from a general theorem establishing that random LDPC codes and random linear codes have the same threshold rate for distance, list decoding, list recovery from errors and any other \emph{convex} property, which answers a question of Mosheiff, Resch, Ron-Zewi, Silas and Wootters.
This paper introduces LQ8, an open-source weak-signal digital mode for amateur radio that completes structured two-way contacts in 4 transmissions (60 s), achieving a 1.50x speedup over canonical 6-transmission exchanges (90 s) and 1.25x over 5-transmission RR73 exchanges (75 s) while preserving complete bidirectional exchange of Maidenhead grid locators, signal reports, and mutual acknowledgments. By replacing fixed-width message-type headers with variable-length prefix codes matched to physical-layer bit budgets, LQ8 packs the answering station's grid locator and measured signal report into a single 77-bit reply. In multi-station pileup operations, LQ8 confirms up to two answering stations simultaneously within a single-carrier 50.0 Hz transmission with a 0.0 dB RF power-splitting penalty, achieving a peak rate of 240 QSOs/h in continuous pileup (4x over single-carrier FT8; 480 QSOs/h dual-carrier) while retaining -21.0 dB SNR sensitivity. The protocol family also defines three extended profiles (LQ16, LQ4, and LQ2) tailored for extreme sensitivity, VHF/UHF contesting, and fast-burst channels.