We prove that the covering radius of the third-order Reed--Muller code in eight variables is fifty-six. The proof separates even- and odd-weight inputs by moment-controlled slicing. On the even side, a transport invariant on quadratic-label stars and consistency of singleton restrictions give a compatible cubic correction. On the odd side, symmetry of the third moment yields a covariance-rank obstruction. Its rank-two exception is a quartic plus three points of a two-plane; the zero-second-moment case is a prescribed-point perturbation of a quintic. We prove that every such point perturbation has third-order nonlinearity at most fifty-five by a marked derivative identity and complete restriction-code covers. Consequently the maximum among exact-degree-eight functions is fifty-five. The structural reductions are proved analytically, and complete finite certificates verify the explicitly stated local covering and compatibility assertions. The matching lower bound follows from the published quartic relative radius.
We prove that any linear $3$-query locally correctable code $C \colon \mathbb{F}_2^k \to \mathbb{F}_2^n$ with constant correction radius must have length $n \geq 2^{Ω(\sqrt{k})}$. This improves on the prior best lower bound of $2^{Ω(\sqrt{k/\log k})}$, due to [AG24], and shows that the folklore construction of linear $3$-LCCs from Reed-Muller codes, which achieve length $n = 2^{O(\sqrt{k})}$, is optimal up to constant factors in the exponent. Our proof builds on the approach of [KM24a], further refined in [Yan24,KM24b], that uses "chain derived equations" in combination with Kikuchi graphs. The crux of our argument is to show that a certain edge-coloured Kikuchi graph has a unique colour cycle: a cycle in which some colour is used exactly once. We do this by controlling the distribution of colours at each vertex in the graph using a random walk mixing argument and a novel hypergraph decomposition based on edge expansion of the hypergraph's "flattening" into a graph.
We study dependence measures between two discrete random variables. The measures vanish at independence and satisfy the data processing inequality (DPI): stochastic post-processing of one variable cannot increase dependence. We ask which such measures admit an exactly unbiased estimator from a fixed finite number of i.i.d. samples, a property equivalent to being polynomial in the joint probabilities. We distinguish fixed-alphabet DPI, which preserves the alphabet size of the variable being processed, from dimension-changing DPI. Under one-sided fixed-alphabet DPI, every measure with a continuously differentiable extension to a neighborhood of the closed probability simplex vanishes whenever one processed state has zero probability. If the processed alphabet is larger than the other alphabet, the measure is identically zero. If it has $n$ states and the other alphabet has at least $n$, every nonzero polynomial measure has degree at least $2n$ and requires at least $2n$ samples for unbiased estimation. Both bounds are attained by the Gram determinant. Under one-sided dimension-changing DPI, every family with the same boundary regularity is identically zero. These results yield sharp task bounds for multi-task peer prediction. For two agents with $n$ signals each, $2n$ tasks are necessary and sufficient for nontrivial expected payments that vanish for independent reports and cannot increase under memoryless stochastic garbling. Under these requirements, unequal signal-space sizes force the larger-alphabet agent's expected payment to vanish identically for any finite number of tasks.
Cicero Carvalho, Maria Vaz Pinto, Rafael H. Villarreal
Let $X$ be a projective nested product of fields and let $δ_X(d)$ be the minimum distance in degree $d\geq 1$ of the projective nested Cartesian code $C_X(d)$. The regularity index ${\rm reg}(δ_X)$ of the minimum distance function $δ_X$ is the minimum integer $d_0\geq 0$ such that $δ_X(d)=1$ for $d\geq d_0$. We give a formula for ${\rm reg}(δ_X)$ by determining an indicator function of least degree for each point of $X$ and using the fact that ${\rm reg}(δ_X)$ is the ${\rm v}$-number of the vanishing ideal $I_X$ of $X$. Then we give an arithmetical criterion that characterizes when $X$ is Cayley--Bacharach.
Sana Javed, Francisco Garcia-Herrero, Bane Vasić, Mark F. Flanagan
In quantum error correction, the decoder must estimate the errors from the measurement data accurately and fast enough to avoid a backlog. Search-based decoders such as Tesseract achieve high accuracy by finding a minimum-weight set of error events with an A* search, but their search effort grows rapidly with the physical error rate and the code size. To reduce this search effort while maintaining a logical error rate close to that of Tesseract, we propose a belief propagation (BP)-guided modification of the Tesseract decoder for quantum low-density parity-check (LDPC) codes. Damped sum-product BP is applied to the triggered detectors before the Tesseract search. If the detectors triggered by the BP hard decision match the triggered detectors, this hard decision is accepted directly, and the Tesseract search is skipped. Otherwise, the BP marginal probability estimates, weighted by a trust coefficient, modify the search priority, while the path cost keeps the channel-prior weights so that the decoding objective is unchanged. The framework also supports BP-based initialization, in which selected BP decisions form the starting point of a residual search whose signed-cost objective allows incorrect initial decisions to be removed. A node-exploration limit bounds this residual search; if the limit is reached, the decoder falls back to the BP-guided search on the original triggered detector set. The method is evaluated on the [[72,12,6]], [[90,8,10]], and [[144,12,12]] bivariate bicycle codes under circuit-level noise. With BP-based initialization and a global trust coefficient, the number of Tesseract search nodes expanded is reduced by up to more than two orders of magnitude at low physical error rates, while the logical error rate remains close to that of Tesseract.
Dean Doron, Tal Leonov, Jonathan Mosheiff, Henrique Navas, Nicolas Resch, João Ribeiro
We show that random linear codes (RLCs) possess nearly optimal discrepancy-type properties in a broad range of settings. Our main results are two general discrepancy theorems: one controls all translates of a fixed test, and the other controls large families of Fourier-pseudorandom tests. Two motivating examples follow: First, RLCs behave essentially like unstructured random codes for list-decoding from errors above capacity. More precisely, an RLC $C\subseteq \mathbb{F}_q^n$ of rate $1 - \frac{1}{n}\log_q|B_ρ| + \varepsilon$, where $|B_ρ|$ is the volume of a radius-$ρ$ Hamming ball in $\mathbb{F}_q^n$, satisfies $|C \cap B| = (1\pm o(1)) \frac{|C|\cdot |B|}{q^n}$ simultaneously for all radius-$ρ$ Hamming balls $B$ with high probability. This significantly strengthens the best prior results, which follow from work by Blinovsky (1987, 1990) and Levitin (1988) on the covering properties of RLCs. Second, over prime fields, RLCs behave essentially like unstructured random codes for zero-error list-recovery, and list-recovery from erasures, above capacity. More precisely, for a prime $q>2$ and input list size $2\leq \ell\leq q-1$, an RLC $C\subseteq \mathbb{F}_q^n$ of rate $1-\log_q \ell+\varepsilon$ will satisfy $|C \cap S| = (1\pm o(1)) \frac{|C|\cdot \ell^n}{q^n}$ simultaneously for all combinatorial rectangles $S=S_1\times S_2\times\cdots\times S_n$, where $|S_i|=\ell$ for all $i$, with high probability. An analogous result also holds when we can bound $|S_i|$ only for some of the $i$'s. We use this to show the abundance of locally leakage-resilient $n$-party linear ramp secret sharing schemes with any linear reconstruction threshold and sublinear threshold gap $O(n/\log n)$ over fields of polynomial size $q=Θ(n^γ)$ for a constant $γ\in(0,1/5)$. Prior work was stuck at reconstruction thresholds above $n/2$ for both threshold and ramp schemes.
Oways Alsoloh, Robert-Jeron Reifert, Aymen Khaleel, Stefan Roth, Aydin Sezgin
Beamforming designs for integrated sensing and communication (ISAC) in cell-free multiple-input multiple-output (MIMO) systems face the challenge to stay reliable under uncertainties from both channel state information (CSI) as well as clutter. To this end, this paper proposes an impairment-aware heterogeneous graph neural network (GNN) framework for beamforming that obtains the CSI error level and the clutter covariance as edge features, which enables a single trained model to adapt to both impairments. In particular, the GNN is trained on a low quantile of the minimum user rate with a clutter-aware signal-to-clutter-plus-noise ratio, balanced by a normalized Tchebycheff scalarization. Simulation results show that the proposed GNN framework outperforms the considered baselines in sensing-only and communication-only settings. Depending on the operating point, a single GNN model attains approximately 97\% of each baseline's rate while serving both functionalities at once. The model further generalizes to unseen CSI error levels and clutter counts and renders the ISAC system resilient.
Aamer Mohamed Huroon, Ali A. Nasir, Daniel B. da Costa
Beyond-diagonal reconfigurable intelligent surfaces (BD-RISs) extend conventional diagonal RISs by allowing controllable coupling among reflecting elements. This flexibility is attractive for aerial networks, where unmanned aerial vehicles (UAVs) face rapidly varying channels and strict power limits. In this paper, we study a hybrid BD-RIS-assisted multi-UAV rate-splitting multiple access (RSMA) downlink, in which UAVs within favourable BD-RIS coverage use both direct and BD-RIS-aided links, whereas the remaining UAVs are served through direct links only. We formulate a network sum-rate maximization problem that jointly optimizes UAV trajectories, RSMA common-rate allocation, beamforming, BD-RIS scattering matrices, and UAV-BD-RIS association. The resulting mixed-integer non-convex problem is solved by using deep deterministic policy gradient (DDPG) algorithm, equipped with a constraint-preserving action layer that generates reciprocal and lossless BD-RIS responses in closed form and handles the binary association inside the environment transition. Simulation results, averaged over three training seeds under a physically consistent channel model with blocked direct links near the BD-RISs, show that the proposed design attains a sum rate comparable to SAC and higher than twin delayed deep deterministic policy gradient ( TD3), proximal policy optimization (PPO), and deep Q-network (DQN), exceeds per-slot alternating optimization with fixed trajectories at about 1/65 of its per-slot runtime, and benefits mainly from RSMA, while the additional BD-RIS gain is modest.
In the hotplug coded caching model, $K$ users fill their caches of size $M$ as a function of $N$ files, but only an unknown subset of $A\leq K$ users is active in the delivery phase. In all regimes where the optimal hotplug tradeoff is known, it depends only on $A$, not on $K$; whether this holds in general is open. We show that: (i) Under uncoded placement, YMA delivery with MAN placement, where offline users are assigned the demands of active users, is optimal. Hence, offline users cause a strict load penalty at intermediate memory sizes, while the MAN placement is optimal for every number of active users; (ii) Under row-wise placement (RWP), where each cache is a function of the user's own row of each file, every classical scheme can be embedded in a Reed-Solomon code. The resulting hotplug scheme has the tradeoff of the classical model with $A$ users, for every $A\leq K$: there is no load penalty, but the placement depends on $K$. We then derive a converse for RWP, which shows that: (a) for $2\leq N\leq A$, the scheme of Gomez-Vilardebo (GV) is RWP optimal for $AM\leq N/(N-1)$, which settles the RWP tradeoff for $N=2$; (b) YMA is RWP optimal at $AM=N$; and (c) for $N=A=3$, GV is RWP optimal for $M\leq 1$. Hence, the Reed-Solomon embeddings of these schemes are optimal among embedded RWP schemes.
Chandan Kumar Sheemar, Sourabh Solanki, Wali Ullah Khan, George C. Alexandropoulos, Symeon Chatzinotas
Stacked intelligent metasurfaces (SIMs) cascade several closely spaced programmable metasurface layers so that an electromagnetic wave undergoes repeated modulation-propagation interactions before leaving the stack. The stack thereby implements, at the speed of propagation and with few radio-frequency chains, high-dimensional analog transformations that would otherwise require digital precoding, combining, spatial filtering, focusing, or inference. Since 2023, SIM research has produced more than two hundred articles, a dedicated magazine special issue, and two survey-level overviews organized around applications and wave-domain computing. This article complements them with a model-to-hardware perspective. First, we present the electromagnetic modeling hierarchy of SIMs, making explicit the assumptions under which the models coincide, their validity regimes, and their computational complexity, with a common notation for hardware non-idealities and power consumption. Second, we present a methodology-first taxonomy (SIM-aware channel acquisition, model-based optimization, statistical-CSI design, learning-based control, and hardware-aware robust design), compare the families in terms of CSI requirements, complexity, convergence, and hardware constraints, and reconcile conflicting findings in the literature. Third, we synthesize applications by the physical role of the SIM. Fourth, we quantitatively compare experimentally demonstrated multilayer prototypes, separate validated from conceptual architectures, and discuss thermal, tolerance, and calibration issues. Fifth, we provide a tutorial-style performance and trade-off analysis anchored in reported results. Finally, we map evidence-based challenges to research directions with measurable targets. Lessons learned are summarized at the end of every section.
We study local coordination on finite graphs, equivalently, the ability of randomized local protocols with independent private randomness to produce highly correlated outputs at neighboring vertices. Hutchcroft, Rospuskova, and Tamuz (2026) showed that if such local coordination can be achieved with low cost, then the graph admits a low-cost leader profile, or equivalently an appropriate bounded-radius decomposition, with a square-root loss in the cost. We substantially improve this bound for unbiased binary outputs. If the average disagreement is $\varepsilon$, we construct a leader profile of cost $O(\varepsilon\log(1/\varepsilon))$. The key ingredient is an information-theoretic influence measure: after fixing an ordering of the independent information sources, we assign to each binary output the increments of mutual information revealed along that ordering. For two outputs that disagree with probability $p$, the corresponding measures are within binary entropy $h(p)$ in total variation. Combined with a grand coupling theorem, this yields the improved bound. We also show that a universal linear bound is impossible. We construct graphs with binary local profiles of cost $O(\varepsilon)$ for which every leader profile has cost $$ Ω\!\left(\varepsilon\sqrt{\log(1/\varepsilon)}\right). $$ The construction uses weighted majority functions and can be implemented as an action-symmetric Nash equilibrium, giving a negative answer to the question of HRT whether leader equilibria are always optimal up to a constant factor. Finally, we show that the binary assumption is essential: for general real-valued outputs, the square-root dependence of the HRT theorem is sharp up to a universal constant.
Fluid antenna systems (FASs) have shown that activating a single port from a densely packed antenna array can yield spatial diversity comparable to that of tens of independent antennas, a property that has substantially improved communication reliability and efficiency. The fluid antenna array (FAA) extends this concept to multi-port configurations while avoiding complex multi-dimensional spatial correlation, and offers significant geometrical flexibility under a finite aperture and a limited port budget. These attributes motivate environment-adaptive array geometry for sensing in integrated sensing and communication (ISAC) systems. Although this flexibility enables adaptive array geometries that exploit near-field distance-angle information, improving multi-parameter target estimation under communication and deployment constraints remains challenging. In this paper, we propose a planar FAA-assisted near-field ISAC framework for multiuser communication and target sensing. Specifically, we derive the Fisher information matrix (FIM) and the corresponding Cramér-Rao bound (CRB) for the joint estimation of target range, zenith angle, azimuth angle, and radial velocity. Based on the derived CRB, we jointly optimize the FAA port positions and transmit beamforming to improve sensing accuracy while satisfying communication signal-to-interference-plus-noise ratio (SINR), transmit power, and physical deployment constraints. To solve the resulting non-convex problem, we develop a two-stage alternating optimization algorithm, in which transmit beamforming is optimized through semidefinite relaxation (SDR), while FAA port positions are successively optimized through discrete search and continuous refinement. Simulation results indicate that the proposed algorithm achieves favorable sensing performance while maintaining a reasonable computational cost.
Coded distributed computing (CDC) mitigates the Shuffle communication bottleneck through coded multicast, but existing schemes with predetermined worker populations do not directly adapt to worker arrivals and disconnections. To address these dynamics, we propose a dynamic CDC scheme that preserves surviving workers' caches and Reduce assignments while exploiting the storage brought by arriving clusters. The model accommodates general MapReduce tasks under a placement that is partly fixed and partly new. The scheme uses Cartesian products of cluster-wise placement delivery arrays (PDAs) for file placement. A delivery-aware greedy algorithm reassigns abandoned Reduce functions, and a Communication Array allows workers with no Reduce function to serve as coded transmitters. For arbitrary feasible disconnections, the scheme's exact communication load is derived. A converse bound under one-shot communication shows that, in the absence of disconnections, the scheme lies within a factor of 2 of the lower bound under these assumptions when new clusters arrive, and within a factor of 4 otherwise.
Since self-orthogonal codes, few-weight codes and linear complementary dual codes(LCD codes, for short) have nice applications in coding theory and cryptography, they have received continuous attention. In 2024, by introducing the notion of the augment code, Heng et al.[16] constructed several classes of few-weight self-orthogonal codes basing on defining sets, which are introduced by Ding et al.[7] in 2007. In this manuscript, for two classes of defining sets, we consider the corresponding augmented codes, construct three classes of four-weight self-orthogonal projective codes and determine the parameters of their dual codes. And then, we construct three classes of LCD codes. In particular, we prove that there exists a class of these LCD codes whose dual codes are almost optimal LCD codes according to the sphere packing bound.
A subspace design is a collection of subspaces $H_1,\ldots,H_n$ of $\mathbb{F}_q^k$ with the property that no low-dimensional subspace $W$ intersects the collection "too much". Subspace designs and related objects in linear-algebraic pseudorandomness have found a broad range of applications, ranging from list decoding to derandomizing algorithms. We construct explicit strong subspace designs over every finite field. In the extremal case where the co-dimension $t$ of each $H_i$ is equal to the dimension of $W$, for every constant field size our construction attains $n=Ω(k)$ and matches the probabilistic intersection bound up to a constant factor. All previous constructions required the field size to grow with $t$ (or $k$). Our subspace designs also imply new constructions of rank condensers over arbitrary finite fields. This result is the first to achieve an optimal dependence on $k$ while maintaining both a constant output entropy rate and a constant field size. As an application, we construct lossless rank extractors for linear sources of rank $r$, for all $r < q$, with parameters matching those of Guo, Raj, Shangguan and Zhang (FOCS '26), thereby generalizing their result to prime fields and smaller field sizes. Our construction is based on an algebraic-geometric version of the Parvaresh--Vardy codes (Parvaresh--Vardy FOCS '05, Guruswami ECCC '05), extending the framework underlying the condensers of Guruswami, Umans and Vadhan (JACM '09). We view our construction as a linear-algebraic analysis -- tailored to affine sources -- of the GUV construction, generalized to functions over algebraic curves. More specifically, inspired by Ta-Shma and Umans (CCC '12) we develop a two-level evaluation scheme, where we first evaluate a function on a curve at extension-field points, and then evaluate a corresponding affine-linear polynomial to obtain outputs over the base field.
By adjusting their reflection coefficients, intelligent reflecting surfaces (IRSs) can reshape the channels between a base station (BS) and user equipment (UE). Existing studies mainly optimize IRS phase-shifts for communication objectives, leaving the physical attainability of prescribed IRS-reflected channels largely unexplored. This paper investigates channel customization with a phase-only IRS under three progressively relaxed criteria. Observing that the customization mean-squared error (MSE) has the same mathematical form as the signal MSE of a point-to-point multiple-input multiple-output system, we construct a counterpart problem to characterize individual singular-coordinate gain limits and the condition for attaining the amplitude-matching upper bound. To address multi-stream phase conflicts, we analyze principal contribution area (PCA) overlap and derive sufficient array-size conditions for disjoint PCAs under a specified focused-vector construction with parallel uniform linear arrays. We also derive necessary conditions from the two propagation links' singular values and an array-size restriction under the parallel-array Fresnel model. Both the restriction and the construction involve the BS--IRS array-size product. Numerical results show that jointly selecting right singular vectors and IRS phase-shifts reduces mean customization MSE, whereas gains exceeding propagation spectral limits cannot be realized exactly. These results provide design guidance and highlight spectral limits of phase-only IRS channel customization.
In undirected multiple-unicast networks, where independent messages are sent between specified source--destination pairs, network coding allows intermediate nodes to combine messages, whereas fractional routing splits and forwards individual messages along paths without mixing them. Proposed in 2004 by Li and Li and independently by Harvey, Kleinberg, and Lehman, the multiple-unicast conjecture---a central conjecture in network coding with deep connections to computational complexity---asserts that network coding and fractional routing have the same achievable rate region. We construct a counterexample refuting this conjecture and use it to reduce block transfers in external-memory data rearrangement, thereby accelerating external-memory integer sorting and answering in the affirmative the longstanding question of Aggarwal and Vitter (1988) on whether integer operations can beat the comparison-sorting input/output (I/O) bound. Specifically, we give a deterministic sorting algorithm: for $N$ integers of $Θ(\log N)$ bits, a memory holding $M$ integers, and block transfers of $B$ integers, where $2B\le M\le N$, the number of block transfers is \[ O\!\left(\frac{N}{B}\left[1+ \frac{\log N}{(\log(M/B))^{1-\varepsilon}(\log M)^\varepsilon} \right]\right), \] where $\varepsilon=1.5\times10^{-5}$ is an absolute constant. This bound asymptotically improves on the classical $Θ\!\left(\frac{N}{B}\left[1+ \frac{\log(N/M)}{\log(M/B)}\right]\right)$ comparison-sorting bound in certain parameter regimes. Under the external-memory model specified in this paper, we have formally verified the algorithm's correctness and I/O complexity bound in Lean~4.
Konstantinos Bountrogiannis, Anthony Ephremides, Panagiotis Tsakalides, George Tzagkarakis
This work introduces a framework for analyzing the Age of Incorrect Information (AoII) in a real-time monitoring system with a generic discrete-time Markov source. We study a noisy communication system employing a hybrid automatic repeat request (HARQ) protocol, subject to a transmission rate constraint. The optimization problem is formulated as a constrained Markov decision process (CMDP), and it is shown that there exists an optimal policy that is a randomized mixture of two stationary policies. To overcome the intractability of computing the optimal stationary policies, we develop a multiple-threshold policy class where thresholds depend on the source, the receiver, and the packet count. By establishing a Markov renewal structure induced by threshold policies, we derive closed-form expressions for the long-term average AoII and transmission rate. The proposed policy is constructed via a relative value iteration algorithm that leverages the threshold structure to skip computations, combined with a bisection search to satisfy the rate constraint. To accommodate scenarios requiring lower computational complexity, we adapt the same technique to produce a simpler single-threshold policy that trades optimality for efficiency. Numerical experiments exhibit that both thresholdbased policies outperform periodic scheduling, with the multiplethreshold approach matching the performance of the globally optimal policy.
This paper develops a receiver-specific mean-squared-error (MSE) framework for cooperative integrated sensing and communication (ISAC) localization using random orthogonal frequency-division multiplexing (OFDM) payloads. It captures local peak perturbations and incorrect ambiguity-peak acquisition for two classical receiver processing schemes: matched filtering (MF) and reciprocal filtering (RF). For scatterers well separated in delay, we quantify how frequency spread and interference induced by symbol-energy fluctuations affect local delay errors under MF. RF removes symbol-dependent weighting but amplifies noise for low-energy symbols. Payload-conditioned joint Gaussian delay profiles yield peak-selection probabilities, which combine with nonlinear multistatic fusion errors to approximate position MSE while accounting for network geometry. Numerical results illustrate receiver-dependent estimation errors and the benefits of frequency-dependent constellation allocation.
Jinpeng Huang, Gangshan Jing, Kai Zhao, Yongduan Song
Angle rigidity theory provides a theoretical basis for characterizing the geometric shape of graphs embedded in the plane under angle constraints, and establishing global convergence of angle-based network localization algorithms. The related references, however, are largely restricted to graphs generated by triangulation or bilateration ordering, which are sufficient but not necessary for angle rigidity. This paper addresses this challenge by focusing on establishing the equivalence between angle constraints and bearing constraints. The conditions for cycle compatible frameworks (with possibly non-generic configurations) to be angle fixable are provided. Moreover, it is shown for the first time that Laman graphs equivalently characterize minimally globally angle rigid graphs, implying that a Laman graph is the simplest graph that allows a generic embedding in the plane to be uniquely determined by subtended angles. As an application, a distributed algorithm for angle-based sensor network localization is proposed, which guarantees global convergence under a much milder network topology condition than those in the literature.
Zhiyu Huang, Chen Sun, Guyue Li, Guanghui Wen, Xianbin Wang
Physical-layer key generation (PLKG) exploits reciprocal channel dynamics to generate symmetric keys, addressing the key distribution problem in wireless communications. However, strong temporal correlation in slow-fading environments limits fresh randomness and results in low key generation rates. Movable antennas (MAs) introduce spatial degrees of freedom through antenna repositioning, providing a new approach to addressing the limitation. This paper investigates MA-assisted PLKG over temporally correlated channels. A first-order Gauss-Markov process is utilized to characterize the temporal correlation of multipath gains. We characterize the full-sequence mutual information (MI) over temporally correlated channels. For fixed antenna positions and beamforming, we establish a finite-horizon approximation error bound that vanishes as both effective signal-to-noise ratios (SNRs) increase. We derive a closed-form expression for the one-step conditional MI and adopt it as a tractable key-information metric. A nonconvex problem is formulated to jointly optimize antenna positions and per-slot beamforming under transmit-power and minimum-spacing constraints. We develop an alternating optimization algorithm, combining an exact principal-eigenvector beamforming solution with feasible SCA-based projected gradient position updates. Simulation results demonstrate that the MA-assisted scheme outperforms the fixed-position antenna baseline. At a high temporal correlation coefficient, position optimization achieves approximately $51\%$ higher rates than fixed antennas. Joint position and beamforming optimization provides a further $106\%$ gain over position optimization alone, demonstrating more pronounced gains under strong temporal correlation.
Pinching-antenna systems (PASS) reconfigure the wireless channel by positioning dielectric antennas along a waveguide. A single waveguide, however, confines its antennas to one line, so that good coverage of an area has relied on several waveguides or waveguide segments with separate feeds. This paper proposes X-PASS, in which a hub feeds radially deployed waveguide arms, one pinching antenna on each, and drives them by arm selection, aggregation or multiplexing. It models the hub with its insertion losses, derives a unified signal-to-noise ratio expression for these three operating modes, and derives in closed form a radius inside which aggregation outperforms selection. Numerical results validate the analysis and compare the coverage of X-PASS with that of the other layouts at equal transmit power.
We determine the information complexity of matrix multiplication over finite fields under independent uniform inputs, up to a universal additive constant. The binary inner-product case resolves the open question of Braverman, Garg, Pankratov, and Weinstein on the optimal dependence of information complexity on the error probability. For inputs in $\mathbb F_2^m$ and error at most $\varepsilon\in[0,1/2]$, the information complexity with output at Bob lies between $(1-2\varepsilon)m-c_0$ and $(1-2\varepsilon)m$, where $c_0<4.772$ is a universal constant. For independent uniform matrices $X\in\mathbb F_q^{t\times m}$ and $Y\in\mathbb F_q^{s\times m}$, where $t\le s$, computing $XY^{\mathsf T}$ with output at Bob and error at most $\varepsilon\in[0,1]$ has information complexity $(1-q^{ts}\varepsilon/(q^{ts}-1))^+mt\log_2q$, up to an additive gap of less than $9.544$ bits. This gap is independent of the matrix dimensions, field size, and error. At zero error, the information complexity is exactly $mt\log_2q$. The information lower bounds for both inner product and matrix multiplication follow from a new Shannon-to-min-entropy theorem for convolution on discrete groups. Let $Q_1,\ldots,Q_k$ be the finitely supported distributions of independent random variables taking values in a discrete group, and let $s$ be the largest support size. We show that if $k\ge\lceil\lfloor\log_2s\rfloor\ln2\rceil$, then the min-entropy of their ordered product is at least the average Shannon entropy of the $Q_i$ minus $c_0$ bits. This holds for arbitrary discrete groups, including infinite and noncommutative groups, even when the input distributions differ. The leading coefficient of the logarithmic threshold is optimal.
Symmetric primitives over Galois rings need nonlinear components whose differentials with respect to ring addition are controlled. Let $R=\mathrm{GR}(4,m)$ and $q=2^m$, so that $(R,+)\cong(\mathbb{Z}/4\mathbb{Z})^m$ has order $N=q^2$. For every $m\ge1$ we construct an explicit permutation $G_c$ of $R$ all of whose differentials with a nonzero input difference have probability at most $36/N$, whereas every permutation polynomial of $R$ has such a differential of probability at least $2/\sqrt{N}$ (Ronjom--Sandrib). The bound holds for the fixed permutation itself, not on average over keys. Equivalently, $Δ(G_c)\le36$ against $Δ\ge2\sqrt{N}$ for permutation polynomials; since every permutation has $Δ\ge2$, the least differential uniformity of a permutation of $(\mathbb{Z}/4\mathbb{Z})^m$ lies between $2$ and $36$ for every $m$. In Teichmuller digits $(a,b)\in\mathbb{F}_q^2$ and for $c\in\mathbb{F}_q$ of absolute trace $1$, $G_c(a,b)=(L,(L^2+L+c)a)$ with $L=(a^2+a+c)b$. The map is $F_c\circ J\circ F_c$, where $F_c(a,b)=(a,(a^2+a+c)b)$ is induced by a polynomial over $R$ and $J$ exchanges the digits: a single digit exchange between two polynomial layers yields a bound independent of $m$. The proof reduces the difference equations, in each of three types of directions, to one-variable polynomials whose degrees do not depend on $m$. For general maps $F\circ J\circ F$ with $F(a,b)=(p(a),h(a)+d(a)b)$, where $p,d,h$ have degrees bounded independently of $m$, $p'\ne0$ and $d$ has no zeros, a Jacobian identity in characteristic $2$ bounds the differentials with nonzero low input and output differences independently of $m$; the remaining directions need a separate argument, which we give for an explicit family ($Δ\le440$, resp. $510$, for odd $m$).
Parallel samplers, including masked diffusion models, generate several coordinates per round from conditional marginals, and their accuracy depends on which coordinates are revealed together. A schedule can be improved in two natural ways: adaptively, by choosing later batches from the values already generated, or by randomization, by drawing the schedule at random. We show that randomization is strictly more powerful. For every $r \geq 1$ we construct a full-support distribution on $9r$ binary coordinates such that every deterministic three-round sampler, even with value-dependent batches and arbitrary product kernels, has forward Kullback-Leibler divergence at least $γr - \log 4$ with $γ\approx 0.0966$, whereas drawing one of four fixed schedules with two fair bits drives the divergence below $18 r β^r$ with $β\approx 0.966$. Both samplers query conditionals of the same target. The separation holds for every fixed number of rounds $T \geq 2$, a strict advantage survives perturbations of the target and errors in the conditional predictor, and exact rational arithmetic certifies the gap at nine coordinates, where trained neural predictors preserve it. The mechanism is a hidden mixture: each schedule preserves the dependence pattern of one component, while no deterministic first batch can serve them all.
Measuring devices do not always function perfectly due to fatigue, damage, or malfunction. When device repair or replacement is not possible, it becomes necessary to seek optimal measurements from a broken device. We show this is possible via a sequential decision making process where we optimize measurement sequences over the remaining available measurements using information theory. With dynamic programming, we show greedy measurement sequences are always suboptimal for a simple class of measurement constraints. Greedy measurement sequences generally lead to equiprobable measurement outcomes, while the optimal policy is found to select each measurement in such a way as to assign a low probability to any measurement outcome that triggers a constraint condition; leading to measurement outcomes that are not equiprobable. A measurement sequence generated under this policy is shown to decompress its source: that is, the expected number of measurement outcomes is strictly greater than the number of bits it encodes, defining a key property of constrained measurements. Dynamic programming is inefficient for finding optimal measurement sequences, so we develop an alternative algorithm related to optimal binary decision trees. By deriving upper and lower complexity bounds for the task, we propose this algorithm as an efficient means to find optimal measurements for a broken or constrained measuring device.
Quantum channel relative entropy can be nonadditive, making its regularization essential for asymptotic analysis. We study when the regularized value is attained at finite blocklength and how efficiently it can be approximated. For the first question, we establish a sharp dichotomy: the regularized value is either attained already at the single-copy level, implying additivity at every blocklength, or is never attained at any finite blocklength. Notably, a simple two-copy additivity test distinguishes between these alternatives for qubit channels and for channel pairs in arbitrary dimensions admitting an interior optimizer. We further show that both the interiority condition and finite nonattainment are generic, holding for almost every channel pair. For the second question, we establish explicit convergence rates for approximating the regularized channel relative entropy. For fixed channel dimensions, $\widetilde O(\varepsilon^{-3/2})$ channel copies suffice to approximate the regularized value to additive accuracy $\varepsilon$. Alternatively, a semidefinite hierarchy achieves the same accuracy at level $\widetilde O(\varepsilon^{-2})$, yielding a certified polynomial-time approximation. Together, these results reveal the intriguing structure and generic behavior of regularized channel relative entropy, sharpening our understanding of both its analytical and computational aspects.
Inspired by the optimization approach to biology, we formulate an inverse problem for communication with memory: construct a finite-state channel for which a given signaling behavior supports capacity-achieving codes. Dynamic measure matching is introduced to turn a directed-information converse into conditions on the channel dynamics. These conditions lead to a new notion of dynamic surprise: the log ratio of physical to test output probabilities with a continuation correction for future signaling opportunities. The matching inequalities bound its conditional mean. For fixed architecture, test law, and potential, channel row synthesis under convex physical restrictions is convex. For every signaling constraint represented by a finite irreducible constrained graph of positive entropy, we construct a channel law under which undesired inputs remain available and behaviorally distinct while incurring a strict information penalty. A noisy refractory family has an exact capacity plateau, followed by an interval in which Shannon and zero-error feedback capacities differ. Explicit zero-error codes attain capacity in the graph construction and on the plateau. In this family, a Gibbs choice maximizes the penalty and makes dynamic surprise equal its conditional mean on every transition, yielding an exact trajectory-wise likelihood identity, a finite-block bound on successful decoding with premature requests, and an exponential strong converse. An exact gap decomposition into action residuals and output-law divergence constrains every reliable capacity-approaching code. Within the strict plateau, positive discrimination exponents for unused dynamics require a positive rate loss, while sparse probing permits consistent estimation at asymptotic capacity. A chemical channel illustrates how premature stimulation can alter future responsiveness while leaving the immediate output law unchanged.
We prove a sharp upper bound on the mutual information between two binary random variables in terms of their distribution-dependent KL contraction coefficient. This resolves the binary-pair conjecture of Anantharam, Gohari, Kamath, and Nair. Equality holds if and only if the variables are independent or form a doubly symmetric binary source. The proof uses supporting tangents of an entropy curve to vary the input distribution and the channel while preserving the contraction coefficient. Together with tensorization and data processing, the result also bounds the mutual information between binary outputs obtained separately from two correlated observation sequences. When the observation pairs are independent copies of a finite-alphabet pair, this bound depends only on the law of one pair and not on the number of observations.
In physical backpropagation, users return loss derivatives over the time-division duplex uplink, giving the base station the downlink gradient without channel reconstruction. Reciprocity calibration conventionally prioritizes base-station chains, as column-normalized zero-forcing reduces a per-user factor to a stream rotation. This priority can reverse. With ideal base-station chains and no noise, per-user amplitude errors make the returned field a weighted sum-rate gradient. With zero-forcing full service at both optima, the loss is independent of array size. Otherwise the selection penalty, serving the wrong users, carries 86 to 94 percent of the amplitude-induced loss in five of six configurations. Per-user phase errors mainly slow the iteration. Base-station chain errors scale the returned field per antenna, and at 3 dB and 25 degrees they cost one user 1.3 dB of signal-to-noise ratio (SNR) that no array size removes. With 80 users, such errors on both sides, and mismatched pilots, oracle per-user and base-station calibration leave 6.2 and 12.3 percent loss at 256 antennas on clustered channels. This ordering holds at 30 dB SNR and reverses for 1 dB, 10 degree user errors. A capped one-echo estimator comes within 2.4 percentage points of oracle per-user calibration but underperforms no calibration at 10 dB SNR.