# Jérémy Barbay

## 1 Info

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. My main research is about the analysis of algorithms and data-structures on finer classes of instances than those merely defined by their size: this is known as "Adaptive (analysis of) Algorithms (and Data Structures)". I am interested in other topics of research, in particular in applying information technologies to the education of humans (https://repositorium.cl) and other animals than humans (INteracciones Computacionales con Animales (InCA)). Contact me directly at jeremy@barbay.cl, or via my secretary Francia Ormeño by phone +56-2-2978-4365 (time zone CLT, Chile Standard Time, which is between GMT-4 and GMT-6 depending on the season).

Navigation: n/p: next and previous pages, m: single long page, i: table of content, ?: for a list of other commands.

## 3 Research

My main area of expertise is in Theoretical Computer Science (TCS), where I specialize in the analysis of algorithms and data-structures on finer classes of instances than those merely defined by their size: this is known as "Adaptive (analysis of) Algorithms (and Data Structures)". I am interested in other topics of research, in particular in applying information technologies to the education of humans through Learning Management Systems (LMS) and other animals than humans in Animal Computer Interaction (ACI).

### 3.1 Theoretical Computer Science (TCS)

In the area of Theoretical Computer Science (TCS), 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.

### 3.2 Learning Management Systems (LMS)

In the area of Learning Management Systems (LMS), I created in 2009 the project https://teachingislearning.cl, where students create and evaluate educational material for other students; and in 2017 the project https://repositorium.cl, where computer science students develop education supporting software (e.g. Easy Program Checking, Easy Quiz, Easy Plan, Easy Oral Exam, Easy Written Exam, Easy Flip, etc.) based on the paradigms of

Some projects combine various paradigms at once!

### 3.3 Animal Computer Interaction (ACI)

In the area of Animal Computer Interaction (ACI), I created in 2021 the project INteracciones Computacionales con Animales (InCA), where computer science students develop applications for non human animals in digital devices, in collaboration with researchers in ACI, so that to 1) support the study of sensory and cognitive capacities of non human animals (always in a way which respects the wellness of the subject); and/or 2) supporting human guardians to entertain, stimulate, train or teach to its non human protegees.

## 4 Publications

I like to write, but I do not like to interact with the academic publishing system. See Google Scholar for a list of publications and statistics, dblp for some other statitics and Arxiv for some drafts. You might find a pdf copy of an article in my publications folder.

## 5 Courses

Ever since my doctorate I have been creating new teaching material and tools, and researching new educational techniques. Currently, I am teaching three courses:

• CC1002, an introduction to programming, using Python;
• CC3001, an introduction to Theoretical Computer Science;

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

## 6 Supervision

I like to work with students on topics where I bring the techniques (typically adaptive analysis in TCS and crowd sourcing in LMS) and they (or a co-advisor) bring the problems from a field I am not familiar with. 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 have a weekly meeting time 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.

## 7 Experience

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

## 8 Vita

I was born in France, I worked 6 years in Canada, I currently live in Chile. I studied Mathematics, I established some expertise in Theoretical Computer Science (analyzing algorithms and data structures beyond their worst case complexity), and have been lately working on designing and studying new ways to learn and to guide learning, of both humans and non-humans: https://teachingislearning.cl (students create and evaluate educational material for other students); https://repositorium.cl (where various tools assists learning guides to design, share and reuse educational material); https://incalab.cl (where computer science students program computer interfaces for Other Animals Than Humans (OATHs)).

I live with Lorenzo and Tina, two monk parakeets, and help taking care of various dogs at a neighboring houses. We have learned various things from each other. I cook in solar ovens and grow my own vegetables. I am trying to learn how to build energy-efficient "rocket" wood stoves and houses in preparation for a sudden energy transition. I would like to (teach myself how to) design, build and study permanent cultures, including the culture of Other Animals Than Human (OATHs) in such designs.

I list below some alternate, older "vita", some redacted in the 1st person and some in the 3rd person: chairs might find those of use to introduce me when I am to give a presentation.

### 8.1 Short vita, 1st person

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 University of Orsay. I was a posdoctoral fellow at 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 currently an assistant professor at the department of Computer Science of the University of Chile in Santiago, Chile.

My main research is about the analysis of algorithms and data-structures on finer classes of instances than those merely defined by their size: this is known as "Adaptive (analysis of) Algorithms (and Data Structures)". I am interested in other topics of research, in particular in applying information technologies to the education of humans (https://teachingislearning.cl) and of Other Animals Than Humans (https://incalab.cl).

### 8.2 Short vita, 3rd person

Jérémy was born in France, in June 1976. He 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 University of Orsay. He was a posdoctoral fellow at 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 currently 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: this is known as "Adaptive (analysis of) Algorithms (and Data Structures)". He is interested in other topics of research, in particular in applying information technologies to the education of humans (https://teachingislearning.cl) and of Other Animals Than Humans (https://incalab.cl).

### 8.3 Medium long, 1st person

I was born in France, worked in Canada, live in Chile. I loved programming as a kid, but was advised as an undergraduate student to study mathematics instead, which I did (learning to program on my own). During my Magister thesis, I worked on the capacity of genetic algorithms to adapt to a changing environment [Machine Learning]. During my PhD thesis, I worked on the Discrete Bak Sneppen model, a model of the coevolution of species [Mathematical Modeling], and on the formal analysis of adaptive intersection algorithms, which run faster on "easier" instances [Algorithm Design and Analysis]. I went on to work on analizing algorithms beyond their worst case, up to optimality ratios and instance optimality. I am also developping some projects in Animal Computer Interaction (ACI).

The main reason to stay in academia is my interest in designing, implementing and studying new ways to learn and to guide learning, of both humans and non-humans. I created in 2009 the project https://teachingislearning.cl, where students create and evaluate educational material for other students; in 2017 the project https://repositorium.cl, where various tools assists learning guides to design, share and reuse educational material for students; and in 2021 the project https://incalab.cl, where computer science students program computer interfaces for non human animals, to be evaluated and used by researchers in Animal Computer Interactions to validate hypothesis about non human sensory and cognitive abilities.

I live with Lorenzo and Tina, two monk parakeets, and help taking care of various dogs at a neighboring houses: we have learned various things from each other. I cook in solar ovens and grow my own vegetables. I am trying to learn how to build energy-efficient "rocket" wood stoves and houses. I would like to (teach myself how to) design, build and study permanent cultures, including the culture of non human animals in such designs.

### 8.4 (Way too) Long, 1st person

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,JACM2017]. 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 [WEA2006,JEA2009]. I am interested in other topics of research (e.g. Models about evolution [MASTER1998,SODA2000], etc.), and in particular in applying information technologies to the education of humans (https://repositorium.cl) and other animals than humans (https://incalab.cl).

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 an accounting program to enter the house expenses with tags, sum them up by categories and print the whole for archives (basically, a crude version of gnumeric, even programming my own menus, ignoring the existence of graphic libraries). 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 and studying how they can adapt to even changing fitness functions). 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 programmed then Moulinette to automatically test, evaluate and rank my student's projects by the number of comparisons that they performed . 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 learned ELISP on my own in 2013 and 2014 and some Quantum Computing in 2017 and 2020. In 2021, I am learning how to use the Svelte framework combining javascript with css and html, with some server-side php, to make Animal Computer Interaction (ACI) applications. In 2022, I am learning how to connect to Firebase database from Google from a Svelte application, in order to centralize the login and application logs in a non relational database.

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, Online Flipped Classroom) 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://repositorium.cl/).

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, Mandarin etc…). I practice sport, regularly learning new ones (e.g. slack lining, 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, painting 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. I rescued two lovebird parrots in 2016, and have adopted various monk parakeets since 2017, experimenting on Memory Models for birds while teaching them some tricks, as an introduction to the field of Animal Computer Interaction (ACI).