Research Papers

• Distance Constraint Satisfaction Problems
  M. Bodirsky, V. Dalmau, B. Martin, A. Mottet, and M. Pinkster.
  Information and Computation 247 (2016), 87-105. A preliminary version of the paper was presented at MFCS 2010.
   
• The Product Homomorphism Problem and its Applications
  B. ten Cate and V. Dalmau.
  Proceedings of the 18th International Conference on Database Theory (ICDT 2015).
   
• Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy
  V. Dalmau, L. Egri, P. Hell, B. Larose, and A. Rafley.
  Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015).
   
• Towards a Characterization of Constant-Factor Approximable MIN CSPs
  V. Dalmau and A. Krokhin.
  Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015).
   
• Datalog and Constraint Satisfaction with Infinite Templates
  M. Bodirsky and V. Dalmau.
  Journal of Computer and System Sciences, 79(2013), 79-100. A preliminary version of the paper was presented at STACS 2006.
   
• Descriptive complexity of approximate counting CSPs
  A. Bulatov, V. Dalmau, and M. Thurley.
  Proceedings of the 22nd EACSL Annual Conference on Computer Science Logic (CSL 2013).
   
• Robust satisfiability for CSPs: hardness and algorithmic results.
  V. Dalmau, A. Krokhin
  ACM Transactions on Computation Theory 5(4):15 (2013).

• Decomposing Quantified Conjunctive (or Disjunctive) Formulas. H. Chen, V. Dalmau. SIAM J. Computing 45(6):2066-2086.  A preliminary version was presented at the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012.

• Learning Schema Mappings
  B. Ten Cate, V. Dalmau, P.H. Kolaitis.
  ACM Trans. Database Syst. 38(4): 28 (2013). A preliminary version was presented at 15th International Conference on Database Theory (ICDT'12)
   
• Arc Consistency and Friends
  H. Chen, V. Dalmau, and B. Grußien.
  Journal of Logic and Computation 23(1): 87-108 (2013).
   
• Enumerating homomorphisms
  A. Bulatov, V. Dalmau, M. Grohe, D. Marx.
  J. Comput. Syst. Sci 78(2):638-650(2012). A preliminary version of the paper was presented at STACS'09.
   
• CSP duality and trees of bounded pathwidth
  C. Carvalho, V. Dalmau, and A. Krokhin.
  Theoretical Computer Science, 411 (34-36), 3188-3208, 2010.
   
• Retractions onto series-parallel posets
  V. Dalmau, A. Krokhin, and B. Larose.
  Discrete Mathematics 308(11) (2008):2104-2114.
   
• Majority Constraints have Bounded Pathwidth Duality
  V. Dalmau and A. Krokhin.
  European Journal on Combinatorics 29(4) (2008):821-837.
   
• Maltsev + Datalog --> Symmetric Datalog
  V. Dalmau and B. Larose.
  Twenty-Third Annual IEEE Symposium on Logic in Computer Science, LICS 2008.
   
• Two new homomorphisms dualities and lattice operations
  C. Carvalho, V. Dalmau, and A. Krokhin.
  Journal of Logic and Computation, 21 (6), 1065-1092, 2011. A preliminary version of the paper was presented at LICS'08 under the title "Caterpillar Duality for Constraint Satisfaction Problems".
   
• There are no pure relational width 2 problems
  V. Dalmau.
  Information Processing Letters 109(4):213-218 (2009).
   
• On the Power of k-Consistency
  A. Atserias, A. Bulatov, and V. Dalmau.
  Automata, Languages and Programming, 34th International Colloquium, ICALP 2007.
   
• CD(4) has bounded width
  C. Carvalho, V. Dalmau, P. Markovik, M. Maroti.
  Algebra Universalis 60: 293-307 (2009).
   
• A Simple Algorithm for Mal'tsev Constraints
  A. Bulatov and V. Dalmau.
  SIAM J. Comput. 36(1): 16-27 (2006)
   
• Generalized Majority-Minority Operations are Tractable
  Victor Dalmau.
  Logical Methods in Computer Science 2(4): (2006). A preliminary version was presented at in the 20th IEEE Symposium on Logic in Computer Science (LICS 2005).
   
• From Pebble Games to Tractability: An Ambidextrous Consistency Algorithm for Quantified Constraint Satisfaction
  Hubie Chen, Victor Dalmau.
  Computer Science Logic, 19th International Workshop, CSL 2005.
   
• Tractable Clones of Polynomials over Semigroups
  Victor Dalmau, Ricard Gavalda, Pascal Tesson, Denis Therien.
  Principles and Practice of Constraint Programming - CP 2005, 11th International Conference.
   
• Beyond Hypertree Width: Decomposition Methods Without Decompositions
  Hubie Chen, Victor Dalmau
  Principles and Practice of Con.straint Programming - CP 2005, 11th International Conference.
   
• Learning Intersection-Closed Classes with Signatures
  Andrei Bulatov, Hubie Chen, and Victor Dalmau.
  Theoretical Computer Science 282(3): 209-220 (2007). A preliminary version was presented in ALT'04 under the title "Learnability of Relatively Quantified Generalized Formulas".
   
• First-order Definable Retraction Problems for Posets and Reflexive Graphs
  Victor Dalmau, Andrei Krokhin, and Benoit Larose.
  Journal of Logic and Computation, 17(1), 31-51, 2007. A preliminary version was presented at 19th IEEE Symposium on Logic in Computer Science (LICS 2004).
   
• "Smart" Look-Ahead Arc Consistency and the Pursuit of CSP Tractability
  Hubie Chen and Victor Dalmau.
  Principles and Practice of Constraint Programming - CP 2004, 10th International Conference.
   
• Looking Algebraically at Tractable Quantified Boolean Formulas
  Hubie Chen and Victor Dalmau.
  Theory and Applications of Satisfiability Testing, 7th International Conference, SAT 2004.
   
• The complexity of counting homomorphisms seen from the other side
  V. Dalmau and P. Jonsson.
  Theor. Comput. Sci. 329(1-3): 315-323 (2004).
   
• Towards a Dichotomy Theorem for Counting CSP
  Andrei Bulatov and Victor Dalmau.
  Inf. Comput. 205(5): 651-678 (2007). A preliminary version was presented at FOCS'03.
   
• Generalized Satisfiability with k occurrences per variable: a study through Delta-Matroid Parity
  Victor Dalmau and Daniel Ford.
  Mathematical Foundations of Computer Science 2003, 28th International Symposium, MFCS 2003.
   
• A Combinatorial Characterization of Resolution Width
  Albert Atserias and Victor Dalmau.
  J. Comput. Syst. Sci. 74(3): 323-334 (2008). A preliminary version of the paper has been presented at CCC'03.
   
• Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics.
  Victor Dalmau, Phokion G. Kolaitis and Moshe Y. Vardi.
  Principles and Practice of Constraint Programming - CP 2002.
   
• Linear Datalog and Bounded Path Duality of Relational Structures.
  Victor Dalmau.
  Logical Methods in Computer Science, Volume 1, Issue 1. Extended version of ICALP'02 paper (the title has changed, the title of the ICALP'02 paper is "Constraint Satisfaction Problems in Non-Deterministic Logarithmic Space").
   
• Comparing Phase Transitions and Peak Cost in PP-Complete Satisfiability Problems
  Delbert D. Bailey, Victor Dalmau and Phokion G. Kolaitis.
  Eighteenth National Conference on Artificial Intelligence (AAAI'02).
   
• Phase Transitions on PP-Complete Satisfiability Problems.
  Delbert D. Bailey, Victor Dalmau and Phokion G. Kolaitis.
  Discrete Applied Mathematics 155(12): 1627-1639 (2007). A preliminary version of the paper has been presented at IJCAI'01.
   
• A New Tractable Class of Constraint Satisfaction Problems.
  Victor Dalmau
  Annals of Mathematics and Artificial. Intelligence, 44(1-2): 61-85 (A preliminary version of the paper has been presented at the 6th International Symposium on Artificial Intelligence and Mathematics (2000)).
   
• Set Functions and Width 1.
  Victor Dalmau and Justin Pearson.
  Principles and Practice of Constraint Programming - CP'99.
   
• Boolean Formulas are Hard to Learn for Most Gate Basis.
  Victor Dalmau.
  Algorithmic Learning Theory, 10th International Conference, ALT '99.
   
• Learnability of Quantifed Formulas.
  Victor Dalmau and Peter Jeavons.
  Theoretical Computer Science 306 (1-3) 485-511. A preliminary version of the paper was presented at EuroColt'99.
   
• A Dichotomy Theorem for Learning Quantified Boolean Formulas.
  Victor Dalmau.
  Machine Learning 35(3), June 1999. A preliminary version of the paper was presented at COLT'97.
   
• Some Dichotomy Theorems on Constant-free Quantified Boolean Formulas.
  Victor Dalmau.
  Technical Report LSI-97-43-R. Departament LSI (UPC).
   

 Doctoral Thesis

• Computational Complexity of Problems over Generalized Formulas.
  Victor Dalmau