Combinatorial proof of Muchnik's theorem
Alexander Shen · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2006
Original proof of Muchnik's theorem on conditional descriptions can be modified and split into two parts: 1) we construct a graph that allows large online matchings (main part) 2) we use this graph to prove the theorem The question about online matching could be interesting in itself.