Papers

For a prime \(p\) and a positive integer \(m\), let \(\mathbb{F}_{p^m}\) be the finite field of cardinality \(p^m\), and let $ R_{u^2,v^2,p^m} =\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}+v\mathbb{F}_{p^m} +uv\mathbb{F}_{p^m}, ~ u^2=v^2=0,\ uv=vu, $ be a finite non-chain ring. In this paper, we study skew polycyclic codes of length \(lj\) associated with \(f(x)^j\), where \(f(x)\) is a central polynomial of degree \(l\) in $R_{u^2, v^2, p^m}[x; \Theta],$ where $\Theta$ being an automorphism of \(R_{u^2,v^2,p^m}\). We describe these codes, characterize free skew polycyclic codes, and determine their ranks. Under suitable centrality assumptions, we decompose the quotient ring associated with \(x^{np^s}-\lambda\), where \(\gcd(n,p)=1\) and \(\Theta(\lambda)=\lambda\). This reduces the study of skew \((\lambda,\Theta)\)-constacyclic codes of length \(np^s\) to the study of left ideals of $\frac{R_{u^2,v^2,p^m}[x;\Theta]}{\langle f(x)^j\rangle}, $ where \(f(x)\) is a central irreducible divisor of degree \(l\) of \(x^{np^s}-\lambda\), for an invertible element \(\lambda\in R_{u^2,v^2,p^m}\) and \(j\in\mathbb{N}\). We then apply these results to skew \((\lambda,\Theta)\)-constacyclic codes of length \(p^s\) for different classes of units \(\lambda\). Several examples are presented to illustrate the theory and to obtain optimal codes. Finally, when \(\Theta\) is the identity automorphism, we study constacyclic codes of length \(np^s\) over \(R_{u^2,v^2,p^m}\), according as \(x^n-\alpha_0\) is irreducible or reducible over \(\mathbb{F}_{p^m}\). These results extend the work of \cite{CCDF18} and \cite{ZTG18} on constacyclic codes of length \(np^s\) over \(\mathbb{F}_{p^m}+u\mathbb{F}_{p^m}\) to the finite non-chain ring \(R_{u^2,v^2,p^m}\).

Robots are increasingly deployed in remote or hazardous areas for mission-critical control tasks. Due to their limited individual capabilities, they have to rely on other field sensors to obtain the state information of targets, and also a dedicated edge information hub (EIH) to enable information exchange, sensing data analysis and control command generation. Such configuration follows a sensing-communication-computing-control (SC3) closed loop. To optimize the whole closed-loop performance, this paper minimizes the linear quadratic regulator (LQR) control cost by designing the sensor-to-EIH bandwidth allocation. Specifically, we first model the distortion noise caused by limited communication data rate based on the mutual information theory. Next, under the control policy based on the Kalman filter and LQR controller, we formulate the control process as a partially observable Markov decision process (POMDP), and develop a deep reinforcement learning (DRL)-based sensor-to-EIH bandwidth allocation scheme. The proximal policy optimization (PPO) algorithm is utilized to train the DRL agent. Simulation results are provided to show the superiority of the proposed DRL-based scheme.

In this paper, we consider the uplink of a multiuser Zak-OTFS system comprising users with heterogeneous delay-Doppler (DD) periods/frame sizes. Multiple access is achieved through time-frequency (TF) shifts that place the users in non-overlapping regions of the TF plane. Closed-form expressions for the effective DD domain channel between each user and the base station are derived for sinc and Gaussian pulse shaping filters. The inter-user interference (IUI) is shown to be negligible under the TF-shift-based multiple access, thereby decoupling the multiuser input-output relation (IOR) estimation problem into independent single-user estimation problems. For IOR estimation, a superimposed spread-pilot framework is employed. The spread-pilot sequence is obtained by applying FFT to a reshaped Zadoff-Chu sequence. To mitigate the pilot-data interference introduced by the superimposed spread-pilot, a DD dictionary-based IOR estimation scheme that iterates between IOR estimation and data detection is employed. Simulation results for a multiuser Zak-OTFS system demonstrate that the resulting IOR estimates achieve normalized mean-square error (NMSE) and bit error rate (BER) performances that closely match those of the corresponding single-user system. Furthermore, for sinc pulse shaping, the superimposed spread-pilot frame achieves higher spectral-efficiency compared to embedded pilot frame across a wide range of inter-user power ratios. For Gaussian pulse shaping, however, the embedded pilot frame achieves a higher spectral efficiency due to the combined effects of residual IUI and significant pilot-data interference in the case of superimposed spread-pilot. The robustness of the estimation framework to variations in channel power-delay profile and maximum Doppler shift is also demonstrated.

Ferrers diagram rank-metric codes are rank-metric codes with prescribed support, and their dimension is bounded from above by the Etzion–Silberstein bound. In this paper, we study this problem for block Ferrers diagrams, namely Ferrers diagrams whose dots are grouped into square blocks of a fixed size. Motivated by the diagonal construction for MDS-constructible Ferrers diagrams, we introduce the notion of MSRD-constructibility, where MDS codes on diagonals are replaced by maximum sum-rank distance (MSRD) codes on block diagonals. We show that MSRD-constructible pairs yield optimal Ferrers diagram rank-metric codes over sufficiently large finite fields. We then relate MSRD-constructibility of a block Ferrers diagram to MDS-constructibility of its contraction, proving an equivalence when the distance is compatible with the block size and giving lifting criteria in the general case. As a consequence, we obtain MSRD-constructibility for strictly block-monotone and initially block-convex diagrams. Finally, we prove a reduction to block triangular diagrams and use it to obtain new arbitrary-field cases of the Etzion–Silberstein conjecture for MSRD-constructible block Ferrers diagrams.

Through-the-wall radar (TWR) human activity recognition (HAR) is important for non-line-of-sight indoor sensing, security monitoring, and emergency rescue. However, structured distribution shifts caused by person variation, observation-view variation, and wall-condition variation severely degrade recognition generalization, while the origin of the target-domain error still lacks a rigorous theoretical explanation. To address this issue, a generalization-analysis framework for TWR HAR is proposed in this paper. First, models for indoor human kinematics, TWR echo generation, radar image formation, feature representation, and bounded-weight neural networks are established within a unified source-to-target learning formulation. Then, the source risk, target risk, empirical risk, and admissible physical domain descriptor are defined, and a unified target-domain generalization bound is derived. Next, the structured shift term is decomposed into cross-person, cross-view, and cross-wall components, and the bound-tightening effects of physical low-dimensional representations, multi-source training, and parameter-space coverage are analyzed. Simulated and measured experiments jointly support the resulting theoretical analysis and illustrate its application value.

A central problem in quantum information theory is understanding how quantum resources can be used to communicate information more efficiently than classical resources. We introduce quantum dense network coding – a protocol that transmits the output of a non-Boolean function to a receiver using provably half as many qubits as bits for each sender by not transmitting the entirety of the function inputs. We show this advantage requires both shared entanglement and quantum communication, is robust to noise, and the gap in success probability between quantum and classical communication can be amplified exponentially in the number of senders. Finally, we show that dense network coding gives rise to a novel, information-theoretically secure, quantum cryptographic protocol, which we call measurement-device-independent quantum key growing.

Angular radio maps describe the received-power distribution over the angle of arrival and underpin beam selection and receiver localization in sixth-generation (6G) networks. Predicting the angular power spectrum (APS) from geometry is difficult, because the mapping is ill-posed in non-line-of-sight (NLOS) conditions and must generalize to unseen environments. Distortion-minimizing regressors return the conditional mean, which over-smooths the spectrum and erases the multipath structure that downstream tasks need. We cast the task as a perception-distortion problem and propose RadioDiff-v2, a dual-branch one-dimensional diffusion transformer trained with flow matching. It couples periodic angular encoding, adaptive layer-normalization conditioning, a Fourier angular mixer, and joint velocity and clean-signal heads. A per-metric estimator portfolio reads every deployment quantity from this single model, so that samples carry the distribution, the clean-signal head supplies a regression-grade point estimate, Bayes-optimal rules select beams, and the conditional likelihood localizes the receiver. We prove that a concentrated conditional yields a straight probability-flow trajectory that one step integrates exactly, identifying deterministic transport as the correct inductive bias. On a zero-shot test of 99 environments and one million links, RadioDiff-v2 leads every baseline on every metric, with a 0.39 dB Wasserstein-1 distance, per-bin error below the regression baseline, a 2.43 dB eight-beam NLOS sweep loss, and a 20.6-pixel localization error with four base stations. Code is available at https://github.com/UNIC-Lab/RadioDiff-v2.

This paper develops principled updating rules for possibilistic inference, where uncertainty about a fixed parameter is represented by a possibility function, the maxitive analogue of a probability distribution, and comparisons are made pointwise via a partial order. From two complementary foundations, an information-conservation viewpoint and an axiomatic viewpoint, we derive the same canonical update: the posterior is the prior-likelihood product followed by supremum normalisation. The two derivations agree for an arbitrary loss, differing only in where the learning-rate parameter enters. This parameter controls epistemic strength and is not identifiable from the normalising evidence alone, clarifying the role of analogous learning-rate parameters in generalised Bayesian updating.

We establish the exact exponent for smoothing the max-relative entropy on arbitrary von Neumann algebras. The proof first develops the required large-deviation and smoothing estimates in the semifinite setting and then passes to general von Neumann algebras through Haagerup-Junge-Xu reduction. We next study catalytic quantum information decoupling when the reference system is described by an arbitrary von Neumann algebra. A key ingredient is an operator layer-cake formula valid on arbitrary von Neumann algebras. This formula leads to a convex-split estimate for normal states with a general von Neumann algebraic reference system. Combining this estimate with the smoothing exponent result, we obtain lower and upper bounds on the catalytic-decoupling reliability function. These bounds coincide below the corresponding critical rate, yielding the exact decoupling reliability function in that regime.

A key question in operator learning is how to design surrogate operators with provable approximation guarantees in reasonable computational time. Whereas smooth operators can be approximated efficiently, i.e., with at least algebraic convergence in the amount of training data, learning finitely regular operators is known to be less efficient. The reason is an intrinsic curse of sample complexity, which allows only subalgebraic sample complexity rates. This fact makes it all the more important to develop algorithms which provably achieve these rates. In this work, we present a fully data-driven algorithm, termed Hermite-PCA approximation, for learning Gaussian Sobolev operators with near-optimal sample complexity. It employs principal component analysis and weighted least-squares methods and is therefore computationally efficient. Moreover, it is spectral, in the sense that it achieves faster (and near-optimal) convergence the higher the Sobolev regularity. We provide a full error analysis of this algorithm, taking into account all sources of error, along with numerical experiments that verify our theoretical results and empirically confirm the efficacy of Hermite-PCA approximation for learning Sobolev operators.

Real-image diffusion inversion is governed by a tight quality-cost trade-off, with costs incurred in computation, storage, or per-image optimization. We study this trade-off through the forward Gaussian noise anchor that defines a diffusion trajectory and isolate two mechanisms behind effective stored-noise inversion. First, diffusion noise exhibits an element-wise compression asymmetry: int8 full-dimensional anchors preserve reconstruction, whereas low-dimensional subspace summaries are much less reliable, often collapsing even at comparable or smaller payloads; the element-wise over subspace ordering persists across five stored-noise inversion methods. Second, inversion is trajectory-bound and score-prior coupled: the matched forward anchor and a trained score network are both necessary, arguing against a purely algebraic-identity explanation. Together, these findings specify what to store and how to use it. They lead to Noise-Anchored Reverse Correction (NARC), a training-free inversion primitive that stores a single int8 latent anchor and reuses it with a fixed, noise-level-dependent anchor-weight schedule: strong anchoring when the reverse trajectory is noise-dominated, then relaxed anchoring as image detail emerges. On PIE-Bench++ with Stable Diffusion 1.5, NARC outperforms five modern non-exact baselines and improves PSNR by +3.24 dB over PnP DirectInv while using about 400x less inversion storage than PnP DirectInv. The compression asymmetry, anchor specificity, and editing plug-in also transfer to SDXL 1024^2.

Decentralized federated learning (DFL) dispenses with the central server of classical FL by utilizing peer-to-peer model exchanges among edge devices. This server-free architecture enables ad-hoc, flexible distributed learning in large device-to-device (D2D) networks. However, wireless DFL converges slowly because peer-to-peer model aggregation incurs high delays and errors. Each DFL training round involves many-to-many gradient sharing over wireless channels, resulting in uncoordinated channel access, large communication errors from stragglers, and slow model consensus, especially in large-scale D2D networks with pronounced clustering structures. We address these aggregation bottlenecks by provisioning a few reliable backhaul links at straggling nodes to enhance network connectivity. Building on this idea, our budget-aware, cluster-centric DFL framework first partitions the network into densely connected clusters, and then allocates the limited backhaul budget to selected cluster heads. The resulting two-tier protocol executes fast, parallel model aggregation within clusters and infrequent inter-cluster exchanges among the heads, yielding an O(1/t) convergence rate in t iterations. Numerical experiments on image-classification tasks confirm that our approach accelerates convergence compared to state-of-the-art DFL baselines with only a few strategically placed backhaul links.

Redundancy in non-standard numeration systems is often associated with robustness, but its practical value in finite digital arithmetic depends on how representation, storage, and repair are defined. We study intrinsic redundancy in finite beta-expansion systems using a bounded-window model that separates semantic non-uniqueness from canonical codebook admissibility. The model distinguishes arithmetic canonicalization from corruption repair and evaluates structural detectability, value-preserving repair of the observed state, and survival of the original value. For the golden-ratio system and related multinacci bases, we prove that a genuine single-digit corruption in a canonically injective finite codebook cannot be semantically recovered by exact repair without external information. Semantic survival under exact structural repair is possible only for localized multi-digit perturbations corresponding to algebraic rewrite identities, such as the equivalence of 100 and 011. Experiments comparing standard binary, signed-digit non-adjacent form, and multinacci systems quantify trade-offs among codebook sparsity, fault visibility, canonicalization cost, residual error, and boundary loss. The results show that intrinsic beta-redundancy is a constrained-language resource for structural digital integrity rather than a substitute for classical error-control redundancy.

This paper investigates semantic-aware neural joint source-channel coding (JSCC) for robust video transmission over block erasure channels. We propose a neural video compression framework exploring both spatial-domain and feature-domain designs. In the spatial domain, video frames are partitioned into blocks, enabling localized erasure handling and fine-grained robustness control via uniform erasure and two-level, semantic-guided non-uniform erasure strategies. In the feature domain, latent features are partitioned, enabling missing features to be semantically recovered while maintaining overall spatial consistency. Comprehensive experiments quantify reconstruction quality under varying uniform and non-uniform erasure probabilities. Our results show that spatial-domain JSCC excels at handling random localized losses, whereas feature-domain JSCC provides superior robustness to distributed erasures and maintains fidelity under low-loss scenarios. The analysis highlights the trade-offs between spatial continuity and semantic redundancy, offering insights for designing robust, task-aware video communication systems.

We propose a novel approach to the minimax estimation of high-order functionals from the perspective of quantum computing. Specifically, for any real number $\alpha \gg 1$, we present two estimators, one for the classical functional $\mathrm{F}_\alpha(P) = \sum_{i=1}^S p_i^\alpha$ of a discrete distribution $P$ and the other for the quantum functional $\mathrm{F}_\alpha(\rho) = \operatorname{tr}(\rho^\alpha)$ of a mixed state $\rho$. These functionals have close connections with the Rényi entropy and the Tsallis entropy. We show that both estimators achieve the minimax optimal $L_2$ rate $\alpha \mathsf{n}^{-1}$ in the range $\alpha \lesssim \mathsf{n} \lesssim \alpha^{3-o(1)}$, where the support size $S$ of $P$ or the dimension of $\rho$ can be much larger than the number of samples $\mathsf{n}$. As a result, both estimators achieve the optimal sample complexity $\mathsf{n} \asymp \alpha$, improving upon the prior best upper bounds $O(\alpha^2)$ established by Jiao, Venkat, Han, and Weissman (IEEE Trans. Inf. Theory 2017) for classical functionals and Chen and Wang (COLT 2025) for quantum functionals. Our estimators are constructed under a unified framework using quantum primitives and run in linear time on a quantum computer. This work reveals an unexpected path from quantum computing to statistics, suggesting a conceptually new methodology for functional estimation. It adds to the growing list of quantum proofs for classical theorems.

We study Schubert subspace codes, which are constant-dimension subspace codes with prescribed intersection conditions with a fixed subspace. Our goal is to construct codes of maximum possible size in the extremal distance cases where a natural counting upper bound applies. We give two families of constructions. The first one uses a direct-sum decomposition of the ambient space, together with partial spreads and colorings of powers of $q$-Johnson graphs. For this construction, we also prove necessary conditions, which show how chromatic and clique obstructions arise. The second family is obtained by field reduction from evasive and scattered subspaces over extension fields. This gives codes whose size can be computed exactly in the scattered case and recovers the only previously known construction as a special case.

Nonverbal communication through head and neck movement is fundamental to human social signalling, yet how robotic neck morphology translates motion into communicative information remains poorly understood. We present an information-theoretic framework characterising robot neck movement as a communication channel, quantifying information transmitted and energy expended across varied configurations. Using a robotic neck platform, we recorded 84 video stimuli spanning three rotational degrees of freedom (DoF), varying amplitude, acceleration, and frequency, measuring Shannon entropy of pixel-change signals alongside energy consumption. A perceptual study validated communicative interpretations of each motion. While humans typically engage one axis per gesture, robots are unconstrained by biological architecture, motivating tests up to 3 DoF. Yet communicative information peaks at two DoF and decreases at three despite rising energy cost, a phenomenon we term the morphological information bottleneck. Motion parameter effects were parameter-dependent, some additive, others non-linear. We introduce the Motor Information Space, a framework mapping entropy against energy to expose communicative efficiency across morphologies, in which the optimal configuration achieves 5.26 bits at competitive energy cost. Perception data further confirm multi-axis movements reduce clarity. These findings challenge the assumption that anatomical completeness improves robotic expressiveness, establishing a quantitative basis for morphological design in robots, especially humanoids.

I formulate black-hole-horizon-induced decoherence of charged branch codes as the leading-soft QED restricted to an exterior algebra, formulated as an open quantum system. The fixed-history Feynman–Vernon identity ${\cal F}[J,J]=1$ remains exact. Decoherence enters through the unequal-history influence factor that survives exterior monitoring and belongs to the complementary horizon output. In the coherent eikonal regime, I derive the completely positive Schur channel $({\cal E}_H^{(0)}\rho)_{ab}=\langle\Phi_b^{H,(0)}|\Phi_a^{H,(0)}\rangle \, \rho_{ab}$. The leading soft input is the eikonal factor, projected onto the horizon radiative algebra. The channel yields Gram-positivity constraints, an exterior quantum-eraser bound, finite-time non-Markovianity tests, soft/hard scaling criteria, and a charged-qutrit interferometer measuring a leading-soft Bargmann holonomy. The holonomy phase is the rephasing-invariant symplectic area of a triangle in horizon soft phase space. I show that its orientation, common-mode, triangulation, and completely positive determinant identities render falsifiable tests beyond pairwise two-path visibility.

Since self-orthogonal codes, few-weight codes, linear complementary dual codes(LCD codes, for short) and quantum codes 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.[30] constructed several classes of few-weight self-orthogonal codes basing on defining sets, which are introduced by Ding et al.[10] in 2007. In this manuscript, for two classes of defining sets, we consider the corresponding augmented codes, construct a class of projective four-weight self-orthogonal codes and three classes of four-weight self-orthogonal codes. And for two classes of these four-weight self-orthogonal linear codes, we determine the parameters of their dual codes. As applications, we construct two classes of LCD codes and a class of quantum 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, and a class of quantum codes are AMDS according to the quantum Singleton bound.

The Stochastic-Oracle Turing Machine (SOTM) framework models AI-augmented computation as the interaction of a probabilistic Turing machine with an oracle whose responses are drawn from context-dependent distributions. This paper studies what an SOTM can achieve under two oracle-response schemes: in a cached-response oracle, each distinct query receives one response that is reused on later calls to the same query, while in a fresh-response oracle, each call returns an independent response. In both schemes, the SOTM first computes from its input and internal random source to generate its first query, then proceeds adaptively, computing from its query-response transcript (the record of queries issued and responses received) to generate each subsequent query or produce a final output. Cached responses impose two transcript-based ceilings on achievable performance: a correct-identification ceiling governed by the total variation distance between the transcript distributions induced by the hidden states of the oracle, and an output quality ceiling equal to the expected score of the best output the SOTM can compute from the transcript. Fresh responses can raise these ceilings by allowing repeated calls to accumulate independent evidence toward correct or high-quality outputs. In the binary single-informative-query case, the error probability decreases exponentially in the number of calls to the same query at the Chernoff rate. For output quality, query-count bounds characterize threshold stopping when the score function is incorporated as part of the SOTM, and majority-based amplification bounds characterize the binary candidate-output model when it is not. Together, the results identify how response reuse, transcript information, and access to the score function determine what an SOTM can compute and at what token cost.

Each WSI slide contains thousands of candidate tissue patches, while supervision is usually available only at slide level. Existing bag-construction strategies like Uniform extraction and handcrafted heuristics do not control redundancy while attention-based multiple-instance models couple patch importance to a particular downstream classifier, and coreset methods optimise embedding-space coverage without modelling task-relevant patch quality. We introduce InfoDPP-PAC, a principled patch-selection framework that combines teacher-seeded Gaussian process relevance modelling, determinantal log-determinant diversity,submodular greedy optimisation, and a concentration-based adaptive stopping rule. The main theoretical result shows that the log-determinant diversity term used in DPP-style selection is the Gaussian process mutual information between a selected subset and the latent relevance function. We further derive a PAC-style certificate for residual information gain, allowing the number of retained patches to vary by slide rather than being fixed a priori. The empirical study evaluates whether the selected subset is diverse, spatially and morphologically covering, non-redundant, and enriched for the teacher-derived relevance signal. It does not claim end-to-end diagnostic improvement after retraining a downstream MIL model. On 202 HISTAI gastrointestinal whole-slide images, the adaptive rule uses 83.7% fewer patches on average than a fixed full budget while retaining 97.9% of full-budget composite selection quality. At a matched budget, InfoDPP-PAC achieves the highest mean teacher-derived relevance score among fourteen baselines, with diversity and composite scores close to the strongest coreset methods. The results support InfoDPP-PAC as a controlled quality-diversity-cardinality selection framework, rather than as a downstream clinical predictor.

Continuous variable quantum key distribution protocols (CV-QKD) with discrete modulation have been intensively investigated to bridge the gap between ideal Gaussian modulation and modern coherent optical communication systems. To mitigate the penalty of discrete modulation, probabilistic constellation shaping (PCS) is applied to the modulation format and is typically performed by distribution matching (DM) algorithms. In this paper, we address the application of DM algorithms to perform PCS in CV-QKD protocols. We investigate the impact of approximating optimized Maxwell-Boltzman distributions with DM algorithms based on Huffman (HDM) and constant composition (CCDM) codes on the protocol's secret key rate (SKR) and tolerance to excess noise. Our results show that specifically symbol-by-symbol HDM degrades the SKR by at least 30%, whereas CCDM matches the optimal SKR with code length of $10^3$ or more symbols. Furthermore, we also provide a statistical analysis of symbol dependence for both approaches, showing that CCDM must operate with blocks of at least $10^5$ symbols for the correlations become negligible. Finally, we propose an algorithm to generate independent symbols following near-optimal distributions.

This paper investigates over-the-air federated learning (AirFL) in wireless systems where the access point is equipped with a multi-waveguide pinching antenna system (PASS). We adopt the widely studied learning-oriented AirFL formulation, which seeks to maximize the number of selected devices while keeping the aggregation distortion below a prescribed threshold. The resulting joint optimization of device selection, receive beamforming, and pinching-antenna placement is highly nonconvex due to the intricate coupling among these system variables. To address this challenge, we develop AirPASS, an alternating optimization framework with two main components: a homotopy-Riemannian margin-consolidation method for device selection and receive beamforming under a fixed PASS configuration, and a homotopy-assisted geometry optimization method for updating the pinching-antenna positions under fixed selected devices and beamformer.

This paper provides the first near-optimal lower bounds for one-bit compressed sensing of approximately sparse signals lying in a scaled $\ell_1$ ball, which is a commonly adopted relaxation of the exactly $k$-sparse assumption. In prior works, the best known upper bounds on uniform Euclidean error are of order $\widetilde{O}((k/m)^{1/3})$, where $m$ is the number of measurements. Under sub-Gaussian matrices, we establish nearly matching lower bounds for both the canonical one-bit compressed sensing model and the uniformly dithered model. Our argument is to first embed a small Euclidean ball into the signal set, which is straightforward for the dithered model but relies on a lifting map for the canonical model, and then construct two signals in this small ball that are separated in Euclidean distance by at least $(k/m)^{1/3}$ (up to logarithmic factor) but are indistinguishable from the binary measurements. Moreover, our argument extends to approximately sparse signals that live in a properly scaled $\ell_q$ ball $(q\in [0,1])$, yielding a lower bound $\widetilde{\Omega}((k/m)^{\frac{2-q}{2+q}})$ that smoothly bridges the cases of exact sparsity ($q=0$) and $\ell_1$ sparsity ($q=1$). Finally, we discuss the extensions of our lower bounds to sub-Weibull matrices, adversarial bit flipping, matrix recovery, and characterize the transition to the non-sparse case.

Quantum sensing is a promising technology capable of demonstrating clear advantage over comparable classical techniques for precise measurement. One application of quantum sensing is in function estimation, which can be done using a network of entangled quantum sensors, allowing for measurements with greater optimal sensitivity than unentangled sensing protocols. In cases where quantum sensor networks will be used to measure data that should remain private (e.g., biomedical data), it is imperative that these protocols include a privacy mechanism to hide sensitive information. In this work, we show that entangled sensor networks are vulnerable to certain privacy-violating attacks. To mitigate these attacks, we introduce secure sensing protocols endowed with differential privacy. We reconcile differential privacy with retaining Heisenberg-limited scaling, and introduce several protocols achieving varying balances between the two. We show that our main protocol, an $n$-node network sensing protocol that injects noise directly into the sensing Hamiltonian, exhibits a tradeoff between the desirable $O(1/n^2)$ Heisenberg scaling of the mean-squared error of the function estimate and the level of privacy attainable. Under assumptions on the network (a common source of randomness and a constant fraction of honest parties), we show that this protocol is locally implementable and achieves $(O(1), \delta)$-differential privacy for arbitrarily small $\delta$ while retaining Heisenberg scaling of the mean-squared error. We prove that our protocols are resilient to attacks by broad classes of classical and quantum adversaries, and find advantages in the privacy-utility tradeoff when using quantum techniques.

This paper studies the constrained-capacity for precoded faster-than-Nyquist (FTN) signaling with finite-alphabet inputs. Despite the promise of accelerated transmission, the fundamental rate limit of precoded FTN signaling under practical finite-alphabet constraints remains unclear. By introducing cyclic prefix (CP) and cyclic suffix (CS), the FTN channel is decomposed into a set of parallel eigenchannels by the discrete Fourier transform (DFT) matrix, based on which the constrained capacity is derived. The results demonstrate that time acceleration can improve spectral efficiency over Nyquist signaling even when a fixed modulation order is employed. Moreover, in the low and moderate signal-to-noise ratio (SNR) regimes, a smaller constellation combined with stronger time acceleration can outperform a larger constellation with weaker acceleration. Next, the asymptotic behavior of the constrained capacity is analyzed as the acceleration factor tends to zero under both fixed transmit-SNR and fixed receive-SNR definitions. It is shown that the constrained capacity for DFT-precoded FTN is fundamentally limited by the constellation size. In addition, the constrained capacity under channel mismatch is studied and a mismatched achievable information rate (AIR) formulation is developed to show the effects of practical constraints on the performance degradation. Finally, adaptive bit loading across eigenchannels is investigated to exploit the higher-quality eigenchannels.

Due to significant progress in physical layer (PHY) technologies, future 6G networks are expected to feature much denser antenna deployments. Cell-free MIMO network designs are one of the most promising candidates to enable denser networks. While significant effort has been put into its PHY research, the challenges it brings to networking disciplines remain relatively unexplored. In this work, we propose various fronthaul network designs for cell-free MIMO. Our results show that while tree topologies may suffice for small-scale deployments, they become infeasible as the number of antennas increases. In contrast, with growing network size, the proposed Clos topology performs almost as well as the optimal topology.

The Jensen-Shannon divergence (JSD) is a symmetric and bounded measure of the dissimilarity of two probability distributions, which has become a standard tool in statistics, information theory, and machine learning. We complement the understanding of its mathematical properties by presenting an analysis of the amount of data that is needed to distinguish between two distributions, given the value of JSD between them. We find the number of independent and identically distributed samples that suffice for a classifier to determine which of two distributions generated observed data at a desired error rate, for two complementary classifiers: we show that for the log-likelihood-ratio classifier, a sample size that grows as the inverse JSD is sufficient, whereas for a majority-vote classifier assembled from independent single-sample decisions, the sufficient size grows as the squared inverse JSD. These distinct scalings offer operational readings of JSD values and their translation into distinguishability in different contexts.

We present a succinct encoding of planar graphs that supports executing a breadth-first search directly on the encoding. The succinct encoding can be constructed in expected $O(n)$ time using $O(n)$ bits during construction; a compact variant can be constructed in deterministic $O(n)$ time using $O(n)$ bits. Once the encoding is constructed, a BFS from any start vertex can be computed in $O(n)$ time using $o(n)$ additional bits, including the space needed to represent the BFS tree. The resulting BFS tree $T$ remains available for standard tree operations, such as traversal, parent and child queries, layer queries, and lowest common ancestor queries, in constant time per query or output element. The encoding also supports standard graph queries. For plane graphs $G=(V, E)$, we provide traversal of the interdigitating tree $\hat T$, i.e., the spanning tree of the dual graph whose edges correspond to $E \setminus E(T)$. As our main application, we implement the well-known planar separator theorem in a space-efficient way. For biconnected plane graphs, our encoding allows us to compute a balanced separator of size $O(\sqrt n)$ in $O(n)$ time using $o(n)$ additional bits. Along the way, we show that biconnected plane graphs encoded by our representation can be triangulated in expected $O(n)$ time and $o(n)$ bits in the succinct variant, or in deterministic $O(n)$ time using $O(n)$ bits in the compact variant. Further applications include computation of a tree decomposition of width $O(d)$ where $d$ is the diameter of the plane graph at hand and testing for bipartiteness. Finally, all results that do not rely on a plane embedding generalize to separable graph classes.

Levenshtein's sequence reconstruction model plays an essential role in information retrieval of advanced memory systems, such as the DNA-based storage systems. In the model, a word $\mathbf{x}\in\mathbb{Z}_q^n$ is transmitted through $N$ noisy channels, and the goal is to recover it. Errors occurring in the channels usually involve substitutions, insertions and deletions. Our focus is on insertions. One of the main questions in this context is determining the minimum number of channels $N$ required to recover the transmitted word $\mathbf{x}$. The original formulation of the reconstruction problem requires that all the output words from the channels are distinct. However, different insertion errors may lead to the same output words. In this paper, we investigate two reconstruction models where the channels are allowed to produce identical output words even though different insertion errors occur in the channels. These two models, called the multiset model and non-multiset model, generalize the Levenshtein's model. We denote the minimum number of channels required to unambiguously recover the transmitted word $\mathbf{x}\in\mathbb{Z}_q^n$ by $N_q^m(n,t)+1$ in the multiset model and $N_q^{nm}(n,t)+1$ in the non-multiset model, where $t$ is the exact number of insertions occurring in a channel. We determine $N_q^m(n,1)$ and $N_q^{nm}(n,1)$ for all $n$ and $q$, and show the somewhat surprising fact that $N_q^m(n,1)=N_q^{nm}(n,1)$. We also provide a full characterization of the words attaining this value and give a general lower bound on $N_q^m(n,t)$ for $t\ge1$ and a recursive upper bound. For $t=1$, we construct codes $C'\subseteq\mathbb{Z}_q^{n+2}$ from codes $C\subseteq\mathbb{Z}_q^n$ such that the number of channels required to determine the transmitted word $\mathbf{x}\in C'$ is small. This construction is shown to be optimal for certain parameters.