English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Insdel errors occur in communication systems caused by the loss of positionalinformation of the message. Since the work by Guruswami and Wang, there havebeen some further investigations on the list decoding of insertion codes,deletion codes and insdel codes. However, unlike classical Hamming metric oreven rank-metric, there are still many unsolved problems on list decoding ofinsdel codes.  The contributions of this paper mainly consist of two parts. Firstly, weanalyze the list decodability of random insdel codes. We show that listdecoding of random insdel codes surpasses the Singleton bound when there aremore insertion errors than deletion errors and the alphabet size issufficiently large. Furthermore, our results reveal the existence of an insdelcode that can be list decoded against insdel errors beyond its minimum insdeldistance while still having polynomial list size. This provides a more completepicture on the list decodability of insdel codes when both insertion anddeletion errors happen. Secondly, we construct a family of explicit insdelcodes with efficient list decoding algorithm. As a result, we derive aZyablov-type bound for insdel errors. Recently, after our results appeared,Guruswami et al. provided a complete solution for another open problem on listdecoding of insdel codes. In contrast to the problems we considered, theyprovided a region containing all possible insertion and deletion errors thatare still list decodable by some q-ary insdel codes of non-zero rate. Morespecifically, for a fixed number of insertion and deletion errors, while ourpaper focuses on maximizing the rate of a code that is list decodable againstthat amount of insertion and deletion errors, Guruswami et al. focuses onfinding out the existence of a code with asymptotically non-zero rate which islist decodable against this amount of insertion and deletion errors.

On List Decoding of Insertion and Deletion Errors