FR1.R4.4

Improved bounds on the interactive capacity via error pattern analysis

Mudit Aggarwal, University of British Columbia, Vancouver, Canada; Manuj Mukherjee, Indraprastha Institute of Information Technology Delhi, India

Session:
Capacity and Guessing

Track:
9: Shannon Theory

Location:
Omikron II

Presentation Time:
Fri, 12 Jul, 10:45 - 11:05

Session Chair:
Charalambos Charalambous, University of Cyprus
Abstract
[THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD] Any interactive protocol between a pair of parties can be reliably simulated in the presence of noise with a multiplicative overhead on the number of rounds (Schulman 1996). The reciprocal of the best (least) overhead is called the interactive capacity of the noisy channel. In this work, we present lower bounds on the interactive capacity of the binary erasure channel. Our lower bound improves the best-known bound due to Ben-Yishai et al. 2021 by roughly a factor of 1.75. The improvement is due to a tighter analysis of the correctness of the simulation protocol using error pattern analysis. More precisely, instead of using the well-known technique of bounding the least number of erasures needed to make the simulation fail, we identify and bound the probability of specific erasure patterns causing simulation failure. We remark that error pattern analysis can be useful in solving other problems involving stochastic noise, such as bounding the interactive capacity of different channels.
Resources