Agenda

Abstract: Many practical problems can be reduced recursively to smaller or simpler instances, down to the base cases. Most often, a straightforward implementation of such reduction fails to yield a solution running in reasonable time. In many cases it is Dynamic Programming which yields solutions of industrial value, based on an adequate tuning of the reduction and the memoization of past computations, in areas as diverse as Stringology, Bio Informatics and many other areas, with solutions running in time polynomial in the size of the input, and space linear in this input size (e.g. Longest Common Sub-Sequence (LCSS) in time within $O(mn)$ and space within $O(n+m)$). Yet, such worst-case results analysis of algorithms has often been criticized as overly pessimistic. As a remedy, some researchers have turned towards multivariate analysis where the execution cost of algorithms is measured as a function of not just the input size but of other parameters that capture, in various ways, the difficulty of the input instance. This approach has been the subject of extensive work on arrays of elements on problems such as sorting, computing the intersection or the union of sorted arrays; and on data structures supporting operators on permutations, Multisets and on Strings. While the technique of dynamic programming is used in many polynomial algorithms introduced in the context of parameterized complexity of NP-hard problems, the dynamic programming is rarely analyzed parametrically itself. The only exception, in the case of the computation of the Insert Swap Edit Distance, yield a much better understanding of the problem, and even improvements on the worst case complexity among instances of fixed sizes.

We aim to systematically consider the application of multivariate analysis to other problems for which dynamic programming has yield good results, such as those used for the computation of the Frechet Distance between two sequence of points, with application to computational geometry, and to the indexed search in multimedia databases; of the distance between skeletons and meshes, with application to computational geometry, and to the indexed search in multimedia databases; of the String Edit Distance between two strings, for various subsets of operators from the commonly considered set {Delete, Insert, Replace, Swap}, with applications to Bioinformatics and text search; of the Tree Edit Distance between two structured texts, with applications to phylogenetics, to the detection of plagiarism and to the evaluation of commits in systems of version control; of the Block Edit Distance between two strings, with applications to the analysis of genomes as well as to the detection of plagiarism.

About the speaker: Jeremy received a Bachelor of Science degree in Mathematics in 1997 in Rouen, a Master degree in 1998 and a Philosophy Doctorate in 2002, both in Computer Science at the Laboratoire de Recherche en Informatique of the University of Orsay, under the supervision of Claire Mathieu. He was a posdoctoral 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 now an assistant professor at the department of Computer Science of the University of Chile in Santiago, Chile.

His 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 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 (TCS2013); the first Compressed Index achieving space within o(n Hk) + O(n) instead of merely within o(n lg s) (ALGO2014); Succinct Indexes (TALG2011); and (input order oblivious) Instance Optimality in Computational Geometry (FOCS2009). Albeit a theoretician by formation, Jeremy did implement and experimentally evaluate some of his theoretical results, either in collaboration with students or on his own (JEA2009,WEA2006). He is interested in other topics of research, in particular in pedagogy.

Fecha:Viernes 11 de mayo de 2018,

Hora: 12:00 a 13:00

Lugar: Sala Alvaro Campos, DCC Universidad Católica, Campus San Joaquín.