Publications

Publications and pre-prints

• The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems
  L. Barto, S. Butti and V. Dalmau
  ACM Transactions on Computation Theory, 2026 PDF DOI
• Optimal Inapproximability of Promise Equations over Finite Groups
  S. Butti, A. Larrauri and S. Živný
  Submitted, 2025 PDF
  An extended abstract appeared in ICALP2025 DOI
• The Rise of Plurimorphisms: Algebraic Approach to Approximation
  L. Barto, S. Butti, A. Kazda, C. Viola and S. Živný
  Submitted, 2025 PDF
  An extended abstract, Algebraic Approach to Approximation, appeared in LICS2024 PDF DOI
• Fixed-Template Promise Model Checking Problems
  K. Asimi, L. Barto and S. Butti
  CP2022 PDF DOI
• Weisfeiler-Leman Invariant Promise Valued CSPs
  L. Barto and S. Butti
  CP2022 PDF DOI
• Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem
  S. Butti and V. Dalmau
  MFCS2021 PDF DOI
• The Complexity of the Distributed Constraint Satisfaction Problem
  S. Butti and V. Dalmau
  Theory of Computing Systems (STACS special issue), 2024 PDF DOI
  An extended abstract appeared in STACS2021 PDF DOI
• Stochastic Local Search Algorithms for Constraint Satisfaction
  S. Butti and V. Dalmau
  CP2020 doctoral program PDF
• Sparsification of Binary CSPs
  S. Butti and S. Živný
  SIAM Journal on Discrete Mathematics, 2020. PDF DOI
  An extended abstract appeared in STACS2019 PDF DOI

Theses

• Symmetries in Constraint Satisfaction: Weisfeiler-Leman Invariance and Promise Problems
  PhD thesis, Department of Information and Communication Technologies, Universitat Pompeu Fabra, 2022. PDF
• On the Sparsifiability of Valued Constraint Satisfaction Problems
  MSc thesis, Mathematical Institute, University of Oxford, 2018. PDF