[{"ddc":["000"],"volume":2017,"external_id":{"isi":["000418371405009"]},"isi":1,"year":"2017","citation":{"apa":"Swoboda, P., &#38; Andres, B. (2017). A message passing algorithm for the minimum cost multicut problem (Vol. 2017, pp. 4990–4999). Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. <a href=\"https://doi.org/10.1109/CVPR.2017.530\">https://doi.org/10.1109/CVPR.2017.530</a>","ama":"Swoboda P, Andres B. A message passing algorithm for the minimum cost multicut problem. In: Vol 2017. IEEE; 2017:4990-4999. doi:<a href=\"https://doi.org/10.1109/CVPR.2017.530\">10.1109/CVPR.2017.530</a>","chicago":"Swoboda, Paul, and Bjoern Andres. “A Message Passing Algorithm for the Minimum Cost Multicut Problem,” 2017:4990–99. IEEE, 2017. <a href=\"https://doi.org/10.1109/CVPR.2017.530\">https://doi.org/10.1109/CVPR.2017.530</a>.","ieee":"P. Swoboda and B. Andres, “A message passing algorithm for the minimum cost multicut problem,” presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 4990–4999.","short":"P. Swoboda, B. Andres, in:, IEEE, 2017, pp. 4990–4999.","mla":"Swoboda, Paul, and Bjoern Andres. <i>A Message Passing Algorithm for the Minimum Cost Multicut Problem</i>. Vol. 2017, IEEE, 2017, pp. 4990–99, doi:<a href=\"https://doi.org/10.1109/CVPR.2017.530\">10.1109/CVPR.2017.530</a>.","ista":"Swoboda P, Andres B. 2017. A message passing algorithm for the minimum cost multicut problem. CVPR: Computer Vision and Pattern Recognition vol. 2017, 4990–4999."},"date_updated":"2023-09-26T15:43:27Z","abstract":[{"lang":"eng","text":"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."}],"day":"01","doi":"10.1109/CVPR.2017.530","file_date_updated":"2020-07-14T12:48:15Z","quality_controlled":"1","ec_funded":1,"page":"4990-4999","publisher":"IEEE","author":[{"full_name":"Swoboda, Paul","first_name":"Paul","last_name":"Swoboda","id":"446560C6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Andres, Bjoern","first_name":"Bjoern","last_name":"Andres"}],"scopus_import":"1","_id":"915","intvolume":"      2017","title":"A message passing algorithm for the minimum cost multicut problem","date_created":"2018-12-11T11:49:11Z","department":[{"_id":"VlKo"}],"article_processing_charge":"No","publication_status":"published","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file":[{"creator":"dernst","file_id":"5849","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_name":"Swoboda_A_Message_Passing_CVPR_2017_paper.pdf","date_updated":"2020-07-14T12:48:15Z","file_size":883264,"checksum":"7e51dacefa693574581a32da3eff63dc","date_created":"2019-01-18T12:52:46Z"}],"type":"conference","date_published":"2017-07-01T00:00:00Z","publist_id":"6526","oa":1,"publication_identifier":{"isbn":["978-153860457-1"]},"language":[{"iso":"eng"}],"conference":{"name":"CVPR: Computer Vision and Pattern Recognition","start_date":"2017-07-21","end_date":"2017-07-26","location":"Honolulu, HA, United States"},"has_accepted_license":"1","month":"07","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"oa_version":"Submitted Version"},{"ddc":["000"],"volume":2017,"abstract":[{"text":"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.","lang":"eng"}],"doi":"10.1109/CVPR.2017.747","day":"01","isi":1,"external_id":{"isi":["000418371407018"]},"date_updated":"2023-09-26T15:41:40Z","year":"2017","citation":{"mla":"Swoboda, Paul, et al. <i>A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching</i>. Vol. 2017, IEEE, 2017, pp. 7062–71, doi:<a href=\"https://doi.org/10.1109/CVPR.2017.747\">10.1109/CVPR.2017.747</a>.","short":"P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, B. Savchynskyy, in:, IEEE, 2017, pp. 7062–7071.","ista":"Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. 2017. A study of lagrangean decompositions and dual ascent solvers for graph matching. CVPR: Computer Vision and Pattern Recognition vol. 2017, 7062–7071.","ama":"Swoboda P, Rother C, Abu Alhaija C, Kainmueller D, Savchynskyy B. A study of lagrangean decompositions and dual ascent solvers for graph matching. In: Vol 2017. IEEE; 2017:7062-7071. doi:<a href=\"https://doi.org/10.1109/CVPR.2017.747\">10.1109/CVPR.2017.747</a>","apa":"Swoboda, P., Rother, C., Abu Alhaija, C., Kainmueller, D., &#38; Savchynskyy, B. (2017). A study of lagrangean decompositions and dual ascent solvers for graph matching (Vol. 2017, pp. 7062–7071). Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. <a href=\"https://doi.org/10.1109/CVPR.2017.747\">https://doi.org/10.1109/CVPR.2017.747</a>","ieee":"P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, and B. Savchynskyy, “A study of lagrangean decompositions and dual ascent solvers for graph matching,” presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 7062–7071.","chicago":"Swoboda, Paul, Carsten Rother, Carsten Abu Alhaija, Dagmar Kainmueller, and Bogdan Savchynskyy. “A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching,” 2017:7062–71. IEEE, 2017. <a href=\"https://doi.org/10.1109/CVPR.2017.747\">https://doi.org/10.1109/CVPR.2017.747</a>."},"publisher":"IEEE","file_date_updated":"2020-07-14T12:48:15Z","page":"7062-7071","quality_controlled":"1","ec_funded":1,"title":"A study of lagrangean decompositions and dual ascent solvers for graph matching","intvolume":"      2017","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T11:49:11Z","department":[{"_id":"VlKo"}],"author":[{"first_name":"Paul","last_name":"Swoboda","full_name":"Swoboda, Paul","id":"446560C6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Rother","first_name":"Carsten","full_name":"Rother, Carsten"},{"full_name":"Abu Alhaija, Carsten","first_name":"Carsten","last_name":"Abu Alhaija"},{"last_name":"Kainmueller","first_name":"Dagmar","full_name":"Kainmueller, Dagmar"},{"first_name":"Bogdan","last_name":"Savchynskyy","full_name":"Savchynskyy, Bogdan"}],"_id":"916","scopus_import":"1","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","file":[{"file_id":"5848","creator":"dernst","relation":"main_file","access_level":"open_access","date_updated":"2020-07-14T12:48:15Z","file_name":"2017_CVPR_Swoboda2.pdf","content_type":"application/pdf","date_created":"2019-01-18T12:49:38Z","file_size":944332,"checksum":"e38a2740daad1ea178465843b5072906"}],"publist_id":"6525","oa":1,"publication_identifier":{"isbn":["978-153860457-1"]},"date_published":"2017-01-01T00:00:00Z","type":"conference","conference":{"start_date":"2017-07-21","name":"CVPR: Computer Vision and Pattern Recognition","location":"Honolulu, HA, United States","end_date":"2017-07-26"},"language":[{"iso":"eng"}],"month":"01","oa_version":"Submitted Version","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"has_accepted_license":"1"},{"doi":"10.1109/CVPR.2017.526","day":"01","abstract":[{"lang":"eng","text":"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."}],"date_updated":"2023-09-26T15:41:11Z","citation":{"apa":"Swoboda, P., Kuske, J., &#38; Savchynskyy, B. (2017). A dual ascent framework for Lagrangean decomposition of combinatorial problems (Vol. 2017, pp. 4950–4960). Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. <a href=\"https://doi.org/10.1109/CVPR.2017.526\">https://doi.org/10.1109/CVPR.2017.526</a>","ama":"Swoboda P, Kuske J, Savchynskyy B. A dual ascent framework for Lagrangean decomposition of combinatorial problems. In: Vol 2017. IEEE; 2017:4950-4960. doi:<a href=\"https://doi.org/10.1109/CVPR.2017.526\">10.1109/CVPR.2017.526</a>","ieee":"P. Swoboda, J. Kuske, and B. Savchynskyy, “A dual ascent framework for Lagrangean decomposition of combinatorial problems,” presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 4950–4960.","chicago":"Swoboda, Paul, Jan Kuske, and Bogdan Savchynskyy. “A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems,” 2017:4950–60. IEEE, 2017. <a href=\"https://doi.org/10.1109/CVPR.2017.526\">https://doi.org/10.1109/CVPR.2017.526</a>.","short":"P. Swoboda, J. Kuske, B. Savchynskyy, in:, IEEE, 2017, pp. 4950–4960.","mla":"Swoboda, Paul, et al. <i>A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems</i>. Vol. 2017, IEEE, 2017, pp. 4950–60, doi:<a href=\"https://doi.org/10.1109/CVPR.2017.526\">10.1109/CVPR.2017.526</a>.","ista":"Swoboda P, Kuske J, Savchynskyy B. 2017. A dual ascent framework for Lagrangean decomposition of combinatorial problems. CVPR: Computer Vision and Pattern Recognition vol. 2017, 4950–4960."},"year":"2017","isi":1,"external_id":{"isi":["000418371405005"]},"volume":2017,"ddc":["000"],"publication_status":"published","date_created":"2018-12-11T11:49:11Z","department":[{"_id":"VlKo"}],"article_processing_charge":"No","title":"A dual ascent framework for Lagrangean decomposition of combinatorial problems","intvolume":"      2017","_id":"917","scopus_import":"1","author":[{"id":"446560C6-F248-11E8-B48F-1D18A9856A87","full_name":"Swoboda, Paul","first_name":"Paul","last_name":"Swoboda"},{"first_name":"Jan","last_name":"Kuske","full_name":"Kuske, Jan"},{"full_name":"Savchynskyy, Bogdan","first_name":"Bogdan","last_name":"Savchynskyy"}],"publisher":"IEEE","page":"4950-4960","ec_funded":1,"quality_controlled":"1","file_date_updated":"2020-07-14T12:48:15Z","publication_identifier":{"isbn":["978-153860457-1"]},"oa":1,"publist_id":"6524","date_published":"2017-07-01T00:00:00Z","type":"conference","file":[{"creator":"dernst","file_id":"5847","relation":"main_file","access_level":"open_access","file_name":"2017_CVPR_Swoboda.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:48:15Z","file_size":898652,"checksum":"72fd291046bd8e5717961bd68f6b6f03","date_created":"2019-01-18T12:45:55Z"}],"status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","oa_version":"Submitted Version","project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"month":"07","has_accepted_license":"1","conference":{"location":"Honolulu, HA, United States","end_date":"2017-07-26","start_date":"2017-07-21","name":"CVPR: Computer Vision and Pattern Recognition"},"language":[{"iso":"eng"}]},{"publication_status":"published","department":[{"_id":"VlKo"}],"article_processing_charge":"No","date_created":"2018-12-11T11:50:38Z","title":"Even delta-matroids and the complexity of planar Boolean CSPs","_id":"1192","author":[{"id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","last_name":"Kazda","first_name":"Alexandr","full_name":"Kazda, Alexandr"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"},{"full_name":"Rolinek, Michal","first_name":"Michal","last_name":"Rolinek","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"}],"publisher":"SIAM","page":"307 - 326","ec_funded":1,"quality_controlled":"1","doi":"10.1137/1.9781611974782.20","day":"01","abstract":[{"lang":"eng","text":"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."}],"date_updated":"2023-09-20T11:20:26Z","year":"2017","citation":{"ieee":"A. Kazda, V. Kolmogorov, and M. Rolinek, “Even delta-matroids and the complexity of planar Boolean CSPs,” presented at the SODA: Symposium on Discrete Algorithms, Barcelona, Spain, 2017, pp. 307–326.","chicago":"Kazda, Alexandr, Vladimir Kolmogorov, and Michal Rolinek. “Even Delta-Matroids and the Complexity of Planar Boolean CSPs,” 307–26. SIAM, 2017. <a href=\"https://doi.org/10.1137/1.9781611974782.20\">https://doi.org/10.1137/1.9781611974782.20</a>.","apa":"Kazda, A., Kolmogorov, V., &#38; Rolinek, M. (2017). Even delta-matroids and the complexity of planar Boolean CSPs (pp. 307–326). Presented at the SODA: Symposium on Discrete Algorithms, Barcelona, Spain: SIAM. <a href=\"https://doi.org/10.1137/1.9781611974782.20\">https://doi.org/10.1137/1.9781611974782.20</a>","ama":"Kazda A, Kolmogorov V, Rolinek M. Even delta-matroids and the complexity of planar Boolean CSPs. In: SIAM; 2017:307-326. doi:<a href=\"https://doi.org/10.1137/1.9781611974782.20\">10.1137/1.9781611974782.20</a>","ista":"Kazda A, Kolmogorov V, Rolinek M. 2017. Even delta-matroids and the complexity of planar Boolean CSPs. SODA: Symposium on Discrete Algorithms, 307–326.","short":"A. Kazda, V. Kolmogorov, M. Rolinek, in:, SIAM, 2017, pp. 307–326.","mla":"Kazda, Alexandr, et al. <i>Even Delta-Matroids and the Complexity of Planar Boolean CSPs</i>. SIAM, 2017, pp. 307–26, doi:<a href=\"https://doi.org/10.1137/1.9781611974782.20\">10.1137/1.9781611974782.20</a>."},"isi":1,"external_id":{"isi":["000426965800020"]},"oa_version":"Submitted Version","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"month":"01","conference":{"location":"Barcelona, Spain","end_date":"2017-01019","start_date":"2017-01-16","name":"SODA: Symposium on Discrete Algorithms"},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-161197478-2"]},"oa":1,"publist_id":"6159","date_published":"2017-01-01T00:00:00Z","type":"conference","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.03124"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"6032"}]},"status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1"},{"date_published":"2017-05-01T00:00:00Z","type":"dissertation","publication_identifier":{"issn":["2663-337X"]},"supervisor":[{"full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"oa":1,"publist_id":"6407","file":[{"date_updated":"2020-07-14T12:48:18Z","file_name":"IST-2017-815-v1+3_final_blank_signature_maybe_pdfa.pdf","content_type":"application/pdf","date_created":"2018-12-12T10:07:55Z","checksum":"81761fb939acb7585c36629f765b4373","file_size":786145,"file_id":"4654","creator":"system","relation":"main_file","access_level":"open_access"},{"date_updated":"2020-07-14T12:48:18Z","file_name":"2017_Thesis_Rolinek_source.zip","content_type":"application/zip","date_created":"2019-04-05T08:43:24Z","checksum":"2b2d7e1d6c1c79a9795a7aa0f860baf3","file_size":5936337,"file_id":"6208","creator":"dernst","access_level":"closed","relation":"source_file"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","has_accepted_license":"1","oa_version":"Published Version","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"month":"05","language":[{"iso":"eng"}],"date_updated":"2023-09-07T12:05:41Z","year":"2017","citation":{"chicago":"Rolinek, Michal. “Complexity of Constraint Satisfaction.” Institute of Science and Technology Austria, 2017. <a href=\"https://doi.org/10.15479/AT:ISTA:th_815\">https://doi.org/10.15479/AT:ISTA:th_815</a>.","ieee":"M. Rolinek, “Complexity of constraint satisfaction,” Institute of Science and Technology Austria, 2017.","apa":"Rolinek, M. (2017). <i>Complexity of constraint satisfaction</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:th_815\">https://doi.org/10.15479/AT:ISTA:th_815</a>","ama":"Rolinek M. Complexity of constraint satisfaction. 2017. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_815\">10.15479/AT:ISTA:th_815</a>","ista":"Rolinek M. 2017. Complexity of constraint satisfaction. Institute of Science and Technology Austria.","short":"M. Rolinek, Complexity of Constraint Satisfaction, Institute of Science and Technology Austria, 2017.","mla":"Rolinek, Michal. <i>Complexity of Constraint Satisfaction</i>. Institute of Science and Technology Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:th_815\">10.15479/AT:ISTA:th_815</a>."},"degree_awarded":"PhD","doi":"10.15479/AT:ISTA:th_815","day":"01","abstract":[{"lang":"eng","text":"An instance of the Constraint Satisfaction Problem (CSP) is given by a finite set of\r\nvariables, a finite domain of labels, and a set of constraints, each constraint acting on\r\na subset of the variables. The goal is to find an assignment of labels to its variables\r\nthat satisfies all constraints (or decide whether one exists). If we allow more general\r\n“soft” constraints, which come with (possibly infinite) costs of particular assignments,\r\nwe obtain instances from a richer class called Valued Constraint Satisfaction Problem\r\n(VCSP). There the goal is to find an assignment with minimum total cost.\r\nIn this thesis, we focus (assuming that P\r\n6\r\n=\r\nNP) on classifying computational com-\r\nplexity of CSPs and VCSPs under certain restricting conditions. Two results are the core\r\ncontent of the work. In one of them, we consider VCSPs parametrized by a constraint\r\nlanguage, that is the set of “soft” constraints allowed to form the instances, and finish\r\nthe complexity classification modulo (missing pieces of) complexity classification for\r\nanalogously parametrized CSP. The other result is a generalization of Edmonds’ perfect\r\nmatching algorithm. This generalization contributes to complexity classfications in two\r\nways. First, it gives a new (largest known) polynomial-time solvable class of Boolean\r\nCSPs in which every variable may appear in at most two constraints and second, it\r\nsettles full classification of Boolean CSPs with planar drawing (again parametrized by a\r\nconstraint language)."}],"acknowledgement":"FP7/2007-2013/ERC grant agreement no 616160","ddc":["004"],"_id":"992","author":[{"full_name":"Rolinek, Michal","last_name":"Rolinek","first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","department":[{"_id":"VlKo"}],"article_processing_charge":"No","date_created":"2018-12-11T11:49:35Z","pubrep_id":"815","alternative_title":["ISTA Thesis"],"title":"Complexity of constraint satisfaction","page":"97","ec_funded":1,"file_date_updated":"2020-07-14T12:48:18Z","publisher":"Institute of Science and Technology Austria"},{"publication":"Algorithmica","month":"09","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"oa_version":"Preprint","language":[{"iso":"eng"}],"type":"journal_article","date_published":"2016-09-01T00:00:00Z","oa":1,"publist_id":"5316","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","related_material":{"record":[{"relation":"earlier_version","id":"2272","status":"public"}]},"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1210.0508"}],"issue":"1","author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87","last_name":"Takhanov","first_name":"Rustem","full_name":"Takhanov, Rustem"}],"scopus_import":1,"_id":"1794","intvolume":"        76","title":"Inference algorithms for pattern-based CRFs on sequence data","department":[{"_id":"VlKo"}],"date_created":"2018-12-11T11:54:02Z","publication_status":"published","quality_controlled":"1","ec_funded":1,"page":"17 - 46","publisher":"Springer","external_id":{"arxiv":["1210.0508"]},"year":"2016","citation":{"apa":"Kolmogorov, V., &#38; Takhanov, R. (2016). Inference algorithms for pattern-based CRFs on sequence data. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/s00453-015-0017-7\">https://doi.org/10.1007/s00453-015-0017-7</a>","ama":"Kolmogorov V, Takhanov R. Inference algorithms for pattern-based CRFs on sequence data. <i>Algorithmica</i>. 2016;76(1):17-46. doi:<a href=\"https://doi.org/10.1007/s00453-015-0017-7\">10.1007/s00453-015-0017-7</a>","chicago":"Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” <i>Algorithmica</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s00453-015-0017-7\">https://doi.org/10.1007/s00453-015-0017-7</a>.","ieee":"V. Kolmogorov and R. Takhanov, “Inference algorithms for pattern-based CRFs on sequence data,” <i>Algorithmica</i>, vol. 76, no. 1. Springer, pp. 17–46, 2016.","mla":"Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” <i>Algorithmica</i>, vol. 76, no. 1, Springer, 2016, pp. 17–46, doi:<a href=\"https://doi.org/10.1007/s00453-015-0017-7\">10.1007/s00453-015-0017-7</a>.","short":"V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46.","ista":"Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 76(1), 17–46."},"date_updated":"2023-10-17T09:51:31Z","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."}],"day":"01","doi":"10.1007/s00453-015-0017-7","arxiv":1,"volume":76,"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."},{"month":"09","title":"Synthetic discrete tomography problems","oa_version":"Published Version","department":[{"_id":"VlKo"}],"article_processing_charge":"No","date_created":"2018-12-12T12:31:31Z","author":[{"id":"446560C6-F248-11E8-B48F-1D18A9856A87","last_name":"Swoboda","first_name":"Paul","full_name":"Swoboda, Paul"}],"datarep_id":"46","_id":"5557","license":"https://creativecommons.org/publicdomain/zero/1.0/","has_accepted_license":"1","publisher":"Institute of Science and Technology Austria","contributor":[{"last_name":"Kuske","contributor_type":"data_collector","first_name":"Jan"}],"file_date_updated":"2020-07-14T12:47:02Z","keyword":["discrete tomography"],"abstract":[{"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.","lang":"eng"}],"oa":1,"doi":"10.15479/AT:ISTA:46","day":"20","date_published":"2016-09-20T00:00:00Z","type":"research_data","tmp":{"legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","short":"CC0 (1.0)","name":"Creative Commons Public Domain Dedication (CC0 1.0)","image":"/images/cc_0.png"},"date_updated":"2024-02-21T13:50:21Z","citation":{"ista":"Swoboda P. 2016. Synthetic discrete tomography problems, Institute of Science and Technology Austria, <a href=\"https://doi.org/10.15479/AT:ISTA:46\">10.15479/AT:ISTA:46</a>.","short":"P. Swoboda, (2016).","mla":"Swoboda, Paul. <i>Synthetic Discrete Tomography Problems</i>. Institute of Science and Technology Austria, 2016, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:46\">10.15479/AT:ISTA:46</a>.","ieee":"P. Swoboda, “Synthetic discrete tomography problems.” Institute of Science and Technology Austria, 2016.","chicago":"Swoboda, Paul. “Synthetic Discrete Tomography Problems.” Institute of Science and Technology Austria, 2016. <a href=\"https://doi.org/10.15479/AT:ISTA:46\">https://doi.org/10.15479/AT:ISTA:46</a>.","apa":"Swoboda, P. (2016). Synthetic discrete tomography problems. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:46\">https://doi.org/10.15479/AT:ISTA:46</a>","ama":"Swoboda P. Synthetic discrete tomography problems. 2016. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:46\">10.15479/AT:ISTA:46</a>"},"year":"2016","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["006"],"file":[{"checksum":"aa5a16a0dc888da7186fb8fc45e88439","file_size":36058401,"date_created":"2018-12-12T13:05:19Z","content_type":"application/zip","file_name":"IST-2016-46-v1+1_discrete_tomography_synthetic.zip","date_updated":"2020-07-14T12:47:02Z","access_level":"open_access","relation":"main_file","creator":"system","file_id":"5645"}]},{"author":[{"id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","first_name":"Alexandr","last_name":"Kazda","full_name":"Kazda, Alexandr"}],"issue":"1","_id":"1612","publication":"Algebra Universalis","scopus_import":1,"title":"CSP for binary conservative relational structures","month":"02","intvolume":"        75","publication_status":"published","oa_version":"Preprint","date_created":"2018-12-11T11:53:01Z","department":[{"_id":"VlKo"}],"language":[{"iso":"eng"}],"page":"75 - 84","quality_controlled":"1","publisher":"Springer","date_published":"2016-02-01T00:00:00Z","type":"journal_article","date_updated":"2021-01-12T06:52:00Z","year":"2016","citation":{"ieee":"A. Kazda, “CSP for binary conservative relational structures,” <i>Algebra Universalis</i>, vol. 75, no. 1. Springer, pp. 75–84, 2016.","chicago":"Kazda, Alexandr. “CSP for Binary Conservative Relational Structures.” <i>Algebra Universalis</i>. Springer, 2016. <a href=\"https://doi.org/10.1007/s00012-015-0358-8\">https://doi.org/10.1007/s00012-015-0358-8</a>.","ama":"Kazda A. CSP for binary conservative relational structures. <i>Algebra Universalis</i>. 2016;75(1):75-84. doi:<a href=\"https://doi.org/10.1007/s00012-015-0358-8\">10.1007/s00012-015-0358-8</a>","apa":"Kazda, A. (2016). CSP for binary conservative relational structures. <i>Algebra Universalis</i>. Springer. <a href=\"https://doi.org/10.1007/s00012-015-0358-8\">https://doi.org/10.1007/s00012-015-0358-8</a>","ista":"Kazda A. 2016. CSP for binary conservative relational structures. Algebra Universalis. 75(1), 75–84.","short":"A. Kazda, Algebra Universalis 75 (2016) 75–84.","mla":"Kazda, Alexandr. “CSP for Binary Conservative Relational Structures.” <i>Algebra Universalis</i>, vol. 75, no. 1, Springer, 2016, pp. 75–84, doi:<a href=\"https://doi.org/10.1007/s00012-015-0358-8\">10.1007/s00012-015-0358-8</a>."},"abstract":[{"lang":"eng","text":"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)."}],"oa":1,"publist_id":"5554","doi":"10.1007/s00012-015-0358-8","day":"01","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","volume":75,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1112.1099"}]},{"language":[{"iso":"eng"}],"month":"07","oa_version":"Preprint","publication":"International Journal of Algebra and Computation","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1512.07009"}],"oa":1,"publist_id":"5893","date_published":"2016-07-20T00:00:00Z","type":"journal_article","publisher":"World Scientific Publishing","page":"1033 - 1060","quality_controlled":"1","title":"Deciding absorption","intvolume":"        26","publication_status":"published","department":[{"_id":"VlKo"}],"date_created":"2018-12-11T11:51:32Z","author":[{"full_name":"Barto, Libor","first_name":"Libor","last_name":"Barto"},{"last_name":"Kazda","first_name":"Alexandr","full_name":"Kazda, Alexandr","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87"}],"issue":"5","_id":"1353","scopus_import":1,"acknowledgement":"Libor Barto and Alexandr Kazda were supported by the the Grant Agency of the Czech Republic, grant GACR 13-01832S. ","volume":26,"abstract":[{"text":"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.","lang":"eng"}],"doi":"10.1142/S0218196716500430","day":"20","date_updated":"2021-01-12T06:50:06Z","year":"2016","citation":{"ieee":"L. Barto and A. Kazda, “Deciding absorption,” <i>International Journal of Algebra and Computation</i>, vol. 26, no. 5. World Scientific Publishing, pp. 1033–1060, 2016.","chicago":"Barto, Libor, and Alexandr Kazda. “Deciding Absorption.” <i>International Journal of Algebra and Computation</i>. World Scientific Publishing, 2016. <a href=\"https://doi.org/10.1142/S0218196716500430\">https://doi.org/10.1142/S0218196716500430</a>.","ama":"Barto L, Kazda A. Deciding absorption. <i>International Journal of Algebra and Computation</i>. 2016;26(5):1033-1060. doi:<a href=\"https://doi.org/10.1142/S0218196716500430\">10.1142/S0218196716500430</a>","apa":"Barto, L., &#38; Kazda, A. (2016). Deciding absorption. <i>International Journal of Algebra and Computation</i>. World Scientific Publishing. <a href=\"https://doi.org/10.1142/S0218196716500430\">https://doi.org/10.1142/S0218196716500430</a>","ista":"Barto L, Kazda A. 2016. Deciding absorption. International Journal of Algebra and Computation. 26(5), 1033–1060.","mla":"Barto, Libor, and Alexandr Kazda. “Deciding Absorption.” <i>International Journal of Algebra and Computation</i>, vol. 26, no. 5, World Scientific Publishing, 2016, pp. 1033–60, doi:<a href=\"https://doi.org/10.1142/S0218196716500430\">10.1142/S0218196716500430</a>.","short":"L. Barto, A. Kazda, International Journal of Algebra and Computation 26 (2016) 1033–1060."}},{"issue":"2","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"},{"first_name":"Thomas","last_name":"Pock","full_name":"Pock, Thomas"},{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal","first_name":"Michal","last_name":"Rolinek"}],"scopus_import":1,"_id":"1377","intvolume":"         9","title":"Total variation on a tree","date_created":"2018-12-11T11:51:40Z","department":[{"_id":"VlKo"}],"publication_status":"published","ec_funded":1,"quality_controlled":"1","page":"605 - 636","publisher":"Society for Industrial and Applied Mathematics ","citation":{"apa":"Kolmogorov, V., Pock, T., &#38; Rolinek, M. (2016). Total variation on a tree. <i>SIAM Journal on Imaging Sciences</i>. Society for Industrial and Applied Mathematics . <a href=\"https://doi.org/10.1137/15M1010257\">https://doi.org/10.1137/15M1010257</a>","ama":"Kolmogorov V, Pock T, Rolinek M. Total variation on a tree. <i>SIAM Journal on Imaging Sciences</i>. 2016;9(2):605-636. doi:<a href=\"https://doi.org/10.1137/15M1010257\">10.1137/15M1010257</a>","ieee":"V. Kolmogorov, T. Pock, and M. Rolinek, “Total variation on a tree,” <i>SIAM Journal on Imaging Sciences</i>, vol. 9, no. 2. Society for Industrial and Applied Mathematics , pp. 605–636, 2016.","chicago":"Kolmogorov, Vladimir, Thomas Pock, and Michal Rolinek. “Total Variation on a Tree.” <i>SIAM Journal on Imaging Sciences</i>. Society for Industrial and Applied Mathematics , 2016. <a href=\"https://doi.org/10.1137/15M1010257\">https://doi.org/10.1137/15M1010257</a>.","mla":"Kolmogorov, Vladimir, et al. “Total Variation on a Tree.” <i>SIAM Journal on Imaging Sciences</i>, vol. 9, no. 2, Society for Industrial and Applied Mathematics , 2016, pp. 605–36, doi:<a href=\"https://doi.org/10.1137/15M1010257\">10.1137/15M1010257</a>.","short":"V. Kolmogorov, T. Pock, M. Rolinek, SIAM Journal on Imaging Sciences 9 (2016) 605–636.","ista":"Kolmogorov V, Pock T, Rolinek M. 2016. Total variation on a tree. SIAM Journal on Imaging Sciences. 9(2), 605–636."},"year":"2016","date_updated":"2021-01-12T06:50:15Z","abstract":[{"lang":"eng","text":"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."}],"day":"03","doi":"10.1137/15M1010257","volume":9,"publication":"SIAM Journal on Imaging Sciences","month":"05","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"oa_version":"Preprint","language":[{"iso":"eng"}],"type":"journal_article","date_published":"2016-05-03T00:00:00Z","oa":1,"publist_id":"5834","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1502.07770"}]},{"_id":"1193","scopus_import":1,"author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"}],"publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T11:50:38Z","department":[{"_id":"VlKo"}],"title":"Commutativity in the algorithmic Lovasz local lemma","ec_funded":1,"quality_controlled":"1","publisher":"IEEE","date_updated":"2023-09-19T14:24:57Z","citation":{"ista":"Kolmogorov V. 2016. Commutativity in the algorithmic Lovasz local lemma. Proceedings - Annual IEEE Symposium on Foundations of Computer Science. FOCS: Foundations of Computer Science vol. 2016–December, 7782993.","mla":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovasz Local Lemma.” <i>Proceedings - Annual IEEE Symposium on Foundations of Computer Science</i>, vol. 2016–December, 7782993, IEEE, 2016, doi:<a href=\"https://doi.org/10.1109/FOCS.2016.88\">10.1109/FOCS.2016.88</a>.","short":"V. Kolmogorov, in:, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2016.","chicago":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovasz Local Lemma.” In <i>Proceedings - Annual IEEE Symposium on Foundations of Computer Science</i>, Vol. 2016–December. IEEE, 2016. <a href=\"https://doi.org/10.1109/FOCS.2016.88\">https://doi.org/10.1109/FOCS.2016.88</a>.","ieee":"V. Kolmogorov, “Commutativity in the algorithmic Lovasz local lemma,” in <i>Proceedings - Annual IEEE Symposium on Foundations of Computer Science</i>, New Brunswick, NJ, USA , 2016, vol. 2016–December.","apa":"Kolmogorov, V. (2016). Commutativity in the algorithmic Lovasz local lemma. In <i>Proceedings - Annual IEEE Symposium on Foundations of Computer Science</i> (Vol. 2016–December). New Brunswick, NJ, USA : IEEE. <a href=\"https://doi.org/10.1109/FOCS.2016.88\">https://doi.org/10.1109/FOCS.2016.88</a>","ama":"Kolmogorov V. Commutativity in the algorithmic Lovasz local lemma. In: <i>Proceedings - Annual IEEE Symposium on Foundations of Computer Science</i>. Vol 2016-December. IEEE; 2016. doi:<a href=\"https://doi.org/10.1109/FOCS.2016.88\">10.1109/FOCS.2016.88</a>"},"year":"2016","external_id":{"arxiv":["1506.08547"]},"arxiv":1,"doi":"10.1109/FOCS.2016.88","day":"15","abstract":[{"text":"We consider the recent formulation of the Algorithmic Lovász Local Lemma [1], [2] for finding objects that avoid &quot;bad features&quot;, or &quot;flaws&quot;. 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 &quot;resamples&quot; it using a &quot;resampling oracle&quot; 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 &quot;commutativity&quot; 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.","lang":"eng"}],"acknowledgement":"European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160","volume":"2016-December","publication":"Proceedings - Annual IEEE Symposium on Foundations of Computer Science","oa_version":"Preprint","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"month":"12","article_number":"7782993","language":[{"iso":"eng"}],"conference":{"location":"New Brunswick, NJ, USA ","end_date":"2016-09-11","name":"FOCS: Foundations of Computer Science","start_date":"2016-09-09"},"date_published":"2016-12-15T00:00:00Z","type":"conference","publist_id":"6158","oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1506.08547v7"}],"related_material":{"record":[{"relation":"later_version","id":"5975","status":"public"}]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"oa_version":"Submitted Version","project":[{"call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425","grant_number":"259668","name":"Provable Security for Physical Cryptography"},{"name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"month":"04","conference":{"start_date":"2016-05-08","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","location":"Vienna, Austria","end_date":"2016-05-12"},"language":[{"iso":"eng"}],"oa":1,"publist_id":"6103","date_published":"2016-04-28T00:00:00Z","type":"conference","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/100"}],"status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publication_status":"published","department":[{"_id":"KrPi"},{"_id":"VlKo"}],"date_created":"2018-12-11T11:50:51Z","alternative_title":["LNCS"],"title":"On the complexity of scrypt and proofs of space in the parallel random oracle model","intvolume":"      9666","_id":"1231","scopus_import":1,"author":[{"full_name":"Alwen, Joel F","last_name":"Alwen","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Chen, Binyi","last_name":"Chen","first_name":"Binyi"},{"full_name":"Kamath Hosdurg, Chethan","first_name":"Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"},{"last_name":"Tessaro","first_name":"Stefano","full_name":"Tessaro, Stefano"}],"publisher":"Springer","page":"358 - 387","quality_controlled":"1","ec_funded":1,"doi":"10.1007/978-3-662-49896-5_13","day":"28","abstract":[{"lang":"eng","text":"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)."}],"date_updated":"2021-01-12T06:49:15Z","year":"2016","citation":{"chicago":"Alwen, Joel F, Binyi Chen, Chethan Kamath Hosdurg, Vladimir Kolmogorov, Krzysztof Z Pietrzak, and Stefano Tessaro. “On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model,” 9666:358–87. Springer, 2016. <a href=\"https://doi.org/10.1007/978-3-662-49896-5_13\">https://doi.org/10.1007/978-3-662-49896-5_13</a>.","ieee":"J. F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K. Z. Pietrzak, and S. Tessaro, “On the complexity of scrypt and proofs of space in the parallel random oracle model,” presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria, 2016, vol. 9666, pp. 358–387.","apa":"Alwen, J. F., Chen, B., Kamath Hosdurg, C., Kolmogorov, V., Pietrzak, K. Z., &#38; Tessaro, S. (2016). On the complexity of scrypt and proofs of space in the parallel random oracle model (Vol. 9666, pp. 358–387). Presented at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna, Austria: Springer. <a href=\"https://doi.org/10.1007/978-3-662-49896-5_13\">https://doi.org/10.1007/978-3-662-49896-5_13</a>","ama":"Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S. On the complexity of scrypt and proofs of space in the parallel random oracle model. In: Vol 9666. Springer; 2016:358-387. doi:<a href=\"https://doi.org/10.1007/978-3-662-49896-5_13\">10.1007/978-3-662-49896-5_13</a>","ista":"Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S. 2016. On the complexity of scrypt and proofs of space in the parallel random oracle model. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 9666, 358–387.","mla":"Alwen, Joel F., et al. <i>On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model</i>. Vol. 9666, Springer, 2016, pp. 358–87, doi:<a href=\"https://doi.org/10.1007/978-3-662-49896-5_13\">10.1007/978-3-662-49896-5_13</a>.","short":"J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2016, pp. 358–387."},"acknowledgement":"Joël Alwen, Chethan Kamath, and Krzysztof Pietrzak’s research is partially supported by an ERC starting grant (259668-PSPC). Vladimir Kolmogorov is partially supported by an ERC consolidator grant (616160-DOICV). Binyi Chen was partially supported by NSF grants CNS-1423566 and CNS-1514526, and a gift from the Gareatis Foundation. Stefano Tessaro was partially supported by NSF grants CNS-1423566, CNS-1528178, a Hellman Fellowship, and the Glen and Susanne Culler Chair.\r\n\r\nThis work was done in part while the authors were visiting the Simons Institute for the Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons Collaboration in Cryptography through NSF grant CNS-1523467.","volume":9666},{"_id":"1636","scopus_import":"1","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir"},{"full_name":"Rolinek, Michal","last_name":"Rolinek","first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Takhanov","first_name":"Rustem","full_name":"Takhanov, Rustem"}],"publication_status":"published","department":[{"_id":"VlKo"}],"date_created":"2018-12-11T11:53:10Z","article_processing_charge":"No","alternative_title":["LNCS"],"title":"Effectiveness of structural restrictions for hybrid CSPs","intvolume":"      9472","page":"566 - 577","ec_funded":1,"quality_controlled":"1","publisher":"Springer Nature","date_updated":"2022-02-01T15:12:35Z","citation":{"ama":"Kolmogorov V, Rolinek M, Takhanov R. Effectiveness of structural restrictions for hybrid CSPs. In: <i>26th International Symposium</i>. Vol 9472. Springer Nature; 2015:566-577. doi:<a href=\"https://doi.org/10.1007/978-3-662-48971-0_48\">10.1007/978-3-662-48971-0_48</a>","apa":"Kolmogorov, V., Rolinek, M., &#38; Takhanov, R. (2015). Effectiveness of structural restrictions for hybrid CSPs. In <i>26th International Symposium</i> (Vol. 9472, pp. 566–577). Nagoya, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-48971-0_48\">https://doi.org/10.1007/978-3-662-48971-0_48</a>","chicago":"Kolmogorov, Vladimir, Michal Rolinek, and Rustem Takhanov. “Effectiveness of Structural Restrictions for Hybrid CSPs.” In <i>26th International Symposium</i>, 9472:566–77. Springer Nature, 2015. <a href=\"https://doi.org/10.1007/978-3-662-48971-0_48\">https://doi.org/10.1007/978-3-662-48971-0_48</a>.","ieee":"V. Kolmogorov, M. Rolinek, and R. Takhanov, “Effectiveness of structural restrictions for hybrid CSPs,” in <i>26th International Symposium</i>, Nagoya, Japan, 2015, vol. 9472, pp. 566–577.","mla":"Kolmogorov, Vladimir, et al. “Effectiveness of Structural Restrictions for Hybrid CSPs.” <i>26th International Symposium</i>, vol. 9472, Springer Nature, 2015, pp. 566–77, doi:<a href=\"https://doi.org/10.1007/978-3-662-48971-0_48\">10.1007/978-3-662-48971-0_48</a>.","short":"V. Kolmogorov, M. Rolinek, R. Takhanov, in:, 26th International Symposium, Springer Nature, 2015, 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."},"year":"2015","external_id":{"arxiv":["1504.07067"]},"doi":"10.1007/978-3-662-48971-0_48","arxiv":1,"day":"01","abstract":[{"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.","lang":"eng"}],"volume":9472,"publication":"26th International Symposium","oa_version":"Preprint","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"month":"12","language":[{"iso":"eng"}],"conference":{"end_date":"2015-12-11","location":"Nagoya, Japan","start_date":"2015-12-09","name":"ISAAC: International Symposium on Algorithms and Computation"},"date_published":"2015-12-01T00:00:00Z","type":"conference","publication_identifier":{"isbn":["978-3-662-48970-3"]},"publist_id":"5519","oa":1,"main_file_link":[{"url":"http://arxiv.org/abs/1504.07067","open_access":"1"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","status":"public"},{"doi":"10.1109/FOCS.2015.80","day":"01","abstract":[{"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.","lang":"eng"}],"date_updated":"2023-02-23T12:44:26Z","year":"2015","citation":{"mla":"Kolmogorov, Vladimir, et al. <i>The Complexity of General-Valued CSPs</i>. IEEE, 2015, pp. 1246–58, doi:<a href=\"https://doi.org/10.1109/FOCS.2015.80\">10.1109/FOCS.2015.80</a>.","short":"V. Kolmogorov, A. Krokhin, M. Rolinek, in:, IEEE, 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.","apa":"Kolmogorov, V., Krokhin, A., &#38; 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. <a href=\"https://doi.org/10.1109/FOCS.2015.80\">https://doi.org/10.1109/FOCS.2015.80</a>","ama":"Kolmogorov V, Krokhin A, Rolinek M. The complexity of general-valued CSPs. In: IEEE; 2015:1246-1258. doi:<a href=\"https://doi.org/10.1109/FOCS.2015.80\">10.1109/FOCS.2015.80</a>","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.","chicago":"Kolmogorov, Vladimir, Andrei Krokhin, and Michal Rolinek. “The Complexity of General-Valued CSPs,” 1246–58. IEEE, 2015. <a href=\"https://doi.org/10.1109/FOCS.2015.80\">https://doi.org/10.1109/FOCS.2015.80</a>."},"publisher":"IEEE","page":"1246 - 1258","quality_controlled":"1","ec_funded":1,"publication_status":"published","date_created":"2018-12-11T11:53:10Z","department":[{"_id":"VlKo"}],"title":"The complexity of general-valued CSPs","alternative_title":["56th Annual Symposium on Foundations of Computer Science"],"_id":"1637","scopus_import":1,"author":[{"last_name":"Kolmogorov","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Krokhin","first_name":"Andrei","full_name":"Krokhin, Andrei"},{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal","last_name":"Rolinek","full_name":"Rolinek, Michal"}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1502.07327"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","related_material":{"record":[{"relation":"other","id":"644","status":"public"}]},"oa":1,"publist_id":"5518","date_published":"2015-12-01T00:00:00Z","type":"conference","conference":{"start_date":"2015-10-18","name":"FOCS: Foundations of Computer Science","end_date":"2015-10-20","location":"Berkeley, CA, United States"},"language":[{"iso":"eng"}],"oa_version":"Preprint","project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"month":"12"},{"intvolume":"      9216","title":"Proofs of space","pubrep_id":"671","alternative_title":["LNCS"],"date_created":"2018-12-11T11:53:24Z","department":[{"_id":"VlKo"},{"_id":"KrPi"}],"publication_status":"published","author":[{"full_name":"Dziembowski, Stefan","first_name":"Stefan","last_name":"Dziembowski"},{"full_name":"Faust, Sebastian","last_name":"Faust","first_name":"Sebastian"},{"last_name":"Kolmogorov","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","last_name":"Pietrzak"}],"scopus_import":1,"_id":"1675","publisher":"Springer","series_title":"Lecture Notes in Computer Science","quality_controlled":"1","ec_funded":1,"page":"585 - 605","abstract":[{"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).","lang":"eng"}],"day":"01","doi":"10.1007/978-3-662-48000-7_29","year":"2015","citation":{"ista":"Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2015. Proofs of space. 9216, 585–605.","short":"S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, 9216 (2015) 585–605.","mla":"Dziembowski, Stefan, et al. <i>Proofs of Space</i>. Vol. 9216, Springer, 2015, pp. 585–605, doi:<a href=\"https://doi.org/10.1007/978-3-662-48000-7_29\">10.1007/978-3-662-48000-7_29</a>.","chicago":"Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Z Pietrzak. “Proofs of Space.” Lecture Notes in Computer Science. Springer, 2015. <a href=\"https://doi.org/10.1007/978-3-662-48000-7_29\">https://doi.org/10.1007/978-3-662-48000-7_29</a>.","ieee":"S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, “Proofs of space,” vol. 9216. Springer, pp. 585–605, 2015.","ama":"Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. Proofs of space. 2015;9216:585-605. doi:<a href=\"https://doi.org/10.1007/978-3-662-48000-7_29\">10.1007/978-3-662-48000-7_29</a>","apa":"Dziembowski, S., Faust, S., Kolmogorov, V., &#38; Pietrzak, K. Z. (2015). Proofs of space. Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United States: Springer. <a href=\"https://doi.org/10.1007/978-3-662-48000-7_29\">https://doi.org/10.1007/978-3-662-48000-7_29</a>"},"date_updated":"2023-02-23T10:35:50Z","volume":9216,"month":"08","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"},{"name":"Provable Security for Physical Cryptography","grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"oa_version":"None","conference":{"location":"Santa Barbara, CA, United States","end_date":"2015-08-20","name":"CRYPTO: International Cryptology Conference","start_date":"2015-08-16"},"language":[{"iso":"eng"}],"publist_id":"5474","type":"conference","date_published":"2015-08-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","related_material":{"record":[{"id":"2274","relation":"earlier_version","status":"public"}]}},{"day":"01","doi":"10.1109/TPAMI.2014.2363465","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."}],"citation":{"chicago":"Kolmogorov, Vladimir. “A New Look at Reweighted Message Passing.” <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>. IEEE, 2015. <a href=\"https://doi.org/10.1109/TPAMI.2014.2363465\">https://doi.org/10.1109/TPAMI.2014.2363465</a>.","ieee":"V. Kolmogorov, “A new look at reweighted message passing,” <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>, vol. 37, no. 5. IEEE, pp. 919–930, 2015.","apa":"Kolmogorov, V. (2015). A new look at reweighted message passing. <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>. IEEE. <a href=\"https://doi.org/10.1109/TPAMI.2014.2363465\">https://doi.org/10.1109/TPAMI.2014.2363465</a>","ama":"Kolmogorov V. A new look at reweighted message passing. <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>. 2015;37(5):919-930. doi:<a href=\"https://doi.org/10.1109/TPAMI.2014.2363465\">10.1109/TPAMI.2014.2363465</a>","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.” <i>IEEE Transactions on Pattern Analysis and Machine Intelligence</i>, vol. 37, no. 5, IEEE, 2015, pp. 919–30, doi:<a href=\"https://doi.org/10.1109/TPAMI.2014.2363465\">10.1109/TPAMI.2014.2363465</a>.","short":"V. Kolmogorov, IEEE Transactions on Pattern Analysis and Machine Intelligence 37 (2015) 919–930."},"year":"2015","date_updated":"2021-01-12T06:53:33Z","volume":37,"department":[{"_id":"VlKo"}],"date_created":"2018-12-11T11:54:18Z","publication_status":"published","intvolume":"        37","title":"A new look at reweighted message passing","scopus_import":1,"_id":"1841","issue":"5","author":[{"last_name":"Kolmogorov","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"publisher":"IEEE","ec_funded":1,"quality_controlled":"1","page":"919 - 930","publist_id":"5261","oa":1,"type":"journal_article","date_published":"2015-05-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1309.5655"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"oa_version":"Preprint","month":"05","publication":"IEEE Transactions on Pattern Analysis and Machine Intelligence","language":[{"iso":"eng"}]},{"title":"A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle","month":"06","publication_status":"published","oa_version":"Preprint","date_created":"2018-12-11T11:54:24Z","project":[{"grant_number":"308036","name":"Lifelong Learning of Visual Scene Understanding","call_identifier":"FP7","_id":"2532554C-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"department":[{"_id":"VlKo"},{"_id":"ChLa"}],"author":[{"full_name":"Shah, Neel","first_name":"Neel","last_name":"Shah","id":"31ABAF80-F248-11E8-B48F-1D18A9856A87"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov"},{"full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","last_name":"Lampert","first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"}],"_id":"1859","scopus_import":1,"conference":{"end_date":"2015-06-12","location":"Boston, MA, USA","start_date":"2015-06-07","name":"CVPR: Computer Vision and Pattern Recognition"},"publisher":"IEEE","language":[{"iso":"eng"}],"page":"2737 - 2745","ec_funded":1,"quality_controlled":"1","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. "}],"publist_id":"5240","oa":1,"doi":"10.1109/CVPR.2015.7298890","day":"01","date_published":"2015-06-01T00:00:00Z","type":"conference","date_updated":"2021-01-12T06:53:40Z","citation":{"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.","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. <a href=\"https://doi.org/10.1109/CVPR.2015.7298890\">https://doi.org/10.1109/CVPR.2015.7298890</a>.","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:<a href=\"https://doi.org/10.1109/CVPR.2015.7298890\">10.1109/CVPR.2015.7298890</a>","apa":"Shah, N., Kolmogorov, V., &#38; 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. <a href=\"https://doi.org/10.1109/CVPR.2015.7298890\">https://doi.org/10.1109/CVPR.2015.7298890</a>","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.","short":"N. Shah, V. Kolmogorov, C. Lampert, in:, IEEE, 2015, pp. 2737–2745.","mla":"Shah, Neel, et al. <i>A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly Max-Oracle</i>. IEEE, 2015, pp. 2737–45, doi:<a href=\"https://doi.org/10.1109/CVPR.2015.7298890\">10.1109/CVPR.2015.7298890</a>."},"year":"2015","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1408.6804"}]},{"publisher":"SIAM","page":"1 - 36","quality_controlled":"1","publication_status":"published","date_created":"2018-12-11T11:56:41Z","department":[{"_id":"VlKo"}],"title":"The power of linear programming for general-valued CSPs","intvolume":"        44","_id":"2271","scopus_import":1,"author":[{"full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Johan","last_name":"Thapper","full_name":"Thapper, Johan"},{"full_name":"Živný, Stanislav","first_name":"Stanislav","last_name":"Živný"}],"issue":"1","volume":44,"arxiv":1,"doi":"10.1137/130945648","day":"01","abstract":[{"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. ","lang":"eng"}],"date_updated":"2023-02-23T10:46:30Z","citation":{"chicago":"Kolmogorov, Vladimir, Johan Thapper, and Stanislav Živný. “The Power of Linear Programming for General-Valued CSPs.” <i>SIAM Journal on Computing</i>. SIAM, 2015. <a href=\"https://doi.org/10.1137/130945648\">https://doi.org/10.1137/130945648</a>.","ieee":"V. Kolmogorov, J. Thapper, and S. Živný, “The power of linear programming for general-valued CSPs,” <i>SIAM Journal on Computing</i>, vol. 44, no. 1. SIAM, pp. 1–36, 2015.","ama":"Kolmogorov V, Thapper J, Živný S. The power of linear programming for general-valued CSPs. <i>SIAM Journal on Computing</i>. 2015;44(1):1-36. doi:<a href=\"https://doi.org/10.1137/130945648\">10.1137/130945648</a>","apa":"Kolmogorov, V., Thapper, J., &#38; Živný, S. (2015). The power of linear programming for general-valued CSPs. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/130945648\">https://doi.org/10.1137/130945648</a>","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.","short":"V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015) 1–36.","mla":"Kolmogorov, Vladimir, et al. “The Power of Linear Programming for General-Valued CSPs.” <i>SIAM Journal on Computing</i>, vol. 44, no. 1, SIAM, 2015, pp. 1–36, doi:<a href=\"https://doi.org/10.1137/130945648\">10.1137/130945648</a>."},"year":"2015","external_id":{"arxiv":["1311.4219"]},"language":[{"iso":"eng"}],"oa_version":"Preprint","month":"02","publication":"SIAM Journal on Computing","main_file_link":[{"url":"http://arxiv.org/abs/1311.4219","open_access":"1"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","status":"public","related_material":{"record":[{"relation":"earlier_version","id":"2518","status":"public"}]},"oa":1,"publist_id":"4673","date_published":"2015-02-01T00:00:00Z","type":"journal_article"},{"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"content_type":"application/pdf","file_name":"IST-2016-566-v1+1_iccv13_part_enumeration.pdf","date_updated":"2020-07-14T12:45:36Z","file_size":378601,"checksum":"4a74b5c92d6dcd2348c2c10ec8dd18bf","date_created":"2018-12-12T10:09:30Z","creator":"system","file_id":"4754","relation":"main_file","access_level":"open_access"}],"date_published":"2014-03-03T00:00:00Z","type":"conference","publist_id":"4669","oa":1,"language":[{"iso":"eng"}],"conference":{"start_date":"2013-12-01","name":"ICCV: International Conference on Computer Vision","location":"Sydney, Australia","end_date":"2013-12-08"},"has_accepted_license":"1","month":"03","oa_version":"Submitted Version","ddc":["000"],"date_updated":"2021-01-12T06:56:28Z","citation":{"short":"C. Olsson, J. Ulen, Y. Boykov, V. Kolmogorov, in:, IEEE, 2014, pp. 2936–2943.","mla":"Olsson, Carl, et al. <i>Partial Enumeration and Curvature Regularization</i>. IEEE, 2014, pp. 2936–43, doi:<a href=\"https://doi.org/10.1109/ICCV.2013.365\">10.1109/ICCV.2013.365</a>.","ista":"Olsson C, Ulen J, Boykov Y, Kolmogorov V. 2014. Partial enumeration and curvature regularization. ICCV: International Conference on Computer Vision, 2936–2943.","apa":"Olsson, C., Ulen, J., Boykov, Y., &#38; Kolmogorov, V. (2014). Partial enumeration and curvature regularization (pp. 2936–2943). Presented at the ICCV: International Conference on Computer Vision, Sydney, Australia: IEEE. <a href=\"https://doi.org/10.1109/ICCV.2013.365\">https://doi.org/10.1109/ICCV.2013.365</a>","ama":"Olsson C, Ulen J, Boykov Y, Kolmogorov V. Partial enumeration and curvature regularization. In: IEEE; 2014:2936-2943. doi:<a href=\"https://doi.org/10.1109/ICCV.2013.365\">10.1109/ICCV.2013.365</a>","chicago":"Olsson, Carl, Johannes Ulen, Yuri Boykov, and Vladimir Kolmogorov. “Partial Enumeration and Curvature Regularization,” 2936–43. IEEE, 2014. <a href=\"https://doi.org/10.1109/ICCV.2013.365\">https://doi.org/10.1109/ICCV.2013.365</a>.","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."},"year":"2014","abstract":[{"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","lang":"eng"}],"doi":"10.1109/ICCV.2013.365","day":"03","file_date_updated":"2020-07-14T12:45:36Z","page":"2936 - 2943","quality_controlled":"1","publisher":"IEEE","author":[{"last_name":"Olsson","first_name":"Carl","full_name":"Olsson, Carl"},{"full_name":"Ulen, Johannes","last_name":"Ulen","first_name":"Johannes"},{"full_name":"Boykov, Yuri","first_name":"Yuri","last_name":"Boykov"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir"}],"_id":"2275","scopus_import":1,"pubrep_id":"566","title":"Partial enumeration and curvature regularization","publication_status":"published","department":[{"_id":"VlKo"}],"date_created":"2018-12-11T11:56:42Z"},{"date_published":"2014-06-30T00:00:00Z","type":"working_paper","date_updated":"2020-07-14T23:11:45Z","citation":{"short":"K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games, IST Austria, n.d.","mla":"Huszár, Kristóf, and Michal Rolinek. <i>Playful Math - An Introduction to Mathematical Games</i>. IST Austria.","ista":"Huszár K, Rolinek M. Playful Math - An introduction to mathematical games, IST Austria, 5p.","apa":"Huszár, K., &#38; Rolinek, M. (n.d.). <i>Playful Math - An introduction to mathematical games</i>. IST Austria.","ama":"Huszár K, Rolinek M. <i>Playful Math - An Introduction to Mathematical Games</i>. IST Austria","ieee":"K. Huszár and M. Rolinek, <i>Playful Math - An introduction to mathematical games</i>. IST Austria.","chicago":"Huszár, Kristóf, and Michal Rolinek. <i>Playful Math - An Introduction to Mathematical Games</i>. IST Austria, n.d."},"year":"2014","oa":1,"day":"30","ddc":["510"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","file":[{"date_created":"2019-11-18T15:57:51Z","checksum":"2b94e5e1f4c3fe8ab89b12806276fb09","file_size":511233,"date_updated":"2020-07-14T12:47:48Z","file_name":"2014_Playful_Math_Huszar.pdf","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"7039","creator":"dernst"}],"author":[{"orcid":"0000-0002-5445-5057","full_name":"Huszár, Kristóf","first_name":"Kristóf","last_name":"Huszár","id":"33C26278-F248-11E8-B48F-1D18A9856A87"},{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","last_name":"Rolinek","first_name":"Michal","full_name":"Rolinek, Michal"}],"_id":"7038","has_accepted_license":"1","month":"06","title":"Playful Math - An introduction to mathematical games","oa_version":"Published Version","publication_status":"draft","department":[{"_id":"VlKo"},{"_id":"UlWa"}],"date_created":"2019-11-18T15:57:05Z","article_processing_charge":"No","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:47:48Z","page":"5","publisher":"IST Austria"}]