Bio
I am a mathematician working in theoretical computer science. Currently, I am a Senior Research Associate at the University of Oxford, working with Standa Živný on theoretical aspects of the (promise) constraint satisfaction problem within the UKRI - ERC Guarantee grant NAASP. Concurrently, I hold a Junior Research Fellowship at Lady Margaret Hall.
I obtained my PhD from Universitat Pompeu Fabra (Barcelona, ES) under the supervision of Victor Dalmau within the Artificial Intelligence and Machine Learning research group. I defended my doctoral thesis in October 2022 and obtained the highest classification of Excellent Cum Laude. You can find my thesis here and my presentation here. As part of my PhD I spent three months as a visiting researcher at the Department of Algebra of Charles University (Prague, CZ), working with Libor Barto.
Previously, I obtained an MSc in Mathematics and Foundations of Computer Science (MFoCS) from the University of Oxford (2018) and a BSc in Mathematics from University College London (2017).
When I'm not doing maths, you can probably find me dancing salsa, playing beach volleyball, or hiking. My Erdős Number is 3.
Publications and pre-prints
L. Barto, S. Butti and V. Dalmau, The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems, submitted, 2024. [PDF]
L. Barto, S. Butti, A. Kazda, C. Viola and S. Živný, Algebraic Approach to Approximation, to appear in 39th Symposium on Logic in Computer Science, 2024. [PDF][DOI]
K. Asimi, L. Barto and S. Butti, Fixed-Template Promise Model Checking Problems, 28th International Conference on Principles and Practice of Constraint Programming, 2022. [PDF] [DOI]
L. Barto and S. Butti, Weisfeiler-Leman Invariant Promise Valued CSPs, 28th International Conference on Principles and Practice of Constraint Programming, 2022. [PDF] [DOI]
S. Butti and V. Dalmau, Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem, 46th International Symposium on Mathematical Foundations of Computer Science, 2021. [PDF] [DOI]
S. Butti and V. Dalmau, The Complexity of the Distributed Constraint Satisfaction Problem, Theory of Computing Systems (STACS special issue) [PDF] [DOI]
An extended abstract appeared in 38th International Symposium on Theoretical Aspects of Computer Science, 2021. [PDF] [DOI]
S. Butti and V. Dalmau, Stochastic Local Search Algorithms for Constraint Satisfaction, 26th International Conference on Principles and Practice of Constraint Programming Doctoral Program, 2020. [PDF]
S. Butti and S. Živný, Sparsification of Binary CSPs, SIAM Journal on Discrete Mathematics, 34(1), 825-842, 2020. [PDF] [DOI]
An extended abstract appeared in 36th International Symposium on Theoretical Aspects of Computer Science, 2019. [PDF] [DOI]
Theses
S. Butti, Symmetries in Constraint Satisfaction: Weisfeiler-Leman Invariance and Promise Problems, PhD thesis, Department of Information and Communication Technologies, Universitat Pompeu Fabra, 2022. [PDF]
S. Butti, On the Sparsifiability of Valued Constraint Satisfaction Problems, MSc thesis, Mathematical Institute, University of Oxford, 2018. [PDF]
Selected Academic talks ( ! denotes invited talks)
Algebraic Approach to Approximation, LICS2024, Tallinn, July 2024. [slides]
Promise Valued CSPs: an algebraic framework for approximation problems
Algorithms and Complexity Theory seminar, Oxford, November 2023.
ACiD: Algorithms and Complexity in Durham seminar, Durham, November 2023.
Combinatorial Problems in Model Theory and Computer Science, Leeds, November 2023. [slides] !
CWC2023, Weissensee, September 2023. !
Siena Algebra Week, Siena, July 2023. [slides] !
Constraint Satisfaction Problems: when complexity meets algebra, Oxbridge Women in Computer Science Conference, Cambridge, April 2023. [slides]
Weisfeiler-Leman Invariant Promise Valued CSPs, CP2022 (part of FLoC2022), Haifa, August 2022. [slides]
Fixed-Template Promise Model Checking Problems, WiL2022 (part of FLoC2022), Haifa, July 2022. [slides]
Sherali-Adams meets Weisfeiler-Leman on (Promise Valued) CSPs
Dagstuhl seminar 22201 The CSP: Complexity and Approximability, Schloss Dagstuhl, May 2022. [slides] !
CWC2021, Kranjska Gora, September 2021. !
Fractional homomorphism, WL invariance, and the SA hierarchy for the CSP, MFCS2021, Tallinn, August 2021. [slides]
The Complexity of the Distributed Constraint Satisfaction Problem
Stochastic Local Search Algorithms for Constraint Satisfaction, CP2020 Doctoral Program, Online, September 2020. [video] [slides]
Sparsification of Binary CSPs, STACS2019, Berlin, March 2019. [slides]
Deep Learning Versus Boltzmann Machines, 3rd Winter Symposium of the SEMF, Valencia, December 2018. [slides]
How do Numbers Shape our Lives?, Lincoln Leads Seminar Series, Oxford, January 2018. [slides]
Other conference participations and research visits
Dagstuhl seminar 25211 The CSP: Complexity and Approximability, Schloss Dagstuhl, May 2025.
Dagstuhl seminar 25081 Semirings in Databases, Automata, and Logic, Schloss Dagstuhl, February 2025.
12th Logic Mentoring Workshop @CSL2025, Amsterdam, February 2025 (organizer).
CWC2024, Colfosco, September 2024.
Topology, Algebra and Categories in Logic Summer School, Barcelona, June 2024.
Birmingham CSP Meeting 2024, Birmingham, May 2024.
Oxbridge Women in Computer Science Conference, invited panelist, Oxford, May 2024.
Computer Science Postdoctoral Networking Evening, Oxford, May 2024 (organizer).
Cambridge Algorithms and Complexity Workshop, Cambridge, April 2024.
Talking Maths in Public, Newcastle, August 2023.
Spring School in Theoretical Computer Science: Le Kaléidoscope de la Complexité, Ile d'Oléron, June 2023.
One-Day Meeting in Combinatorics, Oxford, May 2023.
Visiting Libor Barto at Charles University, Prague, April 2023.
CWC2022, Molveno, September 2022 (organizer).
Structure meets Power 2022, Online, June 2022.
Visiting Libor Barto at Charles University, Prague, June-September 2021.
AAA100 - Arbeitstagung Allgemeine Algebra, Online, February 2021.
When deep learning meets logic: a three days virtual workshop on neural-symbolic integration, Online, February 2021.
6th Heidelberg Laureate Forum, Heidelberg, September 2018.
Teaching
University of Oxford
Combinatorial Optimization (2024)
Computational Complexity (2024)
Probability and Computing (2023)
UPF, Barcelona
Discrete Mathematics (2019-2022)
Outreach
I have collaborated with a number of excellent outreach initiatives, including:
Funding
I am currently funded by the UKRI (formerly ERC) grant "New Approaches to Approximability of Satisfiable Problems" (NAASP).
My PhD was jointly supported by the INPhINIT fellowship programme of “la Caixa” foundation, and by the European Union's Horizon 2020 research and innovation programme through the Marie Skłodowska-Curie Action (MSCA) COFUND.