2017-WorkshopProposal-AdaptivityAndCompression.tex

\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}

\usepackage{multicol}

\usepackage{times} % Specify font, especially when using ps2pdf after.
\usepackage{amssymb}
%\usepackage[sort]{natbib} % To have the references sorted in good order.
\usepackage{url}
\usepackage{fullpage}
\usepackage{xspace}
\usepackage{versions}
\includeversion{FIVEDAYS}\excludeversion{THREEDAYS}
\excludeversion{INUTILE}
\excludeversion{LONG}
\excludeversion{TODO} \excludeversion{JEREMY} \excludeversion{SIMON} \excludeversion{STEFAN} 

% \usepackage{longtable} % To divide the table with the list of guests between several pages (http://www.ctan.org/pkg/longtable)
% \usepackage{array,etoolbox} %% To number automatically the rows of the list of guests, from http://tex.stackexchange.com/questions/21243/automatic-table-row-numbers
% \preto\tabular{\setcounter{magicrownumbers}{0}}
% \newcounter{magicrownumbers}
% \newcommand\rownumber{\stepcounter{magicrownumbers}\arabic{magicrownumbers}}
% \def\rownumber{}

\usepackage{booktabs}

\usepackage{hyperref}

\newcommand{\access}{\ensuremath{\texttt{access}}}
\newcommand{\rank}{\ensuremath{\texttt{rank}}}
\newcommand{\select}{\ensuremath{\texttt{select}}}
\newcommand{\dataType}{\ensuremath{{\cal T}}}
\newcommand{\abstractDataType}{\ensuremath{{\cal A}}}
\newcommand{\etal}{~et al.}
\newcommand{\Oh}{\ensuremath{{\cal O}}}
\newcommand{\entropy}{\ensuremath{{\cal H}}}
\newcommand{\NP}{\ensuremath{\mathsf{NP}}\xspace}

\begin{document}

\title{Synergies between \\ Adaptive Analysis of Algorithms, Parameterized Complexity, \\ Compressed Data Structures and Compressed Indices}

% \title{ Application for a 5 day long Dagstuhl Seminar, for 45 researchers \\ \emph{
% Adaptive Analysis of Algorithms and Data Structures
% % Parameterized Complexity, Adaptivity, and Compression
% } }

\author{J\'er\'emy Barbay \and Johannes Fischer \and Stefan Kratsch \and Srinivasa Rao Satti }
\maketitle              % typeset the title of the contribution

\begin{abstract}
This seminar will bring together researchers from the area of the adaptive analysis of algorithms; the study of the parameterized complexity of NP Hard problems; the area focused on compressed data structures; and the area concerned with the study of compressed indices. While all of these subareas of algorithms and data structures, respectively, focus on ``going beyond the worst-case'' for classes of structurally restricted inputs, there has been a limited amount of interactions between them, and some results being "discovered" twice. The goal of the seminar is to foster this interaction both during the seminar and in the future by (1) teaching one another the key techniques of ones areas, through tutorials and short talks; (2) discussing open problems at the intersection of the areas in varying small groups; and (3) compiling those techniques and open problems in a collective document realized in collaboration between the participants.  Examples of synergies include (1) techniques developed for sorting multisets and used to design compressed data structures supporting operators on permutations; (2) techniques developed to study the Parameterized Complexity of some graph algorithms used to design compressed data structures for such graphs; (3) the use of difficulty measures such as the entropy for both running times and space usage; (4) techniques taking advantage at once of the input order, the input structure, the query order and the query structure; and others to be discovered during the seminar.
\end{abstract}


\section{Basic information}

\subsubsection*{ Organizers} 
\begin{itemize}
\item Dr.\ J\'er\'emy Barbay, Assistant professor at the University of Chile, \textsc{Chile};
\item Dr.\ Johannes Fischer, Professor at the Tecnische Universitad Dortmund, \textsc{Germany};
\item Dr.\ Stefan Kratsch,  Professor at the University of Bonn, \textsc{Germany};
\item Dr.\ Srinivasa Rao Satti, Professor at Seoul National  University,  \textsc{Korea}.
\end{itemize}

\subsubsection*{Type of event}
Dagstuhl seminar, 5 days, 45 participants. 

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

\subsubsection*{Topics}

% \begin{TODO}
% \begin{JEREMY}
% Can someone read again the bases of the Dagstuhl's seminar to find the specifications of the ``Classification'' section? I did not see it when I studied it before creating this proposal.
% \end{JEREMY}
% \begin{STEFAN}
% I have done that. Below is the complete list of valid choices. I have commented out the things that do not apply (I think).
% \end{STEFAN}
% \end{TODO}

%     artificial intelligence / robotics,
%     computer graphics / computer vision,
%     data bases / information retrieval,
    data structures / algorithms / complexity
%     hardware,
%     multimedia,
%     mobile computing,
%     modelling / simulation,
%     networks,
%     optimization / scheduling,
%     programming languages / compiler,
%     security / cryptography,
%     semantics / formal methods,
%     society / HCI,
%     soft computing / evol. alg.,
%     sw-engineering,
%     verification / logic

% Algorithms /
% Analysis / 
% Complexity /
% Compression /
% Data Structures

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

\subsubsection*{Keywords}
% Please use single words or short phrases and seperate them by ";". Please use no more than 5 words / phrases.


Adaptive (analysis of) algorithms;
compressed data structures;
compressed indices;
parameterized complexity.
% compression-aware algorithms,
% fine-grained analysis, 
% fixed-parameter tractability,
% instance-optimal algorithms,
% output-sensitive algorithms,
% input order;
% input structure;

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

%SK: since Dagstuhl said that we do not need to list the dates in the proposal, I have reduced this to the minimum
\subsubsection*{Preferred dates and block-out dates}

Preferred dates and block-out dates are given via the online portal at\newline \texttt{http://boemund.dagstuhl.de/dosa/author/index.php}.


\section{Description of the seminar}

\begin{INUTILE}
This event is meant to be a follow-up to the \texttt{Dagstuhl Seminar 09171} in 2009, which gathered 45 participants on the topic of ``\emph{Adaptive, Output Sensitive, Online and Parameterized Algorithms}'', which achieved a larger visibility of the idea of going ``beyond the worst case'' (e.g. the recent Berkeley workshop on ``Adaptive Analysis'', and adaptive results in new areas of research \cite{2015-SPIRE-AdaptiveComputationOfTheSwapInsertCorrectionDistance-BarbayPerez}). The proposed event would gather researchers from the same communities as the previous one, plus researchers from the communities related to data compression, in the hope to similarly foster new interactions, in both directions between the field of studies of algorithms and of data structures.
\end{INUTILE}

This application proposes a seminar bringing together two groups of researchers characterized, on the one hand, by research on algorithms which run faster on large families of instances than in the worst case over all instances of same size  (e.g. parameterized complexity and adaptive analysis of algorithms); and on the other hand, by research on data structures which use less space on large families of instances than in the worst case over all instances of same size (e.g. compressed data structures and compressed indices). 
%
Albeit those themes of research share a similar perspective of aiming ``beyond worst case analysis'' (over instances of fixed size), examples of work combining both approaches have been rare: we hope to change this by a joint seminar.  
%
In Section \ref{sec:topics-seminar} we describe the two main topics of the seminar: the analysis of algorithms on one hand, and the analysis of data structures and indices on the other hand. In Section \ref{sec:objectives-seminar} we describe the three main objectives of the seminar: identifying and merging common techniques between the areas; identifying open problems common to both; and compiling both lists in a collective document before and during the seminar.

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

\subsection{Topics of the Seminar}
\label{sec:topics-seminar}

The aim of the seminar is to gather two distinct communities: the one focusing on the design and analysis of algorithms, whose research topics are described in Section~\ref{sec:algorithms}, and the other one focusing on the design and analysis of compression schemes and compressed data structures, whose research topics are described in Section~\ref{sec:dataStructures}.

\subsubsection{Analysis of Algorithms}
\label{sec:algorithms}

Traditionally the analysis of algorithms measures the complexity of a problem or of an algorithm in terms of the worst-case behavior over all inputs of a given size. \begin{LONG} This is the standard analysis of algorithms, pioneered by Knuth\cite{1968-BOOK-TheArtOfComputerProgramming-Knuth}, which measures the performance of the algorithm in the worst case over instances of fixed size. As the volume of data processed grows, the gap between the performance of the best algorithm "optimal in the worst case" and the best algorithm "in practice" grows as well, which reduce the interest of worst case theoretical analysis.

\end{LONG}
However, in certain cases, improved analysis and algorithms can be obtained by considering a finer partition of the input space.  This idea has been independently rediscovered in many areas, under the names of \emph{output-sensitive algorithms} (in \textsc{Computational Geometry}~\cite{1985-SOCG-OutputSizeSensitiveAlgorithmsForFindingMaximalVectors-KirkpatrickSeidel,1986-JCom-TheUltimatePlanarConvexHullAlgorithm-KirkpatrickSeidel}), \emph{parameterized complexity} (in \textsc{Computational Complexity}~\cite{CyganFKLMPPS15}), \emph{adaptive (analysis of) algorithms} (in \textsc{algorithmics}~\cite{1992-ACJ-AnOverviewOfAdaptiveSorting-MoffatPetersson}), \emph{instance-optimal algorithms} (in \textsc{Database}~\cite{2003-JCSS-OptimalAggregationAlgorithmsForMiddleWare-FaginLotemNaor} and \textsc{Computational Geometry}~\cite{2017-JACM-InstanceOptimalGeometricAlgorithms-AfshaniBarbayChan}), or \emph{online competitive ratio} (in \textsc{algorithmics}~\cite{2007-SODA-OnTheSeparationAndEquivalenceOfPagingStrategies-AngelopoulosDorrigivLopezOrtiz}). 
%
We list below a selection of the relevant techniques of analysis:

\begin{itemize}

\item \emph{Adaptive Analysis} of Polynomial problems:
\begin{TODO}
\begin{STEFAN}
@Jeremy: I think it would be nice to have some general words about adaptive algorithms here? Should the entry be called adaptive algorithms for polynomial problems?
\end{STEFAN}
\end{TODO}
  \begin{itemize}

\item \emph{Input Sensitivity}: A generalization of output sensitivity, where any group of instances can be defined (generally by a measure of ``difficulty'' of the instances or an additional ``parameter'' of the problem) in order to refine the standard worst-case analysis to smaller classes of instances. Among those techniques, it is useful to distinguish two classes in particular, which have some potential for synergy through this seminar: \emph{Input-Order Sensitivity} (e.g. adaptive permutation sorting \cite{1992-ACMCS-ASurveyOfAdaptiveSortingAlgorithms-EstivillCastroWood,1992-ACJ-AnOverviewOfAdaptiveSorting-MoffatPetersson}) and \emph{Input Structure Sensitivity} (e.g. multiset sorting adaptive to frequencies~\cite{2017-CPM-SynergisticSortingAndDeferredDataStructuresOnMultiSets-BarbayOchoaRao} or computing Convex hull adaptively to the point positions~\cite{2017-JACM-InstanceOptimalGeometricAlgorithms-AfshaniBarbayChan}).
  \begin{LONG}
  \begin{itemize}
\item \emph{Input-Order Sensitivity}: The only technique of adaptive analysis which can be performed for algorithms sorting permutations~\cite{1992-ACMCS-ASurveyOfAdaptiveSortingAlgorithms-EstivillCastroWood,1995-DAM-AFrameworkForAdaptiveSorting-PeterssonMoffat,2013-TCS-CompressedRepresentationsOfPermutationsAndApplications-BarbayNavarro,2012-TCS-LRMTreesCompressedIndicesAdaptiveSortingAndCompressedPermutations-BarbayFischerNavarro,1994-IC-SortingShuffledMonotoneSequences-LevcopoulosPetersson,1985-TCom-MeasuresOfPresortednessAndOptimalSortingAlgorithms-Mannila,1979-CTCS-SortingPresortedFiles-Mehlhorn,1980-CACM-BestSortingAlgorithmForNearlySortedLists-CookKim,1958-InfAndC-SortingTreesAndMeasuresOfORder-Burge}, it measures the complexity of the algorithm in the worst case over all permutations of a given input. In the case of permutation sorting algorithms, the input is a permutation over $[1..n]$ and is simply described by $n$.

\item \emph{Structure Sensitivity}: Technique referring to algorithms which ignore the order of the input and focus on its content (e.g. such as repetitions of elements in multisets, or such as the position of points in a data set rather than the order in which they are given). While meaningless on permutations, Munro and Spira~\cite{1976-JComp-SortingAndSearchingInMultisets-MunroSpira} showed how it does apply to sorting multisets, and Boyar and Favrholdt~\cite{2007-TALG-TheRelativeWorstOrderRatioForOnlineAlgorithms-BoyarFavrholdt} introduced it as ``relative worst order ratio'' in the context of online algorithms. A particular case is that of \emph{Output Size Sensitivity}, the first technique of adaptive analysis of algorithms to be introduced in Computational Geometry\footnote{This type of analysis was already implicitly performed for all operations on texts and databases which output size can vary from null to exponential in the size of the input.}, by Kirkpatrick and Seidel~\cite{1986-JCom-TheUltimatePlanarConvexHullAlgorithm-KirkpatrickSeidel}, which measures the complexity of the algorithm in the worst case over instances of fixed input and output size.
  \end{itemize}
  \end{LONG}

\item \emph{Instance Optimality}: Fagin et al. \cite{2001-PDS-OptimalAggregationAlgorithmsForMiddleWare-FaginLotemNaor,2003-JCSS-OptimalAggregationAlgorithmsForMiddleWare-FaginLotemNaor} introduced the concept of an instance-optimal algorithm such that its cost is at most a constant factor from the cost of any other algorithm running on the same input, for every input instance.  For many problems, this requirement is too stringent, so Afshani\etal\cite{2017-JACM-InstanceOptimalGeometricAlgorithms-AfshaniBarbayChan} considered instead variants of instance optimality on restricted models, limited to the structure of the instance as opposed to the order in which it is input.

  \end{itemize}

\item \emph{Parameterized Complexity} of \NP-hard problems: This area studies the complexity of (hard) computational problems by relating the running time not only to the input size but also to one or more problem-specific \emph{parameters}. Each choice of parameters for a given problem yields a different \emph{parameterized problem}. Appropriate notions of \emph{parameterized reductions} allow to relate such problems and give rise to a theory of parameterized intractability similar to the theory of \NP-hardness. Complementing this, there are two notions of parameterized tractability:
  \begin{itemize}
\item \emph{Fixed-Parameter Tractability}: 
This relaxes polynomial-time tractability by allowing an additional factor in the runtime that may only depend on the parameter values; for \NP-hard problems this factor is usually exponential in the parameter. Ideally, such runtimes offer a smooth transition between fast polynomial-time algorithms for instances with bounded parameter values and the worst-case exponential-time algorithms that are known for the general case of the problem. A fixed-parameter tractability result also proves that the parameter in question is responsible for the (likely) polynomial-time intractability of the problem, since bounding the parameter yields polynomial-time algorithms.
\item \emph{Kernelization}:
This notion formalizes the intuitive notion of efficient preprocessing for \NP-hard problems. Given an instance of a parameterized problem, i.e., input data plus parameter, a kernelization takes polynomial time and reduces an equivalent instance of size bounded only in the parameter. If we request size polynomial in the parameter then this strictly refines fixed-parameter tractability (modulo complexity assumptions); for arbitrary size bounds the two notions are known to be equivalent. Focus in kernelization is on classifying parameterized problems into admitting or not admitting polynomial or even linear-sized kernels, and proving tightness of these bounds.
  \end{itemize}

\end{itemize}

\begin{TODO}
\begin{STEFAN}
@Jeremy: The following paragraph seems a bit out of synch with the stuff above?
\end{STEFAN}
\end{TODO}
As compression schemes take advantage of the ``easiness'' (in terms of compressibility) of practical data as compared to the worst possible data (e.g. random), so called ``Adaptive Algorithms'' take advantage of the ``easiness'' (in terms of computability) of practical instance as compared to the worst case complexity. The efficiency of such algorithms is measured by their parameterized complexity, a measure of computational complexity taking as parameter not only the size of the input (as in traditional computational complexity analysis), but also one or more measures of difficulty. We describe in the following sections the related concepts on data-structures and compression.


\subsubsection{Analysis of Data Structures}
\label{sec:dataStructures}

There is a relation between the execution time of a comparison based algorithm and the representation of the data it processes (e.g.  the relation between \texttt{Wavelet Trees} for permutations and the \texttt{Merge Sort} algorithm~\cite{2013-TCS-CompressedRepresentationsOfPermutationsAndApplications-BarbayNavarro} yields a better encoding for permutations). We describe here some of the key concepts on compressed data structures, which we hope to put in relation with techniques of analysis of algorithms.

\begin{itemize}
\item An \emph{Encoding} is a coding scheme that supports \emph{access} to the data, either through queries specific to this data type (e.g., $i$-th value of a permutation) or through access to a binary representation of the object (e.g., the $i$-th block of $\lg n$ bits of the integer array representing the permutation).  Information theory indicates that the best possible encoding, in the worst case over the $f(n)$ instances of fixed size $n$, uses at least $\lg f(n)$ bits. 
%
Similarily, given a measure $\mu$ on the instances,  the best possible encoding, in the worst case over the $f(n,\mu)$ instances of fixed size $n$ and measure $\mu$, uses at least $\lg f(n,\mu)$ bits. 
%
These information theory lower bound is used as a baseline (or \emph{uncompressed baseline}) to express the space taken by any encoding.  A \emph{Compressed Encoding} is a compressed data structure supporting at least the {\access} operator, and a \emph{Compression Scheme} is the algorithm producing this compressed encoding.

\item A \emph{Data Structure} $\mathcal{D}$ is an encoding which supports various operators (e.g., a run encoding of permutations~\cite{2013-TCS-CompressedRepresentationsOfPermutationsAndApplications-BarbayNavarro} supporting the operators \texttt{access} and \texttt{inverse access}). Formally, it specifies how to encode data from some \emph{Data Type} {\dataType} (e.g., permutations) so as to support the operators specified by a given \emph{Abstract Data Type} {\abstractDataType} (e.g., \texttt{access} and \texttt{inverse access}).  By definition, any data structure supporting {\access}, and possibly some other operators, will use at least that much space as the lower bound for any encoding. The additional space used to support operators efficiently is called the \emph{redundancy} of the data structure. The following classifications of Data Structures are of particular interest:

\begin{itemize}
\item A \emph{Succinct Data Structure}~\cite{1989-FOCS-SpaceEfficientStaticTreesAndGraphs-Jacobson} is a data structure whose redundancy is negligible in comparison with the size of the data structure when the size of the instance goes to infinity, that is, whose redundancy is within $o(\lg f(n))$.
\item A {\em Compressed Data Structure} (also called ``opportunistic data structure''~\cite{2004-Algoritmica-EngineeringAlightweightSuffixArrayConstructionAlgorithm-ManziniFerragina} or ``ultra-succinct data structure''~\cite{2007-SODA-UltraSuccinctRepresentationOfORderedTrees-JanssonSadakaneSung}) for a compressibility measure $\mu$ is a data structure that requires $\lg f(n,\mu) + o(\lg f(n))$ bits to encode any instance of size $n$ and compressibility $\mu$.
\item A {\em Fully-Compressed Data Structure} for a compressibility measure $\mu$ is a data structure requiring $\lg f(n,\mu) + o(\lg f(n,\mu))$ bits on any instance of size $n$ and compressibility $\mu$. While the $o(\cdot)$ term is asymptotic in $n$, it is useful to allow $\mu$ to depend on $n$ too.
\end{itemize}

\item An \emph{Index} is a structure that, given access to some data structure $\cal D$ supporting a defined abstract data type $\abstractDataType$ (e.g., a data structure for bit-vectors supporting the {\access} operator), extends the set of operators supported to a more general abstract data type $\abstractDataType'$ (e.g., {\rank} and {\select} operators).  By analogy with succinct data structures, the space used by an index is called \emph{redundancy}.
  \begin{itemize}
\item A \emph{Succinct Index}~\cite{2011-TALG-SuccinctIndexesForStringsBinaryRelationsAndMultiLabeledTrees-BarbayHeMunroRao} or \emph{Systematic Data Structure} $\cal I$ is simply an index whose redundancy is asymptotically negligible in comparison to the uncompressed baseline when the size $n$ of the instance goes to infinity, that is, $o(\lg f(n))$ bits.

\item A \emph{Compressed Index} for a compressibility measure $\mu$ is an index whose redundancy is asymptotically negligible in comparison to the compressed baseline for $\mu$ when $n$ goes to infinity, that is, it uses $o(\lg f(n,\mu))$ bits of space.
  \end{itemize}

\end{itemize}

In many cases, the research on compressed data structures is orthogonal to the research on algorithms, in the sense that supporting operators in less time directly yields a faster execution of the algorithms based on those operators, but does not affect the design of the algorithm. We suggest in the next section some more intimate relations between the two topics.

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

\subsection{Objectives of the Seminar}
\label{sec:objectives-seminar}

The main objective of the seminar is to gather researchers who share the philosophy of going ``beyond the worst case'' but have applied it to distinct fields, such as polynomial or \NP-hard problems on one hand, and compressed data structures or indices on the other hand.  We describe three types of interactions (see Section~\ref{sec:synergies}) that we hope such a gathering will promote, and what impact it could have on the community in the long term  (Section~\ref{sec:impact}) in reducing the re-invention of techniques and in identifying new problems.

%\subsubsection{Synergies and Research Questions}
\subsubsection{Synergies}
\label{sec:synergies}

While sharing the same perspective of aiming ``beyond worst case analysis'', each community has been identifying its own problems and developing its own techniques. We describe here three types of interactions between researchers from distinct areas that we hope will occur during the seminar.

\paragraph{Results implied from other fields:}

Some results from a given field can imply results in another field. 
%
For instance, the results on the compression of \texttt{Wavelet Trees} directly inspired an improved analysis of the running time of the \texttt{Adaptive Merge Sort} algorithm \cite{2013-TCS-CompressedRepresentationsOfPermutationsAndApplications-BarbayNavarro}.  
%
Researchers from different fields learning each other's techniques are likely to bring other such refinements.
%
For instance, faster algorithms can inspire compression schemes: any correct algorithm must be able to output a certificate of the correctness of its output for a given input. For some problems (e.g. \textsc{Sorting} a permutation), this certificate describes the instance itself. Then, an algorithm which performs faster on some classes of instances, generates a shorter certificate, which suggests a compressed representation of the input.
% 
Such relations could be exploited more often in the context of problems solvable in polynomial time, and does not seem to have been explored in the context of NP-hard problems (e.g. compression of graphs based on the kernel identified in studies of the parameterized complexity of the decomposition of graphs into cliques).

\paragraph{Methodology implied from other fields:}

Some methodologies from a given field can be applied to other fields.

% \begin{itemize}
% \item 
An example of synergy between compressed data structures and the adaptive analysis of algorithms is the concept of entropy: well known in the field of compressed data structures, it inspired refinements in the analysis of adaptive sorting algorithms \cite{2013-TCS-CompressedRepresentationsOfPermutationsAndApplications-BarbayNavarro}.
%
% \item 
An example of synergy between the adaptive analysis of algorithms and parameterized complexity is how the study of ``Adaptive Sorting'' algorithms has introduced reductions between measures of disorder \cite{1992-ACJ-AnOverviewOfAdaptiveSorting-MoffatPetersson,1995-DAM-AFrameworkForAdaptiveSorting-PeterssonMoffat}, while the study of fixed-parameter tractable problems has introduced the more general \emph{parameterized reductions} between pairs formed by problems and measure~\cite{DowneyF13,CyganFKLMPPS15}. This latest methodology applied to adaptive sorting will bring a better understanding of the input order sensitivity of other problems. We predict that it will inspire the definition of such reductions between pairs formed by \textsc{Abstract Data Types} and measures of compressibility in the study of compressed data structures and of compressed indices.
% \item 
An example of synergy between the adaptive analysis of algorithms and succinct indexes is the application of a measure of difficulty for sorting to the compression of RMQ indices~\cite{2012-TCS-LRMTreesCompressedIndicesAdaptiveSortingAndCompressedPermutations-BarbayFischerNavarro}.
% \end{itemize}

Some examples of similar synergies which have not been explored yet are 
% \begin{itemize}
% \item 
refining the analysis in the worst case of approximation ratios: doing so conditionned to a difficulty measure is prone to yield finer results and a better understanding of the problem to aproximate; and
% \item 
refining the competitive analysis of online algorithms and data structures: for instance, deferred data structures taking advantage of the gaps between queries \cite{2014-WALCOM-DynamicOnlineMultiSelectionInInternalAndExternalMemory-BarbayGuptaJoRaoSorenson,2013-ESA-OnlineRankSelect-BarbayGuptaJoRaoSorenson} can also take advantages of the input order and structure, and of the query order~\cite{2017-CPM-SynergisticSortingAndDeferredDataStructuresOnMultiSets-BarbayOchoaRao,2016-ARXIV-SynergisticSortingAndDeferredDataStructuresOnMultiSets-BarbayOchoaRao}.
% \end{itemize}

\paragraph{Tailored Problems:}

A better understanding of the bottlenecks in a given field will help to focus on specific problems in related fields.
%
For instance, better approximation algorithms for computing the maximum clique of a graph, a well studied problem in the field of algorithmics, has tremendous applications to the compression and indexing of very large graphs (e.g. graph of the web and social networks~\cite{HNkais13}).  On the other hand, faster support for operators of a compressed data structure will yield faster algorithms on it, if the right operators are optimized.
%
A better understanding of the applications of a specific algorithmic problem or of a specific data structure will generate a tailored definition of the problem, on which a fine-grained analysis can be applied to optimize this particular application.




%\subsubsection{Impact on the Research Community}
\subsubsection{Impact}
\label{sec:impact}

It is our hope that such a gathering of researchers from complementary fields of research will produce not only new scientific results in the short term, but also more coherent research in the future (i.e. avoiding to reinvent the same technique or result multiple times). We hope that this seminar will promote
% \begin{itemize}
%\item 
a compendium of  analysis techniques for both algorithms and data structures;  and
%\item 
a compendium of reductions and of dual results between algorithms and data structures.
% \end{itemize}

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

\subsection{Potential Structure}

The proposed seminar aims at bringing together researchers specialized in the analysis of algorithms, and in the analysis of data structures. At a more detailed view, there are the four mentioned subareas of adaptive (analysis of) algorithms, parameterized complexity, compressed data structures, and compressed indices. We will follow the following tentative program:
\begin{itemize}
 \item Monday+Tuesday: Two tutorials per day and a session for open problems and project ideas.
 \item Wednesday: Contributed talks, free interaction time, excursion.
 \item Thursday: Contributed talks, free interaction time.
 \item Friday: Contributed talks, updates on open problems/projects, conclusion.
\end{itemize}

The outcome is a proceedings of short articles about techniques, and of even shorter articles describing open problems. Each guest will have to submit one, and present it at the workshop.  The interaction time will take the well-established format of open problem sessions, with people taking turn at the boards in 10mns rounds.


Since most researchers will have a good understanding of at most two subareas, we want to start the seminar week by having four tutorials on the subareas on Monday and Tuesday. The tutorials will range between 60 and 90 minutes per topic and will be given by one or two people (guest or organizer) each. The topics and speakers will be assigned ahead of time in function of the final list of participants. Furthermore, there will be open problem sessions on both Monday and Tuesday where people can suggest not only established open problems but in particular also ideas for crossover projects that could be initiated during the week.

For the remaining three days we propose a lighter program of not too many short contributed talks and ample  free time for discussion and interaction. We plan sessions for 20 min.\ contributed talks about the key ideas of recent results. Additionally, we will strongly encourage contributed talks that present key techniques or project ideas in more detail. This will have a more flexible time limit of 10-30 min.\ and sessions will have larger breaks for questions and discussions. The talk concept will be announced early and an initial program will be drafted before the beginning of the seminar week, such that no one will need to  prepare a presentation during the event.





%SK: begin previous proposed structure
% We propose the following structure for the seminar:
% 
% \begin{itemize}
% \item On the first day, $4$ participants will be required to give each a 1h introduction talk about one of the following topics:
%   \begin{enumerate}
% \item Compressed Data Structures
% \item Compressed Indices
% \item Adaptive Analysis of Polynomial Algorithms
% \item Parameterized Complexity of \NP-Hard Problems
%   \end{enumerate}
% \item During the four remaining days, 
%   \begin{itemize}
% \item each participant will be offered the occasion to give a 10mns talk about a problem or technique from their research topic (e.g. data compression) which they believe is related to a complementary topic (e.g. algorithm design), 
% \item with ample time (e.g. 10 mns and regular breakout sessions) between such presentations for discussions about the merits of the proposal.
%   \end{itemize}
% \end{itemize}
%SK: end previous proposed structure

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%SK: slightly rephrased suggestion below (original follows in comments)

\section{Relation to previous seminars}

This seminar is a follow-up to \texttt{Dagstuhl Seminar 09171} (April 19-24, 2009) on the topic of ``\emph{Adaptive, Output Sensitive, Online and Parameterized Algorithms}''\footnote{\url{http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=09171}}, organized by J{\'e}r{\'e}my Barbay (co-author of this proposal), Rolf Klein, Alejandro L\'opez-Ortiz, and Rolf Niedermeier (two of which are in the list of potential participants, Alejandro L\'opez-Ortiz being recently deceased). This time, we focus on the shared interest in input structure and classical analysis refined by structural parameters. Accordingly, from the algorithms community we mainly invite researchers specialized in the adaptive analysis of algorithms and in parameterized complexity, and invite an about equal number of researchers from the area of data structures that focus on compressed data structures and compressed indices. We expect such a setting to create a fertile ground for interactions, based on similar perspectives on both avoiding worst-case bounds and considering problems together with structural measures/parameters.

This seminar complements the recent \texttt{Complexity 2015} workshop (August 19- December 18, 2015) organized in Berkeley\footnote{\url{https://simons.berkeley.edu/programs/complexity2015}} on the theme of ``\emph{Fine-Grained Analysis}'', and the \texttt{Dagstuhl Seminar 16431} (October 23--28, 2016) on ``\emph{Computation over Compressed Structured Data}''.\footnote{\url{http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=16431}} The former covered the parameterized complexity of NP-hard problems and the worst-case complexity of polynomial-time problems, but not really the parameterized complexity of polynomial-time problems; the latter did not cover NP-hard problems nor any kind of parameterized complexity of algorithms.  We will consider 1) a wide range of parameterized complexity results on problems solvable in polynomial times, and 2) a different set of problems with Compressed Data Structures and Indices.

Stefan Kratsch was on the organizing team of \texttt{Dagstuhl Seminar 14451} (November 2--7, 2014) on ``\emph{Optimality and tight results in parameterized complexity}''\footnote{\url{http://www.dagstuhl.de/de/programm/kalender/semhp/?semnr=14451}}, which focused on getting tight bounds for parameterized algorithms and kernelization, similar to the mentioned \texttt{Complexity 2015} workshop. This seminar, and preceding seminars on parameterized complexity (Seminars 12241, 09511, and 07281), were aimed at current results and trends in parameterized complexity rather than outreach to adaptive algorithms or data structures.

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

% \section{Relation to previous seminars}
% 
% This seminar is a follow-up to the \texttt{Dagstuhl Seminar 09171} (April 19-24, 2009) on the topic of ``\emph{Adaptive, Output Sensitive, Online and Parameterized Algorithms}''\footnote{\url{http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=09171}}, organized by J{\'e}r{\'e}my Barbay (co-author of this proposal), Rolf Klein, Alejandro L\'opez-Ortiz, and Rolf Niedermeier (all in the list of potential participants). Albeit not all the themes are mentioned in the title of the proposal (e.g. \emph{output sensitivity} and \emph{competitive ratio} of online algorithms), this second seminar encompasses the same themes from the analysis of algorithms, adding to it the themes of compressed data structures and compressed indices from data structure research. The idea is that this brings together researchers with a shared interest in input structure and classical analysis refined by structural parameters.
% 
% This seminar complements the recent \texttt{Complexity 2015} workshop organized in Berkeley\footnote{\url{https://simons.berkeley.edu/programs/complexity2015}} on the theme of ``Fine-Grained Analysis'', and the \texttt{Dagstuhl Seminar 16431} (October 23--28, 2016) on ``Computation over Compressed Structured Data''.\footnote{\url{http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=16431}}  The former covered the parameterized complexity of NP-hard problems and the worst-case complexity of polynomial-time problems, but not really the parameterized complexity of polynomial-time problems; the latter will not cover NP-hard problems.  We will consider 1) a wide range of parameterized complexity results on problems solvable in polynomial times, and 2) a different set of problems with Compressed Data Structures and Indices.
% 
% Stefan Kratsch was on the organizing team of \texttt{Dagstuhl Seminar 14451} (November 2--7, 2014) on ``\emph{Optimality and tight results in parameterized complexity}''\footnote{\url{http://www.dagstuhl.de/de/programm/kalender/semhp/?semnr=14451}}, which focused on getting tight bounds for parameterized algorithms and kernelization. This seminar, and preceding seminars on parameterized complexity (Seminars 12241, 09511, and 07281), were aimed at current results and trends in parameterized complexity rather than outreach to other branches of computer science.


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

\section{Information about the organizers}

% Each organizer should provide a $0.5-1$ page research CV that gives an overview of an organizer’s academic career and especially points out community services and recognitions. However, it should not list every paper ever published as the five most relevant papers are sufficient.

\subsection*{J\'er\'emy Barbay}

%  Dr. J\'er\'emy Barbay
%   \begin{itemize}
% \item Institution: University of Chile (Chile)
% \item Postal Address: 
%   Oficina 303, 
%   Edificio Norte, Piso 3, 
%   Avenida Beauchef 851, 
%   837-0456 Santiago, 
%   Chile.
% \item Phone:  +56-2-2978-4365
% \item Fax: +56-2-2689-5531
% \item mailto:jbarbay@dcc.uchile.cl
% \item Home Page: http://barbay.cl
%   \end{itemize}

\begin{multicols}{2}
\noindent Assistant professor at the University of Chile, \\
% \texttt{http://barbay.cl}\\
Email: \texttt{jeremy@barbay.cl} \\
Phone:  +56-2-2978-4365\\
Fax: +56-2-2689-5531
\begin{tabbing}
Address: \= University of Chile\\
%\> Oficina 303, Edificio Norte, Piso 3\\
\> Departamento de Ciencias de la Computación, \\
\> Avenida Beauchef 851, 837-0456 Santiago\\
\> Chile
\end{tabbing}
\end{multicols}

J\'er\'emy Barbay received his PhD in Computer Science at the ``Laboratoire de Recherche en Informatique'' of the ``University of Orsay'' in 2002, under the supervision of Claire Mathieu.  He was a postdoctoral fellow at the department of Computer Science of the University of British Columbia until 2004, and an assistant professor at the Cheriton School of Computer Science of the University of Waterloo until 2008. He is an assistant professor at the department of Computer Science of the University of Chile in Santiago, Chile since 2008.
%
J\'er\'emy Barbay's main research is about the analysis of algorithms and data-structures on finer classes of instances than those merely defined by their size, which yields the concepts of adaptive (analysis of) algorithms, instance optimality, output sensitive and parameterized complexity, compressed data structures and indexes, and of formal measures of compressibility.  His work has contributed, among others, to clarify the relations between those topics and has introduced a few useful concepts, such as the direct relation between permutation compression and adaptive sorting~\cite{2013-TCS-CompressedRepresentationsOfPermutationsAndApplications-BarbayNavarro}; the first compressed index achieving space within $o(n H_k) + O(n)$ instead of merely within $o(n \lg \sigma)$~\cite{2014-Algorithmica-EfficientFullyCompressedSequenceRepresentations-BarbayClaudeGagieNavarroNekrich}; Succinct Indexes~\cite{2011-TALG-SuccinctIndexesForStringsBinaryRelationsAndMultiLabeledTrees-BarbayHeMunroRao}; and (input order oblivious) Instance Optimality in Computational Geometry~\cite{2017-JACM-InstanceOptimalGeometricAlgorithms-AfshaniBarbayChan}.

\paragraph{Related publications:}
\begin{itemize}
\item 
P.~Afshani, J.~Barbay, and T.~M. Chan.
\newblock Instance-optimal geometric algorithms.
\newblock {\em Journal of the ACM (JACM)}, 64(1):3:1--3:38, Mar. 2017.

% \item
% P.~Afshani, J.~Barbay, and T.~M. Chan.
% \newblock Instance-optimal geometric algorithms.
% \newblock In {\em Proceedings of the Annual IEEE Symposium on Foundations of
%   Computer Science (FOCS)}, pages 129--138. IEEE Computer Society, 2009.

\item
J.~{Barbay}, C.~{Ochoa}, and S.~R.~{Satti}.
\newblock {Synergistic Sorting and Deferred Data Structures on MultiSets}.
\newblock In {\em Combinatorial Pattern Matching (CPM)}. SPRINGER, 2017.
\newblock to appear.

\item
J.~Barbay, F.~Claude, T.~Gagie, G.~Navarro, and Y.~Nekrich.
\newblock Efficient fully-compressed sequence representations.
\newblock {\em Algorithmica}, 69(1):232--268, 2014.

\item
J.~Barbay, M.~He, J.~I. Munro, and S.~R. Satti.
\newblock Succinct indexes for strings, binary relations and multilabeled
  trees.
\newblock {\em ACM Transactions on Algorithms ({TALG})} , 7(4):52, 2011.

\item
J.~Barbay and G.~Navarro.
\newblock On compressing permutations and adaptive sorting.
\newblock {\em Theoretical Computer Science ({TCS})}, 513:109--123, 2013.
\end{itemize}


%\pagebreak[4]
\subsection*{Johannes Fischer}

\begin{multicols}{2}
\noindent Professor (``W2'' aka.\ ``Associate'') at TU Dortmund\\
% \texttt{http://barbay.cl}\\
Email: \texttt{johannes.fischer@cs.tu-dortmund.de} \\
Phone:  +49-231-755 7711\\
Fax: +49-231-755 7740
\begin{tabbing}
Address: \= Technische Universit\"at Dortmund\\
%\> Oficina 303, Edificio Norte, Piso 3\\
\> Facult\"at f\"ur Informatik, \\
\> Otto-Hahn-Str.\ 14, 44227 Dortmund\\
\> Germany
\end{tabbing}
\end{multicols}



Johannes Fischer studied Computer Science at Universit\"at Freiburg (1997--2003) und University of Aberdeen (2000--2001) and received his PhD from Ludwigs-Maximilians-Universität München in 2007. After PostDoc-stays in Santiago (2 months), Tübingen (15 months) and Karlsruhe (3 years + 9 months paternity leave), he has been associate professor for ``Algorithmic Foundations and Education in Computer Science'' at TU Dortmund since October 2013. His research focuses on space efficient and compressed data structures and string algorithmics, in particular text compression algorithms and compressed text indices. 

\paragraph{Related publications:}
\begin{itemize}
\item P.\ Bille, J.\ Fischer, I.\ L.\ G\o{}rtz, T.\ Kopelowitz, B.\ Sach, and H.\ W.\ Vildh\o{}j.
	\newblock Sparse Text Index Construction in Small Space.
	\newblock \emph{ACM Transactions on Algorithms}, \textbf{12}(3):Article No.\ 39, 2016.
\item J.\ Arz and J.\ Fischer.
	\newblock LZ-Compressed String Dictionaries.
	\newblock In \textit{Proceedings of the 2014 Data Compression Conference (DCC)}: 322--331. IEEE Press, 2014.
\item J.\ Barbay, J.\ Fischer, and G.\ Navarro.
	\newblock LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations.
	\newblock \textit{Theoretical Computer Science}, \textbf{459}(1): 26--41, 2012.
\item J.\ Fischer and V.\ Heun.
	\newblock Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays.
	\newblock \textit{SIAM Journal on Computing}, \textbf{40}(2): 465--492, 2011.
\item J.\ Fischer, V.\ M\"akinen, and G.\ Navarro.
	\newblock Faster Entropy Bounded Compressed Suffix Trees.
	\newblock \textit{Theoretical Computer Science}, \textbf{410}(51): 5354--5364, 2009.
\end{itemize}

%\pagebreak[4]
\subsection*{Stefan Kratsch}

\begin{multicols}{2}
\noindent Professor (W2) at University of Bonn, \\
Email: \texttt{kratsch@cs.uni-bonn.de} \\
Phone: +49 228 73-4554\\
Fax: +49 228 73-4321
\begin{tabbing}
Address: \= Universit\"at Bonn\\
\> Institut f\"ur Informatik I\\
\> Friedrich-Ebert-Allee 144\\
\> D-53113 Bonn
\end{tabbing}
\end{multicols}

Stefan Kratsch received his PhD in 2010 from the Max-Planck-Institute for Informatics, Saarbr\"ucken, in Germany. He then was a postdoc in Utrecht (2 years) and at MPI Saarbr\"ucken (2 months). From 2012 till 2014 he was a junior research group leader at Berlin Technical University. Since January 2015 he is a professor at the University of Bonn.
Stefan Kratsch's main research area is parameterized complexity, especially kernelization. His work has, among others, contributed new techniques for both upper and lower bounds for kernelization and faster algorithms for problems on graphs of bounded treewidth. 
% He served on program committees of IPEC 2015, MFCS 2014, STACS 2014, ISAAC 2013, FSTTCS 2012, and IPEC 2012, and recently joined IPEC's steering committee.

\paragraph{Related publications:}
\begin{itemize}
\item Y.~Disser and S.~Kratsch. Robust and adaptive search. To appear in \emph{Proceedings of Symposium on Theoretical Aspects of Computer Science (STACS)}, 2017.
% \item S.~Kratsch, G.~Philip, and S.~Ray. \newblock Point Line Cover: The Easy Kernel is Essentially Tight. \newblock \emph{ACM Transactions on Algorithms}, 12(3):40:1-40:16, 2016.
\item S.~Kratsch. A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter. \newblock In \emph{Proceedings of European Symposium on Algorithms (ESA)}:59:1-59:17, 2016.
\item H.L.~Bodlaender, M.~Cygan, S.~Kratsch, and J.~Nederlof. \newblock Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. \newblock \emph{Information and Computation}, 243:86-111, 2015.
\item H.L.~Bodlaender, B.M.P.~Jansen, and S.~Kratsch. \newblock Kernelization Lower Bounds by Cross-Composition. \newblock \emph{{SIAM} Journal on Discrete Mathematics}, 28(1):277--305, 2014.
\item S.~Kratsch and M.~Wahlstr\"om. \newblock Representative Sets and Irrelevant Vertices: New Tools for Kernelization. \newblock In \emph{Proceedings of the Annual IEEE Symposium on Foundations of
  Computer Science (FOCS)}:450-459. IEEE Computer Society, 2012.
\end{itemize}

\subsection*{Srinivasa Rao Satti}

\begin{multicols}{2}
\noindent Srinivasa Rao Satti, Professor at Seoul National  University; \\
% \texttt{http://www.cs.helsinki.fi/u/gagie/}\\
Email: \texttt{ssrao10@gmail.com} \\
% Phone: XXX\\
% Fax: XXXX
\begin{tabbing}
Address: \=  University of Seoul\\
\> Department of Computer Science\\
\> Korea
\end{tabbing}
\end{multicols}

Srinivasa Rao Satti received his PhD in Theoretical Computer Science from the Institute of Mathematical Sciences, Chennai, India in 2002 under the supervision of Prof. Venkatesh Raman. He is currently working as an Associate Professor in the School of Computer Science and Engineering at Seoul National University, South Korea. He has worked as a researcher at University of Leicester, UK, University of Waterloo, Canada, IT University of Copenhagen, Denmark, and Aarhus University, Denmark before joining Seoul National University in 2009. His primary research area is succinct data structures. His main contributions to this field include optimal compressed representation of bitvectors, succinct tree representation as well as indexes and encodings for various extensions of range minimum data structures.  His other research interests include database indexing, external memory algorithms and space-efficient graph algorithms.

\paragraph{Related publications:}
\begin{itemize}
\item P.~Bille, G.~M.~Landau, R.~Raman, K.~Sadakane, S.~R.~Satti and O.~Weimann. \newblock Random Access to Grammar-Compressed Strings.\newblock \emph{{SIAM} J. Comput.}, 44(3):513--539, 2015.
\item J.~Barbay, M.~He, J.~I.~Munro, and S.~R.~Satti. \newblock Succinct indexes for strings, binary relations and multilabeled trees. \newblock \emph{ACM Transactions on Algorithms (TALG)}, 7 (4):52, 2011.
\item R.~Raman, V.~Raman and S.~R.~Satti. \newblock Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. \newblock \emph{ACM Transactions on Algorithms (TALG)}, 3(4):43, 2007.
\item A.~Golynski, R.~Grossi, A.~Gupta, R.~Raman and S.~R.~Satti. \ newblock On the size of succinct indices. \newblock In \emph {Proceedings of European Symposium on Algorithms (ESA)}:371-382.  Springer, 2007.
\item J.~I.~Munro and S.~R.~Satti. \newblock Succinct Data Structures. \newblock In \emph{Handbook of Data Structures and Applications}, Chapter 37:1-22. {Chapman and Hall/CRC}, 2004.
\end{itemize}

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

%%%%%%%%  BIBLIO  %%%%%%%%%%%%
\newpage
\bibliographystyle{abbrv}
% unsrt to have [1]unsorted, plain to have [1] sorted, alpha to have something horrible, 
% abbrv to have the same but shorter
\bibliography{biblio-Barbay,publications-Barbay,stefan}

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







\end{document}

















%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: