--- _id: '1794' abstract: - lang: eng text: 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. acknowledgement: This work has been partially supported by the European Research Council under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 616160. author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Rustem full_name: Takhanov, Rustem id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87 last_name: Takhanov citation: ama: Kolmogorov V, Takhanov R. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 2016;76(1):17-46. doi:10.1007/s00453-015-0017-7 apa: Kolmogorov, V., & Takhanov, R. (2016). Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. Springer. https://doi.org/10.1007/s00453-015-0017-7 chicago: Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica. Springer, 2016. https://doi.org/10.1007/s00453-015-0017-7. ieee: V. Kolmogorov and R. Takhanov, “Inference algorithms for pattern-based CRFs on sequence data,” Algorithmica, vol. 76, no. 1. Springer, pp. 17–46, 2016. ista: Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 76(1), 17–46. mla: Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica, vol. 76, no. 1, Springer, 2016, pp. 17–46, doi:10.1007/s00453-015-0017-7. short: V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46. date_created: 2018-12-11T11:54:02Z date_published: 2016-09-01T00:00:00Z date_updated: 2023-10-17T09:51:31Z day: '01' department: - _id: VlKo doi: 10.1007/s00453-015-0017-7 ec_funded: 1 external_id: arxiv: - '1210.0508' intvolume: ' 76' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1210.0508 month: '09' oa: 1 oa_version: Preprint page: 17 - 46 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication: Algorithmica publication_status: published publisher: Springer publist_id: '5316' quality_controlled: '1' related_material: record: - id: '2272' relation: earlier_version status: public scopus_import: 1 status: public title: Inference algorithms for pattern-based CRFs on sequence data type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 76 year: '2016' ... --- _id: '5557' abstract: - lang: eng text: "Small synthetic discrete tomography problems.\r\nSizes are 32x32, 64z64 and 256x256.\r\nProjection angles are 2, 4, and 6.\r\nNumber of labels are 3 and 5." article_processing_charge: No author: - first_name: Paul full_name: Swoboda, Paul id: 446560C6-F248-11E8-B48F-1D18A9856A87 last_name: Swoboda citation: ama: Swoboda P. Synthetic discrete tomography problems. 2016. doi:10.15479/AT:ISTA:46 apa: Swoboda, P. (2016). Synthetic discrete tomography problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:46 chicago: Swoboda, Paul. “Synthetic Discrete Tomography Problems.” Institute of Science and Technology Austria, 2016. https://doi.org/10.15479/AT:ISTA:46. ieee: P. Swoboda, “Synthetic discrete tomography problems.” Institute of Science and Technology Austria, 2016. ista: Swoboda P. 2016. Synthetic discrete tomography problems, Institute of Science and Technology Austria, 10.15479/AT:ISTA:46. mla: Swoboda, Paul. Synthetic Discrete Tomography Problems. Institute of Science and Technology Austria, 2016, doi:10.15479/AT:ISTA:46. short: P. Swoboda, (2016). contributor: - contributor_type: data_collector first_name: Jan last_name: Kuske datarep_id: '46' date_created: 2018-12-12T12:31:31Z date_published: 2016-09-20T00:00:00Z date_updated: 2024-02-21T13:50:21Z day: '20' ddc: - '006' department: - _id: VlKo doi: 10.15479/AT:ISTA:46 file: - access_level: open_access checksum: aa5a16a0dc888da7186fb8fc45e88439 content_type: application/zip creator: system date_created: 2018-12-12T13:05:19Z date_updated: 2020-07-14T12:47:02Z file_id: '5645' file_name: IST-2016-46-v1+1_discrete_tomography_synthetic.zip file_size: 36058401 relation: main_file file_date_updated: 2020-07-14T12:47:02Z has_accepted_license: '1' keyword: - discrete tomography license: https://creativecommons.org/publicdomain/zero/1.0/ month: '09' oa: 1 oa_version: Published Version publisher: Institute of Science and Technology Austria status: public title: Synthetic discrete tomography problems tmp: image: /images/cc_0.png legal_code_url: https://creativecommons.org/publicdomain/zero/1.0/legalcode name: Creative Commons Public Domain Dedication (CC0 1.0) short: CC0 (1.0) type: research_data user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2016' ... --- _id: '1636' abstract: - lang: eng text: "Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem that appears in many areas of Computer Science. It can be equivalently stated as computing a homomorphism R→ΓΓ between two relational structures, e.g. between two directed graphs. Analyzing its complexity has been a prominent research direction, especially for the fixed template CSPs where the right side ΓΓ is fixed and the left side R is unconstrained.\r\n\r\nFar fewer results are known for the hybrid setting that restricts both sides simultaneously. It assumes that R belongs to a certain class of relational structures (called a structural restriction in this paper). We study which structural restrictions are effective, i.e. there exists a fixed template ΓΓ (from a certain class of languages) for which the problem is tractable when R is restricted, and NP-hard otherwise. We provide a characterization for structural restrictions that are closed under inverse homomorphisms. The criterion is based on the chromatic number of a relational structure defined in this paper; it generalizes the standard chromatic number of a graph.\r\n\r\nAs our main tool, we use the algebraic machinery developed for fixed template CSPs. To apply it to our case, we introduce a new construction called a “lifted language”. We also give a characterization for structural restrictions corresponding to minor-closed families of graphs, extend results to certain Valued CSPs (namely conservative valued languages), and state implications for (valued) CSPs with ordered variables and for the maximum weight independent set problem on some restricted families of graphs." alternative_title: - LNCS article_processing_charge: No author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Michal full_name: Rolinek, Michal id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87 last_name: Rolinek - first_name: Rustem full_name: Takhanov, Rustem last_name: Takhanov citation: ama: 'Kolmogorov V, Rolinek M, Takhanov R. Effectiveness of structural restrictions for hybrid CSPs. In: 26th International Symposium. Vol 9472. Springer Nature; 2015:566-577. doi:10.1007/978-3-662-48971-0_48' apa: 'Kolmogorov, V., Rolinek, M., & Takhanov, R. (2015). Effectiveness of structural restrictions for hybrid CSPs. In 26th International Symposium (Vol. 9472, pp. 566–577). Nagoya, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-48971-0_48' chicago: Kolmogorov, Vladimir, Michal Rolinek, and Rustem Takhanov. “Effectiveness of Structural Restrictions for Hybrid CSPs.” In 26th International Symposium, 9472:566–77. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-48971-0_48. ieee: V. Kolmogorov, M. Rolinek, and R. Takhanov, “Effectiveness of structural restrictions for hybrid CSPs,” in 26th International Symposium, Nagoya, Japan, 2015, vol. 9472, pp. 566–577. ista: 'Kolmogorov V, Rolinek M, Takhanov R. 2015. Effectiveness of structural restrictions for hybrid CSPs. 26th International Symposium. ISAAC: International Symposium on Algorithms and Computation, LNCS, vol. 9472, 566–577.' mla: Kolmogorov, Vladimir, et al. “Effectiveness of Structural Restrictions for Hybrid CSPs.” 26th International Symposium, vol. 9472, Springer Nature, 2015, pp. 566–77, doi:10.1007/978-3-662-48971-0_48. short: V. Kolmogorov, M. Rolinek, R. Takhanov, in:, 26th International Symposium, Springer Nature, 2015, pp. 566–577. conference: end_date: 2015-12-11 location: Nagoya, Japan name: 'ISAAC: International Symposium on Algorithms and Computation' start_date: 2015-12-09 date_created: 2018-12-11T11:53:10Z date_published: 2015-12-01T00:00:00Z date_updated: 2022-02-01T15:12:35Z day: '01' department: - _id: VlKo doi: 10.1007/978-3-662-48971-0_48 ec_funded: 1 external_id: arxiv: - '1504.07067' intvolume: ' 9472' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1504.07067 month: '12' oa: 1 oa_version: Preprint page: 566 - 577 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication: 26th International Symposium publication_identifier: isbn: - 978-3-662-48970-3 publication_status: published publisher: Springer Nature publist_id: '5519' quality_controlled: '1' scopus_import: '1' status: public title: Effectiveness of structural restrictions for hybrid CSPs type: conference user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9 volume: 9472 year: '2015' ... --- _id: '1841' abstract: - lang: eng text: We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diffusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. The new family of algorithms can be viewed as a generalization of TRW-S from pairwise to higher-order graphical models. We test SRMP on several real-world problems with promising results. author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: Kolmogorov V. A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2015;37(5):919-930. doi:10.1109/TPAMI.2014.2363465 apa: Kolmogorov, V. (2015). A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. https://doi.org/10.1109/TPAMI.2014.2363465 chicago: Kolmogorov, Vladimir. “A New Look at Reweighted Message Passing.” IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE, 2015. https://doi.org/10.1109/TPAMI.2014.2363465. ieee: V. Kolmogorov, “A new look at reweighted message passing,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 5. IEEE, pp. 919–930, 2015. ista: Kolmogorov V. 2015. A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence. 37(5), 919–930. mla: Kolmogorov, Vladimir. “A New Look at Reweighted Message Passing.” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 5, IEEE, 2015, pp. 919–30, doi:10.1109/TPAMI.2014.2363465. short: V. Kolmogorov, IEEE Transactions on Pattern Analysis and Machine Intelligence 37 (2015) 919–930. date_created: 2018-12-11T11:54:18Z date_published: 2015-05-01T00:00:00Z date_updated: 2021-01-12T06:53:33Z day: '01' department: - _id: VlKo doi: 10.1109/TPAMI.2014.2363465 ec_funded: 1 intvolume: ' 37' issue: '5' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1309.5655 month: '05' oa: 1 oa_version: Preprint page: 919 - 930 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication: IEEE Transactions on Pattern Analysis and Machine Intelligence publication_status: published publisher: IEEE publist_id: '5261' quality_controlled: '1' scopus_import: 1 status: public title: A new look at reweighted message passing type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 37 year: '2015' ... --- _id: '1859' abstract: - lang: eng text: "Structural support vector machines (SSVMs) are amongst the best performing models for structured computer vision tasks, such as semantic image segmentation or human pose estimation. Training SSVMs, however, is computationally costly, because it requires repeated calls to a structured prediction subroutine (called \\emph{max-oracle}), which has to solve an optimization problem itself, e.g. a graph cut.\r\nIn this work, we introduce a new algorithm for SSVM training that is more efficient than earlier techniques when the max-oracle is computationally expensive, as it is frequently the case in computer vision tasks. The main idea is to (i) combine the recent stochastic Block-Coordinate Frank-Wolfe algorithm with efficient hyperplane caching, and (ii) use an automatic selection rule for deciding whether to call the exact max-oracle or to rely on an approximate one based on the cached hyperplanes.\r\nWe show experimentally that this strategy leads to faster convergence to the optimum with respect to the number of requires oracle calls, and that this translates into faster convergence with respect to the total runtime when the max-oracle is slow compared to the other steps of the algorithm. " author: - first_name: Neel full_name: Shah, Neel id: 31ABAF80-F248-11E8-B48F-1D18A9856A87 last_name: Shah - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Christoph full_name: Lampert, Christoph id: 40C20FD2-F248-11E8-B48F-1D18A9856A87 last_name: Lampert orcid: 0000-0001-8622-7887 citation: ama: 'Shah N, Kolmogorov V, Lampert C. A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle. In: IEEE; 2015:2737-2745. doi:10.1109/CVPR.2015.7298890' apa: 'Shah, N., Kolmogorov, V., & Lampert, C. (2015). A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle (pp. 2737–2745). Presented at the CVPR: Computer Vision and Pattern Recognition, Boston, MA, USA: IEEE. https://doi.org/10.1109/CVPR.2015.7298890' chicago: Shah, Neel, Vladimir Kolmogorov, and Christoph Lampert. “A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly Max-Oracle,” 2737–45. IEEE, 2015. https://doi.org/10.1109/CVPR.2015.7298890. ieee: 'N. Shah, V. Kolmogorov, and C. Lampert, “A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle,” presented at the CVPR: Computer Vision and Pattern Recognition, Boston, MA, USA, 2015, pp. 2737–2745.' ista: 'Shah N, Kolmogorov V, Lampert C. 2015. A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle. CVPR: Computer Vision and Pattern Recognition, 2737–2745.' mla: Shah, Neel, et al. A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly Max-Oracle. IEEE, 2015, pp. 2737–45, doi:10.1109/CVPR.2015.7298890. short: N. Shah, V. Kolmogorov, C. Lampert, in:, IEEE, 2015, pp. 2737–2745. conference: end_date: 2015-06-12 location: Boston, MA, USA name: 'CVPR: Computer Vision and Pattern Recognition' start_date: 2015-06-07 date_created: 2018-12-11T11:54:24Z date_published: 2015-06-01T00:00:00Z date_updated: 2021-01-12T06:53:40Z day: '01' department: - _id: VlKo - _id: ChLa doi: 10.1109/CVPR.2015.7298890 ec_funded: 1 language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1408.6804 month: '06' oa: 1 oa_version: Preprint page: 2737 - 2745 project: - _id: 2532554C-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '308036' name: Lifelong Learning of Visual Scene Understanding - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication_status: published publisher: IEEE publist_id: '5240' quality_controlled: '1' scopus_import: 1 status: public title: A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ... --- _id: '2271' abstract: - lang: eng text: "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).\r\nOur 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.\r\nUsing 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. " author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Johan full_name: Thapper, Johan last_name: Thapper - first_name: Stanislav full_name: Živný, Stanislav last_name: Živný citation: ama: Kolmogorov V, Thapper J, Živný S. The power of linear programming for general-valued CSPs. SIAM Journal on Computing. 2015;44(1):1-36. doi:10.1137/130945648 apa: Kolmogorov, V., Thapper, J., & Živný, S. (2015). The power of linear programming for general-valued CSPs. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/130945648 chicago: Kolmogorov, Vladimir, Johan Thapper, and Stanislav Živný. “The Power of Linear Programming for General-Valued CSPs.” SIAM Journal on Computing. SIAM, 2015. https://doi.org/10.1137/130945648. ieee: V. Kolmogorov, J. Thapper, and S. Živný, “The power of linear programming for general-valued CSPs,” SIAM Journal on Computing, vol. 44, no. 1. SIAM, pp. 1–36, 2015. ista: Kolmogorov V, Thapper J, Živný S. 2015. The power of linear programming for general-valued CSPs. SIAM Journal on Computing. 44(1), 1–36. mla: Kolmogorov, Vladimir, et al. “The Power of Linear Programming for General-Valued CSPs.” SIAM Journal on Computing, vol. 44, no. 1, SIAM, 2015, pp. 1–36, doi:10.1137/130945648. short: V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015) 1–36. date_created: 2018-12-11T11:56:41Z date_published: 2015-02-01T00:00:00Z date_updated: 2023-02-23T10:46:30Z day: '01' department: - _id: VlKo doi: 10.1137/130945648 external_id: arxiv: - '1311.4219' intvolume: ' 44' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1311.4219 month: '02' oa: 1 oa_version: Preprint page: 1 - 36 publication: SIAM Journal on Computing publication_status: published publisher: SIAM publist_id: '4673' quality_controlled: '1' related_material: record: - id: '2518' relation: earlier_version status: public scopus_import: 1 status: public title: The power of linear programming for general-valued CSPs type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 44 year: '2015' ... --- _id: '1637' abstract: - lang: eng text: 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 ≠ 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 {0, ∞} 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 NP-hard. The case when all allowed functions take only finite values corresponds to finite-valued 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 Zivny. 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. alternative_title: - 56th Annual Symposium on Foundations of Computer Science author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Andrei full_name: Krokhin, Andrei last_name: Krokhin - first_name: Michal full_name: Rolinek, Michal id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87 last_name: Rolinek citation: ama: 'Kolmogorov V, Krokhin A, Rolinek M. The complexity of general-valued CSPs. In: IEEE; 2015:1246-1258. doi:10.1109/FOCS.2015.80' apa: 'Kolmogorov, V., Krokhin, A., & Rolinek, M. (2015). The complexity of general-valued CSPs (pp. 1246–1258). Presented at the FOCS: Foundations of Computer Science, Berkeley, CA, United States: IEEE. https://doi.org/10.1109/FOCS.2015.80' chicago: Kolmogorov, Vladimir, Andrei Krokhin, and Michal Rolinek. “The Complexity of General-Valued CSPs,” 1246–58. IEEE, 2015. https://doi.org/10.1109/FOCS.2015.80. ieee: 'V. Kolmogorov, A. Krokhin, and M. Rolinek, “The complexity of general-valued CSPs,” presented at the FOCS: Foundations of Computer Science, Berkeley, CA, United States, 2015, pp. 1246–1258.' ista: 'Kolmogorov V, Krokhin A, Rolinek M. 2015. The complexity of general-valued CSPs. FOCS: Foundations of Computer Science, 56th Annual Symposium on Foundations of Computer Science, , 1246–1258.' mla: Kolmogorov, Vladimir, et al. The Complexity of General-Valued CSPs. IEEE, 2015, pp. 1246–58, doi:10.1109/FOCS.2015.80. short: V. Kolmogorov, A. Krokhin, M. Rolinek, in:, IEEE, 2015, pp. 1246–1258. conference: end_date: 2015-10-20 location: Berkeley, CA, United States name: 'FOCS: Foundations of Computer Science' start_date: 2015-10-18 date_created: 2018-12-11T11:53:10Z date_published: 2015-12-01T00:00:00Z date_updated: 2023-02-23T12:44:26Z day: '01' department: - _id: VlKo doi: 10.1109/FOCS.2015.80 ec_funded: 1 language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1502.07327 month: '12' oa: 1 oa_version: Preprint page: 1246 - 1258 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication_status: published publisher: IEEE publist_id: '5518' quality_controlled: '1' related_material: record: - id: '644' relation: other status: public scopus_import: 1 status: public title: The complexity of general-valued CSPs type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ... --- _id: '1675' abstract: - lang: eng text: Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system. In this work, we put forward an alternative concept for PoWs - so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model (with one additional mild assumption required for the proof to go through), using graphs with high “pebbling complexity” and Merkle hash-trees. We discuss some applications, including follow-up work where a decentralized digital currency scheme called Spacecoin is constructed that uses PoS (instead of wasteful PoW like in Bitcoin) to prevent double spending. The main technical contribution of this work is the construction of (directed, loop-free) graphs on N vertices with in-degree O(log logN) such that even if one places Θ(N) pebbles on the nodes of the graph, there’s a constant fraction of nodes that needs Θ(N) steps to be pebbled (where in every step one can put a pebble on a node if all its parents have a pebble). alternative_title: - LNCS article_processing_charge: No author: - first_name: Stefan full_name: Dziembowski, Stefan last_name: Dziembowski - first_name: Sebastian full_name: Faust, Sebastian last_name: Faust - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 citation: ama: 'Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. Proofs of space. In: 35th Annual Cryptology Conference. Vol 9216. Springer; 2015:585-605. doi:10.1007/978-3-662-48000-7_29' apa: 'Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2015). Proofs of space. In 35th Annual Cryptology Conference (Vol. 9216, pp. 585–605). Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-662-48000-7_29' chicago: Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Z Pietrzak. “Proofs of Space.” In 35th Annual Cryptology Conference, 9216:585–605. Springer, 2015. https://doi.org/10.1007/978-3-662-48000-7_29. ieee: S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, “Proofs of space,” in 35th Annual Cryptology Conference, Santa Barbara, CA, United States, 2015, vol. 9216, pp. 585–605. ista: 'Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2015. Proofs of space. 35th Annual Cryptology Conference. CRYPTO: International Cryptology Conference, LNCS, vol. 9216, 585–605.' mla: Dziembowski, Stefan, et al. “Proofs of Space.” 35th Annual Cryptology Conference, vol. 9216, Springer, 2015, pp. 585–605, doi:10.1007/978-3-662-48000-7_29. short: S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, in:, 35th Annual Cryptology Conference, Springer, 2015, pp. 585–605. conference: end_date: 2015-08-20 location: Santa Barbara, CA, United States name: 'CRYPTO: International Cryptology Conference' start_date: 2015-08-16 date_created: 2018-12-11T11:53:24Z date_published: 2015-08-01T00:00:00Z date_updated: 2024-03-20T08:31:49Z day: '01' department: - _id: VlKo - _id: KrPi doi: 10.1007/978-3-662-48000-7_29 ec_funded: 1 intvolume: ' 9216' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2013/796.pdf month: '08' oa: 1 oa_version: Preprint page: 585 - 605 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography publication: 35th Annual Cryptology Conference publication_identifier: isbn: - '9783662479995' issn: - 0302-9743 publication_status: published publisher: Springer publist_id: '5474' pubrep_id: '671' quality_controlled: '1' related_material: record: - id: '2274' relation: earlier_version status: public scopus_import: '1' status: public title: Proofs of space type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9216 year: '2015' ... --- _id: '2275' abstract: - lang: eng text: "Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. \r\nThis partial enumeration technique reduces complex high-order energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. \r\nOur main application of interest is curvature regularization. In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach.\r\n" author: - first_name: Carl full_name: Olsson, Carl last_name: Olsson - first_name: Johannes full_name: Ulen, Johannes last_name: Ulen - first_name: Yuri full_name: Boykov, Yuri last_name: Boykov - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Olsson C, Ulen J, Boykov Y, Kolmogorov V. Partial enumeration and curvature regularization. In: IEEE; 2014:2936-2943. doi:10.1109/ICCV.2013.365' apa: 'Olsson, C., Ulen, J., Boykov, Y., & Kolmogorov, V. (2014). Partial enumeration and curvature regularization (pp. 2936–2943). Presented at the ICCV: International Conference on Computer Vision, Sydney, Australia: IEEE. https://doi.org/10.1109/ICCV.2013.365' chicago: Olsson, Carl, Johannes Ulen, Yuri Boykov, and Vladimir Kolmogorov. “Partial Enumeration and Curvature Regularization,” 2936–43. IEEE, 2014. https://doi.org/10.1109/ICCV.2013.365. ieee: 'C. Olsson, J. Ulen, Y. Boykov, and V. Kolmogorov, “Partial enumeration and curvature regularization,” presented at the ICCV: International Conference on Computer Vision, Sydney, Australia, 2014, pp. 2936–2943.' ista: 'Olsson C, Ulen J, Boykov Y, Kolmogorov V. 2014. Partial enumeration and curvature regularization. ICCV: International Conference on Computer Vision, 2936–2943.' mla: Olsson, Carl, et al. Partial Enumeration and Curvature Regularization. IEEE, 2014, pp. 2936–43, doi:10.1109/ICCV.2013.365. short: C. Olsson, J. Ulen, Y. Boykov, V. Kolmogorov, in:, IEEE, 2014, pp. 2936–2943. conference: end_date: 2013-12-08 location: Sydney, Australia name: 'ICCV: International Conference on Computer Vision' start_date: 2013-12-01 date_created: 2018-12-11T11:56:42Z date_published: 2014-03-03T00:00:00Z date_updated: 2021-01-12T06:56:28Z day: '03' ddc: - '000' department: - _id: VlKo doi: 10.1109/ICCV.2013.365 file: - access_level: open_access checksum: 4a74b5c92d6dcd2348c2c10ec8dd18bf content_type: application/pdf creator: system date_created: 2018-12-12T10:09:30Z date_updated: 2020-07-14T12:45:36Z file_id: '4754' file_name: IST-2016-566-v1+1_iccv13_part_enumeration.pdf file_size: 378601 relation: main_file file_date_updated: 2020-07-14T12:45:36Z has_accepted_license: '1' language: - iso: eng month: '03' oa: 1 oa_version: Submitted Version page: 2936 - 2943 publication_status: published publisher: IEEE publist_id: '4669' pubrep_id: '566' quality_controlled: '1' scopus_import: 1 status: public title: Partial enumeration and curvature regularization type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '7038' article_processing_charge: No author: - first_name: Kristóf full_name: Huszár, Kristóf id: 33C26278-F248-11E8-B48F-1D18A9856A87 last_name: Huszár orcid: 0000-0002-5445-5057 - first_name: Michal full_name: Rolinek, Michal id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87 last_name: Rolinek citation: ama: Huszár K, Rolinek M. Playful Math - An Introduction to Mathematical Games. IST Austria apa: Huszár, K., & Rolinek, M. (n.d.). Playful Math - An introduction to mathematical games. IST Austria. chicago: Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction to Mathematical Games. IST Austria, n.d. ieee: K. Huszár and M. Rolinek, Playful Math - An introduction to mathematical games. IST Austria. ista: Huszár K, Rolinek M. Playful Math - An introduction to mathematical games, IST Austria, 5p. mla: Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction to Mathematical Games. IST Austria. short: K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games, IST Austria, n.d. date_created: 2019-11-18T15:57:05Z date_published: 2014-06-30T00:00:00Z date_updated: 2020-07-14T23:11:45Z day: '30' ddc: - '510' department: - _id: VlKo - _id: UlWa file: - access_level: open_access checksum: 2b94e5e1f4c3fe8ab89b12806276fb09 content_type: application/pdf creator: dernst date_created: 2019-11-18T15:57:51Z date_updated: 2020-07-14T12:47:48Z file_id: '7039' file_name: 2014_Playful_Math_Huszar.pdf file_size: 511233 relation: main_file file_date_updated: 2020-07-14T12:47:48Z has_accepted_license: '1' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: '5' publication_status: draft publisher: IST Austria status: public title: Playful Math - An introduction to mathematical games type: working_paper user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '2270' abstract: - lang: eng text: "Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inher-\r\nent tradeoff between how general a language is, allowing it to capture more elaborate games, and how hard \ it is computationally to optimize and solve such games. One prominent such \ language is the simple yet expressive\r\nWeighted Graph Games (WGGs) representation (Deng and Papadimitriou 1994), which maintains knowledge about synergies between agents in the form of an edge weighted graph. We consider the problem of finding \ the optimal coalition structure in WGGs. The agents in such games are vertices in a graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. \ We then provide algorithms with constant factor approximations for planar, minorfree and bounded degree graphs." author: - first_name: Yoram full_name: Bachrach, Yoram last_name: Bachrach - first_name: Pushmeet full_name: Kohli, Pushmeet last_name: Kohli - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Morteza full_name: Zadimoghaddam, Morteza last_name: Zadimoghaddam citation: ama: 'Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. Optimal Coalition Structures in Cooperative Graph Games. In: AAAI Press; 2013:81-87.' apa: 'Bachrach, Y., Kohli, P., Kolmogorov, V., & Zadimoghaddam, M. (2013). Optimal Coalition Structures in Cooperative Graph Games (pp. 81–87). Presented at the AAAI: Conference on Artificial Intelligence, Bellevue, WA, United States: AAAI Press.' chicago: Bachrach, Yoram, Pushmeet Kohli, Vladimir Kolmogorov, and Morteza Zadimoghaddam. “Optimal Coalition Structures in Cooperative Graph Games,” 81–87. AAAI Press, 2013. ieee: 'Y. Bachrach, P. Kohli, V. Kolmogorov, and M. Zadimoghaddam, “Optimal Coalition Structures in Cooperative Graph Games,” presented at the AAAI: Conference on Artificial Intelligence, Bellevue, WA, United States, 2013, pp. 81–87.' ista: 'Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. 2013. Optimal Coalition Structures in Cooperative Graph Games. AAAI: Conference on Artificial Intelligence, 81–87.' mla: Bachrach, Yoram, et al. Optimal Coalition Structures in Cooperative Graph Games. AAAI Press, 2013, pp. 81–87. short: Y. Bachrach, P. Kohli, V. Kolmogorov, M. Zadimoghaddam, in:, AAAI Press, 2013, pp. 81–87. conference: end_date: 2013-07-18 location: Bellevue, WA, United States name: 'AAAI: Conference on Artificial Intelligence' start_date: 2013-07-14 date_created: 2018-12-11T11:56:41Z date_published: 2013-12-31T00:00:00Z date_updated: 2021-01-12T06:56:25Z day: '31' department: - _id: VlKo external_id: arxiv: - '1108.5248' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1108.5248 month: '12' oa: 1 oa_version: None page: 81-87 publication_status: published publisher: AAAI Press publist_id: '4674' quality_controlled: '1' status: public title: Optimal Coalition Structures in Cooperative Graph Games type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '2273' abstract: - lang: eng text: We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. We present such a generalization for the case of higher-order graphical models, and test it on several real-world problems with promising results. author: - first_name: Vladimir full_name: Vladimir Kolmogorov id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: Kolmogorov V. Reweighted Message Passing Revisited. IST Austria; 2013. apa: Kolmogorov, V. (2013). Reweighted message passing revisited. IST Austria. chicago: Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST Austria, 2013. ieee: V. Kolmogorov, Reweighted message passing revisited. IST Austria, 2013. ista: Kolmogorov V. 2013. Reweighted message passing revisited, IST Austria,p. mla: Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST Austria, 2013. short: V. Kolmogorov, Reweighted Message Passing Revisited, IST Austria, 2013. date_created: 2018-12-11T11:56:42Z date_published: 2013-09-22T00:00:00Z date_updated: 2019-01-24T13:07:32Z day: '22' department: - _id: VlKo extern: 0 main_file_link: - open_access: '1' url: http://arxiv.org/abs/1309.5655 month: '09' oa: 1 publication_status: published publisher: IST Austria publist_id: '4671' quality_controlled: 0 status: public title: Reweighted message passing revisited type: report year: '2013' ... --- _id: '2276' abstract: - lang: eng text: The problem of minimizing the Potts energy function frequently occurs in computer vision applications. One way to tackle this NP-hard problem was proposed by Kovtun [19, 20]. It identifies a part of an optimal solution by running k maxflow computations, where k is the number of labels. The number of “labeled” pixels can be significant in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce the runtime to O (log k) maxflow computations (or one parametric maxflow computation). Furthermore, the output of our algorithm allows to speed-up the subsequent alpha expansion for the unlabeled part, or can be used as it is for time-critical applications. To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7] for Tree Metrics . We also show a connection to k-submodular functions from combinatorial optimization, and discuss k-submodular relaxations for general energy functions. author: - first_name: Igor full_name: Gridchyn, Igor id: 4B60654C-F248-11E8-B48F-1D18A9856A87 last_name: Gridchyn - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Gridchyn I, Kolmogorov V. Potts model, parametric maxflow and k-submodular functions. In: IEEE; 2013:2320-2327. doi:10.1109/ICCV.2013.288' apa: 'Gridchyn, I., & Kolmogorov, V. (2013). Potts model, parametric maxflow and k-submodular functions (pp. 2320–2327). Presented at the ICCV: International Conference on Computer Vision, Sydney, Australia: IEEE. https://doi.org/10.1109/ICCV.2013.288' chicago: Gridchyn, Igor, and Vladimir Kolmogorov. “Potts Model, Parametric Maxflow and k-Submodular Functions,” 2320–27. IEEE, 2013. https://doi.org/10.1109/ICCV.2013.288. ieee: 'I. Gridchyn and V. Kolmogorov, “Potts model, parametric maxflow and k-submodular functions,” presented at the ICCV: International Conference on Computer Vision, Sydney, Australia, 2013, pp. 2320–2327.' ista: 'Gridchyn I, Kolmogorov V. 2013. Potts model, parametric maxflow and k-submodular functions. ICCV: International Conference on Computer Vision, 2320–2327.' mla: Gridchyn, Igor, and Vladimir Kolmogorov. Potts Model, Parametric Maxflow and k-Submodular Functions. IEEE, 2013, pp. 2320–27, doi:10.1109/ICCV.2013.288. short: I. Gridchyn, V. Kolmogorov, in:, IEEE, 2013, pp. 2320–2327. conference: end_date: 2013-12-08 location: Sydney, Australia name: 'ICCV: International Conference on Computer Vision' start_date: 2013-12-01 date_created: 2018-12-11T11:56:43Z date_published: 2013-12-01T00:00:00Z date_updated: 2021-01-12T06:56:28Z day: '01' department: - _id: JoCs - _id: VlKo doi: 10.1109/ICCV.2013.288 external_id: arxiv: - '1310.1771' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1310.1771 month: '12' oa: 1 oa_version: Preprint page: 2320 - 2327 publication_status: published publisher: IEEE publist_id: '4668' quality_controlled: '1' status: public title: Potts model, parametric maxflow and k-submodular functions type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '2518' abstract: - lang: eng text: 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. An instance of the problem is specified by a sum of cost functions from the language with the goal to minimise the sum. We study which classes of finite-valued languages can be solved exactly by the basic linear programming relaxation (BLP). Thapper and Živný showed [20] that if BLP solves the language then the language admits a binary commutative fractional polymorphism. We prove that the converse is also true. This leads to a necessary and a sufficient condition which can be checked in polynomial time for a given language. In contrast, the previous necessary and sufficient condition due to [20] involved infinitely many inequalities. More recently, Thapper and Živný [21] showed (using, in particular, a technique introduced in this paper) that core languages that do not satisfy our condition are NP-hard. Taken together, these results imply that a finite-valued language can either be solved using Linear Programming or is NP-hard. alternative_title: - LNCS author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Kolmogorov V. The power of linear programming for finite-valued CSPs: A constructive characterization. In: Vol 7965. Springer; 2013:625-636. doi:10.1007/978-3-642-39206-1_53' apa: 'Kolmogorov, V. (2013). The power of linear programming for finite-valued CSPs: A constructive characterization (Vol. 7965, pp. 625–636). Presented at the ICALP: Automata, Languages and Programming, Riga, Latvia: Springer. https://doi.org/10.1007/978-3-642-39206-1_53' chicago: 'Kolmogorov, Vladimir. “The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization,” 7965:625–36. Springer, 2013. https://doi.org/10.1007/978-3-642-39206-1_53.' ieee: 'V. Kolmogorov, “The power of linear programming for finite-valued CSPs: A constructive characterization,” presented at the ICALP: Automata, Languages and Programming, Riga, Latvia, 2013, vol. 7965, no. 1, pp. 625–636.' ista: 'Kolmogorov V. 2013. The power of linear programming for finite-valued CSPs: A constructive characterization. ICALP: Automata, Languages and Programming, LNCS, vol. 7965, 625–636.' mla: 'Kolmogorov, Vladimir. The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization. Vol. 7965, no. 1, Springer, 2013, pp. 625–36, doi:10.1007/978-3-642-39206-1_53.' short: V. Kolmogorov, in:, Springer, 2013, pp. 625–636. conference: end_date: 2013-07-12 location: Riga, Latvia name: 'ICALP: Automata, Languages and Programming' start_date: 2013-07-08 date_created: 2018-12-11T11:58:08Z date_published: 2013-07-01T00:00:00Z date_updated: 2023-02-23T10:35:42Z day: '01' department: - _id: VlKo doi: 10.1007/978-3-642-39206-1_53 external_id: arxiv: - '1207.7213' intvolume: ' 7965' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1207.7213 month: '07' oa: 1 oa_version: Preprint page: 625 - 636 publication_status: published publisher: Springer publist_id: '4383' quality_controlled: '1' related_material: record: - id: '2271' relation: later_version status: public scopus_import: 1 status: public title: 'The power of linear programming for finite-valued CSPs: A constructive characterization' type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 7965 year: '2013' ... --- _id: '2828' abstract: - lang: eng text: 'We study the complexity of valued constraint satisfaction problems (VCSPs) parametrized by a constraint language, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from the language and the goal is to minimize the sum. Under the unique games conjecture, the approximability of finite-valued VCSPs is well understood, see Raghavendra [2008]. However, there is no characterization of finite-valued VCSPs, let alone general-valued VCSPs, that can be solved exactly in polynomial time, thus giving insights from a combinatorial optimization perspective. We consider the case of languages containing all possible unary cost functions. In the case of languages consisting of only {0, ∞}-valued cost functions (i.e., relations), such languages have been called conservative and studied by Bulatov [2003, 2011] and recently by Barto [2011]. Since we study valued languages, we call a language conservative if it contains all finite-valued unary cost functions. The computational complexity of conservative valued languages has been studied by Cohen et al. [2006] for languages over Boolean domains, by Deineko et al. [2008] for {0, 1}-valued languages (a.k.a Max-CSP), and by Takhanov [2010a] for {0, ∞}-valued languages containing all finite-valued unary cost functions (a.k.a. Min-Cost-Hom). We prove a Schaefer-like dichotomy theorem for conservative valued languages: if all cost functions in the language satisfy a certain condition (specified by a complementary combination of STP and MJN multimor-phisms), then any instance can be solved in polynomial time (via a new algorithm developed in this article), otherwise the language is NP-hard. This is the first complete complexity classification of general-valued constraint languages over non-Boolean domains. It is a common phenomenon that complexity classifications of problems over non-Boolean domains are significantly harder than the Boolean cases. The polynomial-time algorithm we present for the tractable cases is a generalization of the submodular minimization problem and a result of Cohen et al. [2008]. Our results generalize previous results by Takhanov [2010a] and (a subset of results) by Cohen et al. [2006] and Deineko et al. [2008]. Moreover, our results do not rely on any computer-assisted search as in Deineko et al. [2008], and provide a powerful tool for proving hardness of finite-valued and general-valued languages.' article_number: '10' author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Stanislav full_name: Živný, Stanislav last_name: Živný citation: ama: Kolmogorov V, Živný S. The complexity of conservative valued CSPs. Journal of the ACM. 2013;60(2). doi:10.1145/2450142.2450146 apa: Kolmogorov, V., & Živný, S. (2013). The complexity of conservative valued CSPs. Journal of the ACM. ACM. https://doi.org/10.1145/2450142.2450146 chicago: Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative Valued CSPs.” Journal of the ACM. ACM, 2013. https://doi.org/10.1145/2450142.2450146. ieee: V. Kolmogorov and S. Živný, “The complexity of conservative valued CSPs,” Journal of the ACM, vol. 60, no. 2. ACM, 2013. ista: Kolmogorov V, Živný S. 2013. The complexity of conservative valued CSPs. Journal of the ACM. 60(2), 10. mla: Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative Valued CSPs.” Journal of the ACM, vol. 60, no. 2, 10, ACM, 2013, doi:10.1145/2450142.2450146. short: V. Kolmogorov, S. Živný, Journal of the ACM 60 (2013). date_created: 2018-12-11T11:59:48Z date_published: 2013-04-02T00:00:00Z date_updated: 2021-01-12T07:00:00Z day: '02' department: - _id: VlKo doi: 10.1145/2450142.2450146 external_id: arxiv: - '1110.2809' intvolume: ' 60' issue: '2' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1110.2809 month: '04' oa: 1 oa_version: Preprint publication: Journal of the ACM publication_status: published publisher: ACM publist_id: '3971' quality_controlled: '1' scopus_import: 1 status: public title: The complexity of conservative valued CSPs type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 60 year: '2013' ... --- _id: '2901' abstract: - lang: eng text: ' We introduce the M-modes problem for graphical models: predicting the M label configurations of highest probability that are at the same time local maxima of the probability landscape. M-modes have multiple possible applications: because they are intrinsically diverse, they provide a principled alternative to non-maximum suppression techniques for structured prediction, they can act as codebook vectors for quantizing the configuration space, or they can form component centers for mixture model approximation. We present two algorithms for solving the M-modes problem. The first algorithm solves the problem in polynomial time when the underlying graphical model is a simple chain. The second algorithm solves the problem for junction chains. In synthetic and real dataset, we demonstrate how M-modes can improve the performance of prediction. We also use the generated modes as a tool to understand the topography of the probability distribution of configurations, for example with relation to the training set size and amount of noise in the data. ' alternative_title: - ' JMLR: W&CP' author: - first_name: Chao full_name: Chen, Chao id: 3E92416E-F248-11E8-B48F-1D18A9856A87 last_name: Chen - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Zhu full_name: Yan, Zhu last_name: Yan - first_name: Dimitris full_name: Metaxas, Dimitris last_name: Metaxas - first_name: Christoph full_name: Lampert, Christoph id: 40C20FD2-F248-11E8-B48F-1D18A9856A87 last_name: Lampert orcid: 0000-0001-8622-7887 citation: ama: 'Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. Computing the M most probable modes of a graphical model. In: Vol 31. JMLR; 2013:161-169.' apa: 'Chen, C., Kolmogorov, V., Yan, Z., Metaxas, D., & Lampert, C. (2013). Computing the M most probable modes of a graphical model (Vol. 31, pp. 161–169). Presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States: JMLR.' chicago: Chen, Chao, Vladimir Kolmogorov, Zhu Yan, Dimitris Metaxas, and Christoph Lampert. “Computing the M Most Probable Modes of a Graphical Model,” 31:161–69. JMLR, 2013. ieee: 'C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, and C. Lampert, “Computing the M most probable modes of a graphical model,” presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States, 2013, vol. 31, pp. 161–169.' ista: 'Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. 2013. Computing the M most probable modes of a graphical model. AISTATS: Conference on Uncertainty in Artificial Intelligence, JMLR: W&CP, vol. 31, 161–169.' mla: Chen, Chao, et al. Computing the M Most Probable Modes of a Graphical Model. Vol. 31, JMLR, 2013, pp. 161–69. short: C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, C. Lampert, in:, JMLR, 2013, pp. 161–169. conference: end_date: 2013-05-01 location: Scottsdale, AZ, United States name: ' AISTATS: Conference on Uncertainty in Artificial Intelligence' start_date: 2013-04-29 date_created: 2018-12-11T12:00:14Z date_published: 2013-01-01T00:00:00Z date_updated: 2021-01-12T07:00:35Z day: '01' department: - _id: HeEd - _id: VlKo - _id: ChLa intvolume: ' 31' language: - iso: eng main_file_link: - open_access: '1' url: http://jmlr.org/proceedings/papers/v31/chen13a.html month: '01' oa: 1 oa_version: None page: 161 - 169 publication_status: published publisher: JMLR publist_id: '3846' quality_controlled: '1' scopus_import: 1 status: public title: Computing the M most probable modes of a graphical model type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 31 year: '2013' ... --- _id: '2272' abstract: - lang: eng text: "We consider Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x1...xn is the sum of terms over intervals [i,j] where each term is non-zero only if the substring xi...xj equals a prespecified pattern α. Such CRFs can be naturally applied to many sequence tagging problems.\r\nWe 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 O(nL), O(nLℓmax) and O(nLmin{|D|,log(ℓmax+1)}) where L is the combined length of input patterns, ℓmax is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of (Ye et al., 2009) whose complexities are respectively O(nL|D|), O(n|Γ|L2ℓ2max) and O(nL|D|), where |Γ| is the number of input patterns.\r\nIn addition, we give an efficient algorithm for sampling. Finally, we consider the case of non-positive weights. (Komodakis & Paragios, 2009) gave an O(nL) algorithm for computing the MAP. We present a modification that has the same worst-case complexity but can beat it in the best case. " alternative_title: - JMLR article_processing_charge: No author: - first_name: Rustem full_name: Takhanov, Rustem id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87 last_name: Takhanov - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Takhanov R, Kolmogorov V. Inference algorithms for pattern-based CRFs on sequence data. In: ICML’13 Proceedings of the 30th International Conference on International. Vol 28. ML Research Press; 2013:145-153.' apa: 'Takhanov, R., & Kolmogorov, V. (2013). Inference algorithms for pattern-based CRFs on sequence data. In ICML’13 Proceedings of the 30th International Conference on International (Vol. 28, pp. 145–153). Atlanta, GA, USA: ML Research Press.' chicago: Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” In ICML’13 Proceedings of the 30th International Conference on International, 28:145–53. ML Research Press, 2013. ieee: R. Takhanov and V. Kolmogorov, “Inference algorithms for pattern-based CRFs on sequence data,” in ICML’13 Proceedings of the 30th International Conference on International, Atlanta, GA, USA, 2013, vol. 28, no. 3, pp. 145–153. ista: 'Takhanov R, Kolmogorov V. 2013. Inference algorithms for pattern-based CRFs on sequence data. ICML’13 Proceedings of the 30th International Conference on International. ICML: International Conference on Machine Learning, JMLR, vol. 28, 145–153.' mla: Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” ICML’13 Proceedings of the 30th International Conference on International, vol. 28, no. 3, ML Research Press, 2013, pp. 145–53. short: R. Takhanov, V. Kolmogorov, in:, ICML’13 Proceedings of the 30th International Conference on International, ML Research Press, 2013, pp. 145–153. conference: end_date: 2013-06-21 location: Atlanta, GA, USA name: 'ICML: International Conference on Machine Learning' start_date: 2013-06-16 date_created: 2018-12-11T11:56:41Z date_published: 2013-06-01T00:00:00Z date_updated: 2023-10-17T09:51:32Z day: '01' department: - _id: VlKo intvolume: ' 28' issue: '3' language: - iso: eng main_file_link: - open_access: '1' url: http://proceedings.mlr.press/v28/takhanov13.pdf?CFID=105472548&CFTOKEN=5c5859b5d97b4439-27B4AC58-BA92-A964-B598CAACEE6CC515 month: '06' oa: 1 oa_version: Submitted Version page: 145 - 153 publication: ICML'13 Proceedings of the 30th International Conference on International publication_status: published publisher: ML Research Press publist_id: '4672' quality_controlled: '1' related_material: record: - id: '1794' relation: later_version status: public scopus_import: '1' status: public title: Inference algorithms for pattern-based CRFs on sequence data type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 28 year: '2013' ... --- _id: '2274' abstract: - lang: eng text: "Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto'92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system.\r\n\r\nIn this work, we put forward an alternative concept for PoWs -- so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model, using graphs with high "pebbling complexity" and Merkle hash-trees. " author: - first_name: Stefan full_name: Dziembowski, Stefan last_name: Dziembowski - first_name: Sebastian full_name: Faust, Sebastian last_name: Faust - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 citation: ama: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. Proofs of Space. IST Austria; 2013. apa: Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2013). Proofs of Space. IST Austria. chicago: Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Z Pietrzak. Proofs of Space. IST Austria, 2013. ieee: S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, Proofs of Space. IST Austria, 2013. ista: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2013. Proofs of Space, IST Austria,p. mla: Dziembowski, Stefan, et al. Proofs of Space. IST Austria, 2013. short: S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, Proofs of Space, IST Austria, 2013. date_created: 2018-12-11T11:56:42Z date_published: 2013-11-28T00:00:00Z date_updated: 2024-03-20T08:31:49Z day: '28' ddc: - '530' department: - _id: VlKo - _id: KrPi file: - access_level: open_access checksum: 37b61637b62fc079d9141c59d9f1a94f content_type: application/pdf creator: system date_created: 2018-12-12T10:16:11Z date_updated: 2020-07-14T12:45:36Z file_id: '5197' file_name: IST-2016-671-v1+1_796.pdf file_size: 405870 relation: main_file file_date_updated: 2020-07-14T12:45:36Z has_accepted_license: '1' language: - iso: eng month: '11' oa: 1 oa_version: Published Version publication_status: published publisher: IST Austria publist_id: '4670' pubrep_id: '671' related_material: record: - id: '1675' relation: later_version status: public scopus_import: 1 status: public title: Proofs of Space type: report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2013' ... --- _id: '2930' abstract: - lang: eng text: "In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k = 1 and k = 2 respectively.\r\n\r\nIn particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron.\r\n" acknowledgement: "We would like to thank Andrei Krokhin for encourag- ing our cooperation, for helpful discussions, and for his critical reading of the manuscript.\r\n" alternative_title: - LNCS author: - first_name: Anna full_name: Huber, Anna last_name: Huber - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Huber A, Kolmogorov V. Towards minimizing k-submodular functions. In: Vol 7422. Springer; 2012:451-462. doi:10.1007/978-3-642-32147-4_40' apa: 'Huber, A., & Kolmogorov, V. (2012). Towards minimizing k-submodular functions (Vol. 7422, pp. 451–462). Presented at the ISCO: International Symposium on Combinatorial Optimization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-642-32147-4_40' chicago: Huber, Anna, and Vladimir Kolmogorov. “Towards Minimizing K-Submodular Functions,” 7422:451–62. Springer, 2012. https://doi.org/10.1007/978-3-642-32147-4_40. ieee: 'A. Huber and V. Kolmogorov, “Towards minimizing k-submodular functions,” presented at the ISCO: International Symposium on Combinatorial Optimization, Athens, Greece, 2012, vol. 7422, pp. 451–462.' ista: 'Huber A, Kolmogorov V. 2012. Towards minimizing k-submodular functions. ISCO: International Symposium on Combinatorial Optimization, LNCS, vol. 7422, 451–462.' mla: Huber, Anna, and Vladimir Kolmogorov. Towards Minimizing K-Submodular Functions. Vol. 7422, Springer, 2012, pp. 451–62, doi:10.1007/978-3-642-32147-4_40. short: A. Huber, V. Kolmogorov, in:, Springer, 2012, pp. 451–462. conference: end_date: 2012-04-21 location: Athens, Greece name: 'ISCO: International Symposium on Combinatorial Optimization' start_date: 2012-04-19 date_created: 2018-12-11T12:00:24Z date_published: 2012-04-01T00:00:00Z date_updated: 2021-01-12T07:00:46Z day: '01' department: - _id: VlKo doi: 10.1007/978-3-642-32147-4_40 intvolume: ' 7422' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1309.5469 month: '04' oa: 1 oa_version: Preprint page: 451 - 462 publication_status: published publisher: Springer publist_id: '3806' quality_controlled: '1' scopus_import: 1 status: public title: Towards minimizing k-submodular functions type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 7422 year: '2012' ... --- _id: '2928' abstract: - lang: eng text: ' This paper addresses the problem of approximate MAP-MRF inference in general graphical models. Following [36], we consider a family of linear programming relaxations of the problem where each relaxation is specified by a set of nested pairs of factors for which the marginalization constraint needs to be enforced. We develop a generalization of the TRW-S algorithm [9] for this problem, where we use a decomposition into junction chains, monotonic w.r.t. some ordering on the nodes. This generalizes the monotonic chains in [9] in a natural way. We also show how to deal with nested factors in an efficient way. Experiments show an improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on a number of computer vision and natural language processing problems. ' article_processing_charge: No author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Thomas full_name: Schoenemann, Thomas last_name: Schoenemann citation: ama: Kolmogorov V, Schoenemann T. Generalized sequential tree-reweighted message passing. arXiv. 2012. apa: Kolmogorov, V., & Schoenemann, T. (2012). Generalized sequential tree-reweighted message passing. arXiv. ArXiv. chicago: Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted Message Passing.” ArXiv. ArXiv, 2012. ieee: V. Kolmogorov and T. Schoenemann, “Generalized sequential tree-reweighted message passing,” arXiv. ArXiv, 2012. ista: Kolmogorov V, Schoenemann T. 2012. Generalized sequential tree-reweighted message passing. arXiv, . mla: Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted Message Passing.” ArXiv, ArXiv, 2012. short: V. Kolmogorov, T. Schoenemann, ArXiv (2012). date_created: 2018-12-11T12:00:23Z date_published: 2012-05-29T00:00:00Z date_updated: 2021-01-12T07:00:45Z day: '29' department: - _id: VlKo external_id: arxiv: - '1205.6352' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1205.6352 month: '05' oa: 1 oa_version: Preprint page: '16' publication: arXiv publication_status: published publisher: ArXiv publist_id: '3809' status: public title: Generalized sequential tree-reweighted message passing type: preprint user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '2931' abstract: - lang: eng text: "In this paper, we present a new approach for establishing correspondences between sparse image features related by an unknown nonrigid mapping and corrupted by clutter and occlusion, such as points extracted from images of different instances of the same object category. We formulate this matching task as an energy minimization problem by defining an elaborate objective function of the appearance and the spatial arrangement of the features. Optimization of this energy is an instance of graph matching, which is in general an NP-hard problem. We describe a novel graph matching optimization technique, which we refer to as dual decomposition (DD), and demonstrate on a variety of examples that this method outperforms existing graph matching algorithms. In the majority of our examples, DD is able to find the global minimum within a minute. The ability to globally optimize the objective allows us to accurately learn the parameters of our matching model from training examples. We show on several matching tasks that our learned model yields results superior to those of state-of-the-art methods.\r\n" acknowledgement: This research was funded in part by Microsoft Research. author: - first_name: Lorenzo full_name: Torresani, Lorenzo last_name: Torresani - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Carsten full_name: Rother, Carsten last_name: Rother citation: ama: Torresani L, Kolmogorov V, Rother C. A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2012;35(2):259-271. doi:10.1109/TPAMI.2012.105 apa: Torresani, L., Kolmogorov, V., & Rother, C. (2012). A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. https://doi.org/10.1109/TPAMI.2012.105 chicago: Torresani, Lorenzo, Vladimir Kolmogorov, and Carsten Rother. “A Dual Decomposition Approach to Feature Correspondence.” IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE, 2012. https://doi.org/10.1109/TPAMI.2012.105. ieee: L. Torresani, V. Kolmogorov, and C. Rother, “A dual decomposition approach to feature correspondence,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 2. IEEE, pp. 259–271, 2012. ista: Torresani L, Kolmogorov V, Rother C. 2012. A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. 35(2), 259–271. mla: Torresani, Lorenzo, et al. “A Dual Decomposition Approach to Feature Correspondence.” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 2, IEEE, 2012, pp. 259–71, doi:10.1109/TPAMI.2012.105. short: L. Torresani, V. Kolmogorov, C. Rother, IEEE Transactions on Pattern Analysis and Machine Intelligence 35 (2012) 259–271. date_created: 2018-12-11T12:00:24Z date_published: 2012-05-08T00:00:00Z date_updated: 2021-01-12T07:00:46Z day: '08' department: - _id: VlKo doi: 10.1109/TPAMI.2012.105 intvolume: ' 35' issue: '2' language: - iso: eng month: '05' oa_version: None page: 259 - 271 project: - _id: 2587B514-B435-11E9-9278-68D0E5697425 name: Microsoft Research Faculty Fellowship publication: IEEE Transactions on Pattern Analysis and Machine Intelligence publication_status: published publisher: IEEE publist_id: '3805' quality_controlled: '1' scopus_import: 1 status: public title: A dual decomposition approach to feature correspondence type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 35 year: '2012' ... --- _id: '3117' abstract: - lang: eng text: We consider the problem of minimizing a function represented as a sum of submodular terms. We assume each term allows an efficient computation of exchange capacities. This holds, for example, for terms depending on a small number of variables, or for certain cardinality-dependent terms. A naive application of submodular minimization algorithms would not exploit the existence of specialized exchange capacity subroutines for individual terms. To overcome this, we cast the problem as a submodular flow (SF) problem in an auxiliary graph in such a way that applying most existing SF algorithms would rely only on these subroutines. We then explore in more detail Iwata's capacity scaling approach for submodular flows (Iwata 1997 [19]). In particular, we show how to improve its complexity in the case when the function contains cardinality-dependent terms. author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: Kolmogorov V. Minimizing a sum of submodular functions. Discrete Applied Mathematics. 2012;160(15):2246-2258. doi:10.1016/j.dam.2012.05.025 apa: Kolmogorov, V. (2012). Minimizing a sum of submodular functions. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2012.05.025 chicago: Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2012.05.025. ieee: V. Kolmogorov, “Minimizing a sum of submodular functions,” Discrete Applied Mathematics, vol. 160, no. 15. Elsevier, pp. 2246–2258, 2012. ista: Kolmogorov V. 2012. Minimizing a sum of submodular functions. Discrete Applied Mathematics. 160(15), 2246–2258. mla: Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete Applied Mathematics, vol. 160, no. 15, Elsevier, 2012, pp. 2246–58, doi:10.1016/j.dam.2012.05.025. short: V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 2246–2258. date_created: 2018-12-11T12:01:29Z date_published: 2012-10-01T00:00:00Z date_updated: 2021-01-12T07:41:11Z day: '01' department: - _id: VlKo doi: 10.1016/j.dam.2012.05.025 intvolume: ' 160' issue: '15' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1006.1990 month: '10' oa: 1 oa_version: Preprint page: 2246 - 2258 publication: Discrete Applied Mathematics publication_status: published publisher: Elsevier publist_id: '3582' quality_controlled: '1' scopus_import: 1 status: public title: Minimizing a sum of submodular functions type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 160 year: '2012' ... --- _id: '3257' abstract: - lang: eng text: Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that the relaxation is totally half-integral if f̂(x) is a polyhedral function with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-Boolean functions f. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean functions. Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations f̂ by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. On the conceptual level, our results show that bisubmodular functions provide a natural generalization of the roof duality approach to higher-order terms. This can be viewed as a non-submodular analogue of the fact that submodular functions generalize the s-t minimum cut problem with non-negative weights to higher-order terms. author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: Kolmogorov V. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 2012;160(4-5):416-426. doi:10.1016/j.dam.2011.10.026 apa: Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2011.10.026 chicago: Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” Discrete Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2011.10.026. ieee: V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” Discrete Applied Mathematics, vol. 160, no. 4–5. Elsevier, pp. 416–426, 2012. ista: Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 160(4–5), 416–426. mla: Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” Discrete Applied Mathematics, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26, doi:10.1016/j.dam.2011.10.026. short: V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426. date_created: 2018-12-11T12:02:18Z date_published: 2012-03-01T00:00:00Z date_updated: 2023-02-23T11:04:49Z day: '01' department: - _id: VlKo doi: 10.1016/j.dam.2011.10.026 external_id: arxiv: - '1005.2305' intvolume: ' 160' issue: 4-5 language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1005.2305 month: '03' oa: 1 oa_version: Preprint page: 416 - 426 publication: Discrete Applied Mathematics publication_status: published publisher: Elsevier publist_id: '3397' quality_controlled: '1' related_material: record: - id: '2934' relation: earlier_version status: public scopus_import: 1 status: public title: Generalized roof duality and bisubmodular functions type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 160 year: '2012' ... --- _id: '3124' abstract: - lang: eng text: "We consider the problem of inference in a graphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pairwise terms over a discretized domain. This allows the use of techniques originally developed for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can outperform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.\r\n" alternative_title: - Inferning 2012 author: - first_name: Filip full_name: Korc, Filip id: 476A2FD6-F248-11E8-B48F-1D18A9856A87 last_name: Korc - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Christoph full_name: Lampert, Christoph id: 40C20FD2-F248-11E8-B48F-1D18A9856A87 last_name: Lampert orcid: 0000-0001-8622-7887 citation: ama: 'Korc F, Kolmogorov V, Lampert C. Approximating marginals using discrete energy minimization. In: ICML; 2012.' apa: 'Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals using discrete energy minimization. Presented at the ICML: International Conference on Machine Learning, Edinburgh, Scotland: ICML.' chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. “Approximating Marginals Using Discrete Energy Minimization.” ICML, 2012. ieee: 'F. Korc, V. Kolmogorov, and C. Lampert, “Approximating marginals using discrete energy minimization,” presented at the ICML: International Conference on Machine Learning, Edinburgh, Scotland, 2012.' ista: 'Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization. ICML: International Conference on Machine Learning, Inferning 2012, .' mla: Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization. ICML, 2012. short: F. Korc, V. Kolmogorov, C. Lampert, in:, ICML, 2012. conference: end_date: 2012-07-01 location: Edinburgh, Scotland name: 'ICML: International Conference on Machine Learning' start_date: 2012-06-26 date_created: 2018-12-11T12:01:31Z date_published: 2012-06-30T00:00:00Z date_updated: 2023-02-23T12:24:24Z day: '30' ddc: - '000' department: - _id: ChLa - _id: VlKo file: - access_level: open_access checksum: 3d0d4246548c736857302aadb2ff5d15 content_type: application/pdf creator: system date_created: 2018-12-12T10:11:34Z date_updated: 2020-07-14T12:46:00Z file_id: '4889' file_name: IST-2016-565-v1+1_DM-inferning2012.pdf file_size: 305836 relation: main_file file_date_updated: 2020-07-14T12:46:00Z has_accepted_license: '1' language: - iso: eng month: '06' oa: 1 oa_version: Submitted Version publication_status: published publisher: ICML publist_id: '3575' pubrep_id: '565' quality_controlled: '1' related_material: record: - id: '5396' relation: later_version status: public status: public title: Approximating marginals using discrete energy minimization type: conference user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 year: '2012' ... --- _id: '5396' abstract: - lang: eng text: We consider the problem of inference in agraphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can out-perform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions. alternative_title: - IST Austria Technical Report author: - first_name: Filip full_name: Korc, Filip id: 476A2FD6-F248-11E8-B48F-1D18A9856A87 last_name: Korc - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Christoph full_name: Lampert, Christoph id: 40C20FD2-F248-11E8-B48F-1D18A9856A87 last_name: Lampert orcid: 0000-0001-8622-7887 citation: ama: Korc F, Kolmogorov V, Lampert C. Approximating Marginals Using Discrete Energy Minimization. IST Austria; 2012. doi:10.15479/AT:IST-2012-0003 apa: Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals using discrete energy minimization. IST Austria. https://doi.org/10.15479/AT:IST-2012-0003 chicago: Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. Approximating Marginals Using Discrete Energy Minimization. IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0003. ieee: F. Korc, V. Kolmogorov, and C. Lampert, Approximating marginals using discrete energy minimization. IST Austria, 2012. ista: Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization, IST Austria, 13p. mla: Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization. IST Austria, 2012, doi:10.15479/AT:IST-2012-0003. short: F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete Energy Minimization, IST Austria, 2012. date_created: 2018-12-12T11:39:06Z date_published: 2012-07-23T00:00:00Z date_updated: 2023-02-23T11:13:22Z day: '23' ddc: - '000' department: - _id: VlKo - _id: ChLa doi: 10.15479/AT:IST-2012-0003 file: - access_level: open_access checksum: 7e0ba85ad123b13223aaf6cdde2d288c content_type: application/pdf creator: system date_created: 2018-12-12T11:53:29Z date_updated: 2020-07-14T12:46:44Z file_id: '5490' file_name: IST-2012-0003_IST-2012-0003.pdf file_size: 618744 relation: main_file file_date_updated: 2020-07-14T12:46:44Z has_accepted_license: '1' language: - iso: eng month: '07' oa: 1 oa_version: Published Version page: '13' publication_identifier: issn: - 2664-1690 publication_status: published publisher: IST Austria pubrep_id: '36' related_material: record: - id: '3124' relation: earlier_version status: public status: public title: Approximating marginals using discrete energy minimization type: technical_report user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2012' ...