Optimal Document Exchange and New Codes for Insertions and Deletions We give the first communicationoptimal document exchange protocol. For any n and k u003c n our randomized scheme takes any nbit file F and computes a xcex98(k log nk) bit summary from which one can reconstruct F, with high probability, given a related file Fu0027 with edit distance ED(F,Fu0027) xe2x89xa4 k. The size of our summary is informationtheoretically order optimal for all values of k, giving a randomized solution to a longstanding open question of Orlitsky; FOCSu002791. It also is the first nontrivial solution for the interesting setting where a small constant fraction of symbols have been edited, producing an optimal summary of size O(H(xcexb4)n) for kxcexb4 n. This concludes a long series of betterandbetter protocols which produce larger summaries for sublinear values of k and subpolynomial failure probabilities. In particular, the recent breakthrough of Belazzougui, Zhang; FOCSu002716 assumes that k u003c ne, produces a summary of size O(klog2 k  k log n), and succeeds with probability 1(k log n) O(1). We also give an efficient derandomized document exchange protocol with summary size O(k log2 nk). This improves, for any k, over a deterministic document exchange protocol by Belazzougui with summary size O(k2  k log2 n). Our deterministic document exchange directly provides new efficient systematic error correcting codes for insertions and deletions. These (binary) codes correct any xcexb4 fraction of adversarial insertionsdeletions while having a rate of 1  O(xcexb4 log2 1xcexb4) and improve over the codes of Guruswami and Li and Haeupler, Shahrasbi and Vitercik which have rate 1  xcex98 (xe2x88x9axcexb4 logO(1) 1e).

Improved Average Complexity for ComparisonBased Sorting. This paper studies the average complexity on the number of comparisons for sorting algorithms. Its informationtheoretic lower bound is (n lg n  1.4427n  O(log n)). For many efficient algorithms, the first (nlg n) term is easy to achieve and our focus is on the (negative) constant factor of the linear term. The current best value is (1.3999) for the MergeInsertion sort. Our new value is (1.4106), narrowing the gap by some (25%). An important building block of our algorithm is xe2x80x9ctwoelement insertion,xe2x80x9d which inserts two numbers A and B, (Au003cB), into a sorted sequence T. This insertion algorithm is still sufficiently simple for rigorous mathematical analysis and works well for a certain range of the length of T for which the simple binary insertion does not, thus allowing us to take a complementary approach with the binary insertion.