Papers

This book is about the mathematical foundations of data science. 1. Introduction 2. Curses, Blessings, and Surprises in High Dimensions 3. Singular Value Decomposition and Principal Component Analysis 4. Linear Regression and Regularization 5. Graphs, Networks, and Clustering 6. Nonlinear Dimension Reduction and Diffusion Maps 7. Linear Dimension Reduction via Random Projections 8. Optimization for Data Science 9. Classification 10. A Mathematical Introduction to Deep Learning 11. Large Sample Limit of Graph Laplacians 12. Community 13. Concentration of Measure and Gaussian Analysis 14. Matrix Concentration Inequalities 15. Compressive Sensing and Sparsity 16. Low-Rank Matrix Recovery

Probability distributions are central to information theory, statistical inference, and modern probabilistic learning. Maximum entropy selects a probability state under prescribed constraints, but it does not specify how that state is reached, how probability is transported, or how dissipation and external information exchange are accounted for along the path. We develop a path-dependent entropic Lagrangian calculus that extends static state selection to probability-path evolution through restricted generators, upper-limit history terms, and explicit balance–entropy port routing. The construction yields the thermal state relation, conservative probability balance, and nonnegative production under standard mobility closure. Its KL/Shannon sector recovers maximum-entropy and Bayesian laws as stationary no-flux states, while time-dependent information potentials separate internal dissipation from supplied information power. Composable information and structural potentials control tails, sparsity, robustness, regularization, and nonlocal multimodality without changing the accounting architecture. Two numerical examples verify mass conservation, energy decomposition, and the total free-energy ledger.

The dual root lattice $A_n^*$ is an important lattice in quantization, coding, and estimation. It can be represented as the projection of the integer lattice $\mathbb{Z}^{n+1}$ onto the $n$-dimensional hyperplane whose coordinates sum to zero. This representation makes $A_n^*$ particularly natural for quantizing simplex-constrained data, such as histograms and probability distributions. This paper studies the closest-point problem for $A_n^*$: given a query vector $y$, find the lattice point $x\in A_n^*$ minimizing $\|y-x\|^2$. The fastest previously known method is the linear-time algorithm of McKilliam, Clarkson, Smith, and Quinn (MCSQ), which employs bucket sort as a core operation. We present a faster linear-time algorithm. The key observation is that the closest-point objective depends on the rounding residuals only through two prefix aggregates: a count and a residual sum. Hence the elements inside each bucket never need to be sorted, stored, or traversed. This replaces the linked-list traversal and pointer chasing of MCSQ with a single bucketing pass over two flat arrays with counting-sort-style accumulates. A scaled objective further makes most of the computation exact integer arithmetic, and when the input coordinates are rationals with a common denominator, for example, histograms or empirical distibutions, the entire algorithm becomes exact and integer-only. Experiments on an Intel Core i9-13900H show speedups of about $1.8\times$ to $3.0\times$ over MCSQ for $n=2,\dots,100$, with larger gains at higher dimensions. The proposed algorithm is also noticeably faster than Conway and Sloan methods for other root lattices, including $A_n$, $D_n^*$, and $E_8$. An open-source implementation is available in the "fanstar" project.

Dimensionality reduction has proven powerful for identifying neural manifolds, which are low-dimensional structures underlying high-dimensional neural activity. These low-dimensional representations have improved the interpretability of population-level coding. Yet whether such low-dimensional representations are biologically relevant and confer functional advantages in learning systems, or merely reflect neuron-level activity, remains contested in neuroscience. We show that an explicit information bottleneck forcing a recurrent neural network to learn a low-dimensional representation is necessary for rotational and out-of-distribution generalisation in a time-series prediction task. Using information-theoretic measures of causal emergence, we characterise the dynamics of this representation across the memorisation-to-generalisation transition, finding a non-monotonic trajectory which shows an initial decrease, a minimum, and a subsequent rise to a maximum, even as prediction loss falls monotonically. This trajectory scales with task complexity, and the magnitude of emergent structure reliably predicts generalisation performance. Analysis of CA1 hippocampal activity in mice learning an alternating maze task reveals analogous non-monotonic emergence dynamics that track behavioural performance. Together, these findings indicate that the ability of neural networks to learn compact, distributed and emergent representations confers a functional advantage for generalisation, supporting a causal role for learned representations in cognition.

A binary $(n,m)$ quantum random access code (QRAC) compresses an $n$-bit classical string into an $m$-qubit quantum state, from which a decoder attempts to recover a randomly selected target bit. Of particular interest is the optimal average probability of success, $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}$, which is numerically conjectured to satisfy the bound $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,m}\leq \frac{1}{2}+\frac{1}{2}\sqrt{\frac{m}{n}}$. Recent constructions of $(n,n-1)$ QRACs by Suzuki and $(n,n-2)$ QRACs by Akibue et al. meet this bound exactly, raising the question of their strict optimality. In this work, we settle this question by proving the conjectured upper bound for $m\in\{n-1,n-2\}$, thereby precisely determining $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-1}$ and $P^{Q,\mathrm{avg},\mathrm{opt}}_{n,n-2}$. The proof utilizes a translation recently studied by Lin and de Wolf from local to global reconstruction via pretty good measurement, along with dimensional and positive-semidefinite constraints on an induced channel.

To meet the extended ultra-low latency and high reliability (xURLLC) requirements for autonomous driving sys-tems, multiple access schemes must operate reliably in high-mobility and complex propagation environments. Recently, rate-splitting multiple access (RSMA) has emerged as a promis-ing multi-user transmission framework, showing robustness in dynamic situations where imperfect and outdated channel state information (CSI) is prevalent. Moreover, the advanced sensing, localization, and on-board computation capabilities of autonomous driving vehicles facilitate the construction of a channel knowledge map (CKM), which is a key enabler for environment-aware communications in future 6G networks. In this work, we propose a CKM-aware finite-blocklength (FBL) RSMA for a downlink autonomous driving system. The location-dependent large-scale channel information provided by CKM is exploited to guide the common/private power split and common-rate allocation in RSMA. Specifically, we derive a new and tight closed-form bound for the private-stream ergodic rate. Combined with the closed-form expression for the common-stream ergodic rate, an optimization design of splitting ratios is formulated to maximize the min-rate performance among multiple users. Numerical results show that the proposed scheme outperforms the considered space-division multiple access (SDMA) and non-orthogonal multiple access (NOMA) schemes in high-mobility scenarios. Comparisons across different CKMs further highlight the benefit of accurate channel information, demonstrating how environment-aware channel knowledge complements flexible in-terference management of RSMA in high-mobility short-packet communications.

While autoregressive models optimize the exact data likelihood via the chain rule, diffusion models are typically trained with denoising objectives. We develop conservation laws based on generalized extrinsic information transfer (GEXIT) functions for a broad class of memoryless noise processes, showing that the data–model cross-entropy (CE) can be characterized exactly as an integral of local information-theoretic derivatives along the noise path. This yields a unified characterization of the likelihood for discrete and continuous diffusion, with the Gaussian case reducing to the well-known mutual information–minimum mean-square error (I-MMSE) relationship. An immediate implication is a locality property: one can compute the information-theoretic derivatives using only the marginal posteriors along the noise path. As a result, training reduces to learning the marginal posteriors by minimizing the negative log-likelihood. While the conservation law implies that the entropy does not depend on the noise path, finite-capacity denoisers approximate the posteriors with varying accuracy across noise types, leading to differences in performance. We validate these predictions on synthetic Markov sources and standard benchmarks, including text8 and CIFAR-10.

We study a symbolic search space for the Collatz conjecture based on finite exponent codes of the accelerated map. Each code records the number of divisions by two after every 3n + 1 step and determines three quantities: real drift, a 2-adic start representative, and a 3-adic endpoint representative. Their combination defines the 2-3-infinity diagnostic. Counterexample-like codes should exhibit near-critical drift, small 2-adic start representatives, and endpoints compatible with growth on the scale of (3/2)^k. We prove that every infinite code generated by a fixed positive integer has asymptotically vanishing 2-adic and 3-adic residue rates. Experiments with random critical codes, mechanical critical codes, and adaptive evolutionary search at lengths 100, 200, and 400 show that adaptive search improves finite-length trade-offs, while all methods retain clearly positive residue rates. The proposed framework is not a verification method for the Collatz conjecture, but a symbolic diagnostic approach for investigating obstruction structures in exponent-code space.

This paper is a continuation of our earlier work, in which we described a Las Vegas algorithm to solve the elliptic curve discrete logarithm problem. The Las Vegas algorithm reduces the elliptic curve discrete logarithm problem to finding a zero minor in a matrix. Using the intersection poset of a hyperplane arrangement, we develop an algorithm to find a zero minor in a rectangular matrix. Our methods are elementary. We discuss the complexity and success probability of our algorithm and provide implementation details. Finding a zero minor in a matrix is also of independent interest.

Reed-Muller (RM) codes have been shown to achieve capacity over a range of channels, and recently proposed projection-aggregation (PA) decoding has been experimentally shown to achieve near-maximum-likelihood decoding performance. These recent achievements motivate theoretical research on PA decoding. In this work, we analyze the density function of the soft output from collapsed projection-aggregation (CPA) decoding for RM codes over the binary-input additive white Gaussian noise (BIAWGN) channel. We prove that soft-decision CPA decoding returns an exact marginal probability and is symmetric. Based on the analysis, we build a density evolution model for CPA decoding. To simplify the density evolution, we approximate the projection and the fast Hadamard transform decoding using hard-decision decoding. Simulation results over the BIAWGN channel show that our proposed density evolution model captures the fast reduction in the mean and the variance of the soft information returned from the CPA decoding, which qualitatively explains the decoding mechanism and the fast convergence speed of the CPA decoding. We perform an asymptotic analysis based on the proposed density evolution, and we show that CPA decoding can achieve a vanishing error probability for RM codes with a vanishing code rate.

This paper investigates the Gaussian-quadratic lossy compression with arbitrary source length under individual distortion constraints. The rate-distortion function (RDF) is lower-bounded by a Hadamard inequality-based rate, which is tight if and only if the semidefinite condition (SDC) holds. Otherwise, this bound becomes loose, and analytical results are lacking. Moreover, the fundamental quantitative relationship between source correlations and the RDF remains incomplete. In this paper, we provide new theoretical results under different source covariance matrices and distortion constraints. First, under arbitrary covariance and distortion constraints, we obtain the spectral properties of the optimal source reconstruction achieving the RDF, and a stronger scalar inequality version of the SDC. We propose a class of source covariance matrices based on hierarchical correlations and show that studying the two-type correlation (2-TC) model is sufficient to establish the analytical foundation for the broader class. Under this covariance, we obtain the RDF with source correlations explicitly incorporated when the SDC holds, and analyze the SDC from the perspectives of distortion constraints and source correlations. Next, under the 2-TC covariance and two-type distortion (2-TD) constraints, we establish the complete RDFs over seven regions on a distortion plane, with the optimal distortion (rate) allocations determined in each region. It is revealed that the essence of pursuing the complete RDF lies in thoroughly analyzing the correlations between the optimal distortions. Finally, under isotropic correlation and identical constraints, we provide the per-component compression rate and show that exploiting correlations can significantly reduce compression costs.

Non-binary successive cancellation list (NB-SCL) decoding expands each surviving path into $q$ candidate branches at every information symbol, which causes high path expansion, sorting, and pruning complexity. To address this issue, this paper proposes low-complexity list decoding algorithms for $2\times2$ kernel non-binary polar codes (NBPCs). First, we design a split-reduced non-binary successive cancellation list (SR-NBSCL) decoder that skips path splitting when the current symbol is sufficiently reliable. We then exploit the final Rate-1 node structure and switch the last group of information symbols to simplified non-binary successive cancellation (NB-SC) decoding, resulting in the enhanced split-reduced non-binary successive cancellation list (ESR-NBSCL) decoder. To further reduce branch expansion at unreliable symbols, we introduce an accumulated reliability-deviation (ARD) metric and propose an adaptive branch-pruning non-binary successive cancellation list (ABP-NBSCL) decoder, which prunes unreliable candidate branches before sorting and then reduces the dominant sorting complexity. Simulation results show that the proposed decoders achieve frame-error-rate (FER) performance close to that of conventional NB-SCL decoding with much lower complexity. In particular, the ABP-NBSCL decoder reduces the path splitting number (PSN) by more than $80\%$ at several tested signal-to-noise ratios (SNRs), with a negligible performance loss.

Grant-Free (GF) random access is promising for low Earth orbit satellite Internet due to its reduced access latency. However, existing schemes suffer from poor performance in massive connectivity scenarios. To address this challenge, we firstly propose an iterative residual feedback multi-measurement vector approximate message passing algorithm. This algorithm leverages multi-domain synergistic sparsity in the spatial-frequency and angular-delay domains to alternately perform active user terminal detection (AUD) and channel estimation (CE). Additionally, a residual feedback mechanism is incorporated to suppress error accumulation, thereby enhancing AUD performance. Furthermore, conventional data detection (DD) methods significantly degrade when active user terminals are spatially close or outnumber the satellite's receive antennas, making the demodulation problem rank-deficient or underdetermined. To mitigate this, we design a data modulation scheme via joint spatial-frequency multi-domain spreading, which utilizes observations from both spatial and frequency domains to facilitate multi-domain DD. Simulation results demonstrate that the proposed scheme significantly outperforms existing GF methods in terms of AUD accuracy, CE precision, and bit error rate, especially under conditions of low effective pilot length and practical signal-to-noise ratios.

Zak-Orthogonal Time Frequency Space (OTFS) modulation is known to be robust to Doppler spread in high mobility scenarios when compared to Orthogonal Frequency Division Multiplexing (OFDM). This is due to the fact that the channel response to a Zak-OTFS carrier within a frame can be accurately estimated from the channel response to another carrier within the same frame. However, an important open problem and question is whether inter-frame channel prediction is possible with Zak-OTFS, i.e., is it possible to accurately predict the channel response to a Zak-OTFS carrier in a frame based on knowledge of the channel response to some Zak-OTFS carrier in another frame (i.e., not the same frame). In this paper we show that indeed inter-frame channel prediction is possible. We show that the effective DD domain channel filter coefficients vary in a deterministic manner as we move from current to future frames in time and frequency. We also show that the subspace spanned by channel filter coefficients of consecutive frames in time/frequency is invariant to discrete shifts in time and frequency. We exploit the deterministic variation and subspace invariance to propose a novel deterministic ESPIRIT-type method which uses the effective DD domain channel filter taps/coefficients estimated in training frames (i.e., current/past frames in time and frequency having both pilot and data carriers) to predict the effective DD domain channel filter for frames which are several tens of frames in future and several tens of frames away in frequency.

The groundbreaking development of generative artificial intelligence (AI) is rapidly boosting the ability to generate content such as images and videos, reshaping communication paradigms. This article introduces generative communications (GenCom), a novel paradigm for 6G networks in which large AI models (LAMs) drive semantic understanding, reasoning, and content generation, embedding these into the communication process. Unlike traditional systems that strictly pursue accurate bit transmission, GenCom enables transmitters to convey only minimal yet sufficient information, while receivers leverage shared generative priors and knowledge bases to synthesize the intended output. Communication is thus redefined as controlled generation rather than data reproduction. We formalize the concept of GenCom, clarify its AI-native and generation-driven properties, and present its core mechanisms. A two-layer GenCom architecture supported by key enabling technologies is proposed, and analysis of four representative application scenarios demonstrates that GenCom offers ultra-efficient transmission, semantic-level robustness, and new network functions. Finally, we outline future research directions, including foundational theory and real-time processing, highlighting a promising pathway toward 6G networks.

The main focus of this paper is on the algebraic structure of two-dimensional $(\lambda,\mu)$-constacyclic codes of length $\ell\mathrm{m}$ over finite chain rings with residue field $\mathbb{F}_q$, where $q \equiv 1 \pmod{r\mathrm{m}}$ and $r$ denotes the multiplicative order of $\bar{\mu}$. In this paper, the structure of two-dimensional $(\lambda,\mu)$-constacyclic codes is obtained. Our approach relies on analysing primitive idempotents within the finite chain ring to determine the generators of these codes. We also find the condition under which two-dimensional constacyclic codes are maximum Hamming distance with respect to rank (MHDR) over finite chain rings.

To provide multiple-satellite coverage for global Internet of Things (IoT), a low Earth orbit (LEO) satellite IoT constellation usually contains multiple-layer orbits with different altitudes. However, the performance of multiple-layer LEO satellite IoT constellations under practical Rician fading satellite channels remains unknown due to complex theoretical modeling and intractable mathematical analysis. To address these challenges, this paper proposes a stochastic geometry-based modeling and analysis framework for multiple-layer LEO satellite IoT constellations, integrating Rician channel modeling and Cox point processes. Specifically, we introduce a novel channel approximation method to overcome the intractable expressions caused by the Rician fading. Building on this method, we derive exact closed-form expressions for key performance metrics, including connectivity probability, coverage probability, and transmission rate, especially in the case of IoT short-packet transmission. Extensive simulation results validate the accuracy and effectiveness of the proposed model and reveal significant design insights. The results not only provide new theoretical perspectives for modeling and analysis of LEO satellite IoT constellations but also offer practical guidance for system deployment and optimization.

This paper proposes a novel continuous aperture array (CAPA)-assisted integrated communication and navigation (ICAN) framework for low Earth orbit (LEO) satellite constellations. Within this framework, an electromagnetic-based collaborative transmission model is developed, in which multiple satellites equipped with CAPAs simultaneously radiate downlink data streams and navigation reference signals over shared spectrum. Building upon this, the achievable communication rate and the navigation Cramer-Rao bound (CRB) are derived, which explicitly characterize the intrinsic coupling between the dual-function beamformers and system performance. To improve the positioning accuracy with communication quality of service guarantee, a joint beamforming optimization problem is formulated to minimize the average CRB subject to transmit power budgets and minimum rate constraints. To tackle the inherent infinite-dimensionality of the CAPA beamformer design, an ICAN channel subspace is introduced to equivalently transform the formulation into a tractable finite-dimensional problem, which is then efficiently solved via an iterative convex optimization algorithm. Finally, numerical results demonstrate that the proposed CAPA-assisted beamforming design algorithm significantly outperforms conventional discrete phased array architectures and other benchmark schemes, yielding notable improvements in ICAN performance.

This letter develops a radio access network (RAN) framework for mixed discrete-continuous optimization problems that arise in user-centric cell=free massive multiple-antenna networks. The novel framework exploits the structural decomposition between discrete clustering decisions and continuous resource allocation variables by modeling the space of feasible serving states as a graph with Hamming-topology neighborhoods. A serving-state graph abstraction is introduced to enable topology-aware search-and-evaluate optimization procedures and a graph-based search-and-evaluate (GBSE) algorithm is devised along with their complexity analysis. Energy efficiency maximization at the RAN level is presented as an application of considered alongside the proposed framework and GBSE algorithm. Numerical results show that minimal Hamming neighborhoods offer an attractive trade-off between scalability and exploration capability in grap-based optimization and GBSE outperforms existing techniques.

Recently, large language models (LLMs) have been successfully adopted in various fields, including wireless communications, robotics, and autonomous vehicles, owing to their outstanding adaptability and reasoning abilities. Despite their huge potential, the application of LLMs for mobility management is relatively scarce since it requires not only analyzing wireless measurements but also predicting dynamic user trajectories and making real-time handover decisions across densely deployed small base stations (SBSs). In this paper, we propose an environment-aware mobility management scheme based on large multimodal models (LMMs), which extend capabilities of LLMs to process multimodal sensing data. By leveraging LMMs, the proposed scheme extracts contextual information on the surrounding environments from RGB-D images to capture user equipment (UE) mobility patterns and identify signal reflections and blockages caused by static reflectors and dynamic obstacles. Using the extracted environmental information, the proposed scheme learns the intrinsic mapping from UE and SBS positions to channel capacity, referred to as channel capacity map (CCM), from which future channel capacities along UE trajectories are predicted. Based on the predicted channel capacities, we determine proactive handover decisions maximizing the cumulative channel capacities. Simulation results demonstrate that the proposed scheme achieves substantial channel capacity improvements over conventional deep learning (DL)-based approaches.

We study covert classical communication over quantum multiple-access channels (MACs) with general message sets. Specifically, we consider a fully quantum MAC with arbitrary message sets and an arbitrary number of transmitters. We demonstrate the feasibility of achieving a positive covert rate over this channel and establish general one-shot and asymptotic achievable rate regions. For classical-quantum MACs with general message sets, we establish the covert capacity, when the transmitters are restricted to deterministic encoding. Our result recovers, as a special case, known results for classical communication over classical MACs with general message sets, covert communication of a classical message over a classical channel with two transmitters, and classical communication over quantum MACs. We provide three examples of MACs to which our results can be applied, either directly or indirectly, to achieve positive covert rates. Specifically, we first study covert communication over a finite-dimensional MAC with a helper. We then analyze a classical Gaussian MAC with a helper and derive its covert capacity. Finally, we extend the analysis to a single-mode bosonic MAC with a helper and show that positive covert rates can also be achieved in this setting. To the best of our knowledge, this is the first work to achieve positive-rate covert communication over both classical and quantum MACs.

In this paper we give a systematic and unified treatment and extensions of various results on a new notion of quantum $f$-divergences defined from quantum hockey stick divergences, the theory of which has been developed recently in \cite{BHT_fdiv,HircheTomamichel_integral,LiuHircheCheng2025}. In particular, we consider non-normalized states and hockey stick $f$-divergences defined from more general notions of quantum hockey stick divergences, as well as a somewhat more general form of the integral representation defined in terms of an additional real parameter. We also consider the extension of the theory to general von Neumann algebras, and extend various results from \cite{HircheTomamichel_integral,LiuHircheCheng2025} to this setting. Our main results here are the representation of the hockey stick $f$-divergences in terms of Neyman-Pearson error probabilities, which was given in the finite-dimensional case in \cite{LiuHircheCheng2025}, an extension of Jen\v cová's result \cite{Jencova2023} on the detection of reversibility of a quantum channel on a pair of states in terms of the hockey stick divergences, and an extension of a result in \cite{HircheTomamichel_integral} showing that the regularized hockey stick Rényi $\alpha$-divergences coincide with the Petz-type Rényi divergences for $\alpha\in(0,1)$ and with the sandwiched Rényi divergences for $\alpha>1$. Moreover, we give some partial results on the characterization of when different notions of quantum $f$-divergences give the same value on a pair of quantum states.

The problem of recovering an (approximately) low-rank Hermitian matrix $\pmb{M}_0 \in \mathbb{C}^{n \times n}$ of rank $r$ from quadratic sampling matrices of the form $\{\pmb{a}_k \pmb{a}_k^*\}_{k=1}^m$ arises in a variety of applications, including phase retrieval. To obtain rigorous recovery guarantees, the sampling vectors $\{\pmb{a}_k\}_{k=1}^m$ are typically modeled probabilistically. However, most existing theoretical results rely on Gaussian or sub-Gaussian assumptions, which may not accurately capture practical data models. In many applications, sampling vectors exhibit heavier tails, while theoretical understanding in such regimes remains scarce. In this paper, we bridge this gap. We show that two widely used convex approaches, nuclear norm minimization and semidefinite-constrained empirical risk minimization, achieve uniform, stable, and robust recovery under the mild assumption that the entries of the sampling vectors have only finite $4+\delta$ moments, with the optimal sample complexity $m = \mathcal{O}(rn)$ up to moment-dependent constants. The two main ingredients of our analysis are moment estimates for quadratic forms established via decoupling, together with recent advances in covariance estimation in heavy-tailed settings. As byproducts, we also establish the optimal sample complexity for low-rank matrix recovery under complex projective $4$-design sampling, thereby improving upon previous results, and obtain stability guarantees for phase retrieval under similarly weak moment assumptions.

Several new and sharp informational inequalities are derived as a byproduct of Stam-like and moment-entropy-like inequalities in the relative framework and a recently established inequality mixing the Rényi entropy, the Rényi divergence and the Rényi cross entropy of suitable probability density functions. More precisely, we obtain a Stam-like inequality connecting the Rényi entropy power, the recently introduced scaling-invariant relative Fisher information and the Rényi cross entropy. Furthermore, we derive an inequality involving only Fisher-like informational measures and another inequality involving only moment-like functionals of non-relative, relative and cross types, respectively. All the inequalities are sharp. The minimizers of the Stam-like inequality are, in certain cases, pairs of Gaussian or stretched Gaussian probability densities; in contrast, each minimizer of the moment-like inequality is the probability density of the generalized Beta distribution.

Suppose we observe two sets of $n$ Gaussian vectors in $\mathbb{R}^d$, with the promise that, after applying a permutation of $[n]$ and a rotation of $\mathbb{R}^d$, the two sets are $\rho$-correlated. The Procrustes matching problem asks us to recover the unknown permutation of $[n]$ that aligns the two sets. The problem is well-studied in the low-dimensional regime $d=O(\log n)$, but the high-dimensional regime $d\gg \log n$ has remained largely uncharted: prior matching guarantees require nearly perfect correlation $\rho=1-o(1)$, even for information-theoretic recovery. Our main result is a polynomial-time algorithm for exact recovery at constant correlation. The algorithm works by computing and comparing weighted counts of a specially chosen family of “wide” trees. So long as $d\ge \mathrm{polylog}(n)$, the algorithm succeeds with high probability for any $\rho^2>\sqrt{\alpha}$, where $\alpha\approx 0.338$ is Otter's tree-counting constant. We complement this algorithmic result with an improved information-theoretic guarantee, showing that exact recovery is possible when $\rho^2 \gtrsim \max\{\log n/d,\sqrt{\log n/n}\}$. We also carry out a low-degree advantage calculation, which suggests that the condition $\rho^2 > \sqrt{\alpha}$ is necessary for any tree-counting algorithm.

Belief propagation (BP) is widely used for data association (DA) in target tracking. Existing convergence analyses of BP for DA address only the two-way correspondence between targets and measurements, where each target generates at most one measurement per scan. Multipath DA (MPDA) allows a single target to produce multiple measurements via distinct propagation paths, creating a three-way correspondence among targets, paths, and measurements, for which a complete convergence proof has not yet been provided. We provide such a proof for the BP updates in MPDA, establishing convergence to a unique fixed point. Simulations illustrate the convergence behavior of BP in MPDA and demonstrate a favorable accuracy–efficiency trade-off relative to both single-scan and two-scan variants of the multiple-detection multiple-hypothesis tracker.

Proximity gaps are a property of error correcting codes that arise in the study of Interactive Oracle Proofs (IOPs) and Succinct Non-interactive Arguments of Zero Knowledge (SNARKs). Recent work of Goyal and Guruswami has established near-optimal proximity gaps for many families of codes, including subspace design codes, as well as random ensembles like random linear codes, Reed-Solomon codes with random evaluation points, and Gallager's ensemble of LDPC codes (Goyal & Guruswami, 2025). However, the parameters for these latter randomized ensembles are worse than the parameters for subspace design codes, and degrade as the degree ell increases. In this work, we obtain improved proximity gaps for random ensembles of codes, including random linear codes, Reed-Solomon codes with random evaluation points, and Gallager's ensemble. Quantitatively, our results for these random ensembles match the results that Goyal and Guruswami attained for subspace design codes. In fact, our techniques are a black-box transference from subspace design codes: any progress on subspace design codes will automatically lead to analogous progress for these random ensembles. To obtain our results, we extend the Local Coordinate-wise Linear (LCL) property framework developed by Levi, Mosheiff, and Shagrithaya and by Brakensiek, Chen, Dhar, and Zhang to a row-span constrained version (Levi, Mosheiff & Shagrithaya, 2025; Brakensiek, Chen, Dhar & Zhang, 2025). This allows us to cast curve-decodability – a property that implies proximity gaps – directly as a row-span constrained LCL property, and make use of that machinery. In contrast, because curve-decodability is not obviously a vanilla LCL property, prior work had worked with a proxy property instead, leading to the aforementioned parameter losses.

We consider the design of low-density parity-check (LDPC) codes for a given iterative decoder. While LDPC performance can be evaluated using simulation, density evolution (DE), or EXIT-chart analysis, selecting a parity-check matrix (PCM) remains a difficult combinatorial optimization problem. Existing approaches often rely on population-based search, random mutations, or genetic algorithms, which require careful tuning and incur high computational cost. Recent gradient descent (GD)-based methods optimize relaxed PCMs by differentiating through decoder simulations, but rely on noisy Monte Carlo estimates, line searches over soft matrix representations, and remain costly for long codes. Moreover, the loss is typically evaluated only at integer-valued PCMs. We focus on long protograph-based LDPC codes and propose a deterministic GD-based framework operating directly on a relaxed protograph representation. The loss is based on DE bit error rate (BER) and can be evaluated directly for relaxed protographs. To justify this relaxation, we associate the relaxed representation with an ensemble of binary PCMs and show that the proposed relaxed DE yields the ensemble-averaged DE performance. The resulting procedure supports standard GD optimization and achieves fast, reliable convergence through deterministic DE evaluation and informative gradients. Numerical results show that the optimized protographs outperform 5G LDPC codes with matching dimensions.

Multi-antenna unmanned aerial vehicle (UAV)-aided communication presents a promising solution to increase the system capacity and improve the quality of service (QoS) of the future wireless networks. In this paper, we equip a UAV platform with a rotatable antenna array (RAA), which can be rotated flexibly in three-dimensional (3D) space via an onboard gimbal, enabling additional spatial degrees of freedom (DoFs) for improving multiuser signal transmission and interference management. Compared with a conventional fixed antenna array (FAA), the RAA can proactively align users with the high-gain region of its antenna elements and reduce the spatial channel correlations among users. To demonstrate the advantages of RAA, we jointly design the RAA orientation and beamforming to maximize the sum-rate of multiple users subject to per-user QoS constraints. The formulated problem is highly nonconvex and exhibits strong coupling between the RAA orientation and beamforming variables. To solve this challenging problem, we propose first an optimization framework based on the penalty dual decomposition (PDD) method to iteratively optimize RAA orientation and beamforming. While the optimization framework yields high reliability in QoS satisfaction and favorable sum-rate performance, its iterative nature may hinder real-time deployment. To accelerate the joint design and preserve a high-quality solution, we further propose a deep learning (DL) framework based on graph neural networks (GNNs). Simulation results demonstrate that RAAs significantly outperform FAAs in UAV-aided communication. Additionally, the proposed optimization framework is capable of satisfying stringent QoS requirements with high reliability, while the proposed DL framework attains comparable sum-rate performance with substantially reduced computation time and exhibits robustness to user position information errors.

Distribution goodness-of-fit testing has developed a powerful rate-level theory: we often know how the required sample size scales with the alphabet size, the separation from the null, and the target error probability. Uniformity testing is the canonical example. One can distinguish the uniform distribution on $N$ categories from alternatives at total-variation distance at least $\epsilon$ with far fewer than $N$ samples, and the optimal scaling is now well understood. But rate-level theory leaves an important question unresolved: among several tests with the same sample-complexity order, which one actually gives the best risk or power? This is a constant-level question. It is especially relevant in modern applications where distribution testing is used not merely as an asymptotic abstraction, but as a practical design tool. This note argues that sharp constants in distribution testing play a role analogous to Fisher information in parametric estimation and Pinsker's constant in nonparametric estimation. First, they distinguish between tests that are all rate-optimal but not equally powerful. Second, they reveal the effective signal-to-noise ratio governing the testing problem. Third, they can guide tuning-parameter choices in downstream applications. We illustrate this perspective through large-alphabet uniformity testing and then explain why the same logic matters for choosing the number of bins in calibration testing.