# Jérémy Barbay's webpage

## Table of Contents

## 1 Contact

I am assistant professor in the Department of Computer Science (DCC) of the Faculty of Physical and Mathematical Sciences of the University of Chile in Santiago, Chile.

- Electronic mail address : mailto:jeremy@barbay.cl
- Physical location: Oficina 303 (Tercer Piso), Beauchef 851, Santiago, Chile.
- Physical mail address :
Jérémy Barbay (a la atención de Francia Ormena) Oficina 303, tercer Piso, Departamento de Ciencias de la Computacion, Universidad de Chile, Edificio Norte, Beauchef 851, C.P. 8370459 Santiago, Chile.

- Phone coordinates : (GMT-3 Oct-Feb, GMT-4 Mar-Sep)
Secretary Francia Ormena `56-2-2978-4365`

Fax Francia Ormena `56-2-2689-5531`

- web : http://barbay.cl

## 2 Research

In **Theoretical Computer Science**, I am interested in the **Adaptive Analysis** of algorithms and data structures, i.e. refining the worst case analysis over instances of fixed size n by adding more parameters to it, in order to intuitively measure the "difficulty" of the instance. The main motivation of this technique is that the gap between practical cases (real world) and the worst case (over instances of same size as practical ones) becomes potentially larger on **massive data**: refining the analysis by adding more parameters to it allows to reduce this gap back to reasonable values, by better understanding the particularities of practical instances. This concept applies both to the analysis of the computational cost of algorithms (leading to **Adaptive Algorithms** and Parameterized Complexity) and of the space usage of data structures (leading to **Compressed Data Structures** and **Compressed Indices**), and is pushed to its extreme with the concept of **Instance Optimality**, a property insuring the asymptotical optimality of an algorithmic construct over each single instance.

In other areas, I am interested in **Collective Quality Control** mechanisms such as calibrated peer review and Re-Captcha (and in particular in **Boot Strapping Databases**), in the development of new techniques of pedagogy, and in the experimental evaluation of learning.

See my (partial) research notes for more details.

## 3 Publications

- My 5 most important publications (according to me) are:
- "
*Succinct Indexes For Strings And Binary Relations*" [TALG2011] - "
*On Compressing Permutations And Adaptive Sorting*" [TCS2013] - "
*Instance Optimal Geometric Algorithms*" [FOCS2009] - "
*Compact Binary Relation Representations With Rich Functionality*" [IC2013] - "
*Efficient Fully Compressed Sequence Representations*" [ALGO2014]

- "
- My 5 most cited publications (according to Google Scholar on ) are
- "
*Succinct indexes for strings, binary relations and multi-labeled trees*" [TALG2011] - "
*An experimental investigation of set intersection algorithms for text searching*" [JEA2009] - "
*Alternation and redundancy analysis of the intersection problem*" [TALG2008] - "
*Adaptive searching in succinctly encoded binary relations and tree-structured documents*" [TCS2007] - "
*Efficient Fully Compressed Sequence Representations*" [ALGO2014]

- "

See my publications page for the rest of my publications in reversed chronological order: you can press "C" on it to see the publications sorted by categories (e.g. Chapters, Journals and Conferences), research area (e.g. Computational Geometry, Evolution Theory, etc…) or type of work (Theory or Simulations). See Google Scholar for more statistics on my publications, dblp for some other lists of my publications and Arxiv for some drafts.

## 4 Courses

Ever since my doctorate I have been creating new teaching material and tools, and researching new educational techniques. **I received the award of "mejor profesor del año académico 2014" (best professor for the academic year 2014) of my department**. The course designs of which I am the most proud are the following:

- The undergraduate research course "
**Fine Analysis**of Algorithms and Data Structures" (translated from "Analisis Fino de Algoritmos y Estructuras de Datos"), composed of two phases. In the first phase, each student reads 8 research articles superficially; studies, presents and summarizes one small set of article. In the second phase, each student either works on a mini research theme or develops some pedagogical material, for instance in the form of a video or a complete wikipedia article. In the whole course students evaluate and criticize the work of the other students. The course mostly features advanced variants of algorithms well known to undergraduate students, so that they refine their understanding of material already studied (e.g. Sequential and Binary Search refined into Doubling Search, Unary and Binary codes refined into Gamma and Delta Codes, Merge Sort refined into "adaptive Merge Sort", etc…). Students said in the anonymous teaching evaluations that this course was more work than other courses, but that they still liked it a lot. - The module
**Alice**of the second year undergraduate course EI2001 Taller de Proyectos, where students design and program pedagogical 3d animations (five over the course of one semester) using the software Alice from CMU, in groups of two students: the hypothesis is that "Teaching is Learning", and that by reflecting and getting feedback on teaching material that they learn in the previous year, the students will deepen their understanding of it, while learning useful skills from software engineering and pedagogy. Teaching evaluations are very positive. - The course "
**Android**- Programming Mobile Devices" was created to support students of the University of Chile participating to the**Competition of Mobile/Android development**(TUApp) which I have been co-organizing with the company Cursor and professors from other universities since 2009. Aimed at Engineering students (including students not majoring in computer science), it was designed for 30 students and received 140 inscriptions, which forced me to extend it to three courses of 30 students each (summing to 120). In total, 90 students finished the course with amazing applications over the theme of "education".

See my Courses webpage for more detailed information, and in particular the list of courses I taught in the past.

## 5 Supervision

I like a lot working with students (even when I am not directing them). I am currently supervising the following students:

- Carlos Ochoa (PhD, 2013-now) "
*Adaptive Algorithms on Convex Hull, Voronoi Diagrams and Delaunay Triangulations*" - Carlos is working on the adaptive computation of Convex Hulls and Delaunay Triangulations, taking advantage of the order of the input (adaptive computation independent of the input order is impossible in 2 or 3 dimensions [FOCS2009]), inspired from adaptive results for sorting permutations. He will later work on other adaptive algorithms for computing and merging Convex Hulls, Delaunay Triangulations and Voronoi Diagrams.
- Javiel Rojas (PhD, 2013-now) "
*Adaptive Algorithms for computing Klee's measure in High Dimension*" - Javiel is working on the adaptive computation of the Klee's measure of a set of rectangles in high dimensions, focusing on algorithms taking advantage of the degeneracy of the input (something which was not done before in Computational Geometry). He will later work on potential finer measures of adaptivity for this problem.
- Manuel Ramirez (Internship, 2014) "
*Repositorium for Music Sheets*" - Manuel is working on the design of a solution permitting musicians to collaborate on a database of music sheets, by submitting new ones, evaluating collaboratively the submissions, searching and downloading them.

I like to work with students on topics where I bring the techniques (typically, adaptive analysis, compressed data structures or collective quality control) and they (or a co-advisor) bring the problems from a field I am not familiar with. **I pay students** to make them accountable. I require **students** who wish to work with me to **write their own proposal** after we find an intersection between our interests: the idea is that **this is their project**, and that they must be the ones convinced that it can be done, so that they are more motivated to resolve problems on the paths to success than if the success is based on my own conviction that the project is doable. During the project, **we meet weekly** to assess the progress made and to re-evaluate the objectives of the project if necessary. I require the students to **start** their **report at the begining of the internship** and to submit updates in pdf regularly during the project. I am thoroughly reviewing the documents sent to me, which I duly annotate in various colors using Xournal on a Tablet PC.

For more details, see my supervised students and my supervision page for informations and tutorials for current and future supervised students.

## 6 Funding

I combine several source of fundings, which cover various research topics and activities:

Grant/Award | Role and Nb | Duration | Period | Dedication | Total amount | Total amount | Total amount | Total amount |
---|---|---|---|---|---|---|---|---|

Participants | (years) | (h/week) | CLP | EUR | CAD | USD | ||

Fondecyt Regular 1120054 (FONDECYT2012) |
PI (out of 4) | 3 | [2012-2014] | 15 | 56,969,000 |
81,490 | 117,319 | 112,320 |

Talleres de Proyecto (EI2001-EI4002) |
SI | DNA | [2011-now] | 6 | 9,056,000 |
11,740 | 16,651 | 15,134 |

Fundo de Incentivo a la Investigación (FII) |
SI | DNA | [2008-now] | DNA | 12,000,000 |
15,557 | 22,068 | 23,659 |

Fundo de Visitas a la Investigación (FVI) |
SI | DNA | [2008-now] | DNA | 1,000,000 /year |
1,296/year | 1,838/year | 2,000/year |

(Original amounts in bold, other amounts at the exchange rates of http://www.xe.com) PI stands for Principal Invesigator, SI stands for Solo Investigator, CI stands for Co-Investigator or participant, DNA stands for "Does Not Apply".

as indicated by- Fondecyt Regular 1120054 "Compressed Data Structures and Compressability Measures" is funded by Conicyt, to finance research on
**Compressed Data Structures**, paying for equipment and travels for me, 3 collaborators and 2 graduate students, over \(3\) years. - Talleres de Proyectos is funded by the School of Engineering. This finances various modules of the
**Project Oriented Courses**EI2001, EI3001, EI4001 and EI4002. - Fundo de Incentivo a la Investigación (FII) is funded by the Department of Computer Science (DCC). This finances
**undergraduate students**,**furniture**and**exploratory research**(e.g. experimental pedagogy) not covered by the other projects. - Fundo de Visitas a la Investigación (FVI) is funded by the Department of Computer Science (DCC). This finances international collaborations, paying for the visit of one international guest per year. The conditions to be eligible are that the guest should stay at least 20 work days, have a doctorate, and give a presentation about his work while visiting. The money is generally enough to pay either for an international trip to Chile or from the hotel: I sometime manage to pay the other half from another project, or the visitor is paying his half. Those restrictions sometimes make it harder to find candidates, so contact me if you are interested in such a visit!

See my Funding page for more details about current and previous sources of funding.

## 7 Service

I fulfill services mostly in the community of Theoretical Computer Science and in the university where I work, but I also participate in other communities related to Pedagogy, Cryptography and Databases:

- in the community of
**Theoretical Computer Science**, I mostly serve as- Organizer of Events such as Workshops and Summer/Winter schools,
- Speaker at Summer/Winter Schools for graduate students and researchers,
- Member of Program Committees,
- Referee for journals and conferences
- answering questions on Stack-Exchange's website for CSTheory; while

- in the universities where I worked, I help in
**outreach activities**such as- animating the stand at the annual fair for high-school students, showing pedagogical game developped by my students,
- serving as jury for "hackathon" and programming competitions, or
- teaching courses at a summer school for high school teachers;

- in the field of
**Pedagogy**I - in the fields of
**DataBases**,**Cryptography**,**Human Computer Interaction**, and**Mechanism Design**I served as a referee for research articles, Phd, master and engineering's thesis.

See my Services page for more detailed information.

## 8 Experience

- I hold the following diploma and positions:
Period Title Institution Country 2008-now Assistant Professor Universidad de Chile Chile 2004-2008 Assistant Professor University of Waterloo Canada 2002-2004 PostDoctoral Fellow University of British Columbia Canada 1998-2002 Ph.D. in Computer Science Université d'Orsay France 1997-1998 M.Sc. (D.E.A.) in Computer Science Université d'Orsay France 1997 B.Sc. (Maitrise) in Mathematics Université de Rouen France - I received the following awards:
Date Short Description Title Institution Location 2014-10 LMDN award "Lo Mejor De Nosotros 2014" Sociedad Chilena de Ciencia de la Computacion Talca, Chile 2014-08 Teaching Award "Mejor profesor del año académico 2014" Department of Computer Science (DCC) Santiago, Chile 2010-10 LMDN award "Lo Mejor De Nosotros 2010" Sociedad Chilena de Ciencia de la Computacion Antofagasta, Chile - I was invited to teach research courses in summer and winter schools:
Date Short Description Title Institution Location 2014-08 Winter School Run-Adaptivity: from Merge sort to Convex Hull Nucleo ACGO Olmue, Chile 2009-01 Summer School Smaller and faster: Succinct data structures Nucleo ACGO Valparaiso, Chile 2008-12 Winter School Smaller and faster: Succinct data structures MADALGO Aarhus, Denmark 2008-12 Winter School Smaller and faster: Succinct data structures ITU Copenhagen, Denmark

## 9 Vita

I was born in France, in June 1976. I 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. During my PhD I did a 3 month internship at the University of Washington in Seattle visiting Ana R. Karlin, and a 1 month internship at the Georgia Institute of Technology visiting Dana Randall and at the Emory institute visiting Stefan Boettcher I 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. I am now an assistant professor at the department of Computer Science of the University of Chile in Santiago, Chile. So far I have lived in France, United States, Canada and Chile.

**I love to do research**.
My 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. My 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 H_k) + O(n)\) instead of merely within \(o(n \lg \sigma)\) (ALGO2014); *Succinct Indexes* (TALG2011); and (input order oblivious) *Instance Optimality* in *Computational Geometry* (FOCS2009). Albeit a theoretician by formation, I did implement and experimentally evaluate some of my theoretical results, either in collaboration with students or on my own (*JEA2009*,*WEA2006*). I am interested in other topics of research, in particular in pedagogy.

**I program as a hobby**.
I learned computer programming on my own (in GFA Basic on Atari ST) in 1990 at the age of 14: my first project was a "Tron" game with scrolling windows for four players in text mode. My second project was a program to enter the house expenses with tags, sum them up by categories and print the whole for archives. My last project on this machine was a maze generator and game for the kindergarten where my mother taught: it was used in class during some 6 years after conception. I learned the C Programming Language from Kernighan and Ritchie's book in 1993 when I got to the University: my first programming course was two years later, in Turbo Pascal: I then read a book about it and did my project in Object Turbo Pascal. I learned C++ during my master in 1997 (programming Genetic Algorithms). I learned and taught CAML, OCAML, Java, test-driven development as a Teaching Assistant from 1998 to 2002, and learned shell script, HTML and PHP on my own. I learned Perl during my postdoctoral fellowship at UBC in 2003. I learned Python in 2006 as an assistant professor at the university of Waterloo, and programmed a simulator of intersection algorithms in C++. I learned (and partially taught) agile development between 2010 and 2012 from my students in Software Engineering. I am learning ELISP on my own in 2013 and 2014.

**I love to help people learning**.
I have directed various undergraduate and graduate students, in both theoretical and practical projects, and supervised various initiatives (creation of learner-centered courses, flipped classrooms, organization of programming competitions) in the various institutions where I have worked.
I experiment with new pedagogical techniques as part of my teaching (e.g. organisation of yearly android programming contests, creation of programming Project Oriented courses, usage of concept questions in more traditional courses, course where university students teach deaf high-school students) and designs tools to help instructors to share and evaluate collectively teaching material over time (e.g. database of solved problems, designed in 2006 at the University of Waterloo, still in use in 2012), and between institutions (https://github.com/jyby/repositorium/).

**I love to learn and to create**.
I speak native French, I am fluent in English and in Spanish, and I have studied (at the beginner's levels) various other languages for fun (e.g. Russian, Romanian, Farsi, Sara, etc…).
I practice sport, regularly learning new ones (e.g. running, hashing, biking, swimming, roller blading, traditional stilts, power bocks, unicycling, juggling and occasionally blowing fire).
I play and compose music (e.g. clarinette, xaphoon, bandoneon, piano, bombarde, percussions, ukulele, etc… ).
I make some craft (drawing, etching glasses and copper, pyro-etcthing wood, paiting clothes, etc… ).
I make some good (and artistic) cooking, with a preference for desserts.
I love to travel and to take pictures of the people I see there, more than the places themselves.