Department of Computer Science Universitat Politècnica de Catalunya [ALBCOM · CS · FIB · UPC]

Students: Learn about the UPC ACM Student Chapter and join!

Conrado Martínez Professor / Catedrático de Universidad ACM Senior Member Address: Campus Nord, Omega-241 Jordi Girona, 1-3 E-08034 Barcelona, Spain Email: {c,C}onrado[.{m,M}artinez]@cs.upc.edu (*) Phone: +34 93 41 37849 Fax: +34 93 41 37833

Google Scholar ResearchGate Researcher ID ORCID

(*) Elements inside braces are choices, e.g., you may use upper- or lowercase in the initials of my name. Elements inside brackets are optional, i.e., you may use my last name or not when writing me. My old email address with subdomain @lsi.upc.{es,edu} will work, but please use the new address @cs.upc.edu instead (and update your address book accordingly).

Research interests & activities

I am member of the Algorithms, Bioinformatics and Complexity Research Group (ALBCOM) of the Dept. of Computer Science (CS). I've participated in many research projects about the design and analysis of algorithms, in some cases as the leading researcher. I'm currently participating in project GRAMM (Graph-based Models and Methods for Computing in the Large), funded by the Spanish Ministry of Economy, Industry and Competitivity, from January 2018 to December 2020.

My current research areas of interest include:

• Analysis of Algorithms and Data Structures.
• Algorithm Science.
• Design of Algorithms and Data Structures.
• Analytic Combinatorics. Discrete Mathematics.

I'm a faculty member of the Barcelona Graduate School of Mathematics (BGSMath) and member of the following academic societies: ACM, SCM and SIAM.

Conference committees and editorial boards

• Latin American Theoretical INformatics Symposium (LATIN ). Member of the Steering Committee since 2020.
• ACM Transactions on Algorithms (TALG). Associate Editor, since 2015.
• Member of the Committee for the Imre Simon Test-of-Time Award.

Past events & committees in which I was involved include:

• International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA). Member of the Steering Committee from 2014 to 2021. Chair of the Steering Committee from 2018 to 2021.
• 14th Latin American Theoretical INformatics Symposium (LATIN 2020). São Paulo, Brasil, May 25-29, 2020 January 5-8, 2021. Member of the PC.
• ACM-SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO). Member of the Steering Committee, from 2010 until 2019. ANALCO 2019 was the last edition, and the SC decided to discontinue this series of meetings.
• 30th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2019). CIRM, Luminy, France, June 24-28, 2019. Member of the scientific committee.
• 43rd Int. Symp. on Mathematical Foundations of Computer Science (MFCS 2018). Liverpool, UK, August 27-31, 2018. Member of the PC.
• 13th Latin American Theoretical INformatics Symposium (LATIN 2018). Buenos Aires, Argentina, April 16-19, 2018. Member of the PC.
• 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA17). Barcelona, Spain, January 16-18, 2017. Chair of the Organizing Committee.
• 14th ACM-SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO17). Barcelona, Spain. January 16, 2017. Co-chair of the PC.
• 13th ACM-SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO16). Arlington, VA, USA, January 11, 2016. Member of the PC.
• 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Orléans, France, February 17-20, 2016. Member of the PC.
• 12th ACM-SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO15). San Diego, USA, January 4, 2015. Member of the PC.
• IX Jornadas de Matemática Discreta y Algorítmica. Tarragona, Spain, July 7-9, 2014. Member of the Scientific Committee.
• 11th Latin American Theoretical Informatics Symposium (LATIN 2014). Montevideo, Uruguay, March 31-April 4, 2014. Member of the PC.
• ALEA Europe 2013, Marseille, France, October 21-25, 2013. Member of the Scientific Committee.
• 24th International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2013). Cala Galdana, Menorca, Spain, May 27-31, 2013. Chair of the Scientific Committee.
• 24th ACM-SIAM Symp. on Discrete Algorithms (SODA 2013). New Orleans, USA, January 6-8, 2013. Member of the PC.
• VIII Jornadas de Matemática Discreta y Algorítmica. Almería, Spain, July 11-13, 2012. Member of the Scientific Committee.
• 10th Latin American Theoretical Informatics Symposium (LATIN 2012). Arequipa, Peru, April 16-20, 2012. Member of the PC.
• Journées ALÉA 2012. CIRM, Marseille, France, March 5-9, 2012. Invited lecturer.
• 9th ACM-SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12). Kyoto, Japan, January 16, 2012. Co-chair of the PC.
• 21st Int. Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA'10). Vienna, Austria, 2010. Member of the PC.
• VII Jornadas de Matemática Discreta y Algorítmica (VII JMDA). Castro Urdiales, Spain, 2010. Member of the PC.
• The Research Program Probabilistic Techniques in Computer Science, from September to December 2009, at the Center for Mathematical Research (CRM) in Bellaterra. Co-director of the Program.
• Sixth ACM-SIAM Workshop on Analytic Algorithms and Combinatorics (ANALCO09). New York, USA, 2009. Co-chair of the PC.
• VI Jornadas de Matemática Discreta y Algorítmica (VI JMDA). Lleida, Spain, 2008. Member of the scientific committee.
• 2008 Int. Conf. on the Analysis of Algorithms (AofA'08). Maresias, Brazil, 2008. Keynote speaker.
• 2007 Int. Conf. on the Analysis of Algorithms (AofA'07, Juan-les-Pins, France). Member of the PC.
• First Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM 2007, Banff, Canada). Co-organizer of the minisymposium on Applications of Discrete Mathematics for the Analysis of Algorithms.
• 4th ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO'07, New Orleans, USA). Member of the PC.
• 2005 International Conference on Analysis of Algorithms (AofA'05). Chair of the Program Committee. Click here to access the on-line proceedings of the Conference, published by Discrete Mathematics & Theoretical Computer Science.

Former PhD students

• Salvador Roura: Divide-and-Conquer Algorithms and Data Structures (1997)
• Amalia Duch: Design and Analysis of Multidimensional Data Structures (2004)
• Xavier Molinero: Ordered Generation of Classes of Combinatorial Structures (2005).
• Ahmed Helmi: The Hiring Problem and its Algorithmic Applications (2013)
• Gustavo Lau: Analysis of Partial Match Queries in Multidimensional Search Trees (2019), co-supervised with Amalia Duch

Click here for a photo of the happy sextet :) (from left to right: X. Molinero, C. Martínez, G. Lau, A. Duch, S. Roura, A. Helmi).

Publications

• A list of references of my publications. Many of them are available in electronic format (click in the [.pdf] or [.ps.gz] links).
• My Doctoral Dissertation, supervised by Dr. R. Cases, Statistics under the BST Model (.pdf, 759 Kb).
• I'm collecting here a few PDF files with some of my last presentations in conferences, seminars, ...

You can also access from here the Technical Reports Archive of the CS Department and the ALCOM-FT Technical Reports Archive.

Besides my PhD students (Salvador Roura, Amalia Duch, Xavier Molinero, Ahmed Helmi and Gustavo Lau), I have coauthored papers with many other good friends around the world: Margaret Archibald, Ricardo Baeza-Yates, Rafel Cases, Hua-Huai 'Felix' Chern, Jean Daligault, Hervé Daudé, Josep Díaz, Vladimir 'Vlad' Estivill-Castro, Maria Inés Fernández-Camacho, Philippe Flajolet, Joaquim Gabarró, 'Jason' Zhicheng Gao, Xavier Gourdon, Hsien-Kuei Hwang, Rosa Maria Jiménez, Peter Kirschenhofer, Guy Louchard, Jérémie Lumbroso, Xavier Messeguer, Lucia Moura, Markus Nebel, Daniel Panario, Alois Panholzer, Helmut Prodinger, Vonjy Rasendrahasina, Vlady Ravelomanana, Bruce Richmond, Uwe Rösler, Brett Stevens, Gabriel Valiente, Alfredo 'Tuba' Viola and Sebastian Wild.

My Erdös number is 2 (via L. B. Richmond > P. Erdös). My Knuth number is also 2 (via Ph. Flajolet > D. E. Knuth). My Flajolet number is 1. My Einstein number is 4 (via several different paths, e.g., J. Díaz > L. H. Harper > E. Gabor Straus > A. Einstein).

If you are curious about your own collaborative distance to other researchers working in Math, Computer Science, Physics or related areas, MathSciNet provides a free tool just for that (they have a huge publication database so it's very likely that it will produce the true value: Collaborative Distance@MathSciNet

Postgraduate Studies

Teaching

I am usually involved in courses at the School of Informatics (FIB), at undergraduate and graduate level. My current teaching activity is concentrated in the following courses:

• Programming II (all materials are in Catalan and/or Spanish)
• Data Structures and Algorithms (most material is in Catalan, but also in English). The following links give access to some additional material, in particular, the slides that I'm using:
  • My slides (in English)
  • Slides by T. Lozano (in Catalan). An English translation (by A. Oliveras) is also available here
  • Slides by G. Valiente (in Catalan)
  • Notes on graphs and exhaustive search by M.T. Abad (in Spanish)
  • Robert Sedgewick and Kevin Wayne's (Princeton) slides for their book Algorithms
  • Kevin Wayne's slides for Jon Kleinberg and Éva Tardos's book Algorithm Design
• Algorithmics
• Advanced Data Structures (Master of Innovation and Research in Informatics)
• Randomized Algorithms (Master of Innovation and Research in Informatics)

Mini-courses & educational talks

• The Barcelona Chapter of Papers We Love kindly invited me to give a talk last February 28th, 2018. Here you can download the slides of the talk that I delivered on randomized data structures.
• In October 2017, I was invited to give a mini-course (3h) in the ALÉA in Europe meeting. My course, Data Stream Analysis: a (New) Triumph for Analytic Combinatorics, was an introduction to the application of Analytic Combinatorics for the design and analysis of data stream algorithms. Click here to download the slides.

Past mini-courses

• In May 2009, I gave the short course (6 hours) Analytic Combinatorics: A Primer at the Fields-MITACS Summer School in Applied Probability (Carleton U., Canada). In April 2011, I gave a longer version of that course at the Facultad de Ingeniería (Universidad de la República, Uruguay). Click the link to download the slides that I've used for the two courses. You can also download the exercices (in Spanish) of the course taught in Uruguay.
• I taught another similar mini-course Applications of Analytic Combinatorics to the Analysis of Algorithms: An Introduction, for the 1st Latin American Theoretical Informatics School, in conjonction with Latin American Theoretical Informatics Symposium (LATIN 2012) in Arequipa, Peru, on April 2012.

Other stuff/Otras cosas

• Few people would pay for using and enjoying their own work. Or not so few? Read what Scott Aaronson wrote in his review of The Access Principle. The initial paragraphs are remarkable, I've found them very funny (better said: ironic).

• El Panfleto Antipedagógico de Ricardo Moreno Castillo, publicado por la editorial Leqtor, denuncia con brillantez la desastrosa situación de la educación en España y sus causas. El panfleto se centra en la enseñanza secundaria, pero muchos de los síntomas del deficiente sistema educativo y de sus causas también se dan en otros niveles, incluído el universitario. No coincido con todas las opiniones del profesor Moreno, pero sí con la inmensa mayoría y desde luego estoy de acuerdo con él en la esencia. Si eres profesor y dispones de un rato no dejes de leer el panfleto. Se lee con rapidez y satisfacción. Satisfacción por la bien expuesta y lúcida argumentación, no porque el tema tratado la produzca. En el enlace de arriba puedes acceder a la versión abreviada y de libre acceso, que durante bastante tiempo ha circulado en Internet, previamente a la publicación del libro del mismo título.

• Otro interesante documento, que el profesor Moreno Castillo ha llamado a mi atención, es La influencia de la nueva pedagogía en la educación: el ejemplo de Suecia, escrito por Inger Enkvist, de la Universidad de Lund. Aunque se describe el caso particular de Suecia, hay muchos elementos comunes con los sistemas educativos de otros países de Europa, incluyendo a España.

• Aquí puedes encontrar otro artículo más escrito por el profesor Moreno Castillo. Con el provocador título Es la pedagogía una ciencia?, fue publicado en el número 11 del Foro de Educación.

  Tanto Foro de Educación como la revista Mercurio recogen opiniones muy interesantes (y otras no tanto, por supuesto!) en sus páginas acerca de temas relacionados con la Educación.

• Tampoco tiene desperdicio el artículo Analfabetos Funcionales Titulados de Gonzalo Guijarro, profesor de secundaria y portavoz de la Asociación de Profesores de Instituto de Andalucía (APIA).

• Plastilina en la universidad es el título del artículo firmado por Francesc de Carreras, catedrático de Derecho Constitucional de la UAB, y publicado el 29 de mayo de 2008 en La Vanguardia.

  Hay mucho en lo que estoy de acuerdo con De Carreras. Aunque un factor que parece no tener en cuenta el profesor De Carreras en su análisis es el desproporcionado número de estudiantes universitarios. El problema no es sólamente que los estudiantes reciban una formación inadecuada. Es que hay estudiantes en la Universidad que no deberían estar en ella. Estos estudiantes están desperdiciando unos años muy valiosos de su vida y unos recursos públicos no menos valiosos en hacer algo que ni les interesa ni para lo cual están bien capacitados. Y dejan al margen otras vías que les pueden interesar y para las cuales sí tienen buenas cualidades. El artículo parece olvidar que en este país (y no es el único) hay mucha titulitis.

• Concurs de Programació de la UPC.