\documentclass[11pt]{article}
\usepackage[english]{babel}
\usepackage{amsmath,ifthen,color,eurosym}
\usepackage{wrapfig,hyperref,cite}
\usepackage{latexsym,amsthm,amsmath,amssymb,url,cite}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{stmaryrd,wasysym}
\usepackage{colortbl}
\usepackage[lined,boxed,commentsnumbered]{algorithm2e}
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}

\def\baselinestretch{1}


\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem{observation}{Observation}
\newtheorem{proposition}{Proposition}

\setlength{\textheight}{22cm}
\setlength{\topmargin}{-1cm}
\setlength{\textwidth}{165mm}
\setlength{\oddsidemargin}{-3mm}
\setlength{\unitlength}{1mm}


%\renewcommand{\refname}{\small References}
\addto{\captionsenglish}{\renewcommand{\refname}{\normalsize
    References}}



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%
%Put here the package you need, new commands, ...



%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%

\begin{document}
 
\noindent{\bf\Large Tree-depth and space efficiency of parameterized graph algorithms}

\noindent Mi. Pilipczuk

\noindent \underline{M. Wrochna} -- {\small University of Warsaw}

\vspace{2ex}
\noindent{\bf Abstract:}

One of the drawbacks of the standard technique of dynamic programming on path and tree decompositions is that the space usage is exponential in the decomposition's width.
We investigate whether this is unavoidable by considering the computational complexity of graph problems limited to instances of small width or depth.
We complete the landscape sketched for pathwidth and treewidth by Allender et al.~\cite{ECLPT14}% [Theory of Computing,~'14]
, by considering the parameter tree-depth:
We prove that computations on tree-depth decompositions correspond to a model of non-deterministic machines that work in polynomial time and logarithmic space, with access to an auxiliary stack of maximum height equal to the decomposition's depth.
Together with the results of Allender et al., this describes a hierarchy of complexity classes for polynomial-time non-deterministic machines with different restrictions on the access to working space, which mirrors the classic relations between treewidth, pathwidth, and tree-depth.
As corollaries we get equivalent characterizations of the complexity classes involved and a result on their determinization. We then comment on plausible deterministic time-space trade-offs.
 

%If you need a ref section, do it more or less like that : 
\small
\begin{thebibliography}{1}

\bibitem{ECLPT14}
E.~Allender, S.~Chen, T.~Lou, P.~A.~Papakonstantinou, and B.~Tang.
\newblock Width-Parametrized {SAT}: Time–Space Tradeoffs.
\newblock {\em Theory of Computing 10, pp. 297–339, 2014}

\end{thebibliography}


\end{document}