Source author record

Roni Con

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Information Theory math.IT

Catalog footprint

Research overview

3works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions

In this work, we study linear error-correcting codes against adversarial insertion-deletion (insdel) errors, a topic that has recently gained a lot of attention. We construct linear codes over $\mathbb{F}_q$ , for $q=\text{poly}(1/\varepsilon)$ , that can efficiently decode from a $δ$ fraction of insdel errors and have rate $(1-4δ)/8-\varepsilon$ . We also show that by allowing codes over $\mathbb{F}_{q^2}$ that are linear over $\mathbb{F}_q$ , we can improve the rate to $(1-δ)/4-\varepsilon$ while not sacrificing efficiency. Using this latter result, we construct fully linear codes over $\mathbb{F}_2$ that can efficiently correct up to $δ< 1/54$ fraction of deletions and have rate $R = (1-54\cdot δ)/1216$ . Cheng, Guruswami, Haeupler, and Li [CGHL21] constructed codes with (extremely small) rates bounded away from zero that can correct up to a $δ< 1/400$ fraction of insdel errors. They also posed the problem of constructing linear codes that get close to the half-Singleton bound (proved in [CGHL21]) over small fields. Thus, our results significantly improve their construction and get much closer to the bound.

preprint2022arXiv

Nonlinear Repair of Reed-Solomon Codes

The problem of repairing linear codes and, in particular, Reed Solomon (RS) codes has attracted a lot of attention in recent years due to their extreme importance to distributed storage systems. In this problem, a failed code symbol (node) needs to be repaired by downloading as little information as possible from a subset of the remaining nodes. By now, there are examples of RS codes that have efficient repair schemes, and some even attain the cut-set bound. However, these schemes fall short in several aspects; they require a considerable field extension degree. They do not provide any nontrivial repair scheme over prime fields. Lastly, they are all linear repairs, i.e., the computed functions are linear over the base field. Motivated by these and by a question raised in [GW17] on the power of nonlinear repair schemes, we study the problem of nonlinear repair schemes of RS codes. Our main results are the first nonlinear repair scheme of RS codes with asymptotically optimal repair bandwidth (asymptotically matching the cut-set bound). This is the first example of a nonlinear repair scheme of any code and also the first example that a nonlinear repair scheme can outperform all linear ones. Lastly, we show that the cut-set bound for RS codes is not tight over prime fields by proving a tighter bound, using additive combinatorics ideas.

preprint2022arXiv

Reed Solomon Codes Against Adversarial Insertions and Deletions

In this work, we study the performance of Reed--Solomon codes against adversarial insertion-deletion (insdel) errors. We prove that over fields of size $n^{O(k)}$ there are $[n,k]$ Reed-Solomon codes that can decode from $n-2k+1$ insdel errors and hence attain the half-Singleton bound. We also give a deterministic construction of such codes over much larger fields (of size $n^{k^{O(k)}}$ ). Nevertheless, for $k=O(\log n /\log\log n)$ our construction runs in polynomial time. For the special case $k=2$ , which received a lot of attention in the literature, we construct an $[n,2]$ Reed-Solomon code over a field of size $O(n^4)$ that can decode from $n-3$ insdel errors. Earlier constructions required an exponential field size. Lastly, we prove that any such construction requires a field of size $Ω(n^3)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Roni Con

Research overview

Is this your work?

3 publications

Explicit and Efficient Constructions of linear Codes Against Adversarial Insertions and Deletions

Nonlinear Repair of Reed-Solomon Codes

Reed Solomon Codes Against Adversarial Insertions and Deletions

See the researcher in context

Building this map preview