2 citations · 3 across the 8 of their papers we have counts for
12 papers
Equations over Finite Monoids with Infinite Promises
Alberto Larrauri, Antoine Mottet, Stanislav Živný
Larrauri and Živný [ICALP'25/ACM ToCL'24] recently established a complete complexity classification of the problem of solving a system of equations over a monoid assuming that…
Optimal Inapproximability of Promise Equations over Finite Groups
Silvia Butti, Alberto Larrauri, Stanislav Živný
A celebrated result of Hastad established that, for any constant , it is NP-hard to find an assignment satisfying a -fraction of the constraints…
A logarithmic approximation of linearly ordered colourings
Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima +1
A linearly ordered (LO) -colouring of a hypergraph assigns to each vertex a colour from the set in such a way that each hyperedge has a unique maximum eleme…
Satisfiability of commutative vs. non-commutative CSPs
Andrei A. Bulatov, Stanislav Živný
The Mermin-Peres magic square is a celebrated example of a system of Boolean linear equations that is not (classically) satisfiable but is satisfiable via linear operators on a Hil…
Solving promise equations over monoids and groups
Alberto Larrauri, Stanislav Živný
We give a complete complexity classification for the problem of finding a solution to a given system of equations over a fixed finite monoid, given that a solution over a more rest…
An approximation algorithm for Maximum DiCut vs. Cut
Tamio-Vesa Nakajima, Stanislav Živný
Goemans and Williamson designed a 0.878-approximation algorithm for Max-Cut in undirected graphs [JACM'95]. Khot, Kindler, Mosel, and O'Donnel showed that the approximation ratio o…
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem…
Semidefinite programming and linear equations vs. homomorphism problems
Lorenzo Ciardo, Stanislav Živný
We introduce a relaxation for homomorphism problems that combines semidefinite programming with linear Diophantine equations, and propose a framework for the analysis of its power…
1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin +2
The 1-in-3 and Not-All-Equal satisfiability problems for Boolean CNF formulas are two well-known NP-hard problems. In contrast, the promise 1-in-3 vs. Not-All-Equal problem can be…
Approximate Graph Colouring and the Crystal with a Hollow Shadow
Lorenzo Ciardo, Stanislav Živný
We show that approximate graph colouring is not solved by the lift-and-project hierarchy for the combination of linear programming and linear Diophantine equations. The proof is ba…
On the complexity of symmetric vs. functional PCSPs
Tamio-Vesa Nakajima, Stanislav Živný
The complexity of the promise constraint satisfaction problem is largely unknown, even for symmetric and , exc…
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
Jacob Focke, Leslie Ann Goldberg, Marc Roth +1
We study the complexity of approximating the number of answers to a small query in a large database . We establish an exhaustive classification into tractable and…