77 citations · 733 across the 54 of their papers we have counts for
6 papers · 1 filter
Sparsification of Monotone -Submodular Functions of Low Curvature
Jannik Kudla, Stanislav Živný
Pioneered by Benczur and Karger for cuts in graphs [STOC'96], sparsification is a fundamental topic with wide-ranging applications that has been studied, e.g., for graphs and hyper…
Additive Sparsification of CSPs
Eden Pelleg, Stanislav Živný
Multiplicative cut sparsifiers, introduced by Benczúr and Karger [STOC'96], have proved extremely influential and found various applications. Precise characterisations were establi…
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…
Using a min-cut generalisation to go beyond Boolean surjective VCSPs
Gregor Matl, Stanislav Zivny
In this work, we first study a natural generalisation of the Min-Cut problem, where a graph is augmented by a superadditive set function defined on its vertex subsets. The goal is…
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 $…
Maximizing k-Submodular Functions and Beyond
Justin Ward, Stanislav Zivny
We consider the maximization problem in the value oracle model of functions defined on -tuples of sets that are submodular in every orthant and -wise monotone, where $k\geq 2…