אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Linear error‑correcting codes that handle insertions and deletions (indels) are fundamental to reliable storage and communication in settings where symbol positions may drift—from DNA data storage to packet‑based networks. Unlike substitution and erasure errors, indels disrupt sequence alignment and therefore require additional synchronization information.

This talk surveys recent constructive techniques that embed such synchronization within fully linear codes, preserving algebraic structure while supporting efficient encoding and decoding. We explain how short synchronization sequences can be interleaved with algebraic‑geometry codes to form “half‑linear” indel codes, and how a padding–flattening procedure converts them into fully linear codes over the base field with only a modest rate penalty. A decoder that combines longest‑common‑subsequence matching with asymmetric Hamming decoding then corrects a prescribed fraction of indels in polynomial time.

Along the way we discuss a subfield‑Singleton–style limitation that shows why rate 1/2 cannot be surpassed—even for a single indel—when only base‑field linearity is assumed. The resulting framework narrows the gap between known lower and upper bounds for linear indel codes and suggests new directions—including tighter synchronization primitives and improved high‑rate constructions—for bringing practical, algebraically structured indel correction closer to theoretical limits.