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.

• 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
  Beauchef 851,
  C.P. 8370459 Santiago, Chile
      

• Phone coordinates: (GMT-3 Oct-Feb, GMT-4 Mar-Sep)
  • Secretary (Francia Ormena): 56-2-2978-4365
    • She can redirect you to my office in case of emergency.
    • If there is no emergency, I prefer you to email me.
  • Communication (Ana Martinez): 56-2-2978 0657
  • Direccion (Magna Bornand): 56-2-2978-0652
  • Fax: 56-2-2689-5531
• email: mailto:[email protected]
• web: http://www.dcc.uchile.cl/~jbarbay

In the field of Theoretical Computer Science, I am interested in 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. Albeit a theoretician by formation, I do implement and evaluate experimentally some of my theoretical results, either in collaboration with students or by myself.

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. Whereas the concepts of adaptive algorithms, parameterized complexity and compressed data structure were defined well before me, I was able to clarify their relations and introduced new useful concepts.

See my (partial) research notes for more details.

Not completely correlated with Google Scholar’s selection, I believe that my five most impacting publications are the following:

1. In the article ”Efficient Fully Compressed Sequence Representations” ALGO2014, in collaboration with Francisco Claude, Travis Gagie, Gonzalo Navarro and Yakov Nekrich, we introduced the first Compressed Index achieving space within o(n H_k) + O(n) instead of merely within o(n lg σ): previous indices were using space within o(n lg σ) which was sometime dominating the n H_k bits used to encoded the compressed data.
2. In the article ”On Compressing Permutations And Adaptive Sorting” TCS2013, in collaboration with Gonzalo Navarro, we connected formally the concepts of compression (of permutations) and adaptive algorithms (for sorting) in the comparison model, by showing that for various adaptive sorting algorithm (in the comparison model), there is a compressed data structure for permutations which supports the operators applying this permutation and its inverse in less time than required to decomporess the permutation.
3. In the article ”Compact Binary Relation Representations With Rich Functionality” IC2013, in collaboration with Francisco Claude and Gonzalo Navarro, we unified the various Compressed Data Structures for Binary Relations previously known in a single common theoretical interface, and explored in practice various implementation alternatives.
4. In the article ”Succinct Indexes For Strings And Binary Relations” TALG2011, in collaboration with Meng He, Ian J. Munro, and Srinivasa Rao, we introduced formally the concept of Succinct Indexes: some succinct data structures previously introduced were indexes without claiming it, nor the advantages of indexes such as their modularity (two succinct indexes supporting distinct operators can be combined into a single succinct index which supports the union of their operator sets, which is not necessarily true of two succinct data structures) or their applications to generate compressed data structures.
5. In the article ”Instance Optimal Geometric Algorithms” FOCS2009, in collaboration with Peyman Afshani and Timothy Chan, we gave the first applications of (input order oblivious) Instance Optimality to Computational Geometry, a fundamental result which generalize to many other problems in computational geometry. (The concept of Instance Optimality had been previously introduced by Fagin et al. on queries to databases.)

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 some statistics on my publications, dblp for some other lists of my publications and Arxiv for some drafts.

Ever since my doctorate I have been creating new teaching material and tools, and researching new educational techniques. The reaction from students to such innovations is sometime confrontational (e.g. because it does not follow the pattern to which they are accustomed, and requires more independent work than usual) but most often enthusiastic (e.g. about the increased creativity and interactivity). The course designs of which I am the most proud are the following:

1. 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 where each student reads 8 research articles superficially; studies, presents and summarizes one small set of articles; and either works on a mini research theme or develops some mini graphical pedagogical material, and evaluates and criticizes the work of other students. It mostly features advanced variants of algorithms well known to undergraduate, in order to force them to 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 say in the anonymous teaching evaluation that this course is more work than other courses, but that they still liked it a lot.
2. 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.
3. 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 calendar of courses I taught in the past.

I like a lot working with students (even when I am not directing them), and I am thoroughly reviewing the thesis that are assigned to me as a referee (some say I am picky), which I duly annotate in various colors using Xournal on a Tablet PC. 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 Delaunay Triangulations, taking advantage of the order of the input (I proved in the past [FOCS2009] that adaptive computation independent of the input order was impossible in 2 or 3 dimensions); on the implied compressed data structure for this triangulation; and on engineering another adaptive algorithm for merging Delaunay triangulations (cosupervision with Pablo Pérez-Lantero).

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. He is focusing first on engineering algorithms which take advantage of the degeneracy of the input, something which was not done before in computational geometry, and then on finer measures of adaptivity (cosupervision with Pablo Pérez-Lantero).

I like to work with students on topics where I bring the techniques (typically, adaptive analysis or compressed data structures) 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 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.

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

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

• I direct the project Fondecyt Regular 1120054 “Compressed Data Structures and Compressability Measures”, funded by Conicyt. This finances my research on compressed data structures, by paying for my equipment, my travels and my students.
• I participate in the project Millenium Nucleus ICM/FIC P10-024F, funded by Conicyt. This is a group project on the processing of network data, and massive data sets in particular. It finances our seminars, summer and winter schools, and some outreach activites in which I participate.
• I dispose of a Fundo de Incentivo a la Investigación (FII) from the Department of Computer Science (DCC). I use it to pay undergraduate students, furniture and exploratory research not covered by the other projects.
• I manage a Fundo de Visitas a la Investigación (FVI) from the Department of Computer Science (DCC), which subventions 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, and in particular for a list of publications acknowledging each source of funding.

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; 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, or
  • teaching courses at a summer school for high school teachers;
• in the field of Pedagogy I
  • co-organized some events (ALE2011, Mecesup 2011), and
  • served as a referee for research articles, engineering thesis; and
• 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.

I hold the following diploma and positions:

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. 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.

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 σ) (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 love to help people to learn. 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. 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, such as Russian, Romanian and Farsi. I practice sport, regularly learning new ones (e.g. running, biking, swimming, roller blading, stilts, unicycling, juggling and occasionally blowing fire). 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, sum them up and print the whole in a achivable form. My last project on this machine was a maze generator and game for the kindergarten where my mother taught: it was used in class for 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 create. I play and compose music (e.g. clarinette, xaphoon, bandoneon, piano,… ). I make some craft (drawing, etching glasses, copper and wood). 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 was kicked out of kindergarten into primary school one year before the normal time because of lack of space, and kept the pace ever since, being usually one to three years younger than my classmates: I was the second youngest alumni to get a PhD from the University of Orsay.