Explicit, Epsilon-Balanced Codes Close to the Gilbert-Varshamov Bound

Amnon Ta-Shma
Tel Aviv University
January 29, 2018

I will show an explicit construction of a binary error correcting code with relative distance $\frac{1-\epsilon}{2}$ and relative rate $\epsilon^{2+o(1)}$. This comes close to the Gilbert-Varshamov bound that shows such codes with rate $\epsilon^2$ exist, and theLP lower bound that shows rate $\frac{\epsilon^2}{\log \frac{1}{\epsilon}}$ is necessary. Previous explicit constructions had rate about$\epsilon^3$, and this is the first explicit construction to get that close to the Gilbert-Varshamov bound.

This talk will have two parts, on Monday and Tuesday.

A Constant-factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Svensson
École polytechnique fédérale de Lausanne
January 23, 2018

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of that relaxation.