Research Papers

• Robust satisfiability for CSPs: hardness and algorithmic results
  V. Dalmau, A. Krokhin
  Submitted for journal publication.
   
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
  H. Chen, V. Dalmau.
  Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, LICS 2012.
   
• Learning Schema Mappings
  B. Ten Cate, V. Dalmau, P.H. Kolaitis.
  15th International Conference on Database Theory (ICDT'12).
   
• 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.
   
• Arc Consistency and Friends
  H. Chen, V. Dalmau, and B. Grußien.
  Journal of Logic and Computation (to appear).
   
• Distance Constraint Satisfaction Problems
  M. Bodirsky, V. Dalmau, B. Martin, and M. Pinkster.
  Mathematical Foundations of Computer Science 2010, 35th International Symposium, MFCS 2010.
   
• 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).
   
• 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.
   
• 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 Constraint 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
   

Back to Victor Dalmau's Home Page