Víctor Dalmau

Affiliations:
  • Universitat Pompeu Fabra, Barcelona, Spain


According to our database1, Víctor Dalmau authored at least 67 papers between 1999 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side.
CoRR, 2024

The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems.
CoRR, 2024

Right-Adjoints for Datalog Programs.
Proceedings of the 27th International Conference on Database Theory, 2024

When Do Homomorphism Counts Help in Query Algorithms?
Proceedings of the 27th International Conference on Database Theory, 2024

2023
Functors on relational structures which admit both left and right adjoints.
CoRR, 2023

Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes.
CoRR, 2023

Local consistency as a reduction between constraint satisfaction problems.
CoRR, 2023

Extremal Fitting Problems for Conjunctive Queries.
Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023

2022
Conjunctive Queries: Unique Characterizations and Exact Learnability.
ACM Trans. Database Syst., 2022

Promise Constraint Satisfaction and Width.
Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021
Dismantlability, connectedness, and mixing in relational structures.
J. Comb. Theory, Ser. B, 2021

Regularizing conjunctive features for classification.
J. Comput. Syst. Sci., 2021

The Complexity of the Distributed Constraint Satisfaction Problem.
Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Fractional Homomorphism, Weisfeiler-Leman Invariance, and the Sherali-Adams Hierarchy for the Constraint Satisfaction Problem.
Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

2020
The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs.
Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

2019
Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs.
SIAM J. Comput., 2019

Long range actions, connectedness, and dismantlability in relational structures.
CoRR, 2019

2018
Towards a characterization of constant-factor approximable finite-valued CSPs.
J. Comput. Syst. Sci., 2018

2017
Conjunctions of Among Constraints.
Proceedings of the Principles and Practice of Constraint Programming, 2017

2016
Decomposing Quantified Conjunctive (or Disjunctive) Formulas.
SIAM J. Comput., 2016

Distance constraint satisfaction problems.
Inf. Comput., 2016

2015
Towards a Characterization of Constant-Factor Approximable Min CSPs.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy.
Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

The Product Homomorphism Problem and Applications.
Proceedings of the 18th International Conference on Database Theory, 2015

2013
Learning schema mappings.
ACM Trans. Database Syst., 2013

Robust Satisfiability for CSPs: Hardness and Algorithmic Results.
ACM Trans. Comput. Theory, 2013

Arc consistency and friends.
J. Log. Comput., 2013

Datalog and constraint satisfaction with infinite templates.
J. Comput. Syst. Sci., 2013

Descriptive complexity of approximate counting CSPs.
Proceedings of the Computer Science Logic 2013 (CSL 2013), 2013

2012
Enumerating homomorphisms.
J. Comput. Syst. Sci., 2012

A note on the product homomorphism problem and CQ-definability
CoRR, 2012

2011
Two new homomorphism dualities and lattice operations.
J. Log. Comput., 2011

2010
CSP duality and trees of bounded pathwidth.
Theor. Comput. Sci., 2010

Distance Constraint Satisfaction Problems.
Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

2009
There are no pure relational width 2 constraint satisfaction problems.
Inf. Process. Lett., 2009

2008
A combinatorial characterization of resolution width.
J. Comput. Syst. Sci., 2008

Majority constraints have bounded pathwidth duality.
Eur. J. Comb., 2008

Retractions onto series-parallel posets.
Discret. Math., 2008

Maltsev + Datalog --> Symmetric Datalog.
Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, 2008

Caterpillar Duality for Constraint Satisfaction Problems.
Proceedings of the Twenty-Third Annual IEEE Symposium on Logic in Computer Science, 2008

2007
Learning intersection-closed classes with signatures.
Theor. Comput. Sci., 2007

First-order Definable Retraction Problems for Posets and Reflexive Graphs.
J. Log. Comput., 2007

Towards a dichotomy theorem for the counting constraint satisfaction problem.
Inf. Comput., 2007

Phase transitions of PP-complete satisfiability problems.
Discret. Appl. Math., 2007

CD(4) has bounded width
CoRR, 2007

On the Power of <i>k</i> -Consistency.
Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006
A Simple Algorithm for Mal'tsev Constraints.
SIAM J. Comput., 2006

Generalized Majority-Minority Operations are Tractable.
Log. Methods Comput. Sci., 2006

2005
Linear datalog and bounded path duality of relational structures.
Log. Methods Comput. Sci., 2005

Tractable Clones of Polynomials over Semigroups
Electron. Colloquium Comput. Complex., 2005

A new tractable class of constraint satisfaction problems.
Ann. Math. Artif. Intell., 2005

From Pebble Games to Tractability: An Ambidextrous Consistency Algorithm for Quantified Constraint Satisfaction.
Proceedings of the Computer Science Logic, 19th International Workshop, 2005

Beyond Hypertree Width: Decomposition Methods Without Decompositions.
Proceedings of the Principles and Practice of Constraint Programming, 2005

2004
The complexity of counting homomorphisms seen from the other side.
Theor. Comput. Sci., 2004

Malt'sev Constraints made Simple
Electron. Colloquium Comput. Complex., 2004

Looking Algebraically at Tractable Quantified Boolean Formulas.
Proceedings of the Theory and Applications of Satisfiability Testing, 2004

First-Order Definable Retraction Problems for Posets and Reflexive Graph.
Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

(Smart) Look-Ahead Arc Consistency and the Pursuit of CSP Tractability.
Proceedings of the Principles and Practice of Constraint Programming, 2004

Learnability of Relatively Quantified Generalized Formulas.
Proceedings of the Algorithmic Learning Theory, 15th International Conference, 2004

2003
Learnability of quantified formulas.
Theor. Comput. Sci., 2003

Generalized Satisfability with Limited Occurrences per Variable: A Study through Delta-Matroid Parity.
Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

2002
Constraint Satisfaction Problems in Non-deterministic Logarithmic Space.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics.
Proceedings of the Principles and Practice of Constraint Programming, 2002

Comparing Phase Transitions and Peak Cost in PP-Complete Satisfiability Problems.
Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28, 2002

1999
A Dichotomy Theorem for Learning Quantified Boolean Formulas.
Mach. Learn., 1999

Closure Functions and Width 1 Problems.
Proceedings of the Principles and Practice of Constraint Programming, 1999

Boolean Formulas are Hard to Learn for most Gate Bases.
Proceedings of the Algorithmic Learning Theory, 10th International Conference, 1999


  Loading...