TY - JOUR
AB - The main result of this article is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Using a reduction to even Δ-matroids, we then extend the tractability result to larger classes of Δ-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely, co-independent, compact, local, linear, and binary, with the following caveat:We represent Δ-matroids by lists of tuples, while the last two use a representation by matrices. Since an n ×n matrix can represent exponentially many tuples, our tractability result is not strictly stronger than the known algorithm for linear and binary Δ-matroids.
AU - Kazda, Alexandr
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
ID - 6032
IS - 2
JF - ACM Transactions on Algorithms
TI - Even delta-matroids and the complexity of planar boolean CSPs
VL - 15
ER -
TY - JOUR
AB - We consider the NP-hard problem of MAP-inference for undirected discrete graphical models. We propose a polynomial time and practically efficient algorithm for finding a part of its optimal solution. Specifically, our algorithm marks some labels of the considered graphical model either as (i) optimal, meaning that they belong to all optimal solutions of the inference problem; (ii) non-optimal if they provably do not belong to any solution. With access to an exact solver of a linear programming relaxation to the MAP-inference problem, our algorithm marks the maximal possible (in a specified sense) number of labels. We also present a version of the algorithm, which has access to a suboptimal dual solver only and still can ensure the (non-)optimality for the marked labels, although the overall number of the marked labels may decrease. We propose an efficient implementation, which runs in time comparable to a single run of a suboptimal dual solver. Our method is well-scalable and shows state-of-the-art results on computational benchmarks from machine learning and computer vision.
AU - Shekhovtsov, Alexander
AU - Swoboda, Paul
AU - Savchynskyy, Bogdan
ID - 703
IS - 7
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
SN - 01628828
TI - Maximum persistency via iterative relaxed inference with graphical models
VL - 40
ER -
TY - CONF
AB - We consider the problem of estimating the partition function Z(β)=∑xexp(−β(H(x)) of a Gibbs distribution with a Hamilton H(⋅), or more precisely the logarithm of the ratio q=lnZ(0)/Z(β). It has been recently shown how to approximate q with high probability assuming the existence of an oracle that produces samples from the Gibbs distribution for a given parameter value in [0,β]. The current best known approach due to Huber [9] uses O(qlnn⋅[lnq+lnlnn+ε−2]) oracle calls on average where ε is the desired accuracy of approximation and H(⋅) is assumed to lie in {0}∪[1,n]. We improve the complexity to O(qlnn⋅ε−2) oracle calls. We also show that the same complexity can be achieved if exact oracles are replaced with approximate sampling oracles that are within O(ε2qlnn) variation distance from exact oracles. Finally, we prove a lower bound of Ω(q⋅ε−2) oracle calls under a natural model of computation.
AU - Kolmogorov, Vladimir
ID - 274
T2 - Proceedings of the 31st Conference On Learning Theory
TI - A faster approximation algorithm for the Gibbs partition function
VL - 75
ER -
TY - DATA
AB - Graph matching problems as described in "Active Graph Matching for Automatic Joint Segmentation and Annotation of C. Elegans." by Kainmueller, Dagmar and Jug, Florian and Rother, Carsten and Myers, Gene, MICCAI 2014. Problems are in OpenGM2 hdf5 format (see http://hciweb2.iwr.uni-heidelberg.de/opengm/) and a custom text format used by the feature matching solver described in "Feature Correspondence via Graph Matching: Models and Global Optimization." by Lorenzo Torresani, Vladimir Kolmogorov and Carsten Rother, ECCV 2008, code at http://pub.ist.ac.at/~vnk/software/GraphMatching-v1.02.src.zip.
AU - Kainmueller, Dagmar
AU - Jug, Florian
AU - Rother, Carsten
AU - Meyers, Gene
ID - 5561
KW - graph matching
KW - feature matching
KW - QAP
KW - MAP-inference
TI - Graph matching problems for annotating C. Elegans
ER -
TY - CONF
AB - We introduce two novel methods for learning parameters of graphical models for image labelling. The following two tasks underline both methods: (i) perturb model parameters based on given features and ground truth labelings, so as to exactly reproduce these labelings as optima of the local polytope relaxation of the labelling problem; (ii) train a predictor for the perturbed model parameters so that improved model parameters can be applied to the labelling of novel data. Our first method implements task (i) by inverse linear programming and task (ii) using a regressor e.g. a Gaussian process. Our second approach simultaneously solves tasks (i) and (ii) in a joint manner, while being restricted to linearly parameterised predictors. Experiments demonstrate the merits of both approaches.
AU - Trajkovska, Vera
AU - Swoboda, Paul
AU - Åström, Freddie
AU - Petra, Stefanie
ED - Lauze, François
ED - Dong, Yiqiu
ED - Bjorholm Dahl, Anders
ID - 641
SN - 978-331958770-7
TI - Graphical model parameter learning by inverse linear programming
VL - 10302
ER -
TY - JOUR
AB - An instance of the valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. We study, assuming that P 6= NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in f0;1g corresponds to ordinary CSPs, where one deals only with the feasibility issue, and there is no optimization. This case is the subject of the algebraic CSP dichotomy conjecture predicting for which constraint languages CSPs are tractable (i.e., solvable in polynomial time) and for which they are NP-hard. The case when all allowed functions take only finite values corresponds to a finitevalued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Živný. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e., the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs.
AU - Kolmogorov, Vladimir
AU - Krokhin, Andrei
AU - Rolinek, Michal
ID - 644
IS - 3
JF - SIAM Journal on Computing
TI - The complexity of general-valued CSPs
VL - 46
ER -
TY - CONF
AB - We present a novel convex relaxation and a corresponding inference algorithm for the non-binary discrete tomography problem, that is, reconstructing discrete-valued images from few linear measurements. In contrast to state of the art approaches that split the problem into a continuous reconstruction problem for the linear measurement constraints and a discrete labeling problem to enforce discrete-valued reconstructions, we propose a joint formulation that addresses both problems simultaneously, resulting in a tighter convex relaxation. For this purpose a constrained graphical model is set up and evaluated using a novel relaxation optimized by dual decomposition. We evaluate our approach experimentally and show superior solutions both mathematically (tighter relaxation) and experimentally in comparison to previously proposed relaxations.
AU - Kuske, Jan
AU - Swoboda, Paul
AU - Petra, Stefanie
ED - Lauze, François
ED - Dong, Yiqiu
ED - Bjorholm Dahl, Anders
ID - 646
SN - 978-331958770-7
TI - A novel convex relaxation for non binary discrete tomography
VL - 10302
ER -
TY - CONF
AB - The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even Δ-matroid constraints allows us to extend the tractability result to a larger class of Δ-matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary.
AU - Kazda, Alexandr
AU - Kolmogorov, Vladimir
AU - Rolinek, Michal
ID - 1192
SN - 978-161197478-2
TI - Even delta-matroids and the complexity of planar Boolean CSPs
ER -
TY - CONF
AB - We propose a dual decomposition and linear program relaxation of the NP-hard minimum cost multicut problem. Unlike other polyhedral relaxations of the multicut polytope, it is amenable to efficient optimization by message passing. Like other polyhedral relaxations, it can be tightened efficiently by cutting planes. We define an algorithm that alternates between message passing and efficient separation of cycle- and odd-wheel inequalities. This algorithm is more efficient than state-of-the-art algorithms based on linear programming, including algorithms written in the framework of leading commercial software, as we show in experiments with large instances of the problem from applications in computer vision, biomedical image analysis and data mining.
AU - Swoboda, Paul
AU - Andres, Bjoern
ID - 915
SN - 978-153860457-1
TI - A message passing algorithm for the minimum cost multicut problem
VL - 2017
ER -
TY - CONF
AB - We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore this direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art anytime solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each.
AU - Swoboda, Paul
AU - Rother, Carsten
AU - Abu Alhaija, Carsten
AU - Kainmueller, Dagmar
AU - Savchynskyy, Bogdan
ID - 916
SN - 978-153860457-1
TI - A study of lagrangean decompositions and dual ascent solvers for graph matching
VL - 2017
ER -
TY - CONF
AB - We propose a general dual ascent framework for Lagrangean decomposition of combinatorial problems. Although methods of this type have shown their efficiency for a number of problems, so far there was no general algorithm applicable to multiple problem types. In this work, we propose such a general algorithm. It depends on several parameters, which can be used to optimize its performance in each particular setting. We demonstrate efficacy of our method on graph matching and multicut problems, where it outperforms state-of-the-art solvers including those based on subgradient optimization and off-the-shelf linear programming solvers.
AU - Swoboda, Paul
AU - Kuske, Jan
AU - Savchynskyy, Bogdan
ID - 917
SN - 978-153860457-1
TI - A dual ascent framework for Lagrangean decomposition of combinatorial problems
VL - 2017
ER -
TY - THES
AB - An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of
variables, a finite domain of labels, and a set of constraints, each constraint acting on
a subset of the variables. The goal is to find an assignment of labels to its variables
that satisfies all constraints (or decide whether one exists). If we allow more general
“soft” constraints, which come with (possibly infinite) costs of particular assignments,
we obtain instances from a richer class called Valued Constraint Satisfaction Problem
(VCSP). There the goal is to find an assignment with minimum total cost.
In this thesis, we focus (assuming that P
6
=
NP) on classifying computational com-
plexity of CSPs and VCSPs under certain restricting conditions. Two results are the core
content of the work. In one of them, we consider VCSPs parametrized by a constraint
language, that is the set of “soft” constraints allowed to form the instances, and finish
the complexity classification modulo (missing pieces of) complexity classification for
analogously parametrized CSP. The other result is a generalization of Edmonds’ perfect
matching algorithm. This generalization contributes to complexity classfications in two
ways. First, it gives a new (largest known) polynomial-time solvable class of Boolean
CSPs in which every variable may appear in at most two constraints and second, it
settles full classification of Boolean CSPs with planar drawing (again parametrized by a
constraint language).
AU - Rolinek, Michal
ID - 992
TI - Complexity of constraint satisfaction
ER -
TY - JOUR
AB - We consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. Such CRFs can be naturally applied to many sequence tagging problems. We present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) is the number of input patterns. In addition, we give an efficient algorithm for sampling, and revisit the case of MAP with non-positive weights.
AU - Kolmogorov, Vladimir
AU - Takhanov, Rustem
ID - 1794
IS - 1
JF - Algorithmica
TI - Inference algorithms for pattern-based CRFs on sequence data
VL - 76
ER -
TY - DATA
AB - Small synthetic discrete tomography problems.
Sizes are 32x32, 64z64 and 256x256.
Projection angles are 2, 4, and 6.
Number of labels are 3 and 5.
AU - Swoboda, Paul
ID - 5557
KW - discrete tomography
TI - Synthetic discrete tomography problems
ER -
TY - JOUR
AB - We characterize absorption in finite idempotent algebras by means of Jónsson absorption and cube term blockers. As an application we show that it is decidable whether a given subset is an absorbing subuniverse of an algebra given by the tables of its basic operations.
AU - Barto, Libor
AU - Kazda, Alexandr
ID - 1353
IS - 5
JF - International Journal of Algebra and Computation
TI - Deciding absorption
VL - 26
ER -
TY - JOUR
AB - We consider the problem of minimizing the continuous valued total variation subject to different unary terms on trees and propose fast direct algorithms based on dynamic programming to solve these problems. We treat both the convex and the nonconvex case and derive worst-case complexities that are equal to or better than existing methods. We show applications to total variation based two dimensional image processing and computer vision problems based on a Lagrangian decomposition approach. The resulting algorithms are very effcient, offer a high degree of parallelism, and come along with memory requirements which are only in the order of the number of image pixels.
AU - Kolmogorov, Vladimir
AU - Pock, Thomas
AU - Rolinek, Michal
ID - 1377
IS - 2
JF - SIAM Journal on Imaging Sciences
TI - Total variation on a tree
VL - 9
ER -
TY - JOUR
AB - We prove that whenever A is a 3-conservative relational structure with only binary and unary relations,then the algebra of polymorphisms of A either has no Taylor operation (i.e.,CSP(A)is NP-complete),or it generates an SD(∧) variety (i.e.,CSP(A)has bounded width).
AU - Kazda, Alexandr
ID - 1612
IS - 1
JF - Algebra Universalis
TI - CSP for binary conservative relational structures
VL - 75
ER -
TY - CONF
AB - We consider the recent formulation of the Algorithmic Lovász Local Lemma [1], [2] for finding objects that avoid "bad features", or "flaws". It extends the Moser-Tardos resampling algorithm [3] to more general discrete spaces. At each step the method picks a flaw present in the current state and "resamples" it using a "resampling oracle" provided by the user. However, it is less flexible than the Moser-Tardos method since [1], [2] require a specific flaw selection rule, whereas [3] allows an arbitrary rule (and thus can potentially be implemented more efficiently). We formulate a new "commutativity" condition, and prove that it is sufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additional assumption. We then show that existing resampling oracles for perfect matchings and permutations do satisfy this condition. Finally, we generalize the precondition in [2] (in the case of symmetric potential causality graphs). This unifies special cases that previously were treated separately.
AU - Kolmogorov, Vladimir
ID - 1193
T2 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science
TI - Commutativity in the algorithmic Lovasz local lemma
VL - 2016-December
ER -
TY - CONF
AB - We study the time-and memory-complexities of the problem of computing labels of (multiple) randomly selected challenge-nodes in a directed acyclic graph. The w-bit label of a node is the hash of the labels of its parents, and the hash function is modeled as a random oracle. Specific instances of this problem underlie both proofs of space [Dziembowski et al. CRYPTO’15] as well as popular memory-hard functions like scrypt. As our main tool, we introduce the new notion of a probabilistic parallel entangled pebbling game, a new type of combinatorial pebbling game on a graph, which is closely related to the labeling game on the same graph. As a first application of our framework, we prove that for scrypt, when the underlying hash function is invoked n times, the cumulative memory complexity (CMC) (a notion recently introduced by Alwen and Serbinenko (STOC’15) to capture amortized memory-hardness for parallel adversaries) is at least Ω(w · (n/ log(n))2). This bound holds for adversaries that can store many natural functions of the labels (e.g., linear combinations), but still not arbitrary functions thereof. We then introduce and study a combinatorial quantity, and show how a sufficiently small upper bound on it (which we conjecture) extends our CMC bound for scrypt to hold against arbitrary adversaries. We also show that such an upper bound solves the main open problem for proofs-of-space protocols: namely, establishing that the time complexity of computing the label of a random node in a graph on n nodes (given an initial kw-bit state) reduces tightly to the time complexity for black pebbling on the same graph (given an initial k-node pebbling).
AU - Alwen, Joel F
AU - Chen, Binyi
AU - Kamath Hosdurg, Chethan
AU - Kolmogorov, Vladimir
AU - Pietrzak, Krzysztof Z
AU - Tessaro, Stefano
ID - 1231
TI - On the complexity of scrypt and proofs of space in the parallel random oracle model
VL - 9666
ER -
TY - JOUR
AB - A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. Finite-valued constraint languages contain functions that take on rational costs and general-valued constraint languages contain functions that take on rational or infinite costs. An instance of the problem is specified by a sum of functions from the language with the goal to minimise the sum. This framework includes and generalises well-studied constraint satisfaction problems (CSPs) and maximum constraint satisfaction problems (Max-CSPs).
Our main result is a precise algebraic characterisation of valued constraint languages whose instances can be solved exactly by the basic linear programming relaxation (BLP). For a general-valued constraint language Γ, BLP is a decision procedure for Γ if and only if Γ admits a symmetric fractional polymorphism of every arity. For a finite-valued constraint language Γ, BLP is a decision procedure if and only if Γ admits a symmetric fractional polymorphism of some arity, or equivalently, if Γ admits a symmetric fractional polymorphism of arity 2.
Using these results, we obtain tractability of several novel and previously widely-open classes of VCSPs, including problems over valued constraint languages that are: (1) submodular on arbitrary lattices; (2) bisubmodular (also known as k-submodular) on arbitrary finite domains; (3) weakly (and hence strongly) tree-submodular on arbitrary trees.
AU - Kolmogorov, Vladimir
AU - Thapper, Johan
AU - Živný, Stanislav
ID - 2271
IS - 1
JF - SIAM Journal on Computing
TI - The power of linear programming for general-valued CSPs
VL - 44
ER -