\documentclass[a4paper]{slides}
\usepackage{amsmath,amssymb}

\advance\textheight \headheight
\advance\textheight \headsep
\topmargin=-10mm
\headheight=0pt
\headsep=0pt
\advance\textheight -\topmargin

\hyphenpenalty=10000
\parindent=0pt

\begin{document}
\begin{titlepage}
\begin{center}
\large\bf
Cryptography in the Context of Kolmogorov Entropy
\end{center}
\vspace{7ex}
\centerline{Alexei Semenov\hfil Andrej Muchnik}
\vspace{3ex}
\centerline{\it Institute of New Technologies}
\centerline{\it Moscow}
\end{titlepage}
\begin{slide}
Cryptographical problem in\\
Kolmogorov theory of complexity:

\setlength{\fboxrule}{0pt}
\unitlength=1em
\begin{picture}(18,11)(0,3)
%\put(0,3){\line(0,1){11}}
%\put(0,14){\line(1,0){18}}
%\put(18,14){\line(0,-1){11}}
%\put(18,3){\line(-1,0){18}}
\thicklines
\put(1.3,9.05){\vector(2,1){6.9}}
\put(1.3,7.95){\vector(2,-1){6.9}}
\put(0,8.17){\fbox{\large $D$}}
%
\thinlines
%\put(9.4,12.5){\vector(2,-1){6.9}}
\multiput(9.4,12.5)(0.9,-0.45){7}{\vector(2,-1){0.5}}
\put(15.7,9.35){\vector(2,-1){0.6}}
%\put(9.4,4.5){\vector(2,1){6.9}}
\multiput(9.4,4.5)(0.9,0.45){7}{\vector(2,1){0.5}}
\put(15.7,7.65){\vector(2,1){0.6}}
%
\put(16.3,8.17){\fbox{\large $B$}}
%
\newlength\bwid
\settowidth{\bwid}{\large $A$}
%
\put(8.2,12.2){\fbox{\large $A$}}
\put(8.2,4.2){\fbox{\hbox to \bwid {\large $C$}}}

\put(8.8,13.4){{\hbox to 0pt{\hss I\hss}}}
\put(8.8,3.1){{\hbox to 0pt{\hss II\hss}}}

\put(13,5.5){\large$-$}
\put(13,11.3){\large$+$}
\end{picture}

$K(B|AD)\approx 0$ \\
$K(B|CD)\approx K(B|C)$\\
$K(D)\approx K(B|A)$

{\small ($\approx$ holds up to logarithm of lengths)}
\end{slide}

\begin{slide}
The Aim:\\
for
%any vector of
any given values\\
{\small $K(A), K(B), K(C)$,
$K(AB), K(BC), K(AC), K(ABC)$}
\begin{itemize}
\item
either to prove that
for all such $A,B,C$
the problem has a solution ($D$ exists)
\item
or to prove that for some such $A,B,C$
the problem has no solution.
\end{itemize}

\vspace{2ex}

%Here we consider several simple cases
%and one non-trivial case.
\end{slide}

\begin{slide}
%W.l.o.g., assume that\\
$K(A)\approx\ell(A)$,
$K(B)\approx\ell(B)$,
$K(C)\approx\ell(C)$.

\begin{enumerate}
\item $K(B|C)\approx 0$

$K(B|CD)\approx K(B|C)$ for any $D$

\item $K(B|A)\approx 0$

$D$ is empty word

\item  $K(A|C)\lnsim K(B|C)$

The problem is never solvable:\\
if $K(B|AD)\approx 0$, then
$K(B|CD)\lesssim K(A|C)$


\item $K(ABC)\approx K(A)+K(B)+K(C)$,\\
$K(A)\gtrsim K(B)$

$D=A'\oplus B$,\\
where $A'$ is a beginning of $A$,
$\ell(A')=\ell(B)$

\end{enumerate}
\end{slide}

\begin{slide}

$I(A:B)\approx 0$,
$I(B:C)\approx 0$,
$I(A:C)\approx 0$

\vspace{2ex}
\hrule

{\bf Theorem 1}

$K(A)\gnsim 2 K(B)$

The problem is always solvable.

\vspace{2ex}

\hrule

\vspace{2ex}

{\bf Theorem 2}

$K(A)\lnsim 2 K(B)$

The problem can be unsolvable.

Moreover,
$\forall A, B$\\
\hbox to 1.1em{if\hfil}
$K(A)\lnsim 2 K(B)$, then\\
$\exists C\;\; \forall D$\\
$K(B|AD)\approx 0\land K(D)\approx K(B)\Rightarrow$\\
\centerline{\hspace*{\stretch{100}} $K(B|CD)\lnsim K(B)$}
(in addition,\\
$K(B|AC)\approx 0$,
$K(C)\le K(B)+\gamma\log K(B)$)

\end{slide}

\begin{slide}
The proof is based on
effective constructing
an auxiliary function $f$
with several properties.

In particular, the condition
$K(B|AC)\approx 0$
is provided by
the property $f(AC)=B$.

We look for the function $f$
in a finite set.
Namely, we consider
finite functions that map
binary words of length
$\ell(A)+\ell(C)$ into
binary words of length $\ell(B)$.

Using a probabilistic argument,
it is proved that
the fraction of functions
without the properties required
is negligibly small.
\end{slide}

\begin{slide}
 The properties of $f$ that we require
are effectively verifiable,
if the function $K$ is known.

But $K$ is not computable.

Consider a finite set of functions
similar to $K$
by their combinatorial properties.

As $f$, we take a function that
has the properties required for all
of those $K$-like functions.\\
Even in this case,
a probabilistic argument shows
that there exists such function $f$.

Thus we can find $f$
by exhaustive search.
\end{slide}

\end{document}