Bernardo Subercaseaux (he/him/his)

Office: 7115 GHC

📍 Pittsburgh, PA

Download my resume

google scholar, dblp

I’m a first year CS PhD student at Carnegie Mellon University, where I am co-advised by Anupam Gupta and Marijn Heule. Before that, I had the fortune of doing my masters under the greats Pablo Barceló and Jorge Pérez, on theoretical aspects of interpretability in Machine Learning. Even before that, I got engineering degrees from CentraleSupélec (École Centrale Paris) , and University of Chile.

Research: At a very high level, I want to understand more about the limits of formal systems, or in other words, what can and cannot be done by a computer. As a consequence, I am interested both in upper and lower bounds for the complexity of different problems, in different parameterizations that attempt to capture what makes a given problem hard, and in what can be expressed within the limits of simple logical languages. Recently, I have become interested in how automated reasoning can be used to help us deal with these questions as well as with other problems in combinatorics.

More in general, I’m a human being, born and raised in Chile, who is interested in all sorts of things. My academic interests usually revolve around algorithms, complexity and logic. Some of my non-academic interests are non-human animals (monkeys are my faves!), brewing beer, dancing salsa, playing sports, writing poetry or short stories, languages (🇪🇸🇺🇸🇫🇷), and philosophy.


May 1, 2022 In joint work with my great advisor Marijn Heule, we improved the lower bound on the chromatic number of the infinite square lattice to 14. I will be posting an arxiv version soon!
May 1, 2022 Together with Daniel Loksthanov, we showed Wordle to be NP-hard. Our paper was accepted to FUN’2022, and an arxiv version can be found here.
Nov 29, 2021 My master thesis “Model Interpretability through the Lens of Computational Complexity” was selected as the best master thesis in Latin America related to artificial intelligence. Check it out here or here.
Sep 28, 2021 Our paper “Foundations of Symbolic Languages for Model Interpretability” got accepted as spotlight for NeurIPS 2021. Check it out here.

selected publications

  1. Model Interpretability through the lens of Computational Complexity
    Barceló, Pablo, Monet, Mikaël, Pérez, Jorge, and Subercaseaux, Bernardo
    In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual 2020
  2. On the Expressiveness of LARA: A Unified Language for Linear and Relational Algebra
    Barceló, Pablo, Higuera, Nelson, Pérez, Jorge, and Subercaseaux, Bernardo
    In 23rd International Conference on Database Theory, ICDT 2020, March 30-April 2, 2020, Copenhagen, Denmark 2020
  3. The Computational Complexity of Evil Hangman
    Barbay, Jérémy, and Subercaseaux, Bernardo
    In 10th International Conference on Fun with Algorithms, FUN 2021, May 30 to June 1, 2021, Favignana Island, Sicily, Italy 2021
  4. Foundations of Symbolic Languages for Model Interpretability
    Arenas, Marcelo, Baez, Daniel, Barceló, Pablo, Pérez, Jorge, and Subercaseaux, Bernardo
    Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021 2021
  5. Wordle is NP-hard
    Lokshtanov, Daniel, and Subercaseaux, Bernardo
    Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021 2022