51 citations · 74 across the 4 of their papers we have counts for
9 papers
Approximate Graph Colouring and Crystals
Lorenzo Ciardo, Stanislav Živný
We show that approximate graph colouring is not solved by any level of the affine integer programming (AIP) hierarchy. To establish the result, we translate the problem of exhibiti…
On rainbow-free colourings of uniform hypergraphs
Ragnar Groot Koerkamp, Stanislav Živný
We study rainbow-free colourings of -uniform hypergraphs; that is, colourings that use colours but with the property that no hyperedge attains all colours. We show that $p^*…
Approximate counting CSP seen from the other side
Andrei A. Bulatov, Stanislav Zivny
In this paper we study the complexity of counting Constraint Satisfaction Problems (CSPs) of the form #CSP(,-), in which the goal is, given a relational structure $\ma…
Point-width and Max-CSPs
Clement Carbonnel, Miguel Romero, Stanislav Zivny
The complexity of (unbounded-arity) Max-CSPs under structural restrictions is poorly understood. The two most general hypergraph properties known to ensure tractability of Max-CSPs…
Sparsification of Binary CSPs
Silvia Butti, Stanislav Zivny
A cut -sparsifier of a weighted graph is a re-weighted subgraph of of (quasi)linear size that preserves the size of all cuts up to a multiplicative factor of $…
The Complexity of Approximately Counting Retractions
Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny
Let be a graph that contains an induced subgraph . A retraction from to is a homomorphism from to that is the identity function on . Retractions are very…