Murilo Santos de Lima

Research Interests:

• Optimization under uncertainty: online algorithms, robust / stochastic optimization etc
• Approximation algorithms
• Distributed algorithms
• Combinatorial optimization

Publications:

• Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty.
  (full paper) with Thomas Erlebach, Nicole Megow, Jens Schlöter. In ESA 2022: 30th
  Annual European Symposium on Algorithms, Potsdam, Germany, 9/5-7/2022. Volume
  244 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 49:1-49:18. (pdf)
  DOI: 10.4230/LIPIcs.ESA.2022.49
  Extended version as technical report arXiv.org, 2206.15201. (pdf)
• Round-Competitive Algorithms for Uncertainty Problems with Parallel Queries.
  (full paper) with Thomas Erlebach, Micheal Hoffmann. Algorithmica, 2022. (pdf)
  DOI: 10.1007/s00453-022-01035-6
  A preliminary version appeared in STACS 2021: 38th International Symposium on
  Theoretical Aspects of Computer Science, Saarbrücken, Germany (online event),
  3/16-19/2021. Volume 187 of Leibniz International Proceedings in Informatics (LIPIcs),
  pp. 27:1-27:18. (pdf) DOI: 10.4230/LIPIcs.STACS.2021.27
• Orienting (hyper)graphs under explorable stochastic uncertainty. (full paper)
  with Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Nicole Megow,
  Jens Schlöter. In ESA 2021: 29th Annual European Symposium on Algorithms,
  Lisbon, Portugal (online event), 9/6-8/2021. Volume 204 of Leibniz International
  Proceedings in Informatics (LIPIcs), pp. 10:1-10:18. (pdf)
  DOI: 10.4230/LIPIcs.ESA.2021.10
  Extended version as technical report arXiv.org, 2107.00572. (pdf)
• Learning-Augmented Query Policies. (full paper)
  with Thomas Erlebach, Nicole Megow, Jens Schlöter.
  Technical report arXiv.org, 2011.07385, 2021. (pdf)
• Query Minimization under Stochastic Uncertainty. (full paper) with Steven
  Chaplick, Magnús M. Halldórsson, Tigran Tonoyan. Theoretical Computer Science,
  895:75-95, 2021. DOI: 10.1016/j.tcs.2021.09.032
  Manuscript available at arXiv.org, 2010.03517. (pdf)
  A preliminary version appeared in LATIN 2020: 14th Latin American Theoretical
  Informatics Symposium, São Paulo, Brazil (online event), 1/5-8/2021. Volume 12118
  of Lecture Notes in Computer Science (LNCS), pp. 181-193, 2020.
  DOI: 10.1007/978-3-030-61792-9_15 (manuscript pdf)
• Query-Competitive Sorting With Uncertainty. (full paper) with Magnús M.
  Halldórsson. Theoretical Computer Science, 867:50-67, 2021.
  DOI: 10.1016/j.tcs.2021.03.021
  Manuscript available at arXiv.org, 2012.09475. (pdf)
  A preliminary version appeared in MFCS 2019: 44th International Symposium on
  Mathematical Foundations of Computer Science, Aachen, Germany, 8/26-30/2019.
  Volume 138 of Leibniz International Proceedings in Informatics (LIPIcs),
  pp. 7:1-7:15. DOI: 10.4230/LIPIcs.MFCS.2019.7 (pdf)
• Group Parking Permit Problems. (full paper) with Mário César San Felice,
  Orlando Lee. Discrete Applied Mathematics, 281:172-194, 2020. (manuscript pdf)
  DOI: 10.1016/j.dam.2019.05.013
• Graph Theory Exercises, translation of the book by Paulo Feofiloff, 2019.
• Parking Permit and Network Leasing Problems.
  Ph.D. thesis (supervisors: Orlando Lee, Mário César San Felice).
  IC-Unicamp, Campinas - SP, Brazil, 05/2018. (pdf)
• On Generalizations of the Parking Permit Problem and Network Leasing
  Problems. (extended abstract) with Mário César San Felice, Orlando Lee.
  In: LAGOS 2017: IX Latin and American Algorithms, Graphs, and Optimization
  Symposium, Marseille, France, 9/11-15/2017. Volume 62 of Electronic Notes in
  Discrete Mathematics, pp. 225-230. (manuscript pdf)
  DOI: 10.1016/j.endm.2017.10.039
• Connected facility leasing problems. (full paper) with Mário César San Felice,
  Orlando Lee. In: ICTCS 2017: 18th Italian Conference on Theoretical Computer
  Science, Naples, Italy, 9/26-28/2017, pp. 162-173. (pdf)
• Facility Leasing with Penalties. (short paper) with Mário César San Felice,
  Orlando Lee. In: ETC 2017: II Encontro de Teoria da Computação, with CSBC 2017:
  XXXVII Congresso da Sociedade Brasileira de Computação, pp. 27-30, São Paulo,
  Brazil, 7/2-6/2017. (pdf)
  Also as technical report arXiv.org, 1610.00575. (pdf)
• Online Network Leasing Problems. (poster) with Mário César San Felice,
  Orlando Lee. In: São Paulo School of Advanced Science on Algorithms, Combinatorics
  and Optimization, São Paulo, Brazil, 7/18-29/2016. (pdf)
• On a Leasing Variant of the Online Connected Facility Location Problem.
  (short paper) with Mário César San Felice, Orlando Lee. In: ETC 2016: I Encontro
  de Teoria da Computação, with CSBC 2016: XXXVI Congresso da Sociedade
  Brasileira de Computação, pp. 836-839, Porto Alegre, Brazil, 7/4-7/2016. (pdf)
This paper received an honorable mention as one of the three best papers of the event.
• A Time-Free Byzantine Failure Detector for Dynamic Networks. (full paper)
  with Fabíola Greve, Luciana Arantes, Pierre Sens. In: EDCC'12: Ninth European
  Dependable Computing Conference, pp. 191-202, Sibiu, Romania, 2012. (pdf)
  DOI: 10.1109/EDCC.2012.28
  Also as INRIA Research Report No 7222 (Byzantine Failure Detection for Dynamic
  Distributed Systems) (pdf)
• Aproximação de métricas finitas por métricas arbóreas e aplicações.
  Master's thesis (supervisor: Cristina Gomes Fernandes).
  IME-USP, São Paulo, Brazil, 12/2011. (pdf with hyperlinks / pdf for printing)
• The Time-Free Approach to Byzantine Failure Detection in Dynamic
  Networks. (full paper) with Fabíola Greve, Luciana Arantes, Pierre Sens.
  In: WRAITS 2011: 5th Workshop on Recent Advances on Intrusion-Tolerant
  Systems, with DSN'2011: The 41th IEEE/IFIP International Conference on
  Dependable Systems and Networks, pp. 1-6, Hong Kong, China, 2011. (pdf)
  DOI: 10.1109/DSNW.2011.5958855
• Detectando Falhas Bizantinas em Sistemas Distribuídos Dinâmicos,
  (full paper) with Fabíola Greve. RB-RESD - Revista Brasileira de Redes
  de Computadores e Sistemas Distribuídos, 2(1):9-21, 2009. (pdf)
  Note: this paper is an extedend version (with full proofs) for the paper published on SBRC 2009.
  Also as Technical Report DCC 06.09 UFBA (in English, Byzantine Failure
  Detection for Dynamic Distributed Systems) (pdf)
• Protocolo Assíncrono para Detecção de Falhas Bizantinas em Sistemas
  Distribuídos Dinâmicos, (full paper) with Fabíola Greve. In SBRC'09: Anais do
  XXVII Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos,
  pp. 887-900, Recife, Brazil, 05/25-29/2009. (pdf)
  Also as Technical Report DCC-UFBA 12-2008 (pdf)
• Protocolo Assíncrono para Detecção de Falhas Bizantinas em Sistemas
  Distribuídos Dinâmicos. Undergraduate thesis (supervisor: Fabíola Greve).
  DCC-UFBA, Salvador, Brazil, 07/2008. (pdf)
• Classificação de Impressões Digitais via Análise de Pontos Singulares.
  (short paper) with Perfilino Eugênio Ferreria Jr. In WUW-SIBGRAPI'07:
  Proceedings of the Workshop of Undergraduate Work, XX Brazilian Symposium
  on Computer Graphics and Image Processing, Belo Horizonte, Brazil, 10/7-10/2007. (pdf)
• Processamento de Imagens Biométricas. (abstract) with Perfilino Eugênio
  Ferreira Júnior. In VIII Seminário de Pesquisa e Pós-Graduação (Universidade Federal da
  Bahia), XXVI Seminário Estudantil de Pesquisa, Salvador, Brazil, 11/7-9/2007.

Software:

• rplac - Ruby Point Location Algorithm Comparator, with Joel Uchoa. This is a
  software for visualizing and comparing point location algorithms, as a project for the
  course MAC5747 - Computational Geometry, DCC-IME-USP, 2009.
• Gaudi-AFIS, a prototype for a fingerprint identification system,
  Gaudi-DCC-UFBA/FAPESB, 2007.
• Sync-groups, with Guillaume Barreau, Rodrigo Rocha Gomes e Souza. A system for
  automatic user management. Graco-DCC-UFBA, 2005.

Music:

I also have a B.A. in Popular Music (which is about jazz & Brazilian music, not Madonna,
unfortunately), from IA-Unicamp. I play the bass (both bass guitar and double bass), I compose
some stuff and I also enjoy producing my own indie songs. I try to play some piano and
drums as well.

My bass professor at Unicamp was Zé Alexandre Carvalho. He was also the supervisor for
my senior recital, which is entitled Primal-Dual (concept in pdf / videos on YouTube).

• Mutação, for solo double bass. This piece uses a composition process which is based
  on I Ching (the Chinese divination system). Supervisor: José Augusto Mannis. (pdf)
• piano forte, for piano. (I consider this to be my best composition, technically speaking.)
  Supervisor: José Augusto Mannis. (pdf / audio soon)
• variação sobre 8 cordas, a double bass duet. This piece is based on Anton Webern's
  Variationen, Op. 27. (One might have a lot of fun playing this with a friend.)
  Supervisor: José Augusto Mannis. (pdf / video)
• Mother Mary, a theme and variations for piano and computer. (The last variation is
  one of my favorite works.) This is deticated to my mother, Maria.
  Supervisor: Denise Garcia. (pdf / audio)
• Traduzir-se, a song for mezzo-soprano and piano. Lyrics are extracted from a poem
  by Ferreira Gullar (which I do not own). This was composed to be sung by my friend
  Maria Cordélia. Supervisor: Denise Garcia. (pdf)
• Boteco, an electroacoustic sound narrative. The jazz piece is from "Beard" by Blur
  (which I do not own), and other samples are from freesound.org.
  Supervisor: Nelson Pinton. (audio)

• Conference of the Birds, by Dave Holland (woof!) (whole double bass line & solo - pdf)
• You Make Me So Happy, by Miroslav Vitous (lead sheet - C pdf / Bb soprano sax pdf)
  (chord changes were given by Prof. Paulo Tiné during the course MP430 - Harmony IV, 2013)
• Pyramid Song, by Radiohead (chord changes & piano - pdf)
• A Wolf at the Door, by Radiohead (chord changes & main riff - pdf)
• Apostolic, by Loose Fur (chord changes & some riffs - pdf)
• Side with the Seeds, by Wilco (chord changes - pdf)

My solo indie project can be found at Bandcamp. (It also has a Facebook page.) I define it
as "glam jazzy psychedelic alt-country", and I write music, lyrics, I sing and play all
instruments, plus I do editing & some mixing.

Etc:

• My Twitter
• An abandoned music blog attempt, about 90's indie
• My projects at Gaudi group, DCC-UFBA
• My personal page on DCC-UFBA's wiki