[{"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"apa":"Mohapatra, P., Rolinek, M., Jawahar, C. V., Kolmogorov, V., & Kumar, M. P. (2018). Efficient optimization for rank-based loss functions. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 3693–3701). Salt Lake City, UT, USA: IEEE. https://doi.org/10.1109/cvpr.2018.00389","ama":"Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. Efficient optimization for rank-based loss functions. In: 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. IEEE; 2018:3693-3701. doi:10.1109/cvpr.2018.00389","ieee":"P. Mohapatra, M. Rolinek, C. V. Jawahar, V. Kolmogorov, and M. P. Kumar, “Efficient optimization for rank-based loss functions,” in 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, Salt Lake City, UT, USA, 2018, pp. 3693–3701.","short":"P. Mohapatra, M. Rolinek, C.V. Jawahar, V. Kolmogorov, M.P. Kumar, in:, 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 3693–3701.","mla":"Mohapatra, Pritish, et al. “Efficient Optimization for Rank-Based Loss Functions.” 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, IEEE, 2018, pp. 3693–701, doi:10.1109/cvpr.2018.00389.","ista":"Mohapatra P, Rolinek M, Jawahar CV, Kolmogorov V, Kumar MP. 2018. Efficient optimization for rank-based loss functions. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition, 3693–3701.","chicago":"Mohapatra, Pritish, Michal Rolinek, C V Jawahar, Vladimir Kolmogorov, and M Pawan Kumar. “Efficient Optimization for Rank-Based Loss Functions.” In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, 3693–3701. IEEE, 2018. https://doi.org/10.1109/cvpr.2018.00389."},"title":"Efficient optimization for rank-based loss functions","author":[{"first_name":"Pritish","full_name":"Mohapatra, Pritish","last_name":"Mohapatra"},{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal","last_name":"Rolinek","full_name":"Rolinek, Michal"},{"first_name":"C V","last_name":"Jawahar","full_name":"Jawahar, C V"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kumar, M Pawan","last_name":"Kumar","first_name":"M Pawan"}],"external_id":{"arxiv":["1604.08269"],"isi":["000457843603087"]},"article_processing_charge":"No","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"day":"28","publication":"2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition","isi":1,"year":"2018","date_published":"2018-06-28T00:00:00Z","doi":"10.1109/cvpr.2018.00389","date_created":"2018-12-11T11:45:33Z","page":"3693-3701","quality_controlled":"1","publisher":"IEEE","oa":1,"date_updated":"2023-09-11T13:24:43Z","department":[{"_id":"VlKo"}],"_id":"273","status":"public","type":"conference","conference":{"start_date":"2018-06-18","end_date":"2018-06-22","location":"Salt Lake City, UT, USA","name":"CVPR: Conference on Computer Vision and Pattern Recognition"},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781538664209"]},"publication_status":"published","ec_funded":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"The accuracy of information retrieval systems is often measured using complex loss functions such as the average precision (AP) or the normalized discounted cumulative gain (NDCG). Given a set of positive and negative samples, the parameters of a retrieval system can be estimated by minimizing these loss functions. However, the non-differentiability and non-decomposability of these loss functions does not allow for simple gradient based optimization algorithms. This issue is generally circumvented by either optimizing a structured hinge-loss upper bound to the loss function or by using asymptotic methods like the direct-loss minimization framework. Yet, the high computational complexity of loss-augmented inference, which is necessary for both the frameworks, prohibits its use in large training data sets. To alleviate this deficiency, we present a novel quicksort flavored algorithm for a large class of non-decomposable loss functions. We provide a complete characterization of the loss functions that are amenable to our algorithm, and show that it includes both AP and NDCG based loss functions. Furthermore, we prove that no comparison based algorithm can improve upon the computational complexity of our approach asymptotically. We demonstrate the effectiveness of our approach in the context of optimizing the structured hinge loss upper bound of AP and NDCG loss for learning models for a variety of vision tasks. We show that our approach provides significantly better results than simpler decomposable loss functions, while requiring a comparable training time."}],"month":"06","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1604.08269"}]},{"department":[{"_id":"KrPi"},{"_id":"HeEd"},{"_id":"VlKo"}],"date_updated":"2023-09-13T09:13:12Z","type":"conference","conference":{"name":"ASIACCS: Asia Conference on Computer and Communications Security ","location":"Incheon, Republic of Korea","end_date":"2018-06-08","start_date":"2018-06-04"},"status":"public","_id":"193","ec_funded":1,"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","main_file_link":[{"url":"https://eprint.iacr.org/2016/783","open_access":"1"}],"month":"06","abstract":[{"text":"We show attacks on five data-independent memory-hard functions (iMHF) that were submitted to the password hashing competition (PHC). Informally, an MHF is a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly lower hardware and/or energy cost than evaluating a single instance on a standard single-core architecture. Data-independent means the memory access pattern of the function is independent of the input; this makes iMHFs harder to construct than data-dependent ones, but the latter can be attacked by various side-channel attacks. Following [Alwen-Blocki'16], we capture the evaluation of an iMHF as a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC. Ideally, one would like the complexity of a DAG underlying an iMHF to be as close to quadratic in the number of nodes of the graph as possible. Instead, we show that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2, TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial property of each underlying DAG (called its depth-robustness. By establishing upper bounds on this property we are then able to apply the general technique of [Alwen-Block'16] for analyzing the hardware costs of an iMHF.","lang":"eng"}],"oa_version":"Submitted Version","author":[{"last_name":"Alwen","full_name":"Alwen, Joel F","first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Gazi","full_name":"Gazi, Peter","first_name":"Peter"},{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Klein, Karen","last_name":"Klein","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"full_name":"Osang, Georg F","orcid":"0000-0002-8882-5116","last_name":"Osang","first_name":"Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"},{"first_name":"Lenoid","last_name":"Reyzin","full_name":"Reyzin, Lenoid"},{"first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","last_name":"Rolinek","full_name":"Rolinek, Michal"},{"last_name":"Rybar","full_name":"Rybar, Michal","id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"}],"publist_id":"7723","external_id":{"isi":["000516620100005"]},"article_processing_charge":"No","title":"On the memory hardness of data independent password hashing functions","citation":{"chicago":"Alwen, Joel F, Peter Gazi, Chethan Kamath Hosdurg, Karen Klein, Georg F Osang, Krzysztof Z Pietrzak, Lenoid Reyzin, Michal Rolinek, and Michal Rybar. “On the Memory Hardness of Data Independent Password Hashing Functions.” In Proceedings of the 2018 on Asia Conference on Computer and Communication Security, 51–65. ACM, 2018. https://doi.org/10.1145/3196494.3196534.","ista":"Alwen JF, Gazi P, Kamath Hosdurg C, Klein K, Osang GF, Pietrzak KZ, Reyzin L, Rolinek M, Rybar M. 2018. On the memory hardness of data independent password hashing functions. Proceedings of the 2018 on Asia Conference on Computer and Communication Security. ASIACCS: Asia Conference on Computer and Communications Security , 51–65.","mla":"Alwen, Joel F., et al. “On the Memory Hardness of Data Independent Password Hashing Functions.” Proceedings of the 2018 on Asia Conference on Computer and Communication Security, ACM, 2018, pp. 51–65, doi:10.1145/3196494.3196534.","apa":"Alwen, J. F., Gazi, P., Kamath Hosdurg, C., Klein, K., Osang, G. F., Pietrzak, K. Z., … Rybar, M. (2018). On the memory hardness of data independent password hashing functions. In Proceedings of the 2018 on Asia Conference on Computer and Communication Security (pp. 51–65). Incheon, Republic of Korea: ACM. https://doi.org/10.1145/3196494.3196534","ama":"Alwen JF, Gazi P, Kamath Hosdurg C, et al. On the memory hardness of data independent password hashing functions. In: Proceedings of the 2018 on Asia Conference on Computer and Communication Security. ACM; 2018:51-65. doi:10.1145/3196494.3196534","ieee":"J. F. Alwen et al., “On the memory hardness of data independent password hashing functions,” in Proceedings of the 2018 on Asia Conference on Computer and Communication Security, Incheon, Republic of Korea, 2018, pp. 51–65.","short":"J.F. Alwen, P. Gazi, C. Kamath Hosdurg, K. Klein, G.F. Osang, K.Z. Pietrzak, L. Reyzin, M. Rolinek, M. Rybar, in:, Proceedings of the 2018 on Asia Conference on Computer and Communication Security, ACM, 2018, pp. 51–65."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"},{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"page":"51 - 65","doi":"10.1145/3196494.3196534","date_published":"2018-06-01T00:00:00Z","date_created":"2018-12-11T11:45:07Z","isi":1,"year":"2018","day":"01","publication":"Proceedings of the 2018 on Asia Conference on Computer and Communication Security","quality_controlled":"1","publisher":"ACM","oa":1,"acknowledgement":"Leonid Reyzin was supported in part by IST Austria and by US NSF grants 1012910, 1012798, and 1422965; this research was performed while he was visiting IST Austria."},{"abstract":[{"text":"An N-superconcentrator is a directed, acyclic graph with N input nodes and N output nodes such that every subset of the inputs and every subset of the outputs of same cardinality can be connected by node-disjoint paths. It is known that linear-size and bounded-degree superconcentrators exist. We prove the existence of such superconcentrators with asymptotic density 25.3 (where the density is the number of edges divided by N). The previously best known densities were 28 [12] and 27.4136 [17].","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1405.7828"}],"scopus_import":"1","intvolume":" 141","month":"10","publication_status":"published","publication_identifier":{"issn":["0381-7032"]},"language":[{"iso":"eng"}],"issue":"10","volume":141,"_id":"18","type":"journal_article","status":"public","date_updated":"2023-09-19T14:46:18Z","department":[{"_id":"VlKo"}],"oa":1,"publisher":"Charles Babbage Research Centre","quality_controlled":"1","year":"2018","isi":1,"publication":"Ars Combinatoria","day":"01","page":"269 - 304","date_created":"2018-12-11T11:44:11Z","date_published":"2018-10-01T00:00:00Z","citation":{"mla":"Kolmogorov, Vladimir, and Michal Rolinek. “Superconcentrators of Density 25.3.” Ars Combinatoria, vol. 141, no. 10, Charles Babbage Research Centre, 2018, pp. 269–304.","apa":"Kolmogorov, V., & Rolinek, M. (2018). Superconcentrators of density 25.3. Ars Combinatoria. Charles Babbage Research Centre.","ama":"Kolmogorov V, Rolinek M. Superconcentrators of density 25.3. Ars Combinatoria. 2018;141(10):269-304.","ieee":"V. Kolmogorov and M. Rolinek, “Superconcentrators of density 25.3,” Ars Combinatoria, vol. 141, no. 10. Charles Babbage Research Centre, pp. 269–304, 2018.","short":"V. Kolmogorov, M. Rolinek, Ars Combinatoria 141 (2018) 269–304.","chicago":"Kolmogorov, Vladimir, and Michal Rolinek. “Superconcentrators of Density 25.3.” Ars Combinatoria. Charles Babbage Research Centre, 2018.","ista":"Kolmogorov V, Rolinek M. 2018. Superconcentrators of density 25.3. Ars Combinatoria. 141(10), 269–304."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000446809500022"],"arxiv":["1405.7828"]},"article_processing_charge":"No","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"},{"full_name":"Rolinek, Michal","last_name":"Rolinek","first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"}],"publist_id":"8037","title":"Superconcentrators of density 25.3"},{"doi":"10.1145/3230649","date_published":"2018-12-01T00:00:00Z","date_created":"2019-02-17T22:59:25Z","isi":1,"year":"2018","day":"01","publication":"ACM Transactions on Algorithms","quality_controlled":"1","publisher":"ACM","oa":1,"author":[{"last_name":"Kazda","full_name":"Kazda, Alexandr","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","first_name":"Alexandr"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"full_name":"Rolinek, Michal","last_name":"Rolinek","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"}],"external_id":{"isi":["000468036500007"],"arxiv":["1602.03124"]},"article_processing_charge":"No","title":"Even delta-matroids and the complexity of planar boolean CSPs","citation":{"chicago":"Kazda, Alexandr, Vladimir Kolmogorov, and Michal Rolinek. “Even Delta-Matroids and the Complexity of Planar Boolean CSPs.” ACM Transactions on Algorithms. ACM, 2018. https://doi.org/10.1145/3230649.","ista":"Kazda A, Kolmogorov V, Rolinek M. 2018. Even delta-matroids and the complexity of planar boolean CSPs. ACM Transactions on Algorithms. 15(2), 22.","mla":"Kazda, Alexandr, et al. “Even Delta-Matroids and the Complexity of Planar Boolean CSPs.” ACM Transactions on Algorithms, vol. 15, no. 2, 22, ACM, 2018, doi:10.1145/3230649.","ama":"Kazda A, Kolmogorov V, Rolinek M. Even delta-matroids and the complexity of planar boolean CSPs. ACM Transactions on Algorithms. 2018;15(2). doi:10.1145/3230649","apa":"Kazda, A., Kolmogorov, V., & Rolinek, M. (2018). Even delta-matroids and the complexity of planar boolean CSPs. ACM Transactions on Algorithms. ACM. https://doi.org/10.1145/3230649","short":"A. Kazda, V. Kolmogorov, M. Rolinek, ACM Transactions on Algorithms 15 (2018).","ieee":"A. Kazda, V. Kolmogorov, and M. Rolinek, “Even delta-matroids and the complexity of planar boolean CSPs,” ACM Transactions on Algorithms, vol. 15, no. 2. ACM, 2018."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"article_number":"22","volume":15,"related_material":{"record":[{"relation":"earlier_version","id":"1192","status":"public"}]},"issue":"2","ec_funded":1,"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.03124"}],"month":"12","intvolume":" 15","abstract":[{"text":"The main result of this article is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Using a reduction to even Δ-matroids, we then extend the tractability result to larger classes of Δ-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely, co-independent, compact, local, linear, and binary, with the following caveat:We represent Δ-matroids by lists of tuples, while the last two use a representation by matrices. Since an n ×n matrix can represent exponentially many tuples, our tractability result is not strictly stronger than the known algorithm for linear and binary Δ-matroids.","lang":"eng"}],"oa_version":"Preprint","department":[{"_id":"VlKo"}],"date_updated":"2023-09-20T11:20:26Z","article_type":"original","type":"journal_article","status":"public","_id":"6032"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Kolmogorov, Vladimir, et al. “The Complexity of General-Valued CSPs.” SIAM Journal on Computing, vol. 46, no. 3, SIAM, 2017, pp. 1087–110, doi:10.1137/16M1091836.","apa":"Kolmogorov, V., Krokhin, A., & Rolinek, M. (2017). The complexity of general-valued CSPs. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/16M1091836","ama":"Kolmogorov V, Krokhin A, Rolinek M. The complexity of general-valued CSPs. SIAM Journal on Computing. 2017;46(3):1087-1110. doi:10.1137/16M1091836","short":"V. Kolmogorov, A. Krokhin, M. Rolinek, SIAM Journal on Computing 46 (2017) 1087–1110.","ieee":"V. Kolmogorov, A. Krokhin, and M. Rolinek, “The complexity of general-valued CSPs,” SIAM Journal on Computing, vol. 46, no. 3. SIAM, pp. 1087–1110, 2017.","chicago":"Kolmogorov, Vladimir, Andrei Krokhin, and Michal Rolinek. “The Complexity of General-Valued CSPs.” SIAM Journal on Computing. SIAM, 2017. https://doi.org/10.1137/16M1091836.","ista":"Kolmogorov V, Krokhin A, Rolinek M. 2017. The complexity of general-valued CSPs. SIAM Journal on Computing. 46(3), 1087–1110."},"title":"The complexity of general-valued CSPs","publist_id":"7138","author":[{"first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"},{"last_name":"Krokhin","full_name":"Krokhin, Andrei","first_name":"Andrei"},{"full_name":"Rolinek, Michal","last_name":"Rolinek","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"}],"project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"day":"29","publication":"SIAM Journal on Computing","year":"2017","doi":"10.1137/16M1091836","date_published":"2017-06-29T00:00:00Z","date_created":"2018-12-11T11:47:40Z","page":"1087 - 1110","publisher":"SIAM","quality_controlled":"1","oa":1,"date_updated":"2023-02-23T10:07:49Z","department":[{"_id":"VlKo"}],"_id":"644","status":"public","type":"journal_article","language":[{"iso":"eng"}],"publication_status":"published","related_material":{"record":[{"relation":"other","id":"1637","status":"public"}]},"volume":46,"issue":"3","ec_funded":1,"oa_version":"Preprint","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 6= NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in f0;1g corresponds to ordinary CSPs, where one deals only with the feasibility issue, and there is no optimization. This case is the subject of the algebraic CSP dichotomy conjecture predicting for which constraint languages CSPs are tractable (i.e., solvable in polynomial time) and for which they are NP-hard. The case when all allowed functions take only finite values corresponds to a finitevalued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Živný. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e., the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs.","lang":"eng"}],"month":"06","intvolume":" 46","scopus_import":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1502.07327"}]},{"type":"dissertation","status":"public","pubrep_id":"815","_id":"992","department":[{"_id":"VlKo"}],"file_date_updated":"2020-07-14T12:48:18Z","supervisor":[{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"date_updated":"2023-09-07T12:05:41Z","ddc":["004"],"alternative_title":["ISTA Thesis"],"month":"05","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)."}],"oa_version":"Published Version","ec_funded":1,"publication_identifier":{"issn":["2663-337X"]},"publication_status":"published","degree_awarded":"PhD","file":[{"date_updated":"2020-07-14T12:48:18Z","file_size":786145,"creator":"system","date_created":"2018-12-12T10:07:55Z","file_name":"IST-2017-815-v1+3_final_blank_signature_maybe_pdfa.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"4654","checksum":"81761fb939acb7585c36629f765b4373"},{"checksum":"2b2d7e1d6c1c79a9795a7aa0f860baf3","file_id":"6208","access_level":"closed","relation":"source_file","content_type":"application/zip","date_created":"2019-04-05T08:43:24Z","file_name":"2017_Thesis_Rolinek_source.zip","creator":"dernst","date_updated":"2020-07-14T12:48:18Z","file_size":5936337}],"language":[{"iso":"eng"}],"project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"author":[{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal","full_name":"Rolinek, Michal","last_name":"Rolinek"}],"publist_id":"6407","article_processing_charge":"No","title":"Complexity of constraint satisfaction","citation":{"chicago":"Rolinek, Michal. “Complexity of Constraint Satisfaction.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_815.","ista":"Rolinek M. 2017. Complexity of constraint satisfaction. Institute of Science and Technology Austria.","mla":"Rolinek, Michal. Complexity of Constraint Satisfaction. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_815.","ama":"Rolinek M. Complexity of constraint satisfaction. 2017. doi:10.15479/AT:ISTA:th_815","apa":"Rolinek, M. (2017). Complexity of constraint satisfaction. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_815","short":"M. Rolinek, Complexity of Constraint Satisfaction, Institute of Science and Technology Austria, 2017.","ieee":"M. Rolinek, “Complexity of constraint satisfaction,” Institute of Science and Technology Austria, 2017."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Institute of Science and Technology Austria","oa":1,"acknowledgement":"FP7/2007-2013/ERC grant agreement no 616160","page":"97","date_published":"2017-05-01T00:00:00Z","doi":"10.15479/AT:ISTA:th_815","date_created":"2018-12-11T11:49:35Z","has_accepted_license":"1","year":"2017","day":"01"},{"oa_version":"Submitted Version","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."}],"month":"01","main_file_link":[{"url":"https://arxiv.org/abs/1602.03124","open_access":"1"}],"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["978-161197478-2"]},"ec_funded":1,"related_material":{"record":[{"id":"6032","status":"public","relation":"later_version"}]},"_id":"1192","status":"public","conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"2017-01019","location":"Barcelona, Spain","start_date":"2017-01-16"},"type":"conference","date_updated":"2023-09-20T11:20:26Z","department":[{"_id":"VlKo"}],"oa":1,"quality_controlled":"1","publisher":"SIAM","day":"01","year":"2017","isi":1,"date_created":"2018-12-11T11:50:38Z","date_published":"2017-01-01T00:00:00Z","doi":"10.1137/1.9781611974782.20","page":"307 - 326","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Kazda, Alexandr, Vladimir Kolmogorov, and Michal Rolinek. “Even Delta-Matroids and the Complexity of Planar Boolean CSPs,” 307–26. SIAM, 2017. https://doi.org/10.1137/1.9781611974782.20.","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.","mla":"Kazda, Alexandr, et al. Even Delta-Matroids and the Complexity of Planar Boolean CSPs. SIAM, 2017, pp. 307–26, doi:10.1137/1.9781611974782.20.","short":"A. Kazda, V. Kolmogorov, M. Rolinek, in:, SIAM, 2017, pp. 307–326.","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.","apa":"Kazda, A., Kolmogorov, V., & 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. https://doi.org/10.1137/1.9781611974782.20","ama":"Kazda A, Kolmogorov V, Rolinek M. Even delta-matroids and the complexity of planar Boolean CSPs. In: SIAM; 2017:307-326. doi:10.1137/1.9781611974782.20"},"title":"Even delta-matroids and the complexity of planar Boolean CSPs","article_processing_charge":"No","external_id":{"isi":["000426965800020"]},"publist_id":"6159","author":[{"last_name":"Kazda","full_name":"Kazda, Alexandr","first_name":"Alexandr","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"},{"full_name":"Rolinek, Michal","last_name":"Rolinek","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"}]},{"year":"2016","publication":"SIAM Journal on Imaging Sciences","day":"03","page":"605 - 636","date_created":"2018-12-11T11:51:40Z","date_published":"2016-05-03T00:00:00Z","doi":"10.1137/15M1010257","oa":1,"publisher":"Society for Industrial and Applied Mathematics ","quality_controlled":"1","citation":{"ista":"Kolmogorov V, Pock T, Rolinek M. 2016. Total variation on a tree. SIAM Journal on Imaging Sciences. 9(2), 605–636.","chicago":"Kolmogorov, Vladimir, Thomas Pock, and Michal Rolinek. “Total Variation on a Tree.” SIAM Journal on Imaging Sciences. Society for Industrial and Applied Mathematics , 2016. https://doi.org/10.1137/15M1010257.","ama":"Kolmogorov V, Pock T, Rolinek M. Total variation on a tree. SIAM Journal on Imaging Sciences. 2016;9(2):605-636. doi:10.1137/15M1010257","apa":"Kolmogorov, V., Pock, T., & Rolinek, M. (2016). Total variation on a tree. SIAM Journal on Imaging Sciences. Society for Industrial and Applied Mathematics . https://doi.org/10.1137/15M1010257","short":"V. Kolmogorov, T. Pock, M. Rolinek, SIAM Journal on Imaging Sciences 9 (2016) 605–636.","ieee":"V. Kolmogorov, T. Pock, and M. Rolinek, “Total variation on a tree,” SIAM Journal on Imaging Sciences, vol. 9, no. 2. Society for Industrial and Applied Mathematics , pp. 605–636, 2016.","mla":"Kolmogorov, Vladimir, et al. “Total Variation on a Tree.” SIAM Journal on Imaging Sciences, vol. 9, no. 2, Society for Industrial and Applied Mathematics , 2016, pp. 605–36, doi:10.1137/15M1010257."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publist_id":"5834","author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Thomas","full_name":"Pock, Thomas","last_name":"Pock"},{"full_name":"Rolinek, Michal","last_name":"Rolinek","first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"}],"title":"Total variation on a tree","project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"publication_status":"published","language":[{"iso":"eng"}],"ec_funded":1,"volume":9,"issue":"2","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."}],"oa_version":"Preprint","main_file_link":[{"url":"http://arxiv.org/abs/1502.07770","open_access":"1"}],"scopus_import":1,"intvolume":" 9","month":"05","date_updated":"2021-01-12T06:50:15Z","department":[{"_id":"VlKo"}],"_id":"1377","type":"journal_article","status":"public"},{"oa_version":"Preprint","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."}],"month":"12","intvolume":" 9472","scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1504.07067"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-3-662-48970-3"]},"publication_status":"published","volume":9472,"ec_funded":1,"_id":"1636","status":"public","type":"conference","conference":{"name":"ISAAC: International Symposium on Algorithms and Computation","end_date":"2015-12-11","location":"Nagoya, Japan","start_date":"2015-12-09"},"date_updated":"2022-02-01T15:12:35Z","department":[{"_id":"VlKo"}],"publisher":"Springer Nature","quality_controlled":"1","oa":1,"day":"01","publication":"26th International Symposium","year":"2015","date_published":"2015-12-01T00:00:00Z","doi":"10.1007/978-3-662-48971-0_48","date_created":"2018-12-11T11:53:10Z","page":"566 - 577","project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","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","short":"V. Kolmogorov, M. Rolinek, R. Takhanov, in:, 26th International Symposium, Springer Nature, 2015, pp. 566–577.","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.","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.","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.","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."},"title":"Effectiveness of structural restrictions for hybrid CSPs","publist_id":"5519","author":[{"first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"},{"first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal","last_name":"Rolinek"},{"first_name":"Rustem","last_name":"Takhanov","full_name":"Takhanov, Rustem"}],"external_id":{"arxiv":["1504.07067"]},"article_processing_charge":"No"},{"department":[{"_id":"VlKo"}],"date_updated":"2023-02-23T12:44:26Z","status":"public","conference":{"name":"FOCS: Foundations of Computer Science","start_date":"2015-10-18","location":"Berkeley, CA, United States","end_date":"2015-10-20"},"type":"conference","_id":"1637","ec_funded":1,"related_material":{"record":[{"status":"public","id":"644","relation":"other"}]},"language":[{"iso":"eng"}],"publication_status":"published","month":"12","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1502.07327"}],"scopus_import":1,"alternative_title":["56th Annual Symposium on Foundations of Computer Science"],"oa_version":"Preprint","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"}],"title":"The complexity of general-valued CSPs","publist_id":"5518","author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Krokhin","full_name":"Krokhin, Andrei","first_name":"Andrei"},{"first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal","last_name":"Rolinek"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","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.","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.","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"},"project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"date_created":"2018-12-11T11:53:10Z","doi":"10.1109/FOCS.2015.80","date_published":"2015-12-01T00:00:00Z","page":"1246 - 1258","day":"01","year":"2015","oa":1,"publisher":"IEEE","quality_controlled":"1"},{"_id":"7038","status":"public","type":"working_paper","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["510"],"citation":{"chicago":"Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction to Mathematical Games. IST Austria, n.d.","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.","ieee":"K. Huszár and M. Rolinek, Playful Math - An introduction to mathematical games. IST Austria.","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."},"date_updated":"2020-07-14T23:11:45Z","title":"Playful Math - An introduction to mathematical games","department":[{"_id":"VlKo"},{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:47:48Z","author":[{"last_name":"Huszár","orcid":"0000-0002-5445-5057","full_name":"Huszár, Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87","first_name":"Kristóf"},{"id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal","full_name":"Rolinek, Michal","last_name":"Rolinek"}],"article_processing_charge":"No","oa_version":"Published Version","month":"06","publisher":"IST Austria","oa":1,"file":[{"checksum":"2b94e5e1f4c3fe8ab89b12806276fb09","file_id":"7039","relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_name":"2014_Playful_Math_Huszar.pdf","date_created":"2019-11-18T15:57:51Z","creator":"dernst","file_size":511233,"date_updated":"2020-07-14T12:47:48Z"}],"day":"30","language":[{"iso":"eng"}],"has_accepted_license":"1","publication_status":"draft","year":"2014","date_published":"2014-06-30T00:00:00Z","date_created":"2019-11-18T15:57:05Z","page":"5"}]