Murilo Santos de Lima
Ph.D., Computer Science, IC-Unicamp, 2018
M.S., Computer Science, IME-USP, 2011
B.S., Computer Science, UFBA, 2008
B.A., Popular Music, IA-Unicamp, 2015
E-mail: mslima at ic dot unicamp dot br
- Optimization under uncertainty: online algorithms, robust / stochastic optimization etc
- Approximation algorithms
- Distributed algorithms
- Combinatorial optimization
- 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)
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. To appear in Algorithmica, 2022.
Manuscript available at arXiv.org, 2101.05032. (pdf)
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)
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.
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)
- 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)
- 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.
This paper received an honorable mention as one of the three best papers of the event.
(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)
- 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)
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)
- 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.
- 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,
- Sync-groups, with Guillaume Barreau, Rodrigo Rocha Gomes e Souza. A system for
automatic user management. Graco-DCC-UFBA, 2005.
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
Here are some of my compositions (all licensed in Creative Commons BY-NC-ND 3.0):
my senior recital, which is entitled Primal-Dual (concept in pdf / videos on YouTube).
Here are some transcriptions I've made (I do not own credit for any of the compositions,
- 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)
and the transcriptions are licensed in Creative Commons BY-NC 3.0 for educational purposes):
My solo indie project can be found at Bandcamp. (It also has a Facebook page.) I define it
You can check my music preferences at last.fm.
I do love Wilco and bears.
as "glam jazzy psychedelic alt-country", and I write music, lyrics, I sing and play all
instruments, plus I do editing & some mixing.