More Like this

1. On finite-length analysis and channel dispersion for broadcast packet erasure channels with feedback

   https://doi.org/10.1109/ISIT45174.2021.9517889  

   Lin, Shih-Chun; Wang, Chih-Chun; Wang, I-Hsiang; Huang, Yu-Chih; Lai, Yi-Chun (July 2021, 2021 IEEE International Symposium on Information Theory (ISIT))

   Motivated by the applications for low-delay communication networks, the finite-length analysis, or channel dispersion identification, of the multi-user channel is very important. Recent studies also incorporate the effects of feedback in point-to-point and common-message broadcast channels (BCs). However, with private messages and feedback, finite-length results for BCs are much more scarce. Though it is known that feedback can strictly enlarge the capacity, the ultimate feedback capacity regions remain unknown for even some classical channels including Gaussian BCs. In this work, we study the two-user broadcast packet erasure channel (PEC) with causal feedback, which is one of the cleanest feedback capacity results and the capacity region can be achieved by elegant linear network coding (LNC). We first derive a new finite-length outer bound for any LNCs and then accompanying inner bound by analyzing a three-phase LNC. For the outer-bound, we adopt a linear-space-based framework, which can successfully find the LNC capacity. However, naively applying this method in finite-length regime will result in a loose outer bound. Thus a new bounding technique based on carefully labelling each time slot according to the type of LNC transmitted is proposed. Simulation results show that the sum-rate gap between our inner and outer bounds is within 0.02 bits/channel use. Asymptotic analysis also shows that our bounds bracket the channel dispersion of LNC feedback capacity for broadcast PEC to within a factor of Q-l (E/2)/Q-l (E). 

   more » « less
2. Outer bounds for Gaussian multiple access channels with state known at one encoder

   https://doi.org/10.1109/ISIT.2017.8006652  

   Yang, Wei; Liang, Yingbin; Shitz, Shlomo Shamai; Poor, H. Vincent (June 2017, 2017 IEEE International Symposium on Information Theory (ISIT))

   This paper studies a two-user state-dependent Gaus- sian multiple-access channel with state noncausally known at one encoder. Two new outer bounds on the capacity region are derived, which improve uniformly over the best known (genie- aided) outer bound. The two corner points of the capacity region as well as the sum rate capacity are established, and it is shown that a single-letter solution is adequate to achieve both the corner points and the sum rate capacity. Furthermore, the full capacity region is characterized in situations in which the sum rate capacity is equal to the capacity of the helper problem. The proof exploits the optimal-transportation idea of Polyanskiy and Wu (which was used previously to establish an outer bound on the capacity region of the interference channel) and the worst- case Gaussian noise result for the case in which the input and the noise are dependent. 

   more » « less
3. A Shannon-Theoretic Approach to the Storage–Retrieval Trade-Off in PIR Systems

   https://doi.org/10.3390/info14010044  

   Tian, Chao; Sun, Hua; Chen, Jun (January 2023, Information)

   We consider the storage–retrieval rate trade-off in private information retrieval (PIR) systems using a Shannon-theoretic approach. Our focus is mostly on the canonical two-message two-database case, for which a coding scheme based on random codebook generation and the binning technique is proposed. This coding scheme reveals a hidden connection between PIR and the classic multiple description source coding problem. We first show that when the retrieval rate is kept optimal, the proposed non-linear scheme can achieve better performance over any linear scheme. Moreover, a non-trivial storage-retrieval rate trade-off can be achieved beyond space-sharing between this extreme point and the other optimal extreme point, achieved by the retrieve-everything strategy. We further show that with a method akin to the expurgation technique, one can extract a zero-error PIR code from the random code. Outer bounds are also studied and compared to establish the superiority of the non-linear codes over linear codes. 

   more » « less
4. The Asymptotic Spectrum of Graphs and the Shannon Capacity

   https://doi.org/10.1007/s00493-019-3992-5  

   Zuiddam, Jeroen (November 2018, Combinatorica)

   We introduce the asymptotic spectrum of graphs and apply the theory of asymptoticspectra of Strassen (J. Reine Angew. Math. 1988) to obtain a new dual characterisation ofthe Shannon capacity of graphs. Elements in the asymptotic spectrum of graphs includethe Lov ́asz theta number, the fractional clique cover number, the complement of thefractional orthogonal rank and the fractional Haemers bound. 

   more » « less
5. Exponentially Simpler Network Rate Regions

   https://doi.org/10.1109/ISIT45174.2021.9517734  

   Liu, Yirui; Walsh, John MacLaren (July 2021, 2021 IEEE International Symposium on Information Theory (ISIT))

   Determining the rate region of a network is of great importance in the research area of network coding. Lots of attempts have been made and significant progress has been achieved over the last decade on this topic. Although these researches provide us with multiple ways of calculating the outer or inner bounds of rate region, the sheer complexity of the problem, which involves expressing and projecting a very high dimensional polyhedra, makes it computationally infeasible beyond networks with 10s of edges. Aimed at reducing the complexity of the rate region calculation, in this paper a new theorem that implicitly determines the rate region of a network is proved and a corresponding systematic way of applying the theorem to calculate explicitly the outer bounds to a rate region is proposed. Compared with the traditional method, the proposed method has the potential to calculate the true rate region via the projection of simpler polyhedra that has exponentially less dimensions and is characterized by exponentially less facets. 

   more » « less