Research Papers

Distance Constraint Satisfaction Problems
M. Bodirsky, V. Dalmau, B. Martin, A. Mottet, and M. Pinkster.
Information and Computation 247 (2016), 87105. 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 HColoring 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 ConstantFactor Approximable MIN CSPs
V. Dalmau and A. Krokhin.
Proceedings of the 26th Annual ACMSIAM 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), 79100. 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.
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.
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): 87108 (2013).

Enumerating homomorphisms
A. Bulatov, V. Dalmau, M. Grohe, D. Marx.
J. Comput. Syst. Sci 78(2):638650(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 (3436), 31883208, 2010.

Retractions onto seriesparallel posets
V. Dalmau, A. Krokhin, and B. Larose.
Discrete Mathematics 308(11) (2008):21042114.

Majority Constraints have Bounded Pathwidth Duality
V. Dalmau and A. Krokhin.
European Journal on Combinatorics 29(4) (2008):821837.

Maltsev + Datalog > Symmetric Datalog
V. Dalmau and B. Larose.
TwentyThird 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), 10651092, 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):213218 (2009).

On the Power of kConsistency
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: 293307 (2009).

A Simple Algorithm for Mal'tsev Constraints
A. Bulatov and V. Dalmau.
SIAM J. Comput. 36(1): 1627 (2006)

Generalized MajorityMinority 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 IntersectionClosed Classes with
Signatures
Andrei Bulatov, Hubie Chen, and Victor Dalmau.
Theoretical Computer Science 282(3): 209220 (2007). A preliminary version
was presented in ALT'04 under the title "Learnability of
Relatively Quantified Generalized Formulas".

Firstorder Definable Retraction
Problems for Posets and Reflexive Graphs
Victor Dalmau, Andrei Krokhin, and Benoit Larose.
Journal of Logic and Computation, 17(1), 3151, 2007. A preliminary version was presented
at 19th IEEE Symposium on Logic in Computer Science (LICS 2004).

"Smart" LookAhead 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(13): 315323 (2004).

Towards a Dichotomy Theorem for Counting CSP
Andrei Bulatov and Victor Dalmau.
Inf. Comput. 205(5): 651678 (2007). A preliminary version was presented at FOCS'03.

Generalized Satisfiability with k occurrences
per variable: a study through DeltaMatroid 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): 323334 (2008). A preliminary
version of the paper has been presented at CCC'03.

Constraint Satisfaction, Bounded
Treewidth, and FiniteVariable 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
NonDeterministic Logarithmic Space").

Comparing Phase Transitions and Peak Cost
in PPComplete Satisfiability Problems.
Delbert D. Bailey, Victor Dalmau and Phokion G. Kolaitis.
Eighteenth National Conference on Artificial Intelligence (AAAI'02).

Phase Transitions on PPComplete
Satisfiability Problems.
Delbert D. Bailey, Victor Dalmau and Phokion G. Kolaitis.
Discrete Applied Mathematics 155(12): 16271639 (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(12): 6185 (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 (13) 485511. 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 Constantfree
Quantified Boolean Formulas.
Victor Dalmau.
Technical Report LSI9743R. Departament LSI (UPC).
Doctoral Thesis
Back to Victor Dalmau's Home Page