Information Theory
See recent articles
Showing new listings for Wednesday, 23 October 2024
- [1] arXiv:2410.16297 [pdf, html, other]
-
Title: Illuminating Networks: Enhancing Visible Light Communication with Physical-Layer Network Coding (PNC-VLC Scheme)Subjects: Information Theory (cs.IT)
Wireless communications using light waves are called visible light communication. A technique called Physical-layer Network coding allows several users to communicate simultaneously over the same channel in a distributed space-time Coding scheme. Herein, we report a new PNC-VLC one-to-many scheme using physical-layer network coding in VLC system for enhancing throughput by boosting data transmission at relay nodes. We develop an integrated PNC-VLC framework including physical-layer signal processing algorithms and medium access control approaches. Our proposed technique is then modelled mathematically and compared with some of the VLC and PNC-VLC schemes under various channel conditions and scenarios. Our investigation revealed that our proposed technique performed better than traditional PNC schemes in achieving better Bit Error Rate performance in different channel
- [2] arXiv:2410.16459 [pdf, html, other]
-
Title: R\'enyi divergence-based uniformity guarantees for $k$-universal hash functionsComments: 24 pagesSubjects: Information Theory (cs.IT); Cryptography and Security (cs.CR)
Universal hash functions map the output of a source to random strings over a finite alphabet, aiming to approximate the uniform distribution on the set of strings. A classic result on these functions, called the Leftover Hash Lemma, gives an estimate of the distance from uniformity based on the assumptions about the min-entropy of the source. We prove several results concerning extensions of this lemma to a class of functions that are $k^\ast$-universal, i.e., $l$-universal for all $2\le l\le k$. As a common distinctive feature, our results provide estimates of closeness to uniformity in terms of the $\alpha$-Rényi divergence for all $\alpha\in (1,\infty]$. For $1\le \alpha\le k$ we show that it is possible to convert all the randomness of the source measured in $\alpha$-Rényi entropy into approximately uniform bits with nearly the same amount of randomness. For large enough $k$ we show that it is possible to distill random bits that are nearly uniform, as measured by min-entropy. We also extend these results to hashing with side information.
- [3] arXiv:2410.16504 [pdf, html, other]
-
Title: Higher-Order Staircase Codes: A Unified Generalization of High-Throughput Coding TechniquesComments: Submitted to 2025 Optical Fiber Communication Conference (OFC 2025)Subjects: Information Theory (cs.IT)
We introduce a unified generalization of several well-established high-throughput coding techniques including OFEC, staircase codes, and continuously interleaved codes. This gives rise to a vast family of new competitive codes.
- [4] arXiv:2410.16535 [pdf, html, other]
-
Title: Performance-Complexity-Latency Trade-offs of Concatenated RS-SDBCH CodesComments: Submitted to Optical Fiber Communication Conference (OFC) 2025Subjects: Information Theory (cs.IT)
Performance-complexity-latency trade-off curves for rate-0.88 concatenated outer Reed--Solomon codes and inner Chase-algorithm-based soft-decision Bose--Ray-Chaudhuri--Hocquenghem codes with PAM4 constellation using bit-interleaved coded modulation and multilevel coding coded modulation schemes over the AWGN channel are presented.
- [5] arXiv:2410.16731 [pdf, html, other]
-
Title: RIS-Assisted THz MIMO Wireless System in the Presence of Direct Link for CV-QKD with Limited Quantum MemoryComments: 13 pages, 6 figuresSubjects: Information Theory (cs.IT)
A reconfigurable intelligent surface (RIS)-aided multiple-input multiple-output (MIMO) wireless communication system is considered in this paper wherein the transmitter, Alice modulates secret keys, by using a continuous variable quantum key distribution technique to be transmitted to the receiver, Bob, which employs homodyne detection for data decoding. The data is transmitted over two paths, namely a direct path between Alice and Bob and the wireless path between them via the RIS. Transmit and receive beamsplitters are employed in the system to transform the MIMO terahertz channels into parallel single-input single-output channels. Considering an eavesdropper, Eve, to attack all the three wireless channels in the system (i.e., the direct channel, the channel between Alice and RIS, and between the RIS and Bob) but having restricted quantum memory limiting it to store the ancilla modes from either of these three wireless channels, novel expressions for the secret key rate (SKR) of the system are derived. Numerical results are presented to demonstrate the dependency of the system's performance on various system parameters. It is observed that the RIS plays a key role in increasing the SKR of the system and the transmission distance, ensuring secure communications between Alice and Bob. The significance of employing RIS is observed specifically for the case when Eve measures the ancilla modes of the channel between the RIS and Bob. Furthermore, for all such measurement scenarios, optimal angles are obtained for the phase shifts of the RIS elements to maximize the SKR for various MIMO configurations and transmission distance between Alice and Bob.
- [6] arXiv:2410.16875 [pdf, html, other]
-
Title: Edge-Spreading Raptor-Like LDPC Codes for 6G Wireless SystemsYuqing Ren, Leyu Zhang, Yifei Shen, Wenqing Song, Emmanuel Boutillon, Alexios Balatsoukas-Stimming, Andreas BurgComments: 13 pages, 14 figuresSubjects: Information Theory (cs.IT)
Next-generation channel coding has stringent demands on throughput, energy consumption, and error rate performance while maintaining key features of 5G New Radio (NR) standard codes such as rate compatibility, which is a significant challenge. Due to excellent capacity-achieving performance, spatially-coupled low-density parity-check (SC-LDPC) codes are considered a promising candidate for next-generation channel coding. In this paper, we propose an SC-LDPC code family called edge-spreading Raptor-like (ESRL) codes for 6G. Unlike other SC-LDPC codes that adopt the structure of existing rate-compatible LDPC block codes before coupling, ESRL codes maximize the possible locations of edge placement and focus on constructing an optimal coupled matrix. Moreover, a new graph representation called the unified graph is introduced. This graph offers a global perspective on ESRL codes and identifies the optimal edge reallocation to optimize the spreading strategy. We conduct comprehensive comparisons of ESRL codes and 5G-NR LDPC codes. Simulation results demonstrate that when all decoding parameters and complexity are the same, ESRL codes have obvious advantages in error rate performance and throughput compared to 5G-NR LDPC codes, making them a promising solution towards next-generation channel coding.
- [7] arXiv:2410.17068 [pdf, html, other]
-
Title: Delay-Constrained Grant-Free Random Access in MIMO Systems: Distributed Pilot Allocation and Power ControlComments: 15 pages, 7 figures. Accepted for publication in IEEE Transactions on Cognitive Communications and NetworkingSubjects: Information Theory (cs.IT); Multiagent Systems (cs.MA)
We study a delay-constrained grant-free random access system with a multi-antenna base station. The users randomly generate data packets with expiration deadlines, which are then transmitted from data queues on a first-in first-out basis. To deliver a packet, a user needs to succeed in both random access phase (sending a pilot without collision) and data transmission phase (achieving a required data rate with imperfect channel information) before the packet expires. We develop a distributed, cross-layer policy that allows the users to dynamically and independently choose their pilots and transmit powers to achieve a high effective sum throughput with fairness consideration. Our policy design involves three key components: 1) a proxy of the instantaneous data rate that depends only on macroscopic environment variables and transmission decisions, considering pilot collisions and imperfect channel estimation; 2) a quantitative, instantaneous measure of fairness within each communication round; and 3) a deep learning-based, multi-agent control framework with centralized training and distributed execution. The proposed framework benefits from an accurate, differentiable objective function for training, thereby achieving a higher sample efficiency compared with a conventional application of model-free, multi-agent reinforcement learning algorithms. The performance of the proposed approach is verified by simulations under highly dynamic and heterogeneous scenarios.
- [8] arXiv:2410.17113 [pdf, html, other]
-
Title: A Unified Activity Detection Framework for Massive Access: Beyond the Block-Fading ParadigmComments: 15 pages, 14 figures. Accepted for publication in IEEE Journal of Selected Topics in Signal ProcessingSubjects: Information Theory (cs.IT); Signal Processing (eess.SP)
The wireless channel changes continuously with time and frequency and the block-fading assumption, which is popular in many theoretical analyses, never holds true in practical scenarios. This discrepancy is critical for user activity detection in grant-free random access, where joint processing across multiple coherence blocks is undesirable, especially when the environment becomes more dynamic. In this paper, we develop a framework for low-dimensional approximation of the channel to capture its variations over time and frequency, and use this framework to implement robust activity detection algorithms. Furthermore, we investigate how to efficiently estimate the principal subspace that defines the low-dimensional approximation. We also examine pilot hopping as a way of exploiting time and frequency diversity in scenarios with limited channel coherence, and extend our algorithms to this case. Through numerical examples, we demonstrate a substantial performance improvement achieved by our proposed framework.
- [9] arXiv:2410.17198 [pdf, html, other]
-
Title: One-shot Multiple Access Channel SimulationComments: Total 42 pages, main text 23 pages, References and Appendices 19 pages, 2 FiguresSubjects: Information Theory (cs.IT); Quantum Physics (quant-ph)
We consider the problem of shared randomness-assisted multiple access channel (MAC) simulation for product inputs and characterize the one-shot communication cost region via almost-matching inner and outer bounds in terms of the smooth max-information of the channel, featuring auxiliary random variables of bounded size. The achievability relies on a rejection-sampling algorithm to simulate an auxiliary channel between each sender and the decoder, and producing the final output based on the output of these intermediate channels. The converse follows via information-spectrum based arguments. To bound the cardinality of the auxiliary random variables, we employ the perturbation method from [Anantharam et al., IEEE Trans. Inf. Theory (2019)] in the one-shot setting. For the asymptotic setting and vanishing errors, our result expands to a tight single-letter rate characterization and consequently extends a special case of the simulation results of [Kurri et al., IEEE Trans. Inf. Theory (2022)] for fixed, independent and identically distributed (iid) product inputs to universal simulation for any product inputs. We broaden our discussion into the quantum realm by studying feedback simulation of quantum-to-classical (QC) MACs with product measurements [Atif et al., IEEE Trans. Inf. Theory (2022)]. For fixed product inputs and with shared randomness assistance, we give a quasi tight one-shot communication cost region with corresponding single-letter asymptotic iid expansion.
New submissions (showing 9 of 9 entries)
- [10] arXiv:2410.16362 (cross-list from quant-ph) [pdf, html, other]
-
Title: Semidefinite optimization of the quantum relative entropy of channelsComments: 13 pagesSubjects: Quantum Physics (quant-ph); Information Theory (cs.IT)
This paper introduces a method for calculating the quantum relative entropy of channels, an essential quantity in quantum channel discrimination and resource theories of quantum channels. By building on recent developments in the optimization of relative entropy for quantum states [Kossmann and Schwonnek, arXiv:2404.17016], we introduce a discretized linearization of the integral representation for the relative entropy for states, enabling us to handle maximization tasks of the relative entropy of a channel over input states. Our approach here extends previous work on minimizing relative entropy to the more complicated domain of maximization. It also provides efficiently computable upper and lower bounds that sandwich the true value with any desired precision, leading to a practical method for computing the relative entropy of channels.
- [11] arXiv:2410.16377 (cross-list from stat.ML) [pdf, html, other]
-
Title: A Simple Model of Inference Scaling LawsComments: 11 pages, 7 figuresSubjects: Machine Learning (stat.ML); Artificial Intelligence (cs.AI); Information Theory (cs.IT); Machine Learning (cs.LG)
Neural scaling laws have garnered significant interest due to their ability to predict model performance as a function of increasing parameters, data, and compute. In this work, we propose a simple statistical ansatz based on memorization to study scaling laws in the context of inference, specifically how performance improves with multiple inference attempts. We explore the coverage, or pass@k metric, which measures the chance of success over repeated attempts and provide a motivation for the observed functional form of the inference scaling behavior of the coverage in large language models (LLMs) on reasoning tasks. We then define an "inference loss", which exhibits a power law decay as the number of trials increases, and connect this result with prompting costs. We further test our construction by conducting experiments on a simple generative model, and find that our predictions are in agreement with the empirical coverage curves in a controlled setting. Our simple framework sets the ground for incorporating inference scaling with other known scaling laws.
- [12] arXiv:2410.16660 (cross-list from math.MG) [pdf, html, other]
-
Title: Difficulties Constructing Lattices with Exponential Kissing Number from CodesSubjects: Metric Geometry (math.MG); Information Theory (cs.IT); Number Theory (math.NT)
In this note, we present examples showing that several natural ways of constructing lattices from error-correcting codes do not in general yield a correspondence between minimum-weight non-zero codewords and shortest non-zero lattice vectors. From these examples, we conclude that the main results in two works of Vlăduţ (Moscow J. Comb. Number Th., 2019 and Discrete Comput. Geom., 2021) on constructing lattices with exponential kissing number from error-correcting codes are invalid. Exhibiting a family of lattices with exponential kissing number therefore remains an open problem.
- [13] arXiv:2410.16692 (cross-list from stat.ML) [pdf, html, other]
-
Title: Lower Bounds for Time-Varying Kernelized BanditsSubjects: Machine Learning (stat.ML); Information Theory (cs.IT); Machine Learning (cs.LG)
The optimization of black-box functions with noisy observations is a fundamental problem with widespread applications, and has been widely studied under the assumption that the function lies in a reproducing kernel Hilbert space (RKHS). This problem has been studied extensively in the stationary setting, and near-optimal regret bounds are known via developments in both upper and lower bounds. In this paper, we consider non-stationary scenarios, which are crucial for certain applications but are currently less well-understood. Specifically, we provide the first algorithm-independent lower bounds, where the time variations are subject satisfying a total variation budget according to some function norm. Under $\ell_{\infty}$-norm variations, our bounds are found to be close to the state-of-the-art upper bound (Hong \emph{et al.}, 2023). Under RKHS norm variations, the upper and lower bounds are still reasonably close but with more of a gap, raising the interesting open question of whether non-minor improvements in the upper bound are possible.
- [14] arXiv:2410.16704 (cross-list from quant-ph) [pdf, html, other]
-
Title: Resolvability of classical-quantum channelsComments: 20 pages, 3 figures. Comments are welcome!Subjects: Quantum Physics (quant-ph); Emerging Technologies (cs.ET); Information Theory (cs.IT)
Channel resolvability concerns the minimum resolution for approximating the channel output. We study the resolvability of classical-quantum channels in two settings, for the channel output generated from the worst input, and form the fixed independent and identically distributed (i.i.d.) input. The direct part of the worst-input setting is derived from sequential hypothesis testing as it involves of non-i.i.d.~inputs. The strong converse of the worst-input setting is obtained via the connection to identification codes. For the fixed-input setting, while the direct part follows from the known quantum soft covering result, we exploit the recent alternative quantum Sanov theorem to solve the strong converse.
- [15] arXiv:2410.16813 (cross-list from cs.LG) [pdf, html, other]
-
Title: Klein Model for Hyperbolic Neural NetworksComments: Accepted to NeurIPS 2024 Symmetry and Geometry in Neural Representations WorkshopSubjects: Machine Learning (cs.LG); Information Theory (cs.IT); Machine Learning (stat.ML)
Hyperbolic neural networks (HNNs) have been proved effective in modeling complex data structures. However, previous works mainly focused on the Poincaré ball model and the hyperboloid model as coordinate representations of the hyperbolic space, often neglecting the Klein model. Despite this, the Klein model offers its distinct advantages thanks to its straight-line geodesics, which facilitates the well-known Einstein midpoint construction, previously leveraged to accompany HNNs in other models. In this work, we introduce a framework for hyperbolic neural networks based on the Klein model. We provide detailed formulation for representing useful operations using the Klein model. We further study the Klein linear layer and prove that the "tangent space construction" of the scalar multiplication and parallel transport are exactly the Einstein scalar multiplication and the Einstein addition, analogous to the Möbius operations used in the Poincaré ball model. We show numerically that the Klein HNN performs on par with the Poincaré ball model, providing a third option for HNN that works as a building block for more complicated architectures.
- [16] arXiv:2410.17000 (cross-list from cs.CR) [pdf, html, other]
-
Title: Beyond Yao's Millionaires: Secure Multi-Party Computation of Non-Polynomial FunctionsComments: 11 pages, 4 figuresSubjects: Cryptography and Security (cs.CR); Information Theory (cs.IT)
In this paper, we present an unconditionally secure $N$-party comparison scheme based on Shamir secret sharing, utilizing the binary representation of private inputs to determine the $\max$ without disclosing any private inputs or intermediate results. Specifically, each party holds a private number and aims to ascertain the greatest number among the $N$ available private numbers without revealing its input, assuming that there are at most $T < \frac{N}{2}$ honest-but-curious parties. The proposed scheme demonstrates a lower computational complexity compared to existing schemes that can only compare two secret numbers at a time. To the best of our knowledge, our scheme is the only information-theoretically secure method for comparing $N$ private numbers without revealing either the private inputs or any intermediate results. We demonstrate that by modifying the proposed scheme, we can compute other well-known non-polynomial functions of the inputs, including the minimum, median, and rank. Additionally, in the proposed scheme, before the final reveal phase, each party possesses a share of the result, enabling the nodes to compute any polynomial function of the comparison result. We also explore various applications of the proposed comparison scheme, including federated learning.
Cross submissions (showing 7 of 7 entries)
- [17] arXiv:2406.06312 (replaced) [pdf, html, other]
-
Title: Memory Complexity of Estimating Entropy and Mutual InformationSubjects: Information Theory (cs.IT)
We observe an infinite sequence of independent identically distributed random variables $X_1,X_2,\ldots$ drawn from an unknown distribution $p$ over $[n]$, and our goal is to estimate the entropy $H(p)=-\mathbb{E}[\log p(X)]$ within an $\varepsilon$-additive error. To that end, at each time point we are allowed to update a finite-state machine with $S$ states, using a possibly randomized but time-invariant rule, where each state of the machine is assigned an entropy estimate. Our goal is to characterize the minimax memory complexity $S^*$ of this problem, which is the minimal number of states for which the estimation task is feasible with probability at least $1-\delta$ asymptotically, uniformly in $p$. Specifically, we show that there exist universal constants $C_1$ and $C_2$ such that $ S^* \leq C_1\cdot\frac{n (\log n)^4}{\varepsilon^2\delta}$ for $\varepsilon$ not too small, and $S^* \geq C_2 \cdot \max \{n, \frac{\log n}{\varepsilon}\}$ for $\varepsilon$ not too large. The upper bound is proved using approximate counting to estimate the logarithm of $p$, and a finite memory bias estimation machine to estimate the expectation operation. The lower bound is proved via a reduction of entropy estimation to uniformity testing. We also apply these results to derive bounds on the memory complexity of mutual information estimation.
- [18] arXiv:2406.08916 (replaced) [pdf, html, other]
-
Title: Griesmer type bounds for additive codes over finite fields, integral and fractional MDS codesSubjects: Information Theory (cs.IT); Combinatorics (math.CO)
In this article we prove Griesmer type bounds for additive codes over finite fields. These new bounds give upper bounds on the length of maximum distance separable (MDS) codes, codes which attain the Singleton bound. We will also consider codes to be MDS if they attain the fractional Singleton bound, due to Huffman. We prove that this bound in the fractional case can be obtained by codes whose length surpasses the length of the longest known codes in the integral case. For small parameters, we provide exhaustive computational results for additive MDS codes, by classifying the corresponding (fractional) subspace-arcs. This includes a complete classification of fractional additive MDS codes of size 243 over the field of order 9.
- [19] arXiv:2408.15925 (replaced) [pdf, html, other]
-
Title: Explicit Folded Reed-Solomon and Multiplicity Codes Achieve Relaxed Generalized Singleton BoundsSubjects: Information Theory (cs.IT); Combinatorics (math.CO)
In this paper, we prove that explicit FRS codes and multiplicity codes achieve relaxed generalized Singleton bounds for list size $L\ge1.$ Specifically, we show the following: (1) FRS code of length $n$ and rate $R$ over the alphabet $\mathbb{F}_q^s$ with distinct evaluation points is $\left(\frac{L}{L+1}\left(1-\frac{sR}{s-L+1}\right),L\right)$ list-decodable (LD) for list size $L\in[s]$. (2) Multiplicity code of length $n$ and rate $R$ over the alphabet $\mathbb{F}_p^s$ with distinct evaluation points is $\left(\frac{L}{L+1}\left(1-\frac{sR}{s-L+1}\right),L\right)$ LD for list size $L\in[s]$.
Choosing $s=\Theta(1/\epsilon^2)$ and $L=O(1/\epsilon)$, our results imply that both FRS codes and multiplicity codes achieve LD capacity $1-R-\epsilon$ with optimal list size $O(1/\epsilon)$. This exponentially improves the previous state of the art $(1/\epsilon)^{O(1/\epsilon)}$ established by Kopparty et. al. (FOCS 2018) and Tamo (IEEE TIT, 2024). In particular, our results on FRS codes fully resolve a open problem proposed by Guruswami and Rudra (STOC 2006). Furthermore, our results imply the first explicit constructions of $(1-R-\epsilon,O(1/\epsilon))$ LD codes of rate $R$ with poly-sized alphabets.
Our method can also be extended to analyze the list-recoverability (LR) of FRS codes. We provide a tighter radius upper bound that FRS codes cannot be $(\frac{L+1-\ell}{L+1}(1-\frac{mR}{m-1})+o(1),\ell, L)$ LR where $m=\lceil\log_{\ell}{(L+1)}\rceil$. We conjecture this bound is almost tight when $L+1=\ell^a$ for any $a\in\mathbb{N}^{\ge 2}$. To give some evidences, we show FRS codes are $\left(\frac{1}{2}-\frac{sR}{s-2},2,3\right)$ LR, which proves the tightness in the smallest non-trivial case. Our bound refutes the possibility that FRS codes could achieve LR capacity $(1-R-\epsilon, \ell, O(\frac{\ell}{\epsilon}))$. This implies an intrinsic separation between LD and LR of FRS codes. - [20] arXiv:2410.15839 (replaced) [pdf, html, other]
-
Title: Covering Codes as Near-Optimal Quantizers for Distributed Testing Against IndependenceComments: 10 pages, 3 figures, 1 pseudo code, 1 table, ITW 2024, accepted to be presentedSubjects: Information Theory (cs.IT)
We explore the problem of distributed Hypothesis Testing (DHT) against independence, focusing specifically on Binary Symmetric Sources (BSS). Our investigation aims to characterize the optimal quantizer among binary linear codes, with the objective of identifying optimal error probabilities under the Neyman-Pearson (NP) criterion for short code-length regime. We define optimality as the direct minimization of analytical expressions of error probabilities using an alternating optimization (AO) algorithm. Additionally, we provide lower and upper bounds on error probabilities, leading to the derivation of error exponents applicable to large code-length regime. Numerical results are presented to demonstrate that, with the proposed algorithm, binary linear codes with an optimal covering radius perform near-optimally for the independence test in DHT.