Stanislav Zivný

Affiliations:
  • University of Oxford, Department of Computer Science, UK


According to our database1, Stanislav Zivný authored at least 106 papers between 2008 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Additive Sparsification of CSPs.
ACM Trans. Algorithms, January, 2024

Solving promise equations over monoids and groups.
CoRR, 2024

An approximation algorithm for Maximum DiCut vs. Cut.
CoRR, 2024

Algebraic Approach to Approximation.
CoRR, 2024

2023
Pliability and Approximating Max-CSPs.
J. ACM, December, 2023

PTAS for Sparse General-valued CSPs.
ACM Trans. Algorithms, April, 2023

CLAP: A New Algorithm for Promise CSPs.
SIAM J. Comput., February, 2023

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

Semidefinite programming and linear equations vs. homomorphism problems.
CoRR, 2023

Maximum k- vs. 𝓁-colourings of graphs.
CoRR, 2023

On the complexity of the approximate hypergraph homomorphism problem.
CoRR, 2023

Sparsification of Monotone k-Submodular Functions of Low Curvature.
CoRR, 2023

Approximate Graph Colouring and the Hollow Shadow.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Approximate Graph Colouring and Crystals.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Hierarchies of Minion Tests for PCSPs through Tensors.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Boolean symmetric vs. functional PCSP dichotomy.
LICS, 2023

A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible Degrees.
Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

2022
Linearly Ordered Colourings of Hypergraphs.
ACM Trans. Comput. Theory, December, 2022

QCSP on Reflexive Tournaments.
ACM Trans. Comput. Log., 2022

The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side.
SIAM J. Comput., 2022

Beyond PCSP(1-in-3, NAE).
Inf. Comput., 2022

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

The Sherali-Adams Hierarchy for Promise CSPs through Tensors.
CoRR, 2022

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations.
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.
ACM Trans. Comput. Theory, 2021

On rainbow-free colourings of uniform hypergraphs.
Theor. Comput. Sci., 2021

The Combined Basic LP and Affine IP Relaxation for Promise VCSPs on Infinite Domains.
ACM Trans. Algorithms, 2021

The Complexity of Approximately Counting Retractions to Square-free Graphs.
ACM Trans. Algorithms, 2021

Counting Homomorphisms to K<sub>4</sub>-Minor-Free Graphs, Modulo 2.
SIAM J. Discret. Math., 2021

Treewidth-Pliability and PTAS for Max-CSPs.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Counting Homomorphisms to <i>K</i><sub>4</sub>-minor-free Graphs, modulo 2.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020
The Complexity of Approximately Counting Retractions.
ACM Trans. Comput. Theory, 2020

Approximate Counting CSP Seen from the Other Side.
ACM Trans. Comput. Theory, 2020

Point-Width and Max-CSPs.
ACM Trans. Algorithms, 2020

Sparsification of Binary CSPs.
SIAM J. Discret. Math., 2020

The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.
SIAM J. Comput., 2020

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin.
J. Comput. Syst. Sci., 2020

Topology and adjunction in promise constraint satisfaction.
Electron. Colloquium Comput. Complex., 2020

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs.
Electron. Colloquium Comput. Complex., 2020

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

Improved hardness for <i>H</i>-colourings of <i>G</i>-colourable graphs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Galois Connections for Patterns: An Algebra of Labelled Graphs.
Proceedings of the Graph Structures for Knowledge Representation and Reasoning, 2020

2019
The Complexity of Boolean Surjective General-Valued CSPs.
ACM Trans. Comput. Theory, 2019

A Tractable Class of Binary VCSPs via M-Convex Intersection.
ACM Trans. Algorithms, 2019

The Complexity of Counting Surjective Homomorphisms and Compactions.
SIAM J. Discret. Math., 2019

Binary constraint satisfaction problems defined by excluded topological minors.
Inf. Comput., 2019

Improved hardness for H-colourings of G-colourable graphs.
CoRR, 2019

On Singleton Arc Consistency for CSPs Defined by Monotone Patterns.
Algorithmica, 2019

Beyond Boolean Surjective VCSPs.
Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018
The Limits of SDP Relaxations for General-Valued CSPs.
ACM Trans. Comput. Theory, 2018

Discrete convexity in joint winner property.
Discret. Optim., 2018

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

Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection.
Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

The Complexity of General-Valued CSPs Seen from the Other Side.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Functional clones and expressibility of partition functions.
Theor. Comput. Sci., 2017

Binarisation for Valued Constraint Satisfaction Problems.
SIAM J. Discret. Math., 2017

The Power of Sherali-Adams Relaxations for General-Valued CSPs.
SIAM J. Comput., 2017

The Power of Arc Consistency for CSPs Defined by Partially-Ordered Forbidden Patterns.
Log. Methods Comput. Sci., 2017

Backdoors into heterogeneous classes of SAT and CSP.
J. Comput. Syst. Sci., 2017

On planar valued CSPs.
J. Comput. Syst. Sci., 2017

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

The Complexity of Boolean Surjective General-Valued CSPs.
Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

The Complexity of Valued CSPs.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

Hybrid Tractable Classes of Constraint Problems.
Proceedings of the Constraint Satisfaction Problem: Complexity and Approximability, 2017

2016
A Galois Connection for Weighted (Relational) Clones of Infinite Size.
ACM Trans. Comput. Theory, 2016

Maximizing <i>k</i>-Submodular Functions and Beyond.
ACM Trans. Algorithms, 2016

The Complexity of Finite-Valued CSPs.
J. ACM, 2016

Minimal Weighted Clones with Boolean Support.
Proceedings of the 46th IEEE International Symposium on Multiple-Valued Logic, 2016

2015
Necessary Conditions for Tractability of Valued CSPs.
SIAM J. Discret. Math., 2015

The Power of Linear Programming for General-Valued CSPs.
SIAM J. Comput., 2015

Variable and value elimination in binary constraint satisfaction via forbidden patterns.
J. Comput. Syst. Sci., 2015

Tractable Classes of Binary CSPs Defined by Excluded Topological Minors.
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

Sherali-Adams Relaxations for Valued CSPs.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

A Galois Connection for Valued Constraint Languages of Infinite Size.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Binarisation via Dualisation for Valued Constraints.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014
The Complexity of Valued Constraint Satisfaction.
Bull. EATCS, 2014

Maximizing k-Submodular Functions and Beyond.
CoRR, 2014

Maximizing Bisubmodular and <i>k</i>-Submodular Functions.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Tractable Valued Constraints.
Proceedings of the Tractability: Practical Approaches to Hard Problems, 2014

2013
An Algebraic Theory of Complexity for Discrete Optimization.
SIAM J. Comput., 2013

The complexity of conservative valued CSPs.
J. ACM, 2013

Variable Elimination in Binary CSP via Forbidden Patterns.
Proceedings of the IJCAI 2013, 2013

Tractable Combinations of Global Constraints.
Proceedings of the Principles and Practice of Constraint Programming, 2013

2012
The Complexity of Valued Constraint Satisfaction Problems
Cognitive Technologies, Springer, ISBN: 978-3-642-33973-8, 2012

Tractable Triangles and Cross-Free Convexity in Discrete Optimisation.
J. Artif. Intell. Res., 2012

An Algebraic Theory of Complexity for Discrete Optimisation
CoRR, 2012

The Power of Linear Programming for Valued CSPs.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Relating Proof Complexity Measures and Practical Hardness of SAT.
Proceedings of the Principles and Practice of Constraint Programming, 2012

A Characterisation of the Complexity of Forbidding Subproblems in Binary Max-CSP.
Proceedings of the Principles and Practice of Constraint Programming, 2012

2011
Hybrid tractability of valued constraint problems.
Artif. Intell., 2011

An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection.
Proceedings of the Mathematical Foundations of Computer Science 2011, 2011

On Minimal Weighted Clones.
Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011

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

Hierarchically Nested Convex VCSP.
Proceedings of the Principles and Practice of Constraint Programming - CP 2011, 2011

2010
Hybrid tractability of soft constraint problems
CoRR, 2010

Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms
CoRR, 2010

The complexity of conservative finite-valued CSPs
CoRR, 2010

Classes of submodular constraints expressible by graph cuts.
Constraints An Int. J., 2010

A New Hybrid Tractable Class of Soft Constraint Problems.
Proceedings of the Principles and Practice of Constraint Programming - CP 2010, 2010

2009
The complexity and expressive power of valued constraints.
PhD thesis, 2009

Structural properties of oracle classes.
Inf. Process. Lett., 2009

A note on some collapse results of valued constraints.
Inf. Process. Lett., 2009

The expressive power of binary submodular functions.
Discret. Appl. Math., 2009

The Complexity of Valued Constraint Models.
Proceedings of the Principles and Practice of Constraint Programming, 2009

Same-Relation Constraints.
Proceedings of the Principles and Practice of Constraint Programming, 2009

2008
The expressive power of valued constraints: Hierarchies and collapses.
Theor. Comput. Sci., 2008


  Loading...