Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, Mikhail V. Vyugin

Let a program p on input a output b. We are looking for a

shorter program p' having the same property (p'(a)=b). In

addition, we want p' to be simple conditional to p (this

means that the conditional Kolmogorov complexity K(p'|p) is

negligible). In the present paper, we prove that ...
more >>>

Venkatesan Guruswami, Nicolas Resch, Chaoping Xing

For a vector space $\mathbb{F}^n$ over a field $\mathbb{F}$, an $(\eta,\beta)$-dimension expander of degree $d$ is a collection of $d$ linear maps $\Gamma_j : \mathbb{F}^n \to \mathbb{F}^n$ such that for every subspace $U$ of $\mathbb{F}^n$ of dimension at most $\eta n$, the image of $U$ under all the maps, $\sum_{j=1}^d ... more >>>

Shachar Lovett

The GM-MDS conjecture of Dau et al. (ISIT 2014) speculates that the MDS condition, which guarantees the existence of MDS matrices with a prescribed set of zeros over large fields, is in fact sufficient for existence of such matrices over small fields. We prove this conjecture.