Stanislav Zivný

ACM Trans. Algorithms, October, 2024

Additive Sparsification of CSPs.

[BibT_eX]

[DOI]

Eden Pelleg

ACM Trans. Algorithms, January, 2024

Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity.

[BibT_eX]

[DOI]

Proc. ACM Manag. Data, 2024

Optimal Inapproximability of Promise Equations over Finite Groups.

[BibT_eX]

[DOI]

Silvia Butti

Alberto Larrauri

CoRR, 2024

Maximum And- vs. Even-SAT.

[BibT_eX]

[DOI]

CoRR, 2024

Maximum Bipartite vs. Triangle-Free Subgraph.

[BibT_eX]

[DOI]

CoRR, 2024

The periodic structure of local consistency.

[BibT_eX]

[DOI]

CoRR, 2024

Satisfiability of commutative vs. non-commutative CSPs.

[BibT_eX]

[DOI]

Andrei A. Bulatov

CoRR, 2024

An approximation algorithm for Maximum DiCut vs. Cut.

[BibT_eX]

[DOI]

CoRR, 2024

Semidefinite Programming and Linear Equations vs. Homomorphism Problems.

[BibT_eX]

[DOI]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

Algebraic Approach to Approximation.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

Solving Promise Equations over Monoids and Groups.

[BibT_eX]

[DOI]

Alberto Larrauri

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

A Logarithmic Approximation of Linearly-Ordered Colourings.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

Pliability and Approximating Max-CSPs.

[BibT_eX]

[DOI]

J. ACM, December, 2023

PTAS for Sparse General-valued CSPs.

[BibT_eX]

[DOI]

Balázs F. Mezei

ACM Trans. Algorithms, April, 2023

Topology and Adjunction in Promise Constraint Satisfaction.

[BibT_eX]

[DOI]

SIAM J. Comput., February, 2023

CLAP: A New Algorithm for Promise CSPs.

[BibT_eX]

[DOI]

SIAM J. Comput., February, 2023

Maximum k- vs. 𝓁-colourings of graphs.

[BibT_eX]

[DOI]

CoRR, 2023

On the complexity of the approximate hypergraph homomorphism problem.

[BibT_eX]

[DOI]

CoRR, 2023

Sparsification of Monotone k-Submodular Functions of Low Curvature.

[BibT_eX]

[DOI]

Jannik Kudla

CoRR, 2023

Approximate Graph Colouring and the Hollow Shadow.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Approximate Graph Colouring and Crystals.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Hierarchies of Minion Tests for PCSPs through Tensors.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Boolean symmetric vs. functional PCSP dichotomy.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM/IEEE Symposium on Logic in Computer Science, 2023

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees.

[BibT_eX]

[DOI]

Shuai Shao

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

2022

Linearly Ordered Colourings of Hypergraphs.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, December, 2022

QCSP on Reflexive Tournaments.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2022

The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side.

[BibT_eX]

[DOI]

Clément Carbonnel

SIAM J. Comput., 2022

Beyond PCSP(1-in-3, NAE).

[BibT_eX]

[DOI]

Alex Brandts

Inf. Comput., 2022

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 22201).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2022

The Sherali-Adams Hierarchy for Promise CSPs through Tensors.

[BibT_eX]

[DOI]

CoRR, 2022

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations.

[BibT_eX]

[DOI]

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

2021

The Complexity of Promise SAT on Non-Boolean Domains.

[BibT_eX]

[DOI]

Alex Brandts

ACM Trans. Comput. Theory, 2021

On rainbow-free colourings of uniform hypergraphs.

[BibT_eX]

[DOI]

Ragnar Groot Koerkamp

Theor. Comput. Sci., 2021

The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains.

[BibT_eX]

[DOI]

Caterina Viola

ACM Trans. Algorithms, 2021

The Complexity of Approximately Counting Retractions to Square-free Graphs.

[BibT_eX]

[DOI]

Jacob Focke

Leslie Ann Goldberg

ACM Trans. Algorithms, 2021

Counting Homomorphisms to K4-Minor-Free Graphs, Modulo 2.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

Treewidth-Pliability and PTAS for Max-CSPs.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Counting Homomorphisms to K4-minor-free Graphs, modulo 2.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

The Complexity of Approximately Counting Retractions.

[BibT_eX]

[DOI]

Jacob Focke

Leslie Ann Goldberg

ACM Trans. Comput. Theory, 2020

Approximate Counting CSP Seen from the Other Side.

[BibT_eX]

[DOI]

Andrei A. Bulatov

ACM Trans. Comput. Theory, 2020

Point-Width and Max-CSPs.

[BibT_eX]

[DOI]

Clément Carbonnel

ACM Trans. Algorithms, 2020

Sparsification of Binary CSPs.

[BibT_eX]

[DOI]

Silvia Butti

SIAM J. Discret. Math., 2020

The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2020

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Using a Min-Cut Generalisation to Go Beyond Boolean Surjective VCSPs.

[BibT_eX]

[DOI]

Gregor Matl

Algorithmica, 2020

Improved hardness for H-colourings of G-colourable graphs.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Galois Connections for Patterns: An Algebra of Labelled Graphs.

[BibT_eX]

[DOI]

Proceedings of the Graph Structures for Knowledge Representation and Reasoning, 2020

2019

The Complexity of Boolean Surjective General-Valued CSPs.

[BibT_eX]

[DOI]

Hannes Uppman

ACM Trans. Comput. Theory, 2019

A Tractable Class of Binary VCSPs via M-Convex Intersection.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2019

The Complexity of Counting Surjective Homomorphisms and Compactions.

[BibT_eX]

[DOI]

Jacob Focke

Leslie Ann Goldberg

SIAM J. Discret. Math., 2019

Binary constraint satisfaction problems defined by excluded topological minors.

[BibT_eX]

[DOI]

Inf. Comput., 2019

Improved hardness for H-colourings of G-colourable graphs.

[BibT_eX]

[DOI]

CoRR, 2019

On Singleton Arc Consistency for CSPs Defined by Monotone Patterns.

[BibT_eX]

[DOI]

Algorithmica, 2019

Beyond Boolean Surjective VCSPs.

[BibT_eX]

[DOI]

Gregor Matl

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018

The Limits of SDP Relaxations for General-Valued CSPs.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2018

Discrete convexity in joint winner property.

[BibT_eX]

[DOI]

Yuni Iwamasa

Kazuo Murota

Discret. Optim., 2018

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231).

[BibT_eX]

[DOI]

Martin Grohe

Venkatesan Guruswami

Dagstuhl Reports, 2018

Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection.

[BibT_eX]

[DOI]

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

The Complexity of General-Valued CSPs Seen from the Other Side.

[BibT_eX]

[DOI]

Clément Carbonnel

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017

Functional clones and expressibility of partition functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Binarisation for Valued Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2017

The Power of Sherali-Adams Relaxations for General-Valued CSPs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2017

Backdoors into heterogeneous classes of SAT and CSP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

On planar valued CSPs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2017

On Singleton Arc Consistency for Natural CSPs Defined by Forbidden Patterns.

[BibT_eX]

[DOI]

CoRR, 2017

The Complexity of Boolean Surjective General-Valued CSPs.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

The Complexity of Valued CSPs.

[BibT_eX]

[DOI]

Andrei A. Krokhin

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

Hybrid Tractable Classes of Constraint Problems.

[BibT_eX]

[DOI]

Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016

A Galois Connection for Weighted (Relational) Clones of Infinite Size.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2016

Maximizing k-Submodular Functions and Beyond.

[BibT_eX]

[DOI]

Justin Ward

ACM Trans. Algorithms, 2016

The Complexity of Finite-Valued CSPs.

[BibT_eX]

[DOI]

J. ACM, 2016

Minimal Weighted Clones with Boolean Support.

[BibT_eX]

[DOI]

Andrius Vaicenavicius

Proceedings of the 46th IEEE International Symposium on Multiple-Valued Logic, 2016

2015

Necessary Conditions for Tractability of Valued CSPs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2015

The Power of Linear Programming for General-Valued CSPs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

Variable and value elimination in binary constraint satisfaction via forbidden patterns.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2015

Tractable Classes of Binary CSPs Defined by Excluded Topological Minors.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Sherali-Adams Relaxations for Valued CSPs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

A Galois Connection for Valued Constraint Languages of Infinite Size.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Binarisation via Dualisation for Valued Constraints.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014

The Complexity of Valued Constraint Satisfaction.

[BibT_eX]

[DOI]

Peter Jeavons

Andrei A. Krokhin

Bull. EATCS, 2014

Maximizing k-Submodular Functions and Beyond.

[BibT_eX]

[DOI]

Justin Ward

CoRR, 2014

Maximizing Bisubmodular and k-Submodular Functions.

[BibT_eX]

[DOI]

Justin Ward

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Tractable Valued Constraints.

[BibT_eX]

[DOI]

Proceedings of the Tractability: Practical Approaches to Hard Problems, 2014

2013

An Algebraic Theory of Complexity for Discrete Optimization.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

The complexity of conservative valued CSPs.

[BibT_eX]

[DOI]

J. ACM, 2013

Variable Elimination in Binary CSP via Forbidden Patterns.

[BibT_eX]

[DOI]

Proceedings of the IJCAI 2013, 2013

Tractable Combinations of Global Constraints.

[BibT_eX]

[DOI]

Proceedings of the Principles and Practice of Constraint Programming, 2013

2012

The Complexity of Valued Constraint Satisfaction Problems

[BibT_eX]

[DOI]

Cognitive Technologies, Springer, ISBN: 978-3-642-33973-8, 2012

Tractable Triangles and Cross-Free Convexity in Discrete Optimisation.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2012

An Algebraic Theory of Complexity for Discrete Optimisation

[BibT_eX]

[DOI]

CoRR, 2012

The Power of Linear Programming for Valued CSPs.

[BibT_eX]

[DOI]

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Relating Proof Complexity Measures and Practical Hardness of SAT.

[BibT_eX]

[DOI]

Proceedings of the Principles and Practice of Constraint Programming, 2012

A Characterisation of the Complexity of Forbidding Subproblems in Binary Max-CSP.

[BibT_eX]

[DOI]

Guillaume Escamocher

Proceedings of the Principles and Practice of Constraint Programming, 2012

2011

Hybrid tractability of valued constraint problems.

[BibT_eX]

[DOI]

Artif. Intell., 2011

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

On Minimal Weighted Clones.

[BibT_eX]

[DOI]

Páidí Creed

Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011

Tractable Triangles.

[BibT_eX]

[DOI]

Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011

Hierarchically Nested Convex VCSP.

[BibT_eX]

[DOI]

Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011

2010

Hybrid tractability of soft constraint problems

[BibT_eX]

[DOI]

CoRR, 2010

Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms

[BibT_eX]

[DOI]

CoRR, 2010

The complexity of conservative finite-valued CSPs

[BibT_eX]

[DOI]

CoRR, 2010

Classes of submodular constraints expressible by graph cuts.

[BibT_eX]

[DOI]

Constraints An Int. J., 2010

A New Hybrid Tractable Class of Soft Constraint Problems.

[BibT_eX]

[DOI]

Proceedings of the Principles and Practice of Constraint Programming - CP 2010, 2010

2009

The complexity and expressive power of valued constraints.

[BibT_eX]

[DOI]

PhD thesis, 2009

Structural properties of oracle classes.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2009

A note on some collapse results of valued constraints.

[BibT_eX]

[DOI]

Bruno Zanuttini

Inf. Process. Lett., 2009

The expressive power of binary submodular functions.

[BibT_eX]

[DOI]

David A. Cohen

Discret. Appl. Math., 2009

The Complexity of Valued Constraint Models.

[BibT_eX]

[DOI]

Proceedings of the Principles and Practice of Constraint Programming, 2009

Same-Relation Constraints.

[BibT_eX]

[DOI]

Christopher Jefferson

Proceedings of the Principles and Practice of Constraint Programming, 2009

2008

The expressive power of valued constraints: Hierarchies and collapses.

[BibT_eX]

[DOI]

David A. Cohen