[{"project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"},{"name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"title":"New strong convergence method for the sum of two maximal monotone operators","author":[{"last_name":"Shehu","orcid":"0000-0001-9224-7139","full_name":"Shehu, Yekini","first_name":"Yekini","id":"3FC7CB58-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Dong","full_name":"Dong, Qiao-Li","first_name":"Qiao-Li"},{"first_name":"Lu-Lu","last_name":"Liu","full_name":"Liu, Lu-Lu"},{"first_name":"Jen-Chih","full_name":"Yao, Jen-Chih","last_name":"Yao"}],"external_id":{"isi":["000559345400001"]},"article_processing_charge":"Yes (via OA deal)","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Shehu, Yekini, Qiao-Li Dong, Lu-Lu Liu, and Jen-Chih Yao. “New Strong Convergence Method for the Sum of Two Maximal Monotone Operators.” Optimization and Engineering. Springer Nature, 2021. https://doi.org/10.1007/s11081-020-09544-5.","ista":"Shehu Y, Dong Q-L, Liu L-L, Yao J-C. 2021. New strong convergence method for the sum of two maximal monotone operators. Optimization and Engineering. 22, 2627–2653.","mla":"Shehu, Yekini, et al. “New Strong Convergence Method for the Sum of Two Maximal Monotone Operators.” Optimization and Engineering, vol. 22, Springer Nature, 2021, pp. 2627–53, doi:10.1007/s11081-020-09544-5.","ieee":"Y. Shehu, Q.-L. Dong, L.-L. Liu, and J.-C. Yao, “New strong convergence method for the sum of two maximal monotone operators,” Optimization and Engineering, vol. 22. Springer Nature, pp. 2627–2653, 2021.","short":"Y. Shehu, Q.-L. Dong, L.-L. Liu, J.-C. Yao, Optimization and Engineering 22 (2021) 2627–2653.","apa":"Shehu, Y., Dong, Q.-L., Liu, L.-L., & Yao, J.-C. (2021). New strong convergence method for the sum of two maximal monotone operators. Optimization and Engineering. Springer Nature. https://doi.org/10.1007/s11081-020-09544-5","ama":"Shehu Y, Dong Q-L, Liu L-L, Yao J-C. New strong convergence method for the sum of two maximal monotone operators. Optimization and Engineering. 2021;22:2627-2653. doi:10.1007/s11081-020-09544-5"},"quality_controlled":"1","publisher":"Springer Nature","oa":1,"acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). The project of Yekini Shehu has received funding from the European Research Council (ERC) under the European Union’s Seventh Framework Program (FP7—2007–2013) (Grant Agreement No. 616160). The authors are grateful to the anonymous referees and the handling Editor for their comments and suggestions which have improved the earlier version of the manuscript greatly.","doi":"10.1007/s11081-020-09544-5","date_published":"2021-02-25T00:00:00Z","date_created":"2020-08-03T14:29:57Z","page":"2627-2653","day":"25","publication":"Optimization and Engineering","has_accepted_license":"1","isi":1,"year":"2021","status":"public","type":"journal_article","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"_id":"8196","department":[{"_id":"VlKo"}],"file_date_updated":"2020-08-03T15:24:39Z","ddc":["510"],"date_updated":"2024-03-07T14:39:29Z","month":"02","intvolume":" 22","scopus_import":"1","oa_version":"Published Version","abstract":[{"text":"This paper aims to obtain a strong convergence result for a Douglas–Rachford splitting method with inertial extrapolation step for finding a zero of the sum of two set-valued maximal monotone operators without any further assumption of uniform monotonicity on any of the involved maximal monotone operators. Furthermore, our proposed method is easy to implement and the inertial factor in our proposed method is a natural choice. Our method of proof is of independent interest. Finally, some numerical implementations are given to confirm the theoretical analysis.","lang":"eng"}],"volume":22,"license":"https://creativecommons.org/licenses/by/4.0/","ec_funded":1,"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","success":1,"file_id":"8197","file_size":2137860,"date_updated":"2020-08-03T15:24:39Z","creator":"dernst","file_name":"2020_OptimizationEngineering_Shehu.pdf","date_created":"2020-08-03T15:24:39Z"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1389-4420"],"eissn":["1573-2924"]},"publication_status":"published"},{"year":"2021","has_accepted_license":"1","isi":1,"publication":"Optimization Letters","day":"01","page":"2109-2126","date_created":"2020-06-04T11:28:33Z","doi":"10.1007/s11590-020-01603-1","date_published":"2021-09-01T00:00:00Z","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). The authors are grateful to the referees for their insightful comments which have improved the earlier version of the manuscript greatly. The first author has received funding from the European Research Council (ERC) under the European Union’s Seventh Framework Program (FP7-2007-2013) (Grant agreement No. 616160).","oa":1,"publisher":"Springer Nature","quality_controlled":"1","citation":{"mla":"Shehu, Yekini, and Aviv Gibali. “New Inertial Relaxed Method for Solving Split Feasibilities.” Optimization Letters, vol. 15, Springer Nature, 2021, pp. 2109–26, doi:10.1007/s11590-020-01603-1.","ieee":"Y. Shehu and A. Gibali, “New inertial relaxed method for solving split feasibilities,” Optimization Letters, vol. 15. Springer Nature, pp. 2109–2126, 2021.","short":"Y. Shehu, A. Gibali, Optimization Letters 15 (2021) 2109–2126.","apa":"Shehu, Y., & Gibali, A. (2021). New inertial relaxed method for solving split feasibilities. Optimization Letters. Springer Nature. https://doi.org/10.1007/s11590-020-01603-1","ama":"Shehu Y, Gibali A. New inertial relaxed method for solving split feasibilities. Optimization Letters. 2021;15:2109-2126. doi:10.1007/s11590-020-01603-1","chicago":"Shehu, Yekini, and Aviv Gibali. “New Inertial Relaxed Method for Solving Split Feasibilities.” Optimization Letters. Springer Nature, 2021. https://doi.org/10.1007/s11590-020-01603-1.","ista":"Shehu Y, Gibali A. 2021. New inertial relaxed method for solving split feasibilities. Optimization Letters. 15, 2109–2126."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"Yes (via OA deal)","external_id":{"isi":["000537342300001"]},"author":[{"first_name":"Yekini","id":"3FC7CB58-F248-11E8-B48F-1D18A9856A87","full_name":"Shehu, Yekini","orcid":"0000-0001-9224-7139","last_name":"Shehu"},{"first_name":"Aviv","full_name":"Gibali, Aviv","last_name":"Gibali"}],"title":"New inertial relaxed method for solving split feasibilities","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"},{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"publication_status":"published","publication_identifier":{"eissn":["1862-4480"],"issn":["1862-4472"]},"language":[{"iso":"eng"}],"file":[{"file_id":"15089","checksum":"63c5f31cd04626152a19f97a2476281b","success":1,"content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2024-03-07T14:58:51Z","file_name":"2021_OptimizationLetters_Shehu.pdf","date_updated":"2024-03-07T14:58:51Z","file_size":2148882,"creator":"kschuh"}],"ec_funded":1,"volume":15,"abstract":[{"lang":"eng","text":"In this paper, we introduce a relaxed CQ method with alternated inertial step for solving split feasibility problems. We give convergence of the sequence generated by our method under some suitable assumptions. Some numerical implementations from sparse signal and image deblurring are reported to show the efficiency of our method."}],"oa_version":"Published Version","scopus_import":"1","intvolume":" 15","month":"09","date_updated":"2024-03-07T15:00:43Z","ddc":["510"],"file_date_updated":"2024-03-07T14:58:51Z","department":[{"_id":"VlKo"}],"_id":"7925","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","type":"journal_article","status":"public"},{"project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"chicago":"Shehu, Yekini, Xiao-Huan Li, and Qiao-Li Dong. “An Efficient Projection-Type Method for Monotone Variational Inequalities in Hilbert Spaces.” Numerical Algorithms. Springer Nature, 2020. https://doi.org/10.1007/s11075-019-00758-y.","ista":"Shehu Y, Li X-H, Dong Q-L. 2020. An efficient projection-type method for monotone variational inequalities in Hilbert spaces. Numerical Algorithms. 84, 365–388.","mla":"Shehu, Yekini, et al. “An Efficient Projection-Type Method for Monotone Variational Inequalities in Hilbert Spaces.” Numerical Algorithms, vol. 84, Springer Nature, 2020, pp. 365–88, doi:10.1007/s11075-019-00758-y.","ama":"Shehu Y, Li X-H, Dong Q-L. An efficient projection-type method for monotone variational inequalities in Hilbert spaces. Numerical Algorithms. 2020;84:365-388. doi:10.1007/s11075-019-00758-y","apa":"Shehu, Y., Li, X.-H., & Dong, Q.-L. (2020). An efficient projection-type method for monotone variational inequalities in Hilbert spaces. Numerical Algorithms. Springer Nature. https://doi.org/10.1007/s11075-019-00758-y","short":"Y. Shehu, X.-H. Li, Q.-L. Dong, Numerical Algorithms 84 (2020) 365–388.","ieee":"Y. Shehu, X.-H. Li, and Q.-L. Dong, “An efficient projection-type method for monotone variational inequalities in Hilbert spaces,” Numerical Algorithms, vol. 84. Springer Nature, pp. 365–388, 2020."},"title":"An efficient projection-type method for monotone variational inequalities in Hilbert spaces","author":[{"id":"3FC7CB58-F248-11E8-B48F-1D18A9856A87","first_name":"Yekini","last_name":"Shehu","orcid":"0000-0001-9224-7139","full_name":"Shehu, Yekini"},{"first_name":"Xiao-Huan","last_name":"Li","full_name":"Li, Xiao-Huan"},{"last_name":"Dong","full_name":"Dong, Qiao-Li","first_name":"Qiao-Li"}],"article_processing_charge":"No","external_id":{"isi":["000528979000015"]},"acknowledgement":"The research of this author is supported by the ERC grant at the IST.","publisher":"Springer Nature","quality_controlled":"1","oa":1,"day":"01","publication":"Numerical Algorithms","has_accepted_license":"1","isi":1,"year":"2020","doi":"10.1007/s11075-019-00758-y","date_published":"2020-05-01T00:00:00Z","date_created":"2019-06-27T20:09:33Z","page":"365-388","_id":"6593","status":"public","type":"journal_article","article_type":"original","ddc":["000"],"date_updated":"2023-08-17T13:51:18Z","department":[{"_id":"VlKo"}],"file_date_updated":"2020-07-14T12:47:34Z","oa_version":"Submitted Version","abstract":[{"text":"We consider the monotone variational inequality problem in a Hilbert space and describe a projection-type method with inertial terms under the following properties: (a) The method generates a strongly convergent iteration sequence; (b) The method requires, at each iteration, only one projection onto the feasible set and two evaluations of the operator; (c) The method is designed for variational inequality for which the underline operator is monotone and uniformly continuous; (d) The method includes an inertial term. The latter is also shown to speed up the convergence in our numerical results. A comparison with some related methods is given and indicates that the new method is promising.","lang":"eng"}],"month":"05","intvolume":" 84","scopus_import":"1","file":[{"date_created":"2019-10-01T13:14:10Z","file_name":"ExtragradientMethodPaper.pdf","creator":"kschuh","date_updated":"2020-07-14T12:47:34Z","file_size":359654,"file_id":"6927","checksum":"bb1a1eb3ebb2df380863d0db594673ba","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1017-1398"],"eissn":["1572-9265"]},"publication_status":"published","volume":84,"ec_funded":1},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"ista":"Shehu Y, Iyiola OS. 2020. Projection methods with alternating inertial steps for variational inequalities: Weak and linear convergence. Applied Numerical Mathematics. 157, 315–337.","chicago":"Shehu, Yekini, and Olaniyi S. Iyiola. “Projection Methods with Alternating Inertial Steps for Variational Inequalities: Weak and Linear Convergence.” Applied Numerical Mathematics. Elsevier, 2020. https://doi.org/10.1016/j.apnum.2020.06.009.","ama":"Shehu Y, Iyiola OS. Projection methods with alternating inertial steps for variational inequalities: Weak and linear convergence. Applied Numerical Mathematics. 2020;157:315-337. doi:10.1016/j.apnum.2020.06.009","apa":"Shehu, Y., & Iyiola, O. S. (2020). Projection methods with alternating inertial steps for variational inequalities: Weak and linear convergence. Applied Numerical Mathematics. Elsevier. https://doi.org/10.1016/j.apnum.2020.06.009","ieee":"Y. Shehu and O. S. Iyiola, “Projection methods with alternating inertial steps for variational inequalities: Weak and linear convergence,” Applied Numerical Mathematics, vol. 157. Elsevier, pp. 315–337, 2020.","short":"Y. Shehu, O.S. Iyiola, Applied Numerical Mathematics 157 (2020) 315–337.","mla":"Shehu, Yekini, and Olaniyi S. Iyiola. “Projection Methods with Alternating Inertial Steps for Variational Inequalities: Weak and Linear Convergence.” Applied Numerical Mathematics, vol. 157, Elsevier, 2020, pp. 315–37, doi:10.1016/j.apnum.2020.06.009."},"title":"Projection methods with alternating inertial steps for variational inequalities: Weak and linear convergence","external_id":{"isi":["000564648400018"]},"article_processing_charge":"No","author":[{"id":"3FC7CB58-F248-11E8-B48F-1D18A9856A87","first_name":"Yekini","last_name":"Shehu","orcid":"0000-0001-9224-7139","full_name":"Shehu, Yekini"},{"full_name":"Iyiola, Olaniyi S.","last_name":"Iyiola","first_name":"Olaniyi S."}],"project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"publication":"Applied Numerical Mathematics","day":"01","year":"2020","has_accepted_license":"1","isi":1,"date_created":"2020-07-02T09:02:33Z","doi":"10.1016/j.apnum.2020.06.009","date_published":"2020-11-01T00:00:00Z","page":"315-337","acknowledgement":"The authors are grateful to the two anonymous referees for their insightful comments and suggestions which have improved the earlier version of the manuscript greatly. The first author has received funding from the European Research Council (ERC) under the European Union Seventh Framework Programme (FP7 - 2007-2013) (Grant agreement No. 616160).","oa":1,"quality_controlled":"1","publisher":"Elsevier","ddc":["510"],"date_updated":"2023-08-22T07:50:43Z","file_date_updated":"2020-07-14T12:48:09Z","department":[{"_id":"VlKo"}],"_id":"8077","status":"public","article_type":"original","type":"journal_article","language":[{"iso":"eng"}],"file":[{"date_created":"2020-07-02T09:08:59Z","file_name":"2020_AppliedNumericalMath_Shehu.pdf","creator":"dernst","date_updated":"2020-07-14T12:48:09Z","file_size":2874203,"file_id":"8078","checksum":"87d81324a62c82baa925c009dfcb0200","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"publication_status":"published","publication_identifier":{"issn":["0168-9274"]},"ec_funded":1,"volume":157,"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"The projection methods with vanilla inertial extrapolation step for variational inequalities have been of interest to many authors recently due to the improved convergence speed contributed by the presence of inertial extrapolation step. However, it is discovered that these projection methods with inertial steps lose the Fejér monotonicity of the iterates with respect to the solution, which is being enjoyed by their corresponding non-inertial projection methods for variational inequalities. This lack of Fejér monotonicity makes projection methods with vanilla inertial extrapolation step for variational inequalities not to converge faster than their corresponding non-inertial projection methods at times. Also, it has recently been proved that the projection methods with vanilla inertial extrapolation step may provide convergence rates that are worse than the classical projected gradient methods for strongly convex functions. In this paper, we introduce projection methods with alternated inertial extrapolation step for solving variational inequalities. We show that the sequence of iterates generated by our methods converges weakly to a solution of the variational inequality under some appropriate conditions. The Fejér monotonicity of even subsequence is recovered in these methods and linear rate of convergence is obtained. The numerical implementations of our methods compared with some other inertial projection methods show that our method is more efficient and outperforms some of these inertial projection methods."}],"intvolume":" 157","month":"11","scopus_import":"1"},{"ec_funded":1,"volume":184,"publication_status":"published","publication_identifier":{"eissn":["1573-2878"],"issn":["0022-3239"]},"language":[{"iso":"eng"}],"file":[{"date_updated":"2021-03-16T23:30:04Z","file_size":332641,"creator":"dernst","date_created":"2020-10-12T10:40:27Z","file_name":"2020_JourOptimizationTheoryApplic_Shehu.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"8647","checksum":"9f6dc6c6bf2b48cb3a2091a9ed5feaf2","embargo":"2021-03-15"}],"scopus_import":"1","intvolume":" 184","month":"03","abstract":[{"lang":"eng","text":"In this paper, we introduce an inertial projection-type method with different updating strategies for solving quasi-variational inequalities with strongly monotone and Lipschitz continuous operators in real Hilbert spaces. Under standard assumptions, we establish different strong convergence results for the proposed algorithm. Primary numerical experiments demonstrate the potential applicability of our scheme compared with some related methods in the literature."}],"oa_version":"Submitted Version","department":[{"_id":"VlKo"}],"file_date_updated":"2021-03-16T23:30:04Z","date_updated":"2023-09-06T11:27:15Z","ddc":["518","510","515"],"type":"journal_article","article_type":"original","status":"public","_id":"7161","page":"877–894","date_created":"2019-12-09T21:33:44Z","doi":"10.1007/s10957-019-01616-6","date_published":"2020-03-01T00:00:00Z","year":"2020","isi":1,"has_accepted_license":"1","publication":"Journal of Optimization Theory and Applications","day":"01","oa":1,"quality_controlled":"1","publisher":"Springer Nature","acknowledgement":"We are grateful to the anonymous referees and editor whose insightful comments helped to considerably improve an earlier version of this paper. The research of the first author is supported by an ERC Grant from the Institute of Science and Technology (IST).","external_id":{"isi":["000511805200009"]},"article_processing_charge":"No","author":[{"full_name":"Shehu, Yekini","orcid":"0000-0001-9224-7139","last_name":"Shehu","id":"3FC7CB58-F248-11E8-B48F-1D18A9856A87","first_name":"Yekini"},{"full_name":"Gibali, Aviv","last_name":"Gibali","first_name":"Aviv"},{"full_name":"Sagratella, Simone","last_name":"Sagratella","first_name":"Simone"}],"title":"Inertial projection-type methods for solving quasi-variational inequalities in real Hilbert spaces","citation":{"ista":"Shehu Y, Gibali A, Sagratella S. 2020. Inertial projection-type methods for solving quasi-variational inequalities in real Hilbert spaces. Journal of Optimization Theory and Applications. 184, 877–894.","chicago":"Shehu, Yekini, Aviv Gibali, and Simone Sagratella. “Inertial Projection-Type Methods for Solving Quasi-Variational Inequalities in Real Hilbert Spaces.” Journal of Optimization Theory and Applications. Springer Nature, 2020. https://doi.org/10.1007/s10957-019-01616-6.","ieee":"Y. Shehu, A. Gibali, and S. Sagratella, “Inertial projection-type methods for solving quasi-variational inequalities in real Hilbert spaces,” Journal of Optimization Theory and Applications, vol. 184. Springer Nature, pp. 877–894, 2020.","short":"Y. Shehu, A. Gibali, S. Sagratella, Journal of Optimization Theory and Applications 184 (2020) 877–894.","ama":"Shehu Y, Gibali A, Sagratella S. Inertial projection-type methods for solving quasi-variational inequalities in real Hilbert spaces. Journal of Optimization Theory and Applications. 2020;184:877–894. doi:10.1007/s10957-019-01616-6","apa":"Shehu, Y., Gibali, A., & Sagratella, S. (2020). Inertial projection-type methods for solving quasi-variational inequalities in real Hilbert spaces. Journal of Optimization Theory and Applications. Springer Nature. https://doi.org/10.1007/s10957-019-01616-6","mla":"Shehu, Yekini, et al. “Inertial Projection-Type Methods for Solving Quasi-Variational Inequalities in Real Hilbert Spaces.” Journal of Optimization Theory and Applications, vol. 184, Springer Nature, 2020, pp. 877–894, doi:10.1007/s10957-019-01616-6."},"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"}]},{"page":"77:1-77:12","date_created":"2019-07-29T12:23:29Z","date_published":"2019-07-01T00:00:00Z","doi":"10.4230/LIPICS.ICALP.2019.77","year":"2019","has_accepted_license":"1","publication":"46th International Colloquium on Automata, Languages and Programming","day":"01","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","external_id":{"arxiv":["1803.02289"]},"author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"}],"title":"Testing the complexity of a valued CSP language","citation":{"chicago":"Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” In 46th International Colloquium on Automata, Languages and Programming, 132:77:1-77:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPICS.ICALP.2019.77.","ista":"Kolmogorov V. 2019. Testing the complexity of a valued CSP language. 46th International Colloquium on Automata, Languages and Programming. ICALP 2019: International Colloquim on Automata, Languages and Programming, LIPIcs, vol. 132, 77:1-77:12.","mla":"Kolmogorov, Vladimir. “Testing the Complexity of a Valued CSP Language.” 46th International Colloquium on Automata, Languages and Programming, vol. 132, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12, doi:10.4230/LIPICS.ICALP.2019.77.","short":"V. Kolmogorov, in:, 46th International Colloquium on Automata, Languages and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 77:1-77:12.","ieee":"V. Kolmogorov, “Testing the complexity of a valued CSP language,” in 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 2019, vol. 132, p. 77:1-77:12.","apa":"Kolmogorov, V. (2019). Testing the complexity of a valued CSP language. In 46th International Colloquium on Automata, Languages and Programming (Vol. 132, p. 77:1-77:12). Patras, Greece: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2019.77","ama":"Kolmogorov V. Testing the complexity of a valued CSP language. In: 46th International Colloquium on Automata, Languages and Programming. Vol 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:77:1-77:12. doi:10.4230/LIPICS.ICALP.2019.77"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"ec_funded":1,"volume":132,"publication_status":"published","publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-109-2"]},"language":[{"iso":"eng"}],"file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","checksum":"f5ebee8eec6ae09e30365578ee63a492","file_id":"6738","creator":"dernst","file_size":575475,"date_updated":"2020-07-14T12:47:38Z","file_name":"2019_LIPICS_Kolmogorov.pdf","date_created":"2019-07-31T07:01:45Z"}],"alternative_title":["LIPIcs"],"scopus_import":1,"intvolume":" 132","month":"07","abstract":[{"lang":"eng","text":"A Valued Constraint Satisfaction Problem (VCSP) provides a common framework that can express a wide range of discrete optimization problems. A VCSP instance is given by a finite set of variables, a finite domain of labels, and an objective function to be minimized. This function is represented as a sum of terms where each term depends on a subset of the variables. To obtain different classes of optimization problems, one can restrict all terms to come from a fixed set Γ of cost functions, called a language. \r\nRecent breakthrough results have established a complete complexity classification of such classes with respect to language Γ: if all cost functions in Γ satisfy a certain algebraic condition then all Γ-instances can be solved in polynomial time, otherwise the problem is NP-hard. Unfortunately, testing this condition for a given language Γ is known to be NP-hard. We thus study exponential algorithms for this meta-problem. We show that the tractability condition of a finite-valued language Γ can be tested in O(3‾√3|D|⋅poly(size(Γ))) time, where D is the domain of Γ and poly(⋅) is some fixed polynomial. We also obtain a matching lower bound under the Strong Exponential Time Hypothesis (SETH). More precisely, we prove that for any constant δ<1 there is no O(3‾√3δ|D|) algorithm, assuming that SETH holds."}],"oa_version":"Published Version","file_date_updated":"2020-07-14T12:47:38Z","department":[{"_id":"VlKo"}],"date_updated":"2021-01-12T08:08:40Z","ddc":["000"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"name":"ICALP 2019: International Colloquim on Automata, Languages and Programming","start_date":"2019-07-08","location":"Patras, Greece","end_date":"2019-07-12"},"type":"conference","status":"public","_id":"6725"},{"publication_status":"published","publication_identifier":{"eissn":["1420-9012"],"issn":["1422-6383"]},"language":[{"iso":"eng"}],"file":[{"date_updated":"2020-07-14T12:47:34Z","file_size":466942,"creator":"kschuh","date_created":"2019-07-03T15:20:40Z","file_name":"Springer_2019_Shehu.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"6605","checksum":"c6d18cb1e16fc0c36a0e0f30b4ebbc2d"}],"ec_funded":1,"volume":74,"issue":"4","abstract":[{"lang":"eng","text":"It is well known that many problems in image recovery, signal processing, and machine learning can be modeled as finding zeros of the sum of maximal monotone and Lipschitz continuous monotone operators. Many papers have studied forward-backward splitting methods for finding zeros of the sum of two monotone operators in Hilbert spaces. Most of the proposed splitting methods in the literature have been proposed for the sum of maximal monotone and inverse-strongly monotone operators in Hilbert spaces. In this paper, we consider splitting methods for finding zeros of the sum of maximal monotone operators and Lipschitz continuous monotone operators in Banach spaces. We obtain weak and strong convergence results for the zeros of the sum of maximal monotone and Lipschitz continuous monotone operators in Banach spaces. Many already studied problems in the literature can be considered as special cases of this paper."}],"oa_version":"Published Version","scopus_import":"1","intvolume":" 74","month":"12","date_updated":"2023-08-28T12:26:22Z","ddc":["000"],"department":[{"_id":"VlKo"}],"file_date_updated":"2020-07-14T12:47:34Z","_id":"6596","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"article_type":"original","type":"journal_article","status":"public","year":"2019","isi":1,"has_accepted_license":"1","publication":"Results in Mathematics","day":"01","date_created":"2019-06-29T10:11:30Z","doi":"10.1007/s00025-019-1061-4","date_published":"2019-12-01T00:00:00Z","oa":1,"quality_controlled":"1","publisher":"Springer","citation":{"chicago":"Shehu, Yekini. “Convergence Results of Forward-Backward Algorithms for Sum of Monotone Operators in Banach Spaces.” Results in Mathematics. Springer, 2019. https://doi.org/10.1007/s00025-019-1061-4.","ista":"Shehu Y. 2019. Convergence results of forward-backward algorithms for sum of monotone operators in Banach spaces. Results in Mathematics. 74(4), 138.","mla":"Shehu, Yekini. “Convergence Results of Forward-Backward Algorithms for Sum of Monotone Operators in Banach Spaces.” Results in Mathematics, vol. 74, no. 4, 138, Springer, 2019, doi:10.1007/s00025-019-1061-4.","short":"Y. Shehu, Results in Mathematics 74 (2019).","ieee":"Y. Shehu, “Convergence results of forward-backward algorithms for sum of monotone operators in Banach spaces,” Results in Mathematics, vol. 74, no. 4. Springer, 2019.","ama":"Shehu Y. Convergence results of forward-backward algorithms for sum of monotone operators in Banach spaces. Results in Mathematics. 2019;74(4). doi:10.1007/s00025-019-1061-4","apa":"Shehu, Y. (2019). Convergence results of forward-backward algorithms for sum of monotone operators in Banach spaces. Results in Mathematics. Springer. https://doi.org/10.1007/s00025-019-1061-4"},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"isi":["000473237500002"],"arxiv":["2101.09068"]},"article_processing_charge":"Yes (via OA deal)","author":[{"last_name":"Shehu","orcid":"0000-0001-9224-7139","full_name":"Shehu, Yekini","id":"3FC7CB58-F248-11E8-B48F-1D18A9856A87","first_name":"Yekini"}],"title":"Convergence results of forward-backward algorithms for sum of monotone operators in Banach spaces","article_number":"138","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"},{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}]},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"mla":"Shehu, Yekini, et al. “Convergence Analysis of Projection Method for Variational Inequalities.” Computational and Applied Mathematics, vol. 38, no. 4, 161, Springer Nature, 2019, doi:10.1007/s40314-019-0955-9.","ieee":"Y. Shehu, O. S. Iyiola, X.-H. Li, and Q.-L. Dong, “Convergence analysis of projection method for variational inequalities,” Computational and Applied Mathematics, vol. 38, no. 4. Springer Nature, 2019.","short":"Y. Shehu, O.S. Iyiola, X.-H. Li, Q.-L. Dong, Computational and Applied Mathematics 38 (2019).","ama":"Shehu Y, Iyiola OS, Li X-H, Dong Q-L. Convergence analysis of projection method for variational inequalities. Computational and Applied Mathematics. 2019;38(4). doi:10.1007/s40314-019-0955-9","apa":"Shehu, Y., Iyiola, O. S., Li, X.-H., & Dong, Q.-L. (2019). Convergence analysis of projection method for variational inequalities. Computational and Applied Mathematics. Springer Nature. https://doi.org/10.1007/s40314-019-0955-9","chicago":"Shehu, Yekini, Olaniyi S. Iyiola, Xiao-Huan Li, and Qiao-Li Dong. “Convergence Analysis of Projection Method for Variational Inequalities.” Computational and Applied Mathematics. Springer Nature, 2019. https://doi.org/10.1007/s40314-019-0955-9.","ista":"Shehu Y, Iyiola OS, Li X-H, Dong Q-L. 2019. Convergence analysis of projection method for variational inequalities. Computational and Applied Mathematics. 38(4), 161."},"title":"Convergence analysis of projection method for variational inequalities","author":[{"id":"3FC7CB58-F248-11E8-B48F-1D18A9856A87","first_name":"Yekini","orcid":"0000-0001-9224-7139","full_name":"Shehu, Yekini","last_name":"Shehu"},{"first_name":"Olaniyi S.","full_name":"Iyiola, Olaniyi S.","last_name":"Iyiola"},{"first_name":"Xiao-Huan","last_name":"Li","full_name":"Li, Xiao-Huan"},{"last_name":"Dong","full_name":"Dong, Qiao-Li","first_name":"Qiao-Li"}],"article_processing_charge":"No","external_id":{"isi":["000488973100005"],"arxiv":["2101.09081"]},"article_number":"161","project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"day":"01","publication":"Computational and Applied Mathematics","isi":1,"has_accepted_license":"1","year":"2019","date_published":"2019-12-01T00:00:00Z","doi":"10.1007/s40314-019-0955-9","date_created":"2019-11-12T12:41:44Z","publisher":"Springer Nature","quality_controlled":"1","oa":1,"ddc":["510","515","518"],"date_updated":"2023-08-30T07:20:32Z","department":[{"_id":"VlKo"}],"_id":"7000","status":"public","type":"journal_article","article_type":"original","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2238-3603"],"eissn":["1807-0302"]},"publication_status":"published","issue":"4","volume":38,"ec_funded":1,"oa_version":"Published Version","abstract":[{"text":"The main contributions of this paper are the proposition and the convergence analysis of a class of inertial projection-type algorithm for solving variational inequality problems in real Hilbert spaces where the underline operator is monotone and uniformly continuous. We carry out a unified analysis of the proposed method under very mild assumptions. In particular, weak convergence of the generated sequence is established and nonasymptotic O(1 / n) rate of convergence is established, where n denotes the iteration counter. We also present some experimental results to illustrate the profits gained by introducing the inertial extrapolation steps.","lang":"eng"}],"month":"12","intvolume":" 38","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s40314-019-0955-9"}]},{"intvolume":" 48","month":"10","main_file_link":[{"url":"https://arxiv.org/abs/1809.01537","open_access":"1"}],"scopus_import":"1","oa_version":"Preprint","abstract":[{"text":"We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby state that addresses the violation, while (we hope) not introducing many new violations. An important class of focused local search algorithms with provable performance guarantees has recently arisen from algorithmizations of the Lovász local lemma (LLL), a nonconstructive tool for proving the existence of satisfying states by introducing a background measure on the state space. While powerful, the state transitions of algorithms in this class must be, in a precise sense, perfectly compatible with the background measure. In many applications this is a very restrictive requirement, and one needs to step outside the class. Here we introduce the notion of measure distortion and develop a framework for analyzing arbitrary focused stochastic local search algorithms, recovering LLL algorithmizations as the special case of no distortion. Our framework takes as input an arbitrary algorithm of such type and an arbitrary probability measure and shows how to use the measure as a yardstick of algorithmic progress, even for algorithms designed independently of the measure.","lang":"eng"}],"ec_funded":1,"volume":48,"issue":"5","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"status":"public","article_type":"original","type":"journal_article","_id":"7412","department":[{"_id":"VlKo"}],"date_updated":"2023-09-06T15:25:29Z","oa":1,"quality_controlled":"1","publisher":"SIAM","date_created":"2020-01-30T09:27:32Z","doi":"10.1137/16m109332x","date_published":"2019-10-31T00:00:00Z","page":"1583-1602","publication":"SIAM Journal on Computing","day":"31","year":"2019","isi":1,"project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"title":"A local lemma for focused stochastical algorithms","article_processing_charge":"No","external_id":{"arxiv":["1809.01537"],"isi":["000493900200005"]},"author":[{"last_name":"Achlioptas","full_name":"Achlioptas, Dimitris","first_name":"Dimitris"},{"full_name":"Iliopoulos, Fotis","last_name":"Iliopoulos","first_name":"Fotis"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Achlioptas, Dimitris, Fotis Iliopoulos, and Vladimir Kolmogorov. “A Local Lemma for Focused Stochastical Algorithms.” SIAM Journal on Computing. SIAM, 2019. https://doi.org/10.1137/16m109332x.","ista":"Achlioptas D, Iliopoulos F, Kolmogorov V. 2019. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 48(5), 1583–1602.","mla":"Achlioptas, Dimitris, et al. “A Local Lemma for Focused Stochastical Algorithms.” SIAM Journal on Computing, vol. 48, no. 5, SIAM, 2019, pp. 1583–602, doi:10.1137/16m109332x.","short":"D. Achlioptas, F. Iliopoulos, V. Kolmogorov, SIAM Journal on Computing 48 (2019) 1583–1602.","ieee":"D. Achlioptas, F. Iliopoulos, and V. Kolmogorov, “A local lemma for focused stochastical algorithms,” SIAM Journal on Computing, vol. 48, no. 5. SIAM, pp. 1583–1602, 2019.","ama":"Achlioptas D, Iliopoulos F, Kolmogorov V. A local lemma for focused stochastical algorithms. SIAM Journal on Computing. 2019;48(5):1583-1602. doi:10.1137/16m109332x","apa":"Achlioptas, D., Iliopoulos, F., & Kolmogorov, V. (2019). A local lemma for focused stochastical algorithms. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/16m109332x"}},{"doi":"10.1109/CVPR.2019.01140","date_published":"2019-06-01T00:00:00Z","date_created":"2020-02-09T23:00:52Z","day":"01","publication":"Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition","isi":1,"year":"2019","quality_controlled":"1","publisher":"IEEE","oa":1,"title":"Map inference via block-coordinate Frank-Wolfe algorithm","author":[{"full_name":"Swoboda, Paul","last_name":"Swoboda","first_name":"Paul","id":"446560C6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"article_processing_charge":"No","external_id":{"arxiv":["1806.05049"],"isi":["000542649304076"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"short":"P. Swoboda, V. Kolmogorov, in:, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE, 2019.","ieee":"P. Swoboda and V. Kolmogorov, “Map inference via block-coordinate Frank-Wolfe algorithm,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Long Beach, CA, United States, 2019, vol. 2019–June.","ama":"Swoboda P, Kolmogorov V. Map inference via block-coordinate Frank-Wolfe algorithm. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Vol 2019-June. IEEE; 2019. doi:10.1109/CVPR.2019.01140","apa":"Swoboda, P., & Kolmogorov, V. (2019). Map inference via block-coordinate Frank-Wolfe algorithm. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Vol. 2019–June). Long Beach, CA, United States: IEEE. https://doi.org/10.1109/CVPR.2019.01140","mla":"Swoboda, Paul, and Vladimir Kolmogorov. “Map Inference via Block-Coordinate Frank-Wolfe Algorithm.” Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2019–June, 11138–11147, IEEE, 2019, doi:10.1109/CVPR.2019.01140.","ista":"Swoboda P, Kolmogorov V. 2019. Map inference via block-coordinate Frank-Wolfe algorithm. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition vol. 2019–June, 11138–11147.","chicago":"Swoboda, Paul, and Vladimir Kolmogorov. “Map Inference via Block-Coordinate Frank-Wolfe Algorithm.” In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vol. 2019–June. IEEE, 2019. https://doi.org/10.1109/CVPR.2019.01140."},"project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"article_number":"11138-11147","volume":"2019-June","ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781728132938"],"issn":["10636919"]},"publication_status":"published","month":"06","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1806.05049"}],"oa_version":"Preprint","abstract":[{"text":"We present a new proximal bundle method for Maximum-A-Posteriori (MAP) inference in structured energy minimization problems. The method optimizes a Lagrangean relaxation of the original energy minimization problem using a multi plane block-coordinate Frank-Wolfe method that takes advantage of the specific structure of the Lagrangean decomposition. We show empirically that our method outperforms state-of-the-art Lagrangean decomposition based algorithms on some challenging Markov Random Field, multi-label discrete tomography and graph matching problems.","lang":"eng"}],"department":[{"_id":"VlKo"}],"date_updated":"2023-09-07T14:54:24Z","status":"public","type":"conference","conference":{"start_date":"2019-06-15","end_date":"2019-06-20","location":"Long Beach, CA, United States","name":"CVPR: Conference on Computer Vision and Pattern Recognition"},"_id":"7468"},{"date_created":"2020-04-05T22:00:50Z","doi":"10.1109/ICCVW.2019.00097","date_published":"2019-10-01T00:00:00Z","year":"2019","publication_status":"published","publication_identifier":{"isbn":["9781728150239"]},"isi":1,"language":[{"iso":"eng"}],"publication":"Proceedings of the 2019 International Conference on Computer Vision Workshop","day":"01","publisher":"IEEE","scopus_import":"1","quality_controlled":"1","month":"10","abstract":[{"text":"Deep neural networks (DNNs) have become increasingly important due to their excellent empirical performance on a wide range of problems. However, regularization is generally achieved by indirect means, largely due to the complex set of functions defined by a network and the difficulty in measuring function complexity. There exists no method in the literature for additive regularization based on a norm of the function, as is classically considered in statistical learning theory. In this work, we study the tractability of function norms for deep neural networks with ReLU activations. We provide, to the best of our knowledge, the first proof in the literature of the NP-hardness of computing function norms of DNNs of 3 or more layers. We also highlight a fundamental difference between shallow and deep networks. In the light on these results, we propose a new regularization strategy based on approximate function norms, and show its efficiency on a segmentation task with a DNN.","lang":"eng"}],"oa_version":"None","article_processing_charge":"No","external_id":{"isi":["000554591600090"]},"author":[{"last_name":"Rannen-Triki","full_name":"Rannen-Triki, Amal","first_name":"Amal"},{"full_name":"Berman, Maxim","last_name":"Berman","first_name":"Maxim"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Matthew B.","full_name":"Blaschko, Matthew B.","last_name":"Blaschko"}],"department":[{"_id":"VlKo"}],"title":"Function norms for neural networks","date_updated":"2023-09-08T11:19:12Z","citation":{"chicago":"Rannen-Triki, Amal, Maxim Berman, Vladimir Kolmogorov, and Matthew B. Blaschko. “Function Norms for Neural Networks.” In Proceedings of the 2019 International Conference on Computer Vision Workshop. IEEE, 2019. https://doi.org/10.1109/ICCVW.2019.00097.","ista":"Rannen-Triki A, Berman M, Kolmogorov V, Blaschko MB. 2019. Function norms for neural networks. Proceedings of the 2019 International Conference on Computer Vision Workshop. ICCVW: International Conference on Computer Vision Workshop, 748–752.","mla":"Rannen-Triki, Amal, et al. “Function Norms for Neural Networks.” Proceedings of the 2019 International Conference on Computer Vision Workshop, 748–752, IEEE, 2019, doi:10.1109/ICCVW.2019.00097.","short":"A. Rannen-Triki, M. Berman, V. Kolmogorov, M.B. Blaschko, in:, Proceedings of the 2019 International Conference on Computer Vision Workshop, IEEE, 2019.","ieee":"A. Rannen-Triki, M. Berman, V. Kolmogorov, and M. B. Blaschko, “Function norms for neural networks,” in Proceedings of the 2019 International Conference on Computer Vision Workshop, Seoul, South Korea, 2019.","ama":"Rannen-Triki A, Berman M, Kolmogorov V, Blaschko MB. Function norms for neural networks. In: Proceedings of the 2019 International Conference on Computer Vision Workshop. IEEE; 2019. doi:10.1109/ICCVW.2019.00097","apa":"Rannen-Triki, A., Berman, M., Kolmogorov, V., & Blaschko, M. B. (2019). Function norms for neural networks. In Proceedings of the 2019 International Conference on Computer Vision Workshop. Seoul, South Korea: IEEE. https://doi.org/10.1109/ICCVW.2019.00097"},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","conference":{"location":"Seoul, South Korea","end_date":"2019-10-28","start_date":"2019-10-27","name":"ICCVW: International Conference on Computer Vision Workshop"},"type":"conference","status":"public","_id":"7639","article_number":"748-752"},{"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["01628828"]},"volume":40,"issue":"7","oa_version":"Preprint","abstract":[{"lang":"eng","text":"We consider the NP-hard problem of MAP-inference for undirected discrete graphical models. We propose a polynomial time and practically efficient algorithm for finding a part of its optimal solution. Specifically, our algorithm marks some labels of the considered graphical model either as (i) optimal, meaning that they belong to all optimal solutions of the inference problem; (ii) non-optimal if they provably do not belong to any solution. With access to an exact solver of a linear programming relaxation to the MAP-inference problem, our algorithm marks the maximal possible (in a specified sense) number of labels. We also present a version of the algorithm, which has access to a suboptimal dual solver only and still can ensure the (non-)optimality for the marked labels, although the overall number of the marked labels may decrease. We propose an efficient implementation, which runs in time comparable to a single run of a suboptimal dual solver. Our method is well-scalable and shows state-of-the-art results on computational benchmarks from machine learning and computer vision."}],"intvolume":" 40","month":"07","main_file_link":[{"url":"https://arxiv.org/abs/1508.07902","open_access":"1"}],"scopus_import":1,"date_updated":"2021-01-12T08:11:32Z","department":[{"_id":"VlKo"}],"_id":"703","status":"public","type":"journal_article","publication":"IEEE Transactions on Pattern Analysis and Machine Intelligence","day":"01","year":"2018","date_created":"2018-12-11T11:48:01Z","date_published":"2018-07-01T00:00:00Z","doi":"10.1109/TPAMI.2017.2730884","page":"1668-1682","oa":1,"publisher":"IEEE","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Shekhovtsov, Alexander, et al. “Maximum Persistency via Iterative Relaxed Inference with Graphical Models.” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 7, IEEE, 2018, pp. 1668–82, doi:10.1109/TPAMI.2017.2730884.","ama":"Shekhovtsov A, Swoboda P, Savchynskyy B. Maximum persistency via iterative relaxed inference with graphical models. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2018;40(7):1668-1682. doi:10.1109/TPAMI.2017.2730884","apa":"Shekhovtsov, A., Swoboda, P., & Savchynskyy, B. (2018). Maximum persistency via iterative relaxed inference with graphical models. IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. https://doi.org/10.1109/TPAMI.2017.2730884","ieee":"A. Shekhovtsov, P. Swoboda, and B. Savchynskyy, “Maximum persistency via iterative relaxed inference with graphical models,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 40, no. 7. IEEE, pp. 1668–1682, 2018.","short":"A. Shekhovtsov, P. Swoboda, B. Savchynskyy, IEEE Transactions on Pattern Analysis and Machine Intelligence 40 (2018) 1668–1682.","chicago":"Shekhovtsov, Alexander, Paul Swoboda, and Bogdan Savchynskyy. “Maximum Persistency via Iterative Relaxed Inference with Graphical Models.” IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE, 2018. https://doi.org/10.1109/TPAMI.2017.2730884.","ista":"Shekhovtsov A, Swoboda P, Savchynskyy B. 2018. Maximum persistency via iterative relaxed inference with graphical models. IEEE Transactions on Pattern Analysis and Machine Intelligence. 40(7), 1668–1682."},"title":"Maximum persistency via iterative relaxed inference with graphical models","external_id":{"arxiv":["1508.07902"]},"publist_id":"6992","author":[{"first_name":"Alexander","last_name":"Shekhovtsov","full_name":"Shekhovtsov, Alexander"},{"id":"446560C6-F248-11E8-B48F-1D18A9856A87","first_name":"Paul","last_name":"Swoboda","full_name":"Swoboda, Paul"},{"first_name":"Bogdan","full_name":"Savchynskyy, Bogdan","last_name":"Savchynskyy"}]},{"date_updated":"2023-09-05T15:37:18Z","department":[{"_id":"VlKo"}],"_id":"10864","series_title":"OCTR","status":"public","type":"book_chapter","language":[{"iso":"eng"}],"publication_identifier":{"eisbn":["9783319747729"],"issn":["2211-2758"],"isbn":["9783319747712"],"eissn":["2211-2766"]},"publication_status":"published","volume":16,"oa_version":"Preprint","abstract":[{"text":"We prove that every congruence distributive variety has directed Jónsson terms, and every congruence modular variety has directed Gumm terms. The directed terms we construct witness every case of absorption witnessed by the original Jónsson or Gumm terms. This result is equivalent to a pair of claims about absorption for admissible preorders in congruence distributive and congruence modular varieties, respectively. For finite algebras, these absorption theorems have already seen significant applications, but until now, it was not clear if the theorems hold for general algebras as well. Our method also yields a novel proof of a result by P. Lipparini about the existence of a chain of terms (which we call Pixley terms) in varieties that are at the same time congruence distributive and k-permutable for some k.","lang":"eng"}],"place":"Cham","month":"03","intvolume":" 16","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1502.01072"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"mla":"Kazda, Alexandr, et al. “Absorption and Directed Jónsson Terms.” Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science, edited by J Czelakowski, vol. 16, Springer Nature, 2018, pp. 203–20, doi:10.1007/978-3-319-74772-9_7.","ama":"Kazda A, Kozik M, McKenzie R, Moore M. Absorption and directed Jónsson terms. In: Czelakowski J, ed. Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science. Vol 16. OCTR. Cham: Springer Nature; 2018:203-220. doi:10.1007/978-3-319-74772-9_7","apa":"Kazda, A., Kozik, M., McKenzie, R., & Moore, M. (2018). Absorption and directed Jónsson terms. In J. Czelakowski (Ed.), Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science (Vol. 16, pp. 203–220). Cham: Springer Nature. https://doi.org/10.1007/978-3-319-74772-9_7","short":"A. Kazda, M. Kozik, R. McKenzie, M. Moore, in:, J. Czelakowski (Ed.), Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science, Springer Nature, Cham, 2018, pp. 203–220.","ieee":"A. Kazda, M. Kozik, R. McKenzie, and M. Moore, “Absorption and directed Jónsson terms,” in Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science, vol. 16, J. Czelakowski, Ed. Cham: Springer Nature, 2018, pp. 203–220.","chicago":"Kazda, Alexandr, Marcin Kozik, Ralph McKenzie, and Matthew Moore. “Absorption and Directed Jónsson Terms.” In Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science, edited by J Czelakowski, 16:203–20. OCTR. Cham: Springer Nature, 2018. https://doi.org/10.1007/978-3-319-74772-9_7.","ista":"Kazda A, Kozik M, McKenzie R, Moore M. 2018.Absorption and directed Jónsson terms. In: Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science. vol. 16, 203–220."},"editor":[{"first_name":"J","full_name":"Czelakowski, J","last_name":"Czelakowski"}],"title":"Absorption and directed Jónsson terms","author":[{"last_name":"Kazda","full_name":"Kazda, Alexandr","first_name":"Alexandr","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Marcin","full_name":"Kozik, Marcin","last_name":"Kozik"},{"full_name":"McKenzie, Ralph","last_name":"McKenzie","first_name":"Ralph"},{"first_name":"Matthew","full_name":"Moore, Matthew","last_name":"Moore"}],"article_processing_charge":"No","external_id":{"arxiv":["1502.01072"]},"day":"21","publication":"Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science","year":"2018","doi":"10.1007/978-3-319-74772-9_7","date_published":"2018-03-21T00:00:00Z","date_created":"2022-03-18T10:30:32Z","page":"203-220","acknowledgement":"The second author was supported by National Science Center grant DEC-2011-/01/B/ST6/01006.","quality_controlled":"1","publisher":"Springer Nature","oa":1},{"oa":1,"publisher":"IEEE","quality_controlled":"1","publication":"2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition","day":"28","year":"2018","isi":1,"date_created":"2018-12-11T11:45:33Z","date_published":"2018-06-28T00:00:00Z","doi":"10.1109/cvpr.2018.00389","page":"3693-3701","project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"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.","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.","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","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.","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."},"title":"Efficient optimization for rank-based loss functions","external_id":{"arxiv":["1604.08269"],"isi":["000457843603087"]},"article_processing_charge":"No","author":[{"first_name":"Pritish","last_name":"Mohapatra","full_name":"Mohapatra, Pritish"},{"last_name":"Rolinek","full_name":"Rolinek, Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"},{"first_name":"C V","last_name":"Jawahar","full_name":"Jawahar, C V"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"first_name":"M Pawan","last_name":"Kumar","full_name":"Kumar, M Pawan"}],"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","main_file_link":[{"url":"https://arxiv.org/abs/1604.08269","open_access":"1"}],"scopus_import":"1","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"isbn":["9781538664209"]},"ec_funded":1,"_id":"273","status":"public","conference":{"location":"Salt Lake City, UT, USA","end_date":"2018-06-22","start_date":"2018-06-18","name":"CVPR: Conference on Computer Vision and Pattern Recognition"},"type":"conference","date_updated":"2023-09-11T13:24:43Z","department":[{"_id":"VlKo"}]},{"ec_funded":1,"publication_status":"published","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://eprint.iacr.org/2016/783","open_access":"1"}],"scopus_import":"1","month":"06","abstract":[{"lang":"eng","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."}],"oa_version":"Submitted Version","department":[{"_id":"KrPi"},{"_id":"HeEd"},{"_id":"VlKo"}],"date_updated":"2023-09-13T09:13:12Z","conference":{"location":"Incheon, Republic of Korea","end_date":"2018-06-08","start_date":"2018-06-04","name":"ASIACCS: Asia Conference on Computer and Communications Security "},"type":"conference","status":"public","_id":"193","page":"51 - 65","date_created":"2018-12-11T11:45:07Z","doi":"10.1145/3196494.3196534","date_published":"2018-06-01T00:00:00Z","year":"2018","isi":1,"publication":"Proceedings of the 2018 on Asia Conference on Computer and Communication Security","day":"01","oa":1,"quality_controlled":"1","publisher":"ACM","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.","external_id":{"isi":["000516620100005"]},"article_processing_charge":"No","publist_id":"7723","author":[{"full_name":"Alwen, Joel F","last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F"},{"full_name":"Gazi, Peter","last_name":"Gazi","first_name":"Peter"},{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan"},{"full_name":"Klein, Karen","last_name":"Klein","first_name":"Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Osang","orcid":"0000-0002-8882-5116","full_name":"Osang, Georg F","first_name":"Georg F","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak"},{"first_name":"Lenoid","full_name":"Reyzin, Lenoid","last_name":"Reyzin"},{"full_name":"Rolinek, Michal","last_name":"Rolinek","first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"},{"id":"2B3E3DE8-F248-11E8-B48F-1D18A9856A87","first_name":"Michal","last_name":"Rybar","full_name":"Rybar, Michal"}],"title":"On the memory hardness of data independent password hashing functions","citation":{"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.","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.","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.","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","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."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}]},{"project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Kolmogorov V. 2018. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 47(6), 2029–2056.","chicago":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM), 2018. https://doi.org/10.1137/16m1093306.","apa":"Kolmogorov, V. (2018). Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. Society for Industrial & Applied Mathematics (SIAM). https://doi.org/10.1137/16m1093306","ama":"Kolmogorov V. Commutativity in the algorithmic Lovász local lemma. SIAM Journal on Computing. 2018;47(6):2029-2056. doi:10.1137/16m1093306","short":"V. Kolmogorov, SIAM Journal on Computing 47 (2018) 2029–2056.","ieee":"V. Kolmogorov, “Commutativity in the algorithmic Lovász local lemma,” SIAM Journal on Computing, vol. 47, no. 6. Society for Industrial & Applied Mathematics (SIAM), pp. 2029–2056, 2018.","mla":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovász Local Lemma.” SIAM Journal on Computing, vol. 47, no. 6, Society for Industrial & Applied Mathematics (SIAM), 2018, pp. 2029–56, doi:10.1137/16m1093306."},"title":"Commutativity in the algorithmic Lovász local lemma","external_id":{"arxiv":["1506.08547"],"isi":["000453785100001"]},"article_processing_charge":"No","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"}],"oa":1,"quality_controlled":"1","publisher":"Society for Industrial & Applied Mathematics (SIAM)","publication":"SIAM Journal on Computing","day":"08","year":"2018","isi":1,"date_created":"2019-02-13T12:59:33Z","date_published":"2018-11-08T00:00:00Z","doi":"10.1137/16m1093306","page":"2029-2056","_id":"5975","status":"public","type":"journal_article","date_updated":"2023-09-19T14:24:58Z","department":[{"_id":"VlKo"}],"oa_version":"Preprint","abstract":[{"text":"We consider the recent formulation of the algorithmic Lov ́asz Local Lemma [N. Har-vey and J. Vondr ́ak, inProceedings of FOCS, 2015, pp. 1327–1345; D. Achlioptas and F. Iliopoulos,inProceedings of SODA, 2016, pp. 2024–2038; D. Achlioptas, F. Iliopoulos, and V. Kolmogorov,ALocal Lemma for Focused Stochastic Algorithms, arXiv preprint, 2018] for finding objects that avoid“bad features,” or “flaws.” It extends the Moser–Tardos resampling algorithm [R. A. Moser andG. Tardos,J. ACM, 57 (2010), 11] to more general discrete spaces. At each step the method picks aflaw present in the current state and goes to a new state according to some prespecified probabilitydistribution (which depends on the current state and the selected flaw). However, the recent formu-lation is less flexible than the Moser–Tardos method since it requires a specific flaw selection rule,whereas the algorithm of Moser and Tardos allows an arbitrary rule (and thus can potentially beimplemented more efficiently). We formulate a new “commutativity” condition and prove that it issufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additionalassumption. We then show that existing resampling oracles for perfect matchings and permutationsdo satisfy this condition.","lang":"eng"}],"intvolume":" 47","month":"11","main_file_link":[{"url":"https://arxiv.org/abs/1506.08547","open_access":"1"}],"scopus_import":"1","language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"ec_funded":1,"issue":"6","related_material":{"record":[{"id":"1193","status":"public","relation":"earlier_version"}]},"volume":47},{"page":"6581-6588","date_created":"2019-02-13T13:32:48Z","date_published":"2018-02-01T00:00:00Z","year":"2018","publication_status":"published","isi":1,"language":[{"iso":"eng"}],"publication":"Proceedings of the 32st AAAI Conference on Artificial Intelligence","day":"01","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/2004.06370","open_access":"1"}],"quality_controlled":"1","publisher":"AAAI Press","scopus_import":"1","month":"02","abstract":[{"lang":"eng","text":"We consider the MAP-inference problem for graphical models,which is a valued constraint satisfaction problem defined onreal numbers with a natural summation operation. We proposea family of relaxations (different from the famous Sherali-Adams hierarchy), which naturally define lower bounds for itsoptimum. This family always contains a tight relaxation andwe give an algorithm able to find it and therefore, solve theinitial non-relaxed NP-hard problem.The relaxations we consider decompose the original probleminto two non-overlapping parts: an easy LP-tight part and adifficult one. For the latter part a combinatorial solver must beused. As we show in our experiments, in a number of applica-tions the second, difficult part constitutes only a small fractionof the whole problem. This property allows to significantlyreduce the computational time of the combinatorial solver andtherefore solve problems which were out of reach before."}],"oa_version":"Preprint","article_processing_charge":"No","external_id":{"isi":["000485488906082"],"arxiv":["2004.06370"]},"author":[{"first_name":"Stefan","full_name":"Haller, Stefan","last_name":"Haller"},{"first_name":"Paul","id":"446560C6-F248-11E8-B48F-1D18A9856A87","last_name":"Swoboda","full_name":"Swoboda, Paul"},{"last_name":"Savchynskyy","full_name":"Savchynskyy, Bogdan","first_name":"Bogdan"}],"department":[{"_id":"VlKo"}],"title":"Exact MAP-inference by confining combinatorial search with LP relaxation","date_updated":"2023-09-19T14:26:52Z","citation":{"mla":"Haller, Stefan, et al. “Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation.” Proceedings of the 32st AAAI Conference on Artificial Intelligence, AAAI Press, 2018, pp. 6581–88.","ama":"Haller S, Swoboda P, Savchynskyy B. Exact MAP-inference by confining combinatorial search with LP relaxation. In: Proceedings of the 32st AAAI Conference on Artificial Intelligence. AAAI Press; 2018:6581-6588.","apa":"Haller, S., Swoboda, P., & Savchynskyy, B. (2018). Exact MAP-inference by confining combinatorial search with LP relaxation. In Proceedings of the 32st AAAI Conference on Artificial Intelligence (pp. 6581–6588). New Orleans, LU, United States: AAAI Press.","ieee":"S. Haller, P. Swoboda, and B. Savchynskyy, “Exact MAP-inference by confining combinatorial search with LP relaxation,” in Proceedings of the 32st AAAI Conference on Artificial Intelligence, New Orleans, LU, United States, 2018, pp. 6581–6588.","short":"S. Haller, P. Swoboda, B. Savchynskyy, in:, Proceedings of the 32st AAAI Conference on Artificial Intelligence, AAAI Press, 2018, pp. 6581–6588.","chicago":"Haller, Stefan, Paul Swoboda, and Bogdan Savchynskyy. “Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation.” In Proceedings of the 32st AAAI Conference on Artificial Intelligence, 6581–88. AAAI Press, 2018.","ista":"Haller S, Swoboda P, Savchynskyy B. 2018. Exact MAP-inference by confining combinatorial search with LP relaxation. Proceedings of the 32st AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence, 6581–6588."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","conference":{"name":"AAAI: Conference on Artificial Intelligence","location":"New Orleans, LU, United States","end_date":"2018-02-07","start_date":"2018-02-02"},"type":"conference","status":"public","_id":"5978"},{"isi":1,"year":"2018","day":"01","publication":"Ars Combinatoria","page":"269 - 304","date_published":"2018-10-01T00:00:00Z","date_created":"2018-12-11T11:44:11Z","quality_controlled":"1","publisher":"Charles Babbage Research Centre","oa":1,"citation":{"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.","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.","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.","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."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal","last_name":"Rolinek"}],"publist_id":"8037","article_processing_charge":"No","external_id":{"arxiv":["1405.7828"],"isi":["000446809500022"]},"title":"Superconcentrators of density 25.3","publication_identifier":{"issn":["0381-7032"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":141,"issue":"10","abstract":[{"lang":"eng","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]."}],"oa_version":"Preprint","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1405.7828"}],"month":"10","intvolume":" 141","date_updated":"2023-09-19T14:46:18Z","department":[{"_id":"VlKo"}],"_id":"18","type":"journal_article","status":"public"},{"volume":15,"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1192"}]},"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":[{"lang":"eng","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."}],"oa_version":"Preprint","department":[{"_id":"VlKo"}],"date_updated":"2023-09-20T11:20:26Z","type":"journal_article","article_type":"original","status":"public","_id":"6032","date_published":"2018-12-01T00:00:00Z","doi":"10.1145/3230649","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":[{"id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","first_name":"Alexandr","last_name":"Kazda","full_name":"Kazda, Alexandr"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","last_name":"Rolinek","full_name":"Rolinek, Michal"}],"article_processing_charge":"No","external_id":{"isi":["000468036500007"],"arxiv":["1602.03124"]},"title":"Even delta-matroids and the complexity of planar boolean CSPs","citation":{"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.","short":"A. Kazda, V. Kolmogorov, M. Rolinek, ACM Transactions on Algorithms 15 (2018).","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","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.","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.","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."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"article_number":"22"},{"abstract":[{"text":"Graph matching problems for large displacement optical flow of RGB-D images.","lang":"eng"}],"oa_version":"Published Version","publisher":"Institute of Science and Technology Austria","oa":1,"month":"01","has_accepted_license":"1","year":"2018","datarep_id":"82","file":[{"creator":"system","file_size":1737958,"date_updated":"2020-07-14T12:47:05Z","file_name":"IST-2018-82-v1+1_GraphFlowMatchingProblems.zip","date_created":"2018-12-12T13:02:34Z","relation":"main_file","access_level":"open_access","content_type":"application/zip","checksum":"53c17082848e12f3c2e1b4185b578208","file_id":"5600"}],"day":"04","related_material":{"link":[{"relation":"research_paper","url":"https://doi.org/10.1007/978-3-319-24947-6_23"}]},"doi":"10.15479/AT:ISTA:82","date_published":"2018-01-04T00:00:00Z","contributor":[{"id":"446560C6-F248-11E8-B48F-1D18A9856A87","first_name":"Paul","contributor_type":"researcher","last_name":"Swoboda"}],"license":"https://creativecommons.org/publicdomain/zero/1.0/","date_created":"2018-12-12T12:31:36Z","_id":"5573","type":"research_data","tmp":{"image":"/images/cc_0.png","legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","name":"Creative Commons Public Domain Dedication (CC0 1.0)","short":"CC0 (1.0)"},"status":"public","keyword":["graph matching","quadratic assignment problem<"],"date_updated":"2024-02-21T13:41:17Z","citation":{"chicago":"Alhaija, Hassan, Anita Sellent, Daniel Kondermann, and Carsten Rother. “Graph Matching Problems for GraphFlow – 6D Large Displacement Scene Flow.” Institute of Science and Technology Austria, 2018. https://doi.org/10.15479/AT:ISTA:82.","ista":"Alhaija H, Sellent A, Kondermann D, Rother C. 2018. Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow, Institute of Science and Technology Austria, 10.15479/AT:ISTA:82.","mla":"Alhaija, Hassan, et al. Graph Matching Problems for GraphFlow – 6D Large Displacement Scene Flow. Institute of Science and Technology Austria, 2018, doi:10.15479/AT:ISTA:82.","short":"H. Alhaija, A. Sellent, D. Kondermann, C. Rother, (2018).","ieee":"H. Alhaija, A. Sellent, D. Kondermann, and C. Rother, “Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow.” Institute of Science and Technology Austria, 2018.","apa":"Alhaija, H., Sellent, A., Kondermann, D., & Rother, C. (2018). Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:82","ama":"Alhaija H, Sellent A, Kondermann D, Rother C. Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow. 2018. doi:10.15479/AT:ISTA:82"},"ddc":["001"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Alhaija, Hassan","last_name":"Alhaija","first_name":"Hassan"},{"first_name":"Anita","full_name":"Sellent, Anita","last_name":"Sellent"},{"first_name":"Daniel","full_name":"Kondermann, Daniel","last_name":"Kondermann"},{"first_name":"Carsten","last_name":"Rother","full_name":"Rother, Carsten"}],"article_processing_charge":"No","department":[{"_id":"VlKo"}],"file_date_updated":"2020-07-14T12:47:05Z","title":"Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow"},{"publist_id":"7147","author":[{"full_name":"Trajkovska, Vera","last_name":"Trajkovska","first_name":"Vera"},{"first_name":"Paul","id":"446560C6-F248-11E8-B48F-1D18A9856A87","full_name":"Swoboda, Paul","last_name":"Swoboda"},{"first_name":"Freddie","last_name":"Åström","full_name":"Åström, Freddie"},{"first_name":"Stefanie","full_name":"Petra, Stefanie","last_name":"Petra"}],"editor":[{"first_name":"François","last_name":"Lauze","full_name":"Lauze, François"},{"first_name":"Yiqiu","last_name":"Dong","full_name":"Dong, Yiqiu"},{"last_name":"Bjorholm Dahl","full_name":"Bjorholm Dahl, Anders","first_name":"Anders"}],"title":"Graphical model parameter learning by inverse linear programming","department":[{"_id":"VlKo"}],"date_updated":"2021-01-12T08:07:23Z","citation":{"chicago":"Trajkovska, Vera, Paul Swoboda, Freddie Åström, and Stefanie Petra. “Graphical Model Parameter Learning by Inverse Linear Programming.” edited by François Lauze, Yiqiu Dong, and Anders Bjorholm Dahl, 10302:323–34. Springer, 2017. https://doi.org/10.1007/978-3-319-58771-4_26.","ista":"Trajkovska V, Swoboda P, Åström F, Petra S. 2017. Graphical model parameter learning by inverse linear programming. SSVM: Scale Space and Variational Methods in Computer Vision, LNCS, vol. 10302, 323–334.","mla":"Trajkovska, Vera, et al. Graphical Model Parameter Learning by Inverse Linear Programming. Edited by François Lauze et al., vol. 10302, Springer, 2017, pp. 323–34, doi:10.1007/978-3-319-58771-4_26.","apa":"Trajkovska, V., Swoboda, P., Åström, F., & Petra, S. (2017). Graphical model parameter learning by inverse linear programming. In F. Lauze, Y. Dong, & A. Bjorholm Dahl (Eds.) (Vol. 10302, pp. 323–334). Presented at the SSVM: Scale Space and Variational Methods in Computer Vision, Kolding, Denmark: Springer. https://doi.org/10.1007/978-3-319-58771-4_26","ama":"Trajkovska V, Swoboda P, Åström F, Petra S. Graphical model parameter learning by inverse linear programming. In: Lauze F, Dong Y, Bjorholm Dahl A, eds. Vol 10302. Springer; 2017:323-334. doi:10.1007/978-3-319-58771-4_26","ieee":"V. Trajkovska, P. Swoboda, F. Åström, and S. Petra, “Graphical model parameter learning by inverse linear programming,” presented at the SSVM: Scale Space and Variational Methods in Computer Vision, Kolding, Denmark, 2017, vol. 10302, pp. 323–334.","short":"V. Trajkovska, P. Swoboda, F. Åström, S. Petra, in:, F. Lauze, Y. Dong, A. Bjorholm Dahl (Eds.), Springer, 2017, pp. 323–334."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2017-06-04","location":"Kolding, Denmark","end_date":"2017-06-08","name":"SSVM: Scale Space and Variational Methods in Computer Vision"},"type":"conference","status":"public","_id":"641","page":"323 - 334","date_created":"2018-12-11T11:47:39Z","doi":"10.1007/978-3-319-58771-4_26","volume":10302,"date_published":"2017-01-01T00:00:00Z","year":"2017","publication_status":"published","publication_identifier":{"isbn":["978-331958770-7"]},"language":[{"iso":"eng"}],"day":"01","scopus_import":1,"publisher":"Springer","alternative_title":["LNCS"],"quality_controlled":"1","intvolume":" 10302","month":"01","abstract":[{"text":"We introduce two novel methods for learning parameters of graphical models for image labelling. The following two tasks underline both methods: (i) perturb model parameters based on given features and ground truth labelings, so as to exactly reproduce these labelings as optima of the local polytope relaxation of the labelling problem; (ii) train a predictor for the perturbed model parameters so that improved model parameters can be applied to the labelling of novel data. Our first method implements task (i) by inverse linear programming and task (ii) using a regressor e.g. a Gaussian process. Our second approach simultaneously solves tasks (i) and (ii) in a joint manner, while being restricted to linearly parameterised predictors. Experiments demonstrate the merits of both approaches.","lang":"eng"}],"oa_version":"None"},{"publist_id":"7138","author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"first_name":"Andrei","full_name":"Krokhin, Andrei","last_name":"Krokhin"},{"first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","last_name":"Rolinek","full_name":"Rolinek, Michal"}],"title":"The complexity of general-valued CSPs","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","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.","short":"V. Kolmogorov, A. Krokhin, M. Rolinek, SIAM Journal on Computing 46 (2017) 1087–1110.","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."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"page":"1087 - 1110","date_created":"2018-12-11T11:47:40Z","doi":"10.1137/16M1091836","date_published":"2017-06-29T00:00:00Z","year":"2017","publication":"SIAM Journal on Computing","day":"29","oa":1,"quality_controlled":"1","publisher":"SIAM","department":[{"_id":"VlKo"}],"date_updated":"2023-02-23T10:07:49Z","type":"journal_article","status":"public","_id":"644","ec_funded":1,"related_material":{"record":[{"relation":"other","id":"1637","status":"public"}]},"volume":46,"issue":"3","publication_status":"published","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/1502.07327","open_access":"1"}],"scopus_import":1,"intvolume":" 46","month":"06","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"}],"oa_version":"Preprint"},{"date_updated":"2021-01-12T08:07:34Z","department":[{"_id":"VlKo"}],"_id":"646","status":"public","type":"conference","conference":{"name":"SSVM: Scale Space and Variational Methods in Computer Vision","start_date":"2017-06-04","end_date":"2017-06-08","location":"Kolding, Denmark"},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-331958770-7"]},"publication_status":"published","volume":10302,"ec_funded":1,"oa_version":"Submitted Version","abstract":[{"text":"We present a novel convex relaxation and a corresponding inference algorithm for the non-binary discrete tomography problem, that is, reconstructing discrete-valued images from few linear measurements. In contrast to state of the art approaches that split the problem into a continuous reconstruction problem for the linear measurement constraints and a discrete labeling problem to enforce discrete-valued reconstructions, we propose a joint formulation that addresses both problems simultaneously, resulting in a tighter convex relaxation. For this purpose a constrained graphical model is set up and evaluated using a novel relaxation optimized by dual decomposition. We evaluate our approach experimentally and show superior solutions both mathematically (tighter relaxation) and experimentally in comparison to previously proposed relaxations.","lang":"eng"}],"month":"06","intvolume":" 10302","alternative_title":["LNCS"],"scopus_import":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1703.03769"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Kuske, Jan, et al. A Novel Convex Relaxation for Non Binary Discrete Tomography. Edited by François Lauze et al., vol. 10302, Springer, 2017, pp. 235–46, doi:10.1007/978-3-319-58771-4_19.","apa":"Kuske, J., Swoboda, P., & Petra, S. (2017). A novel convex relaxation for non binary discrete tomography. In F. Lauze, Y. Dong, & A. Bjorholm Dahl (Eds.) (Vol. 10302, pp. 235–246). Presented at the SSVM: Scale Space and Variational Methods in Computer Vision, Kolding, Denmark: Springer. https://doi.org/10.1007/978-3-319-58771-4_19","ama":"Kuske J, Swoboda P, Petra S. A novel convex relaxation for non binary discrete tomography. In: Lauze F, Dong Y, Bjorholm Dahl A, eds. Vol 10302. Springer; 2017:235-246. doi:10.1007/978-3-319-58771-4_19","short":"J. Kuske, P. Swoboda, S. Petra, in:, F. Lauze, Y. Dong, A. Bjorholm Dahl (Eds.), Springer, 2017, pp. 235–246.","ieee":"J. Kuske, P. Swoboda, and S. Petra, “A novel convex relaxation for non binary discrete tomography,” presented at the SSVM: Scale Space and Variational Methods in Computer Vision, Kolding, Denmark, 2017, vol. 10302, pp. 235–246.","chicago":"Kuske, Jan, Paul Swoboda, and Stefanie Petra. “A Novel Convex Relaxation for Non Binary Discrete Tomography.” edited by François Lauze, Yiqiu Dong, and Anders Bjorholm Dahl, 10302:235–46. Springer, 2017. https://doi.org/10.1007/978-3-319-58771-4_19.","ista":"Kuske J, Swoboda P, Petra S. 2017. A novel convex relaxation for non binary discrete tomography. SSVM: Scale Space and Variational Methods in Computer Vision, LNCS, vol. 10302, 235–246."},"title":"A novel convex relaxation for non binary discrete tomography","editor":[{"last_name":"Lauze","full_name":"Lauze, François","first_name":"François"},{"first_name":"Yiqiu","full_name":"Dong, Yiqiu","last_name":"Dong"},{"full_name":"Bjorholm Dahl, Anders","last_name":"Bjorholm Dahl","first_name":"Anders"}],"publist_id":"7132","author":[{"first_name":"Jan","full_name":"Kuske, Jan","last_name":"Kuske"},{"full_name":"Swoboda, Paul","last_name":"Swoboda","first_name":"Paul","id":"446560C6-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Stefanie","last_name":"Petra","full_name":"Petra, Stefanie"}],"project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"day":"01","year":"2017","doi":"10.1007/978-3-319-58771-4_19","date_published":"2017-06-01T00:00:00Z","date_created":"2018-12-11T11:47:41Z","page":"235 - 246","publisher":"Springer","quality_controlled":"1","oa":1},{"type":"dissertation","status":"public","pubrep_id":"815","_id":"992","file_date_updated":"2020-07-14T12:48:18Z","department":[{"_id":"VlKo"}],"supervisor":[{"first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"}],"date_updated":"2023-09-07T12:05:41Z","ddc":["004"],"alternative_title":["ISTA Thesis"],"month":"05","abstract":[{"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).","lang":"eng"}],"oa_version":"Published Version","ec_funded":1,"publication_identifier":{"issn":["2663-337X"]},"degree_awarded":"PhD","publication_status":"published","file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"81761fb939acb7585c36629f765b4373","file_id":"4654","file_size":786145,"date_updated":"2020-07-14T12:48:18Z","creator":"system","file_name":"IST-2017-815-v1+3_final_blank_signature_maybe_pdfa.pdf","date_created":"2018-12-12T10:07:55Z"},{"creator":"dernst","date_updated":"2020-07-14T12:48:18Z","file_size":5936337,"date_created":"2019-04-05T08:43:24Z","file_name":"2017_Thesis_Rolinek_source.zip","access_level":"closed","relation":"source_file","content_type":"application/zip","checksum":"2b2d7e1d6c1c79a9795a7aa0f860baf3","file_id":"6208"}],"language":[{"iso":"eng"}],"project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"publist_id":"6407","author":[{"last_name":"Rolinek","full_name":"Rolinek, Michal","first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"}],"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.","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.","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"},"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"},{"date_updated":"2023-09-20T11:20:26Z","department":[{"_id":"VlKo"}],"_id":"1192","status":"public","type":"conference","conference":{"name":"SODA: Symposium on Discrete Algorithms","location":"Barcelona, Spain","end_date":"2017-01019","start_date":"2017-01-16"},"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-161197478-2"]},"publication_status":"published","related_material":{"record":[{"id":"6032","status":"public","relation":"later_version"}]},"ec_funded":1,"oa_version":"Submitted Version","abstract":[{"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.","lang":"eng"}],"month":"01","main_file_link":[{"url":"https://arxiv.org/abs/1602.03124","open_access":"1"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"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.","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.","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.","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","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","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."},"title":"Even delta-matroids and the complexity of planar Boolean CSPs","publist_id":"6159","author":[{"id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","first_name":"Alexandr","last_name":"Kazda","full_name":"Kazda, Alexandr"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"},{"last_name":"Rolinek","full_name":"Rolinek, Michal","first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"}],"external_id":{"isi":["000426965800020"]},"article_processing_charge":"No","project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425"}],"day":"01","isi":1,"year":"2017","doi":"10.1137/1.9781611974782.20","date_published":"2017-01-01T00:00:00Z","date_created":"2018-12-11T11:50:38Z","page":"307 - 326","quality_controlled":"1","publisher":"SIAM","oa":1},{"abstract":[{"lang":"eng","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."}],"oa_version":"Submitted Version","scopus_import":"1","month":"01","intvolume":" 2017","publication_identifier":{"isbn":["978-153860457-1"]},"publication_status":"published","file":[{"date_updated":"2020-07-14T12:48:15Z","file_size":944332,"creator":"dernst","date_created":"2019-01-18T12:49:38Z","file_name":"2017_CVPR_Swoboda2.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"5848","checksum":"e38a2740daad1ea178465843b5072906"}],"language":[{"iso":"eng"}],"volume":2017,"ec_funded":1,"_id":"916","type":"conference","conference":{"name":"CVPR: Computer Vision and Pattern Recognition","end_date":"2017-07-26","location":"Honolulu, HA, United States","start_date":"2017-07-21"},"status":"public","date_updated":"2023-09-26T15:41:40Z","ddc":["000"],"department":[{"_id":"VlKo"}],"file_date_updated":"2020-07-14T12:48:15Z","publisher":"IEEE","quality_controlled":"1","oa":1,"isi":1,"has_accepted_license":"1","year":"2017","day":"01","page":"7062-7071","date_published":"2017-01-01T00:00:00Z","doi":"10.1109/CVPR.2017.747","date_created":"2018-12-11T11:49:11Z","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"citation":{"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.","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. https://doi.org/10.1109/CVPR.2017.747.","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:10.1109/CVPR.2017.747","apa":"Swoboda, P., Rother, C., Abu Alhaija, C., Kainmueller, D., & 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. https://doi.org/10.1109/CVPR.2017.747","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.","short":"P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, B. Savchynskyy, in:, IEEE, 2017, pp. 7062–7071.","mla":"Swoboda, Paul, et al. A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching. Vol. 2017, IEEE, 2017, pp. 7062–71, doi:10.1109/CVPR.2017.747."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publist_id":"6525","author":[{"last_name":"Swoboda","full_name":"Swoboda, Paul","first_name":"Paul","id":"446560C6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Rother","full_name":"Rother, Carsten","first_name":"Carsten"},{"first_name":"Carsten","full_name":"Abu Alhaija, Carsten","last_name":"Abu Alhaija"},{"first_name":"Dagmar","last_name":"Kainmueller","full_name":"Kainmueller, Dagmar"},{"first_name":"Bogdan","last_name":"Savchynskyy","full_name":"Savchynskyy, Bogdan"}],"article_processing_charge":"No","external_id":{"isi":["000418371407018"]},"title":"A study of lagrangean decompositions and dual ascent solvers for graph matching"},{"has_accepted_license":"1","isi":1,"year":"2017","day":"01","page":"4990-4999","date_published":"2017-07-01T00:00:00Z","doi":"10.1109/CVPR.2017.530","date_created":"2018-12-11T11:49:11Z","publisher":"IEEE","quality_controlled":"1","oa":1,"citation":{"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.","chicago":"Swoboda, Paul, and Bjoern Andres. “A Message Passing Algorithm for the Minimum Cost Multicut Problem,” 2017:4990–99. IEEE, 2017. https://doi.org/10.1109/CVPR.2017.530.","apa":"Swoboda, P., & 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. https://doi.org/10.1109/CVPR.2017.530","ama":"Swoboda P, Andres B. A message passing algorithm for the minimum cost multicut problem. In: Vol 2017. IEEE; 2017:4990-4999. doi:10.1109/CVPR.2017.530","short":"P. Swoboda, B. Andres, in:, IEEE, 2017, pp. 4990–4999.","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.","mla":"Swoboda, Paul, and Bjoern Andres. A Message Passing Algorithm for the Minimum Cost Multicut Problem. Vol. 2017, IEEE, 2017, pp. 4990–99, doi:10.1109/CVPR.2017.530."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"full_name":"Swoboda, Paul","last_name":"Swoboda","id":"446560C6-F248-11E8-B48F-1D18A9856A87","first_name":"Paul"},{"first_name":"Bjoern","last_name":"Andres","full_name":"Andres, Bjoern"}],"publist_id":"6526","external_id":{"isi":["000418371405009"]},"article_processing_charge":"No","title":"A message passing algorithm for the minimum cost multicut problem","project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"publication_identifier":{"isbn":["978-153860457-1"]},"publication_status":"published","file":[{"file_name":"Swoboda_A_Message_Passing_CVPR_2017_paper.pdf","date_created":"2019-01-18T12:52:46Z","file_size":883264,"date_updated":"2020-07-14T12:48:15Z","creator":"dernst","checksum":"7e51dacefa693574581a32da3eff63dc","file_id":"5849","content_type":"application/pdf","relation":"main_file","access_level":"open_access"}],"language":[{"iso":"eng"}],"volume":2017,"ec_funded":1,"abstract":[{"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.","lang":"eng"}],"oa_version":"Submitted Version","scopus_import":"1","month":"07","intvolume":" 2017","date_updated":"2023-09-26T15:43:27Z","ddc":["000"],"file_date_updated":"2020-07-14T12:48:15Z","department":[{"_id":"VlKo"}],"_id":"915","type":"conference","conference":{"end_date":"2017-07-26","location":"Honolulu, HA, United States","start_date":"2017-07-21","name":"CVPR: Computer Vision and Pattern Recognition"},"status":"public"},{"project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"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.","short":"P. Swoboda, J. Kuske, B. Savchynskyy, in:, IEEE, 2017, pp. 4950–4960.","apa":"Swoboda, P., Kuske, J., & 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. https://doi.org/10.1109/CVPR.2017.526","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:10.1109/CVPR.2017.526","mla":"Swoboda, Paul, et al. A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems. Vol. 2017, IEEE, 2017, pp. 4950–60, doi:10.1109/CVPR.2017.526.","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.","chicago":"Swoboda, Paul, Jan Kuske, and Bogdan Savchynskyy. “A Dual Ascent Framework for Lagrangean Decomposition of Combinatorial Problems,” 2017:4950–60. IEEE, 2017. https://doi.org/10.1109/CVPR.2017.526."},"title":"A dual ascent framework for Lagrangean decomposition of combinatorial problems","author":[{"id":"446560C6-F248-11E8-B48F-1D18A9856A87","first_name":"Paul","last_name":"Swoboda","full_name":"Swoboda, Paul"},{"first_name":"Jan","last_name":"Kuske","full_name":"Kuske, Jan"},{"last_name":"Savchynskyy","full_name":"Savchynskyy, Bogdan","first_name":"Bogdan"}],"publist_id":"6524","article_processing_charge":"No","external_id":{"isi":["000418371405005"]},"quality_controlled":"1","publisher":"IEEE","oa":1,"day":"01","has_accepted_license":"1","isi":1,"year":"2017","date_published":"2017-07-01T00:00:00Z","doi":"10.1109/CVPR.2017.526","date_created":"2018-12-11T11:49:11Z","page":"4950-4960","_id":"917","status":"public","type":"conference","conference":{"end_date":"2017-07-26","location":"Honolulu, HA, United States","start_date":"2017-07-21","name":"CVPR: Computer Vision and Pattern Recognition"},"ddc":["000"],"date_updated":"2023-09-26T15:41:11Z","file_date_updated":"2020-07-14T12:48:15Z","department":[{"_id":"VlKo"}],"oa_version":"Submitted Version","abstract":[{"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.","lang":"eng"}],"month":"07","intvolume":" 2017","scopus_import":"1","file":[{"checksum":"72fd291046bd8e5717961bd68f6b6f03","file_id":"5847","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2019-01-18T12:45:55Z","file_name":"2017_CVPR_Swoboda.pdf","creator":"dernst","date_updated":"2020-07-14T12:48:15Z","file_size":898652}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-153860457-1"]},"publication_status":"published","volume":2017,"ec_funded":1},{"title":"A faster approximation algorithm for the Gibbs partition function","publist_id":"7628","author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"article_processing_charge":"No","external_id":{"arxiv":["1608.04223"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function.” In Proceedings of the 31st Conference On Learning Theory, 75:228–49. ML Research Press, 2017.","ista":"Kolmogorov V. 2017. A faster approximation algorithm for the Gibbs partition function. Proceedings of the 31st Conference On Learning Theory. COLT: Annual Conference on Learning Theory vol. 75, 228–249.","mla":"Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function.” Proceedings of the 31st Conference On Learning Theory, vol. 75, ML Research Press, 2017, pp. 228–49.","apa":"Kolmogorov, V. (2017). A faster approximation algorithm for the Gibbs partition function. In Proceedings of the 31st Conference On Learning Theory (Vol. 75, pp. 228–249). ML Research Press.","ama":"Kolmogorov V. A faster approximation algorithm for the Gibbs partition function. In: Proceedings of the 31st Conference On Learning Theory. Vol 75. ML Research Press; 2017:228-249.","short":"V. Kolmogorov, in:, Proceedings of the 31st Conference On Learning Theory, ML Research Press, 2017, pp. 228–249.","ieee":"V. Kolmogorov, “A faster approximation algorithm for the Gibbs partition function,” in Proceedings of the 31st Conference On Learning Theory, 2017, vol. 75, pp. 228–249."},"project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"date_published":"2017-12-27T00:00:00Z","date_created":"2018-12-11T11:45:33Z","page":"228-249","day":"27","publication":"Proceedings of the 31st Conference On Learning Theory","has_accepted_license":"1","year":"2017","publisher":"ML Research Press","quality_controlled":"1","oa":1,"department":[{"_id":"VlKo"}],"file_date_updated":"2020-07-14T12:45:45Z","ddc":["510"],"date_updated":"2023-10-17T12:32:13Z","status":"public","type":"conference","conference":{"end_date":"2018-07-09","start_date":"2018-07-06","name":"COLT: Annual Conference on Learning Theory "},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"_id":"274","volume":75,"ec_funded":1,"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_id":"7820","checksum":"89db06a0e8083524449cb59b56bf4e5b","file_size":408974,"date_updated":"2020-07-14T12:45:45Z","creator":"dernst","file_name":"2018_PMLR_Kolmogorov.pdf","date_created":"2020-05-12T09:23:27Z"}],"language":[{"iso":"eng"}],"publication_status":"published","month":"12","intvolume":" 75","oa_version":"Published Version","abstract":[{"text":"We consider the problem of estimating the partition function Z(β)=∑xexp(−β(H(x)) of a Gibbs distribution with a Hamilton H(⋅), or more precisely the logarithm of the ratio q=lnZ(0)/Z(β). It has been recently shown how to approximate q with high probability assuming the existence of an oracle that produces samples from the Gibbs distribution for a given parameter value in [0,β]. The current best known approach due to Huber [9] uses O(qlnn⋅[lnq+lnlnn+ε−2]) oracle calls on average where ε is the desired accuracy of approximation and H(⋅) is assumed to lie in {0}∪[1,n]. We improve the complexity to O(qlnn⋅ε−2) oracle calls. We also show that the same complexity can be achieved if exact oracles are replaced with approximate sampling oracles that are within O(ε2qlnn) variation distance from exact oracles. Finally, we prove a lower bound of Ω(q⋅ε−2) oracle calls under a natural model of computation.","lang":"eng"}]},{"day":"13","file":[{"checksum":"3dc3e1306a66028a34181ebef2923139","file_id":"5614","content_type":"application/zip","relation":"main_file","access_level":"open_access","file_name":"IST-2017-57-v1+1_wormMatchingProblems.zip","date_created":"2018-12-12T13:02:54Z","file_size":327042819,"date_updated":"2020-07-14T12:47:03Z","creator":"system"}],"datarep_id":"57","year":"2017","has_accepted_license":"1","date_created":"2018-12-12T12:31:32Z","doi":"10.15479/AT:ISTA:57","date_published":"2017-02-13T00:00:00Z","acknowledgement":"We thank Vladimir Kolmogorov and Stephan Saalfeld forinspiring discussions.","oa_version":"Published Version","abstract":[{"text":"Graph matching problems as described in \"Active Graph Matching for Automatic Joint Segmentation and Annotation of C. Elegans.\" by Kainmueller, Dagmar and Jug, Florian and Rother, Carsten and Myers, Gene, MICCAI 2014. Problems are in OpenGM2 hdf5 format (see http://hciweb2.iwr.uni-heidelberg.de/opengm/) and a custom text format used by the feature matching solver described in \"Feature Correspondence via Graph Matching: Models and Global Optimization.\" by Lorenzo Torresani, Vladimir Kolmogorov and Carsten Rother, ECCV 2008, code at http://pub.ist.ac.at/~vnk/software/GraphMatching-v1.02.src.zip. ","lang":"eng"}],"month":"02","oa":1,"publisher":"Institute of Science and Technology Austria","ddc":["000"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Kainmueller, Dagmar, Florian Jug, Carsten Rother, and Gene Meyers. “Graph Matching Problems for Annotating C. Elegans.” Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:57.","ista":"Kainmueller D, Jug F, Rother C, Meyers G. 2017. Graph matching problems for annotating C. Elegans, Institute of Science and Technology Austria, 10.15479/AT:ISTA:57.","mla":"Kainmueller, Dagmar, et al. Graph Matching Problems for Annotating C. Elegans. Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:57.","short":"D. Kainmueller, F. Jug, C. Rother, G. Meyers, (2017).","ieee":"D. Kainmueller, F. Jug, C. Rother, and G. Meyers, “Graph matching problems for annotating C. Elegans.” Institute of Science and Technology Austria, 2017.","ama":"Kainmueller D, Jug F, Rother C, Meyers G. Graph matching problems for annotating C. Elegans. 2017. doi:10.15479/AT:ISTA:57","apa":"Kainmueller, D., Jug, F., Rother, C., & Meyers, G. (2017). Graph matching problems for annotating C. Elegans. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:57"},"date_updated":"2024-02-21T13:46:31Z","department":[{"_id":"VlKo"}],"file_date_updated":"2020-07-14T12:47:03Z","title":"Graph matching problems for annotating C. Elegans","article_processing_charge":"No","author":[{"first_name":"Dagmar","full_name":"Kainmueller, Dagmar","last_name":"Kainmueller"},{"first_name":"Florian","full_name":"Jug, Florian","last_name":"Jug"},{"first_name":"Carsten","full_name":"Rother, Carsten","last_name":"Rother"},{"full_name":"Meyers, Gene","last_name":"Meyers","first_name":"Gene"}],"_id":"5561","keyword":["graph matching","feature matching","QAP","MAP-inference"],"status":"public","tmp":{"image":"/images/cc_0.png","legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","name":"Creative Commons Public Domain Dedication (CC0 1.0)","short":"CC0 (1.0)"},"type":"research_data"},{"project":[{"grant_number":"259668","name":"Provable Security for Physical Cryptography","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"},{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"author":[{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","full_name":"Alwen, Joel F","last_name":"Alwen"},{"full_name":"Chen, Binyi","last_name":"Chen","first_name":"Binyi"},{"full_name":"Kamath Hosdurg, Chethan","last_name":"Kamath Hosdurg","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","first_name":"Chethan"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"},{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"first_name":"Stefano","full_name":"Tessaro, Stefano","last_name":"Tessaro"}],"publist_id":"6103","title":"On the complexity of scrypt and proofs of space in the parallel random oracle model","citation":{"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.","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. https://doi.org/10.1007/978-3-662-49896-5_13.","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:10.1007/978-3-662-49896-5_13","apa":"Alwen, J. F., Chen, B., Kamath Hosdurg, C., Kolmogorov, V., Pietrzak, K. Z., & 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. https://doi.org/10.1007/978-3-662-49896-5_13","short":"J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2016, pp. 358–387.","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.","mla":"Alwen, Joel F., et al. On the Complexity of Scrypt and Proofs of Space in the Parallel Random Oracle Model. Vol. 9666, Springer, 2016, pp. 358–87, doi:10.1007/978-3-662-49896-5_13."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa":1,"quality_controlled":"1","publisher":"Springer","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.","page":"358 - 387","date_created":"2018-12-11T11:50:51Z","date_published":"2016-04-28T00:00:00Z","doi":"10.1007/978-3-662-49896-5_13","year":"2016","day":"28","conference":{"location":"Vienna, Austria","end_date":"2016-05-12","start_date":"2016-05-08","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques"},"type":"conference","status":"public","_id":"1231","department":[{"_id":"KrPi"},{"_id":"VlKo"}],"date_updated":"2021-01-12T06:49:15Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/100"}],"alternative_title":["LNCS"],"scopus_import":1,"intvolume":" 9666","month":"04","abstract":[{"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).","lang":"eng"}],"oa_version":"Submitted Version","ec_funded":1,"volume":9666,"publication_status":"published","language":[{"iso":"eng"}]},{"volume":26,"issue":"5","language":[{"iso":"eng"}],"publication_status":"published","intvolume":" 26","month":"07","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1512.07009"}],"scopus_import":1,"oa_version":"Preprint","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"}],"department":[{"_id":"VlKo"}],"date_updated":"2021-01-12T06:50:06Z","status":"public","type":"journal_article","_id":"1353","date_created":"2018-12-11T11:51:32Z","date_published":"2016-07-20T00:00:00Z","doi":"10.1142/S0218196716500430","page":"1033 - 1060","publication":"International Journal of Algebra and Computation","day":"20","year":"2016","oa":1,"quality_controlled":"1","publisher":"World Scientific Publishing","acknowledgement":"Libor Barto and Alexandr Kazda were supported by the the Grant Agency of the Czech Republic, grant GACR 13-01832S. ","title":"Deciding absorption","publist_id":"5893","author":[{"first_name":"Libor","full_name":"Barto, Libor","last_name":"Barto"},{"last_name":"Kazda","full_name":"Kazda, Alexandr","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","first_name":"Alexandr"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Barto, L., & Kazda, A. (2016). Deciding absorption. International Journal of Algebra and Computation. World Scientific Publishing. https://doi.org/10.1142/S0218196716500430","ama":"Barto L, Kazda A. Deciding absorption. International Journal of Algebra and Computation. 2016;26(5):1033-1060. doi:10.1142/S0218196716500430","short":"L. Barto, A. Kazda, International Journal of Algebra and Computation 26 (2016) 1033–1060.","ieee":"L. Barto and A. Kazda, “Deciding absorption,” International Journal of Algebra and Computation, vol. 26, no. 5. World Scientific Publishing, pp. 1033–1060, 2016.","mla":"Barto, Libor, and Alexandr Kazda. “Deciding Absorption.” International Journal of Algebra and Computation, vol. 26, no. 5, World Scientific Publishing, 2016, pp. 1033–60, doi:10.1142/S0218196716500430.","ista":"Barto L, Kazda A. 2016. Deciding absorption. International Journal of Algebra and Computation. 26(5), 1033–1060.","chicago":"Barto, Libor, and Alexandr Kazda. “Deciding Absorption.” International Journal of Algebra and Computation. World Scientific Publishing, 2016. https://doi.org/10.1142/S0218196716500430."}},{"author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"},{"full_name":"Pock, Thomas","last_name":"Pock","first_name":"Thomas"},{"first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal","last_name":"Rolinek"}],"publist_id":"5834","title":"Total variation on a tree","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","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.","short":"V. Kolmogorov, T. Pock, M. Rolinek, SIAM Journal on Imaging Sciences 9 (2016) 605–636.","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","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"page":"605 - 636","date_created":"2018-12-11T11:51:40Z","date_published":"2016-05-03T00:00:00Z","doi":"10.1137/15M1010257","year":"2016","publication":"SIAM Journal on Imaging Sciences","day":"03","oa":1,"publisher":"Society for Industrial and Applied Mathematics ","quality_controlled":"1","department":[{"_id":"VlKo"}],"date_updated":"2021-01-12T06:50:15Z","type":"journal_article","status":"public","_id":"1377","ec_funded":1,"volume":9,"issue":"2","publication_status":"published","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1502.07770"}],"scopus_import":1,"intvolume":" 9","month":"05","abstract":[{"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.","lang":"eng"}],"oa_version":"Preprint"},{"publisher":"Springer","scopus_import":1,"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1112.1099"}],"oa":1,"month":"02","intvolume":" 75","abstract":[{"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).","lang":"eng"}],"oa_version":"Preprint","page":"75 - 84","issue":"1","doi":"10.1007/s00012-015-0358-8","date_published":"2016-02-01T00:00:00Z","volume":75,"date_created":"2018-12-11T11:53:01Z","publication_status":"published","year":"2016","day":"01","language":[{"iso":"eng"}],"publication":"Algebra Universalis","type":"journal_article","status":"public","_id":"1612","publist_id":"5554","author":[{"id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","first_name":"Alexandr","full_name":"Kazda, Alexandr","last_name":"Kazda"}],"title":"CSP for binary conservative relational structures","department":[{"_id":"VlKo"}],"citation":{"mla":"Kazda, Alexandr. “CSP for Binary Conservative Relational Structures.” Algebra Universalis, vol. 75, no. 1, Springer, 2016, pp. 75–84, doi:10.1007/s00012-015-0358-8.","ieee":"A. Kazda, “CSP for binary conservative relational structures,” Algebra Universalis, vol. 75, no. 1. Springer, pp. 75–84, 2016.","short":"A. Kazda, Algebra Universalis 75 (2016) 75–84.","ama":"Kazda A. CSP for binary conservative relational structures. Algebra Universalis. 2016;75(1):75-84. doi:10.1007/s00012-015-0358-8","apa":"Kazda, A. (2016). CSP for binary conservative relational structures. Algebra Universalis. Springer. https://doi.org/10.1007/s00012-015-0358-8","chicago":"Kazda, Alexandr. “CSP for Binary Conservative Relational Structures.” Algebra Universalis. Springer, 2016. https://doi.org/10.1007/s00012-015-0358-8.","ista":"Kazda A. 2016. CSP for binary conservative relational structures. Algebra Universalis. 75(1), 75–84."},"date_updated":"2021-01-12T06:52:00Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"},{"status":"public","conference":{"start_date":"2016-09-09","location":"New Brunswick, NJ, USA ","end_date":"2016-09-11","name":"FOCS: Foundations of Computer Science"},"type":"conference","_id":"1193","department":[{"_id":"VlKo"}],"date_updated":"2023-09-19T14:24:57Z","month":"12","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1506.08547v7"}],"scopus_import":1,"oa_version":"Preprint","abstract":[{"text":"We consider the recent formulation of the Algorithmic Lovász Local Lemma [1], [2] for finding objects that avoid "bad features", or "flaws". It extends the Moser-Tardos resampling algorithm [3] to more general discrete spaces. At each step the method picks a flaw present in the current state and "resamples" it using a "resampling oracle" provided by the user. However, it is less flexible than the Moser-Tardos method since [1], [2] require a specific flaw selection rule, whereas [3] allows an arbitrary rule (and thus can potentially be implemented more efficiently). We formulate a new "commutativity" condition, and prove that it is sufficient for an arbitrary rule to work. It also enables an efficient parallelization under an additional assumption. We then show that existing resampling oracles for perfect matchings and permutations do satisfy this condition. Finally, we generalize the precondition in [2] (in the case of symmetric potential causality graphs). This unifies special cases that previously were treated separately.","lang":"eng"}],"ec_funded":1,"related_material":{"record":[{"status":"public","id":"5975","relation":"later_version"}]},"volume":"2016-December","language":[{"iso":"eng"}],"publication_status":"published","project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"article_number":"7782993","title":"Commutativity in the algorithmic Lovasz local lemma","external_id":{"arxiv":["1506.08547"]},"article_processing_charge":"No","author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"publist_id":"6158","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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.","chicago":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovasz Local Lemma.” In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, Vol. 2016–December. IEEE, 2016. https://doi.org/10.1109/FOCS.2016.88.","ama":"Kolmogorov V. Commutativity in the algorithmic Lovasz local lemma. In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science. Vol 2016-December. IEEE; 2016. doi:10.1109/FOCS.2016.88","apa":"Kolmogorov, V. (2016). Commutativity in the algorithmic Lovasz local lemma. In Proceedings - Annual IEEE Symposium on Foundations of Computer Science (Vol. 2016–December). New Brunswick, NJ, USA : IEEE. https://doi.org/10.1109/FOCS.2016.88","ieee":"V. Kolmogorov, “Commutativity in the algorithmic Lovasz local lemma,” in Proceedings - Annual IEEE Symposium on Foundations of Computer Science, New Brunswick, NJ, USA , 2016, vol. 2016–December.","short":"V. Kolmogorov, in:, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2016.","mla":"Kolmogorov, Vladimir. “Commutativity in the Algorithmic Lovasz Local Lemma.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, vol. 2016–December, 7782993, IEEE, 2016, doi:10.1109/FOCS.2016.88."},"oa":1,"publisher":"IEEE","quality_controlled":"1","acknowledgement":"European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 616160","date_created":"2018-12-11T11:50:38Z","doi":"10.1109/FOCS.2016.88","date_published":"2016-12-15T00:00:00Z","publication":"Proceedings - Annual IEEE Symposium on Foundations of Computer Science","day":"15","year":"2016"},{"status":"public","type":"journal_article","_id":"1794","department":[{"_id":"VlKo"}],"date_updated":"2023-10-17T09:51:31Z","month":"09","intvolume":" 76","scopus_import":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1210.0508"}],"oa_version":"Preprint","abstract":[{"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.","lang":"eng"}],"volume":76,"issue":"1","related_material":{"record":[{"status":"public","id":"2272","relation":"earlier_version"}]},"ec_funded":1,"language":[{"iso":"eng"}],"publication_status":"published","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"title":"Inference algorithms for pattern-based CRFs on sequence data","publist_id":"5316","author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87","first_name":"Rustem","full_name":"Takhanov, Rustem","last_name":"Takhanov"}],"external_id":{"arxiv":["1210.0508"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 76(1), 17–46.","chicago":"Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica. Springer, 2016. https://doi.org/10.1007/s00453-015-0017-7.","short":"V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46.","ieee":"V. Kolmogorov and R. Takhanov, “Inference algorithms for pattern-based CRFs on sequence data,” Algorithmica, vol. 76, no. 1. Springer, pp. 17–46, 2016.","apa":"Kolmogorov, V., & Takhanov, R. (2016). Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. Springer. https://doi.org/10.1007/s00453-015-0017-7","ama":"Kolmogorov V, Takhanov R. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 2016;76(1):17-46. doi:10.1007/s00453-015-0017-7","mla":"Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica, vol. 76, no. 1, Springer, 2016, pp. 17–46, doi:10.1007/s00453-015-0017-7."},"publisher":"Springer","quality_controlled":"1","oa":1,"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.","doi":"10.1007/s00453-015-0017-7","date_published":"2016-09-01T00:00:00Z","date_created":"2018-12-11T11:54:02Z","page":"17 - 46","day":"01","publication":"Algorithmica","year":"2016"},{"ddc":["006"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2024-02-21T13:50:21Z","citation":{"ista":"Swoboda P. 2016. Synthetic discrete tomography problems, Institute of Science and Technology Austria, 10.15479/AT:ISTA:46.","chicago":"Swoboda, Paul. “Synthetic Discrete Tomography Problems.” Institute of Science and Technology Austria, 2016. https://doi.org/10.15479/AT:ISTA:46.","apa":"Swoboda, P. (2016). Synthetic discrete tomography problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:46","ama":"Swoboda P. Synthetic discrete tomography problems. 2016. doi:10.15479/AT:ISTA:46","short":"P. Swoboda, (2016).","ieee":"P. Swoboda, “Synthetic discrete tomography problems.” Institute of Science and Technology Austria, 2016.","mla":"Swoboda, Paul. Synthetic Discrete Tomography Problems. Institute of Science and Technology Austria, 2016, doi:10.15479/AT:ISTA:46."},"file_date_updated":"2020-07-14T12:47:02Z","title":"Synthetic discrete tomography problems","department":[{"_id":"VlKo"}],"article_processing_charge":"No","author":[{"first_name":"Paul","id":"446560C6-F248-11E8-B48F-1D18A9856A87","full_name":"Swoboda, Paul","last_name":"Swoboda"}],"_id":"5557","keyword":["discrete tomography"],"status":"public","tmp":{"image":"/images/cc_0.png","legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","name":"Creative Commons Public Domain Dedication (CC0 1.0)","short":"CC0 (1.0)"},"type":"research_data","file":[{"file_size":36058401,"date_updated":"2020-07-14T12:47:02Z","creator":"system","file_name":"IST-2016-46-v1+1_discrete_tomography_synthetic.zip","date_created":"2018-12-12T13:05:19Z","content_type":"application/zip","relation":"main_file","access_level":"open_access","file_id":"5645","checksum":"aa5a16a0dc888da7186fb8fc45e88439"}],"day":"20","year":"2016","datarep_id":"46","has_accepted_license":"1","date_created":"2018-12-12T12:31:31Z","contributor":[{"contributor_type":"data_collector","first_name":"Jan","last_name":"Kuske"}],"date_published":"2016-09-20T00:00:00Z","doi":"10.15479/AT:ISTA:46","oa_version":"Published Version","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"}],"month":"09","oa":1,"publisher":"Institute of Science and Technology Austria"},{"project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","citation":{"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.","ista":"Kolmogorov V, Rolinek M, Takhanov R. 2015. Effectiveness of structural restrictions for hybrid CSPs. 26th International Symposium. ISAAC: International Symposium on Algorithms and Computation, LNCS, vol. 9472, 566–577.","mla":"Kolmogorov, Vladimir, et al. “Effectiveness of Structural Restrictions for Hybrid CSPs.” 26th International Symposium, vol. 9472, Springer Nature, 2015, pp. 566–77, doi:10.1007/978-3-662-48971-0_48.","short":"V. Kolmogorov, M. Rolinek, R. Takhanov, in:, 26th International Symposium, Springer Nature, 2015, pp. 566–577.","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.","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","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"},"title":"Effectiveness of structural restrictions for hybrid CSPs","author":[{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"last_name":"Rolinek","full_name":"Rolinek, Michal","first_name":"Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Takhanov, Rustem","last_name":"Takhanov","first_name":"Rustem"}],"publist_id":"5519","article_processing_charge":"No","external_id":{"arxiv":["1504.07067"]},"quality_controlled":"1","publisher":"Springer Nature","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","_id":"1636","status":"public","type":"conference","conference":{"name":"ISAAC: International Symposium on Algorithms and Computation","location":"Nagoya, Japan","end_date":"2015-12-11","start_date":"2015-12-09"},"date_updated":"2022-02-01T15:12:35Z","department":[{"_id":"VlKo"}],"oa_version":"Preprint","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"}],"month":"12","intvolume":" 9472","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"url":"http://arxiv.org/abs/1504.07067","open_access":"1"}],"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["978-3-662-48970-3"]},"publication_status":"published","volume":9472,"ec_funded":1},{"project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"}],"publist_id":"5261","title":"A new look at reweighted message passing","citation":{"chicago":"Kolmogorov, Vladimir. “A New Look at Reweighted Message Passing.” IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE, 2015. https://doi.org/10.1109/TPAMI.2014.2363465.","ista":"Kolmogorov V. 2015. A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence. 37(5), 919–930.","mla":"Kolmogorov, Vladimir. “A New Look at Reweighted Message Passing.” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 5, IEEE, 2015, pp. 919–30, doi:10.1109/TPAMI.2014.2363465.","apa":"Kolmogorov, V. (2015). A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. https://doi.org/10.1109/TPAMI.2014.2363465","ama":"Kolmogorov V. A new look at reweighted message passing. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2015;37(5):919-930. doi:10.1109/TPAMI.2014.2363465","short":"V. Kolmogorov, IEEE Transactions on Pattern Analysis and Machine Intelligence 37 (2015) 919–930.","ieee":"V. Kolmogorov, “A new look at reweighted message passing,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 37, no. 5. IEEE, pp. 919–930, 2015."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"quality_controlled":"1","publisher":"IEEE","page":"919 - 930","date_created":"2018-12-11T11:54:18Z","doi":"10.1109/TPAMI.2014.2363465","date_published":"2015-05-01T00:00:00Z","year":"2015","publication":"IEEE Transactions on Pattern Analysis and Machine Intelligence","day":"01","type":"journal_article","status":"public","_id":"1841","department":[{"_id":"VlKo"}],"date_updated":"2021-01-12T06:53:33Z","main_file_link":[{"url":"http://arxiv.org/abs/1309.5655","open_access":"1"}],"scopus_import":1,"intvolume":" 37","month":"05","abstract":[{"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.","lang":"eng"}],"oa_version":"Preprint","ec_funded":1,"issue":"5","volume":37,"publication_status":"published","language":[{"iso":"eng"}]},{"date_updated":"2021-01-12T06:53:40Z","citation":{"chicago":"Shah, Neel, Vladimir Kolmogorov, and Christoph Lampert. “A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly Max-Oracle,” 2737–45. IEEE, 2015. https://doi.org/10.1109/CVPR.2015.7298890.","ista":"Shah N, Kolmogorov V, Lampert C. 2015. A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle. CVPR: Computer Vision and Pattern Recognition, 2737–2745.","mla":"Shah, Neel, et al. A Multi-Plane Block-Coordinate Frank-Wolfe Algorithm for Training Structural SVMs with a Costly Max-Oracle. IEEE, 2015, pp. 2737–45, doi:10.1109/CVPR.2015.7298890.","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.","short":"N. Shah, V. Kolmogorov, C. Lampert, in:, IEEE, 2015, pp. 2737–2745.","ama":"Shah N, Kolmogorov V, Lampert C. A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle. In: IEEE; 2015:2737-2745. doi:10.1109/CVPR.2015.7298890","apa":"Shah, N., Kolmogorov, V., & Lampert, C. (2015). A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle (pp. 2737–2745). Presented at the CVPR: Computer Vision and Pattern Recognition, Boston, MA, USA: IEEE. https://doi.org/10.1109/CVPR.2015.7298890"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"31ABAF80-F248-11E8-B48F-1D18A9856A87","first_name":"Neel","full_name":"Shah, Neel","last_name":"Shah"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"last_name":"Lampert","full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph"}],"publist_id":"5240","department":[{"_id":"VlKo"},{"_id":"ChLa"}],"title":"A multi-plane block-coordinate Frank-Wolfe algorithm for training structural SVMs with a costly max-oracle","_id":"1859","type":"conference","conference":{"location":"Boston, MA, USA","end_date":"2015-06-12","start_date":"2015-06-07","name":"CVPR: Computer Vision and Pattern Recognition"},"status":"public","project":[{"_id":"2532554C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"308036","name":"Lifelong Learning of Visual Scene Understanding"},{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"year":"2015","publication_status":"published","day":"01","language":[{"iso":"eng"}],"page":"2737 - 2745","doi":"10.1109/CVPR.2015.7298890","date_published":"2015-06-01T00:00:00Z","ec_funded":1,"date_created":"2018-12-11T11:54:24Z","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. "}],"oa_version":"Preprint","publisher":"IEEE","scopus_import":1,"quality_controlled":"1","oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1408.6804"}],"month":"06"},{"date_published":"2015-02-01T00:00:00Z","doi":"10.1137/130945648","date_created":"2018-12-11T11:56:41Z","page":"1 - 36","day":"01","publication":"SIAM Journal on Computing","year":"2015","quality_controlled":"1","publisher":"SIAM","oa":1,"title":"The power of linear programming for general-valued CSPs","publist_id":"4673","author":[{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Thapper, Johan","last_name":"Thapper","first_name":"Johan"},{"first_name":"Stanislav","full_name":"Živný, Stanislav","last_name":"Živný"}],"external_id":{"arxiv":["1311.4219"]},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Kolmogorov, Vladimir, et al. “The Power of Linear Programming for General-Valued CSPs.” SIAM Journal on Computing, vol. 44, no. 1, SIAM, 2015, pp. 1–36, doi:10.1137/130945648.","ieee":"V. Kolmogorov, J. Thapper, and S. Živný, “The power of linear programming for general-valued CSPs,” SIAM Journal on Computing, vol. 44, no. 1. SIAM, pp. 1–36, 2015.","short":"V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015) 1–36.","apa":"Kolmogorov, V., Thapper, J., & Živný, S. (2015). The power of linear programming for general-valued CSPs. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/130945648","ama":"Kolmogorov V, Thapper J, Živný S. The power of linear programming for general-valued CSPs. SIAM Journal on Computing. 2015;44(1):1-36. doi:10.1137/130945648","chicago":"Kolmogorov, Vladimir, Johan Thapper, and Stanislav Živný. “The Power of Linear Programming for General-Valued CSPs.” SIAM Journal on Computing. SIAM, 2015. https://doi.org/10.1137/130945648.","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."},"volume":44,"related_material":{"record":[{"status":"public","id":"2518","relation":"earlier_version"}]},"issue":"1","language":[{"iso":"eng"}],"publication_status":"published","month":"02","intvolume":" 44","scopus_import":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1311.4219"}],"oa_version":"Preprint","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"}],"department":[{"_id":"VlKo"}],"date_updated":"2023-02-23T10:46:30Z","status":"public","type":"journal_article","_id":"2271"},{"doi":"10.1109/FOCS.2015.80","date_published":"2015-12-01T00:00:00Z","date_created":"2018-12-11T11:53:10Z","page":"1246 - 1258","day":"01","year":"2015","quality_controlled":"1","publisher":"IEEE","oa":1,"title":"The complexity of general-valued CSPs","publist_id":"5518","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"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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","mla":"Kolmogorov, Vladimir, et al. The Complexity of General-Valued CSPs. IEEE, 2015, pp. 1246–58, doi: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.","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."},"project":[{"name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"related_material":{"record":[{"relation":"other","status":"public","id":"644"}]},"ec_funded":1,"language":[{"iso":"eng"}],"publication_status":"published","month":"12","alternative_title":["56th Annual Symposium on Foundations of Computer Science"],"scopus_import":1,"main_file_link":[{"url":"http://arxiv.org/abs/1502.07327","open_access":"1"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"An instance of the Valued Constraint Satisfaction Problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values specifying costs of assignments of labels to its variables or the infinite value, which indicates an infeasible assignment. The goal is to find an assignment of labels to the variables that minimizes the sum. We study, assuming that P ≠ NP, how the complexity of this very general problem depends on the set of functions allowed in the instances, the so-called constraint language. The case when all allowed functions take values in {0, ∞} corresponds to ordinary CSPs, where one deals only with the feasibility issue and there is no optimization. This case is the subject of the Algebraic CSP Dichotomy Conjecture predicting for which constraint languages CSPs are tractable (i.e. solvable in polynomial time) and for which NP-hard. The case when all allowed functions take only finite values corresponds to finite-valued CSP, where the feasibility aspect is trivial and one deals only with the optimization issue. The complexity of finite-valued CSPs was fully classified by Thapper and Zivny. An algebraic necessary condition for tractability of a general-valued CSP with a fixed constraint language was recently given by Kozik and Ochremiak. As our main result, we prove that if a constraint language satisfies this algebraic necessary condition, and the feasibility CSP (i.e. the problem of deciding whether a given instance has a feasible solution) corresponding to the VCSP with this language is tractable, then the VCSP is tractable. The algorithm is a simple combination of the assumed algorithm for the feasibility CSP and the standard LP relaxation. As a corollary, we obtain that a dichotomy for ordinary CSPs would imply a dichotomy for general-valued CSPs."}],"department":[{"_id":"VlKo"}],"date_updated":"2023-02-23T12:44:26Z","status":"public","type":"conference","conference":{"name":"FOCS: Foundations of Computer Science","location":"Berkeley, CA, United States","end_date":"2015-10-20","start_date":"2015-10-18"},"_id":"1637"},{"department":[{"_id":"VlKo"},{"_id":"KrPi"}],"date_updated":"2024-03-20T08:31:49Z","status":"public","pubrep_id":"671","type":"conference","conference":{"name":"CRYPTO: International Cryptology Conference","start_date":"2015-08-16","location":"Santa Barbara, CA, United States","end_date":"2015-08-20"},"_id":"1675","related_material":{"record":[{"status":"public","id":"2274","relation":"earlier_version"}]},"volume":9216,"ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0302-9743"],"isbn":["9783662479995"]},"publication_status":"published","month":"08","intvolume":" 9216","alternative_title":["LNCS"],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2013/796.pdf"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system. In this work, we put forward an alternative concept for PoWs - so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model (with one additional mild assumption required for the proof to go through), using graphs with high “pebbling complexity” and Merkle hash-trees. We discuss some applications, including follow-up work where a decentralized digital currency scheme called Spacecoin is constructed that uses PoS (instead of wasteful PoW like in Bitcoin) to prevent double spending. The main technical contribution of this work is the construction of (directed, loop-free) graphs on N vertices with in-degree O(log logN) such that even if one places Θ(N) pebbles on the nodes of the graph, there’s a constant fraction of nodes that needs Θ(N) steps to be pebbled (where in every step one can put a pebble on a node if all its parents have a pebble)."}],"title":"Proofs of space","author":[{"first_name":"Stefan","last_name":"Dziembowski","full_name":"Dziembowski, Stefan"},{"last_name":"Faust","full_name":"Faust, Sebastian","first_name":"Sebastian"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"publist_id":"5474","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2015. Proofs of space. 35th Annual Cryptology Conference. CRYPTO: International Cryptology Conference, LNCS, vol. 9216, 585–605.","chicago":"Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Z Pietrzak. “Proofs of Space.” In 35th Annual Cryptology Conference, 9216:585–605. Springer, 2015. https://doi.org/10.1007/978-3-662-48000-7_29.","ieee":"S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, “Proofs of space,” in 35th Annual Cryptology Conference, Santa Barbara, CA, United States, 2015, vol. 9216, pp. 585–605.","short":"S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, in:, 35th Annual Cryptology Conference, Springer, 2015, pp. 585–605.","ama":"Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. Proofs of space. In: 35th Annual Cryptology Conference. Vol 9216. Springer; 2015:585-605. doi:10.1007/978-3-662-48000-7_29","apa":"Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2015). Proofs of space. In 35th Annual Cryptology Conference (Vol. 9216, pp. 585–605). Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-662-48000-7_29","mla":"Dziembowski, Stefan, et al. “Proofs of Space.” 35th Annual Cryptology Conference, vol. 9216, Springer, 2015, pp. 585–605, doi:10.1007/978-3-662-48000-7_29."},"project":[{"grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"name":"Provable Security for Physical Cryptography","grant_number":"259668","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"}],"date_published":"2015-08-01T00:00:00Z","doi":"10.1007/978-3-662-48000-7_29","date_created":"2018-12-11T11:53:24Z","page":"585 - 605","day":"01","publication":"35th Annual Cryptology Conference","year":"2015","quality_controlled":"1","publisher":"Springer","oa":1},{"type":"conference","conference":{"name":"ICCV: International Conference on Computer Vision","start_date":"2013-12-01","end_date":"2013-12-08","location":"Sydney, Australia"},"status":"public","pubrep_id":"566","_id":"2275","file_date_updated":"2020-07-14T12:45:36Z","department":[{"_id":"VlKo"}],"date_updated":"2021-01-12T06:56:28Z","ddc":["000"],"scopus_import":1,"month":"03","abstract":[{"lang":"eng","text":"Energies with high-order non-submodular interactions have been shown to be very useful in vision due to their high modeling power. Optimization of such energies, however, is generally NP-hard. A naive approach that works for small problem instances is exhaustive search, that is, enumeration of all possible labelings of the underlying graph. We propose a general minimization approach for large graphs based on enumeration of labelings of certain small patches. \r\nThis partial enumeration technique reduces complex high-order energy formulations to pairwise Constraint Satisfaction Problems with unary costs (uCSP), which can be efficiently solved using standard methods like TRW-S. Our approach outperforms a number of existing state-of-the-art algorithms on well known difficult problems (e.g. curvature regularization, stereo, deconvolution); it gives near global minimum and better speed. \r\nOur main application of interest is curvature regularization. In the context of segmentation, our partial enumeration technique allows to evaluate curvature directly on small patches using a novel integral geometry approach.\r\n"}],"oa_version":"Submitted Version","publication_status":"published","file":[{"relation":"main_file","access_level":"open_access","content_type":"application/pdf","file_id":"4754","checksum":"4a74b5c92d6dcd2348c2c10ec8dd18bf","creator":"system","file_size":378601,"date_updated":"2020-07-14T12:45:36Z","file_name":"IST-2016-566-v1+1_iccv13_part_enumeration.pdf","date_created":"2018-12-12T10:09:30Z"}],"language":[{"iso":"eng"}],"author":[{"first_name":"Carl","last_name":"Olsson","full_name":"Olsson, Carl"},{"first_name":"Johannes","full_name":"Ulen, Johannes","last_name":"Ulen"},{"first_name":"Yuri","full_name":"Boykov, Yuri","last_name":"Boykov"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"publist_id":"4669","title":"Partial enumeration and curvature regularization","citation":{"ista":"Olsson C, Ulen J, Boykov Y, Kolmogorov V. 2014. Partial enumeration and curvature regularization. ICCV: International Conference on Computer Vision, 2936–2943.","chicago":"Olsson, Carl, Johannes Ulen, Yuri Boykov, and Vladimir Kolmogorov. “Partial Enumeration and Curvature Regularization,” 2936–43. IEEE, 2014. https://doi.org/10.1109/ICCV.2013.365.","short":"C. Olsson, J. Ulen, Y. Boykov, V. Kolmogorov, in:, IEEE, 2014, pp. 2936–2943.","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.","ama":"Olsson C, Ulen J, Boykov Y, Kolmogorov V. Partial enumeration and curvature regularization. In: IEEE; 2014:2936-2943. doi:10.1109/ICCV.2013.365","apa":"Olsson, C., Ulen, J., Boykov, Y., & Kolmogorov, V. (2014). Partial enumeration and curvature regularization (pp. 2936–2943). Presented at the ICCV: International Conference on Computer Vision, Sydney, Australia: IEEE. https://doi.org/10.1109/ICCV.2013.365","mla":"Olsson, Carl, et al. Partial Enumeration and Curvature Regularization. IEEE, 2014, pp. 2936–43, doi:10.1109/ICCV.2013.365."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IEEE","quality_controlled":"1","oa":1,"page":"2936 - 2943","date_published":"2014-03-03T00:00:00Z","doi":"10.1109/ICCV.2013.365","date_created":"2018-12-11T11:56:42Z","has_accepted_license":"1","year":"2014","day":"03"},{"oa_version":"Published Version","month":"06","publisher":"IST Austria","oa":1,"file":[{"file_id":"7039","checksum":"2b94e5e1f4c3fe8ab89b12806276fb09","content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2019-11-18T15:57:51Z","file_name":"2014_Playful_Math_Huszar.pdf","date_updated":"2020-07-14T12:47:48Z","file_size":511233,"creator":"dernst"}],"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","_id":"7038","status":"public","type":"working_paper","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["510"],"date_updated":"2020-07-14T23:11:45Z","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.","ieee":"K. Huszár and M. 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.","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."},"title":"Playful Math - An introduction to mathematical games","file_date_updated":"2020-07-14T12:47:48Z","department":[{"_id":"VlKo"},{"_id":"UlWa"}],"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"},{"last_name":"Rolinek","full_name":"Rolinek, Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal"}],"article_processing_charge":"No"},{"day":"31","language":[{"iso":"eng"}],"year":"2013","publication_status":"published","date_published":"2013-12-31T00:00:00Z","date_created":"2018-12-11T11:56:41Z","page":"81-87","oa_version":"None","abstract":[{"text":"Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inher-\r\nent tradeoff between how general a language is, allowing it to capture more elaborate games, and how hard it is computationally to optimize and solve such games. One prominent such language is the simple yet expressive\r\nWeighted Graph Games (WGGs) representation (Deng and Papadimitriou 1994), which maintains knowledge about synergies between agents in the form of an edge weighted graph. We consider the problem of finding the optimal coalition structure in WGGs. The agents in such games are vertices in a graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. We then provide algorithms with constant factor approximations for planar, minorfree and bounded degree graphs.","lang":"eng"}],"month":"12","quality_controlled":"1","publisher":"AAAI Press","main_file_link":[{"url":"http://arxiv.org/abs/1108.5248","open_access":"1"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. 2013. Optimal Coalition Structures in Cooperative Graph Games. AAAI: Conference on Artificial Intelligence, 81–87.","chicago":"Bachrach, Yoram, Pushmeet Kohli, Vladimir Kolmogorov, and Morteza Zadimoghaddam. “Optimal Coalition Structures in Cooperative Graph Games,” 81–87. AAAI Press, 2013.","apa":"Bachrach, Y., Kohli, P., Kolmogorov, V., & Zadimoghaddam, M. (2013). Optimal Coalition Structures in Cooperative Graph Games (pp. 81–87). Presented at the AAAI: Conference on Artificial Intelligence, Bellevue, WA, United States: AAAI Press.","ama":"Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. Optimal Coalition Structures in Cooperative Graph Games. In: AAAI Press; 2013:81-87.","ieee":"Y. Bachrach, P. Kohli, V. Kolmogorov, and M. Zadimoghaddam, “Optimal Coalition Structures in Cooperative Graph Games,” presented at the AAAI: Conference on Artificial Intelligence, Bellevue, WA, United States, 2013, pp. 81–87.","short":"Y. Bachrach, P. Kohli, V. Kolmogorov, M. Zadimoghaddam, in:, AAAI Press, 2013, pp. 81–87.","mla":"Bachrach, Yoram, et al. Optimal Coalition Structures in Cooperative Graph Games. AAAI Press, 2013, pp. 81–87."},"date_updated":"2021-01-12T06:56:25Z","department":[{"_id":"VlKo"}],"title":"Optimal Coalition Structures in Cooperative Graph Games","publist_id":"4674","author":[{"first_name":"Yoram","full_name":"Bachrach, Yoram","last_name":"Bachrach"},{"last_name":"Kohli","full_name":"Kohli, Pushmeet","first_name":"Pushmeet"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"first_name":"Morteza","full_name":"Zadimoghaddam, Morteza","last_name":"Zadimoghaddam"}],"external_id":{"arxiv":["1108.5248"]},"_id":"2270","status":"public","type":"conference","conference":{"start_date":"2013-07-14","location":"Bellevue, WA, United States","end_date":"2013-07-18","name":"AAAI: Conference on Artificial Intelligence"}},{"day":"22","publication_status":"published","year":"2013","date_published":"2013-09-22T00:00:00Z","date_created":"2018-12-11T11:56:42Z","abstract":[{"text":"We propose a new family of message passing techniques for MAP estimation in graphical models which we call Sequential Reweighted Message Passing (SRMP). Special cases include well-known techniques such as Min-Sum Diusion (MSD) and a faster Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation is simpler than the original derivation of TRW-S, and does not involve a decomposition into trees. This allows easy generalizations. We present such a generalization for the case of higher-order graphical models, and test it on several real-world problems with promising results.","lang":"eng"}],"month":"09","quality_controlled":0,"publisher":"IST Austria","oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1309.5655"}],"extern":0,"citation":{"ista":"Kolmogorov V. 2013. Reweighted message passing revisited, IST Austria,p.","chicago":"Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST Austria, 2013.","ieee":"V. Kolmogorov, Reweighted message passing revisited. IST Austria, 2013.","short":"V. Kolmogorov, Reweighted Message Passing Revisited, IST Austria, 2013.","ama":"Kolmogorov V. Reweighted Message Passing Revisited. IST Austria; 2013.","apa":"Kolmogorov, V. (2013). Reweighted message passing revisited. IST Austria.","mla":"Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST Austria, 2013."},"date_updated":"2019-01-24T13:07:32Z","title":"Reweighted message passing revisited","department":[{"_id":"VlKo"}],"publist_id":"4671","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Vladimir Kolmogorov"}],"_id":"2273","status":"public","type":"report"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:56:28Z","citation":{"mla":"Gridchyn, Igor, and Vladimir Kolmogorov. Potts Model, Parametric Maxflow and k-Submodular Functions. IEEE, 2013, pp. 2320–27, doi:10.1109/ICCV.2013.288.","ama":"Gridchyn I, Kolmogorov V. Potts model, parametric maxflow and k-submodular functions. In: IEEE; 2013:2320-2327. doi:10.1109/ICCV.2013.288","apa":"Gridchyn, I., & Kolmogorov, V. (2013). Potts model, parametric maxflow and k-submodular functions (pp. 2320–2327). Presented at the ICCV: International Conference on Computer Vision, Sydney, Australia: IEEE. https://doi.org/10.1109/ICCV.2013.288","ieee":"I. Gridchyn and V. Kolmogorov, “Potts model, parametric maxflow and k-submodular functions,” presented at the ICCV: International Conference on Computer Vision, Sydney, Australia, 2013, pp. 2320–2327.","short":"I. Gridchyn, V. Kolmogorov, in:, IEEE, 2013, pp. 2320–2327.","chicago":"Gridchyn, Igor, and Vladimir Kolmogorov. “Potts Model, Parametric Maxflow and k-Submodular Functions,” 2320–27. IEEE, 2013. https://doi.org/10.1109/ICCV.2013.288.","ista":"Gridchyn I, Kolmogorov V. 2013. Potts model, parametric maxflow and k-submodular functions. ICCV: International Conference on Computer Vision, 2320–2327."},"title":"Potts model, parametric maxflow and k-submodular functions","department":[{"_id":"JoCs"},{"_id":"VlKo"}],"external_id":{"arxiv":["1310.1771"]},"publist_id":"4668","author":[{"first_name":"Igor","id":"4B60654C-F248-11E8-B48F-1D18A9856A87","last_name":"Gridchyn","full_name":"Gridchyn, Igor"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"_id":"2276","status":"public","conference":{"name":"ICCV: International Conference on Computer Vision","start_date":"2013-12-01","location":"Sydney, Australia","end_date":"2013-12-08"},"type":"conference","language":[{"iso":"eng"}],"day":"01","publication_status":"published","year":"2013","date_created":"2018-12-11T11:56:43Z","doi":"10.1109/ICCV.2013.288","date_published":"2013-12-01T00:00:00Z","page":"2320 - 2327","oa_version":"Preprint","abstract":[{"text":"The problem of minimizing the Potts energy function frequently occurs in computer vision applications. One way to tackle this NP-hard problem was proposed by Kovtun [19, 20]. It identifies a part of an optimal solution by running k maxflow computations, where k is the number of labels. The number of “labeled” pixels can be significant in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce the runtime to O (log k) maxflow computations (or one parametric maxflow computation). Furthermore, the output of our algorithm allows to speed-up the subsequent alpha expansion for the unlabeled part, or can be used as it is for time-critical applications. To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7] for Tree Metrics . We also show a connection to k-submodular functions from combinatorial optimization, and discuss k-submodular relaxations for general energy functions.","lang":"eng"}],"month":"12","oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1310.1771"}],"publisher":"IEEE","quality_controlled":"1"},{"publisher":"Springer","quality_controlled":"1","oa":1,"year":"2013","day":"01","page":"625 - 636","doi":"10.1007/978-3-642-39206-1_53","date_published":"2013-07-01T00:00:00Z","date_created":"2018-12-11T11:58:08Z","citation":{"chicago":"Kolmogorov, Vladimir. “The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization,” 7965:625–36. Springer, 2013. https://doi.org/10.1007/978-3-642-39206-1_53.","ista":"Kolmogorov V. 2013. The power of linear programming for finite-valued CSPs: A constructive characterization. ICALP: Automata, Languages and Programming, LNCS, vol. 7965, 625–636.","mla":"Kolmogorov, Vladimir. The Power of Linear Programming for Finite-Valued CSPs: A Constructive Characterization. Vol. 7965, no. 1, Springer, 2013, pp. 625–36, doi:10.1007/978-3-642-39206-1_53.","apa":"Kolmogorov, V. (2013). The power of linear programming for finite-valued CSPs: A constructive characterization (Vol. 7965, pp. 625–636). Presented at the ICALP: Automata, Languages and Programming, Riga, Latvia: Springer. https://doi.org/10.1007/978-3-642-39206-1_53","ama":"Kolmogorov V. The power of linear programming for finite-valued CSPs: A constructive characterization. In: Vol 7965. Springer; 2013:625-636. doi:10.1007/978-3-642-39206-1_53","short":"V. Kolmogorov, in:, Springer, 2013, pp. 625–636.","ieee":"V. Kolmogorov, “The power of linear programming for finite-valued CSPs: A constructive characterization,” presented at the ICALP: Automata, Languages and Programming, Riga, Latvia, 2013, vol. 7965, no. 1, pp. 625–636."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"}],"publist_id":"4383","external_id":{"arxiv":["1207.7213"]},"title":"The power of linear programming for finite-valued CSPs: A constructive characterization","abstract":[{"lang":"eng","text":"A class of valued constraint satisfaction problems (VCSPs) is characterised by a valued constraint language, a fixed set of cost functions on a finite domain. An instance of the problem is specified by a sum of cost functions from the language with the goal to minimise the sum. We study which classes of finite-valued languages can be solved exactly by the basic linear programming relaxation (BLP). Thapper and Živný showed [20] that if BLP solves the language then the language admits a binary commutative fractional polymorphism. We prove that the converse is also true. This leads to a necessary and a sufficient condition which can be checked in polynomial time for a given language. In contrast, the previous necessary and sufficient condition due to [20] involved infinitely many inequalities. More recently, Thapper and Živný [21] showed (using, in particular, a technique introduced in this paper) that core languages that do not satisfy our condition are NP-hard. Taken together, these results imply that a finite-valued language can either be solved using Linear Programming or is NP-hard."}],"oa_version":"Preprint","alternative_title":["LNCS"],"scopus_import":1,"main_file_link":[{"url":"http://arxiv.org/abs/1207.7213","open_access":"1"}],"month":"07","intvolume":" 7965","publication_status":"published","language":[{"iso":"eng"}],"related_material":{"record":[{"id":"2271","status":"public","relation":"later_version"}]},"volume":7965,"issue":"1","_id":"2518","type":"conference","conference":{"name":"ICALP: Automata, Languages and Programming","start_date":"2013-07-08","location":"Riga, Latvia","end_date":"2013-07-12"},"status":"public","date_updated":"2023-02-23T10:35:42Z","department":[{"_id":"VlKo"}]},{"article_number":"10","citation":{"mla":"Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative Valued CSPs.” Journal of the ACM, vol. 60, no. 2, 10, ACM, 2013, doi:10.1145/2450142.2450146.","ama":"Kolmogorov V, Živný S. The complexity of conservative valued CSPs. Journal of the ACM. 2013;60(2). doi:10.1145/2450142.2450146","apa":"Kolmogorov, V., & Živný, S. (2013). The complexity of conservative valued CSPs. Journal of the ACM. ACM. https://doi.org/10.1145/2450142.2450146","short":"V. Kolmogorov, S. Živný, Journal of the ACM 60 (2013).","ieee":"V. Kolmogorov and S. Živný, “The complexity of conservative valued CSPs,” Journal of the ACM, vol. 60, no. 2. ACM, 2013.","chicago":"Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative Valued CSPs.” Journal of the ACM. ACM, 2013. https://doi.org/10.1145/2450142.2450146.","ista":"Kolmogorov V, Živný S. 2013. The complexity of conservative valued CSPs. Journal of the ACM. 60(2), 10."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1110.2809"]},"author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"},{"first_name":"Stanislav","last_name":"Živný","full_name":"Živný, Stanislav"}],"publist_id":"3971","title":"The complexity of conservative valued CSPs","oa":1,"publisher":"ACM","quality_controlled":"1","year":"2013","publication":"Journal of the ACM","day":"02","date_created":"2018-12-11T11:59:48Z","doi":"10.1145/2450142.2450146","date_published":"2013-04-02T00:00:00Z","_id":"2828","type":"journal_article","status":"public","date_updated":"2021-01-12T07:00:00Z","department":[{"_id":"VlKo"}],"abstract":[{"text":"We study the complexity of valued constraint satisfaction problems (VCSPs) parametrized by a constraint language, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from the language and the goal is to minimize the sum. Under the unique games conjecture, the approximability of finite-valued VCSPs is well understood, see Raghavendra [2008]. However, there is no characterization of finite-valued VCSPs, let alone general-valued VCSPs, that can be solved exactly in polynomial time, thus giving insights from a combinatorial optimization perspective. We consider the case of languages containing all possible unary cost functions. In the case of languages consisting of only {0, ∞}-valued cost functions (i.e., relations), such languages have been called conservative and studied by Bulatov [2003, 2011] and recently by Barto [2011]. Since we study valued languages, we call a language conservative if it contains all finite-valued unary cost functions. The computational complexity of conservative valued languages has been studied by Cohen et al. [2006] for languages over Boolean domains, by Deineko et al. [2008] for {0, 1}-valued languages (a.k.a Max-CSP), and by Takhanov [2010a] for {0, ∞}-valued languages containing all finite-valued unary cost functions (a.k.a. Min-Cost-Hom). We prove a Schaefer-like dichotomy theorem for conservative valued languages: if all cost functions in the language satisfy a certain condition (specified by a complementary combination of STP and MJN multimor-phisms), then any instance can be solved in polynomial time (via a new algorithm developed in this article), otherwise the language is NP-hard. This is the first complete complexity classification of general-valued constraint languages over non-Boolean domains. It is a common phenomenon that complexity classifications of problems over non-Boolean domains are significantly harder than the Boolean cases. The polynomial-time algorithm we present for the tractable cases is a generalization of the submodular minimization problem and a result of Cohen et al. [2008]. Our results generalize previous results by Takhanov [2010a] and (a subset of results) by Cohen et al. [2006] and Deineko et al. [2008]. Moreover, our results do not rely on any computer-assisted search as in Deineko et al. [2008], and provide a powerful tool for proving hardness of finite-valued and general-valued languages.","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"url":"http://arxiv.org/abs/1110.2809","open_access":"1"}],"scopus_import":1,"intvolume":" 60","month":"04","publication_status":"published","language":[{"iso":"eng"}],"issue":"2","volume":60},{"abstract":[{"lang":"eng","text":" We introduce the M-modes problem for graphical models: predicting the M label configurations of highest probability that are at the same time local maxima of the probability landscape. M-modes have multiple possible applications: because they are intrinsically diverse, they provide a principled alternative to non-maximum suppression techniques for structured prediction, they can act as codebook vectors for quantizing the configuration space, or they can form component centers for mixture model approximation. We present two algorithms for solving the M-modes problem. The first algorithm solves the problem in polynomial time when the underlying graphical model is a simple chain. The second algorithm solves the problem for junction chains. In synthetic and real dataset, we demonstrate how M-modes can improve the performance of prediction. We also use the generated modes as a tool to understand the topography of the probability distribution of configurations, for example with relation to the training set size and amount of noise in the data. "}],"oa_version":"None","publisher":"JMLR","alternative_title":[" JMLR: W&CP"],"quality_controlled":"1","scopus_import":1,"oa":1,"main_file_link":[{"open_access":"1","url":"http://jmlr.org/proceedings/papers/v31/chen13a.html"}],"month":"01","intvolume":" 31","year":"2013","publication_status":"published","day":"01","language":[{"iso":"eng"}],"page":"161 - 169","date_published":"2013-01-01T00:00:00Z","volume":31,"date_created":"2018-12-11T12:00:14Z","_id":"2901","type":"conference","conference":{"start_date":"2013-04-29","location":"Scottsdale, AZ, United States","end_date":"2013-05-01","name":" AISTATS: Conference on Uncertainty in Artificial Intelligence"},"status":"public","date_updated":"2021-01-12T07:00:35Z","citation":{"mla":"Chen, Chao, et al. Computing the M Most Probable Modes of a Graphical Model. Vol. 31, JMLR, 2013, pp. 161–69.","apa":"Chen, C., Kolmogorov, V., Yan, Z., Metaxas, D., & Lampert, C. (2013). Computing the M most probable modes of a graphical model (Vol. 31, pp. 161–169). Presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States: JMLR.","ama":"Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. Computing the M most probable modes of a graphical model. In: Vol 31. JMLR; 2013:161-169.","short":"C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, C. Lampert, in:, JMLR, 2013, pp. 161–169.","ieee":"C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, and C. Lampert, “Computing the M most probable modes of a graphical model,” presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States, 2013, vol. 31, pp. 161–169.","chicago":"Chen, Chao, Vladimir Kolmogorov, Zhu Yan, Dimitris Metaxas, and Christoph Lampert. “Computing the M Most Probable Modes of a Graphical Model,” 31:161–69. JMLR, 2013.","ista":"Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. 2013. Computing the M most probable modes of a graphical model. AISTATS: Conference on Uncertainty in Artificial Intelligence, JMLR: W&CP, vol. 31, 161–169."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"3846","author":[{"last_name":"Chen","full_name":"Chen, Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao"},{"first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"},{"first_name":"Zhu","last_name":"Yan","full_name":"Yan, Zhu"},{"last_name":"Metaxas","full_name":"Metaxas, Dimitris","first_name":"Dimitris"},{"last_name":"Lampert","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"}],"title":"Computing the M most probable modes of a graphical model","department":[{"_id":"HeEd"},{"_id":"VlKo"},{"_id":"ChLa"}]},{"date_updated":"2023-10-17T09:51:32Z","department":[{"_id":"VlKo"}],"_id":"2272","conference":{"name":"ICML: International Conference on Machine Learning","start_date":"2013-06-16","location":"Atlanta, GA, USA","end_date":"2013-06-21"},"type":"conference","status":"public","publication_status":"published","language":[{"iso":"eng"}],"related_material":{"record":[{"id":"1794","status":"public","relation":"later_version"}]},"volume":28,"issue":"3","abstract":[{"text":"We consider Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x1...xn is the sum of terms over intervals [i,j] where each term is non-zero only if the substring xi...xj equals a prespecified pattern α. Such CRFs can be naturally applied to many sequence tagging problems.\r\nWe present efficient algorithms for the three standard inference tasks in a CRF, namely computing (i) the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities are respectively O(nL), O(nLℓmax) and O(nLmin{|D|,log(ℓmax+1)}) where L is the combined length of input patterns, ℓmax is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of (Ye et al., 2009) whose complexities are respectively O(nL|D|), O(n|Γ|L2ℓ2max) and O(nL|D|), where |Γ| is the number of input patterns.\r\nIn addition, we give an efficient algorithm for sampling. Finally, we consider the case of non-positive weights. (Komodakis & Paragios, 2009) gave an O(nL) algorithm for computing the MAP. We present a modification that has the same worst-case complexity but can beat it in the best case. ","lang":"eng"}],"oa_version":"Submitted Version","main_file_link":[{"url":"http://proceedings.mlr.press/v28/takhanov13.pdf?CFID=105472548&CFTOKEN=5c5859b5d97b4439-27B4AC58-BA92-A964-B598CAACEE6CC515","open_access":"1"}],"alternative_title":["JMLR"],"scopus_import":"1","intvolume":" 28","month":"06","citation":{"chicago":"Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” In ICML’13 Proceedings of the 30th International Conference on International, 28:145–53. ML Research Press, 2013.","ista":"Takhanov R, Kolmogorov V. 2013. Inference algorithms for pattern-based CRFs on sequence data. ICML’13 Proceedings of the 30th International Conference on International. ICML: International Conference on Machine Learning, JMLR, vol. 28, 145–153.","mla":"Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” ICML’13 Proceedings of the 30th International Conference on International, vol. 28, no. 3, ML Research Press, 2013, pp. 145–53.","ieee":"R. Takhanov and V. Kolmogorov, “Inference algorithms for pattern-based CRFs on sequence data,” in ICML’13 Proceedings of the 30th International Conference on International, Atlanta, GA, USA, 2013, vol. 28, no. 3, pp. 145–153.","short":"R. Takhanov, V. Kolmogorov, in:, ICML’13 Proceedings of the 30th International Conference on International, ML Research Press, 2013, pp. 145–153.","apa":"Takhanov, R., & Kolmogorov, V. (2013). Inference algorithms for pattern-based CRFs on sequence data. In ICML’13 Proceedings of the 30th International Conference on International (Vol. 28, pp. 145–153). Atlanta, GA, USA: ML Research Press.","ama":"Takhanov R, Kolmogorov V. Inference algorithms for pattern-based CRFs on sequence data. In: ICML’13 Proceedings of the 30th International Conference on International. Vol 28. ML Research Press; 2013:145-153."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","author":[{"full_name":"Takhanov, Rustem","last_name":"Takhanov","first_name":"Rustem","id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"}],"publist_id":"4672","title":"Inference algorithms for pattern-based CRFs on sequence data","year":"2013","publication":"ICML'13 Proceedings of the 30th International Conference on International","day":"01","page":"145 - 153","date_created":"2018-12-11T11:56:41Z","date_published":"2013-06-01T00:00:00Z","oa":1,"quality_controlled":"1","publisher":"ML Research Press"},{"related_material":{"record":[{"status":"public","id":"1675","relation":"later_version"}]},"date_published":"2013-11-28T00:00:00Z","date_created":"2018-12-11T11:56:42Z","day":"28","file":[{"file_size":405870,"date_updated":"2020-07-14T12:45:36Z","creator":"system","file_name":"IST-2016-671-v1+1_796.pdf","date_created":"2018-12-12T10:16:11Z","content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"37b61637b62fc079d9141c59d9f1a94f","file_id":"5197"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","year":"2013","publication_status":"published","month":"11","publisher":"IST Austria","scopus_import":1,"oa":1,"oa_version":"Published Version","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.\r\n\r\nIn this work, we put forward an alternative concept for PoWs -- so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model, using graphs with high "pebbling complexity" and Merkle hash-trees. ","lang":"eng"}],"title":"Proofs of Space","department":[{"_id":"VlKo"},{"_id":"KrPi"}],"file_date_updated":"2020-07-14T12:45:36Z","publist_id":"4670","author":[{"last_name":"Dziembowski","full_name":"Dziembowski, Stefan","first_name":"Stefan"},{"last_name":"Faust","full_name":"Faust, Sebastian","first_name":"Sebastian"},{"first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"ddc":["530"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"short":"S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, Proofs of Space, IST Austria, 2013.","ieee":"S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, Proofs of Space. IST Austria, 2013.","ama":"Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. Proofs of Space. IST Austria; 2013.","apa":"Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2013). Proofs of Space. IST Austria.","mla":"Dziembowski, Stefan, et al. Proofs of Space. IST Austria, 2013.","ista":"Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2013. Proofs of Space, IST Austria,p.","chicago":"Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Z Pietrzak. Proofs of Space. IST Austria, 2013."},"date_updated":"2024-03-20T08:31:49Z","status":"public","pubrep_id":"671","type":"report","_id":"2274"},{"acknowledgement":"We would like to thank Andrei Krokhin for encourag- ing our cooperation, for helpful discussions, and for his critical reading of the manuscript.\r\n","quality_controlled":"1","publisher":"Springer","oa":1,"year":"2012","day":"01","page":"451 - 462","doi":"10.1007/978-3-642-32147-4_40","date_published":"2012-04-01T00:00:00Z","date_created":"2018-12-11T12:00:24Z","citation":{"ama":"Huber A, Kolmogorov V. Towards minimizing k-submodular functions. In: Vol 7422. Springer; 2012:451-462. doi:10.1007/978-3-642-32147-4_40","apa":"Huber, A., & Kolmogorov, V. (2012). Towards minimizing k-submodular functions (Vol. 7422, pp. 451–462). Presented at the ISCO: International Symposium on Combinatorial Optimization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-642-32147-4_40","short":"A. Huber, V. Kolmogorov, in:, Springer, 2012, pp. 451–462.","ieee":"A. Huber and V. Kolmogorov, “Towards minimizing k-submodular functions,” presented at the ISCO: International Symposium on Combinatorial Optimization, Athens, Greece, 2012, vol. 7422, pp. 451–462.","mla":"Huber, Anna, and Vladimir Kolmogorov. Towards Minimizing K-Submodular Functions. Vol. 7422, Springer, 2012, pp. 451–62, doi:10.1007/978-3-642-32147-4_40.","ista":"Huber A, Kolmogorov V. 2012. Towards minimizing k-submodular functions. ISCO: International Symposium on Combinatorial Optimization, LNCS, vol. 7422, 451–462.","chicago":"Huber, Anna, and Vladimir Kolmogorov. “Towards Minimizing K-Submodular Functions,” 7422:451–62. Springer, 2012. https://doi.org/10.1007/978-3-642-32147-4_40."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Huber","full_name":"Huber, Anna","first_name":"Anna"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"}],"publist_id":"3806","title":"Towards minimizing k-submodular functions","abstract":[{"text":"In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k = 1 and k = 2 respectively.\r\n\r\nIn particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron.\r\n","lang":"eng"}],"oa_version":"Preprint","alternative_title":["LNCS"],"scopus_import":1,"main_file_link":[{"url":"http://arxiv.org/abs/1309.5469","open_access":"1"}],"month":"04","intvolume":" 7422","publication_status":"published","language":[{"iso":"eng"}],"volume":7422,"_id":"2930","type":"conference","conference":{"location":"Athens, Greece","end_date":"2012-04-21","start_date":"2012-04-19","name":"ISCO: International Symposium on Combinatorial Optimization"},"status":"public","date_updated":"2021-01-12T07:00:46Z","department":[{"_id":"VlKo"}]},{"_id":"2928","status":"public","type":"preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Kolmogorov, V., & Schoenemann, T. (2012). Generalized sequential tree-reweighted message passing. arXiv. ArXiv.","ama":"Kolmogorov V, Schoenemann T. Generalized sequential tree-reweighted message passing. arXiv. 2012.","short":"V. Kolmogorov, T. Schoenemann, ArXiv (2012).","ieee":"V. Kolmogorov and T. Schoenemann, “Generalized sequential tree-reweighted message passing,” arXiv. ArXiv, 2012.","mla":"Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted Message Passing.” ArXiv, ArXiv, 2012.","ista":"Kolmogorov V, Schoenemann T. 2012. Generalized sequential tree-reweighted message passing. arXiv, .","chicago":"Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted Message Passing.” ArXiv. ArXiv, 2012."},"date_updated":"2021-01-12T07:00:45Z","department":[{"_id":"VlKo"}],"title":"Generalized sequential tree-reweighted message passing","author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"},{"first_name":"Thomas","last_name":"Schoenemann","full_name":"Schoenemann, Thomas"}],"publist_id":"3809","external_id":{"arxiv":["1205.6352"]},"article_processing_charge":"No","oa_version":"Preprint","abstract":[{"lang":"eng","text":" This paper addresses the problem of approximate MAP-MRF inference in general graphical models. Following [36], we consider a family of linear programming relaxations of the problem where each relaxation is specified by a set of nested pairs of factors for which the marginalization constraint needs to be enforced. We develop a generalization of the TRW-S algorithm [9] for this problem, where we use a decomposition into junction chains, monotonic w.r.t. some ordering on the nodes. This generalizes the monotonic chains in [9] in a natural way. We also show how to deal with nested factors in an efficient way. Experiments show an improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on a number of computer vision and natural language processing problems. "}],"month":"05","publisher":"ArXiv","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1205.6352"}],"oa":1,"day":"29","language":[{"iso":"eng"}],"publication":"arXiv","year":"2012","publication_status":"published","date_published":"2012-05-29T00:00:00Z","date_created":"2018-12-11T12:00:23Z","page":"16"},{"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T07:00:46Z","citation":{"ama":"Torresani L, Kolmogorov V, Rother C. A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. 2012;35(2):259-271. doi:10.1109/TPAMI.2012.105","apa":"Torresani, L., Kolmogorov, V., & Rother, C. (2012). A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE. https://doi.org/10.1109/TPAMI.2012.105","short":"L. Torresani, V. Kolmogorov, C. Rother, IEEE Transactions on Pattern Analysis and Machine Intelligence 35 (2012) 259–271.","ieee":"L. Torresani, V. Kolmogorov, and C. Rother, “A dual decomposition approach to feature correspondence,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 2. IEEE, pp. 259–271, 2012.","mla":"Torresani, Lorenzo, et al. “A Dual Decomposition Approach to Feature Correspondence.” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 35, no. 2, IEEE, 2012, pp. 259–71, doi:10.1109/TPAMI.2012.105.","ista":"Torresani L, Kolmogorov V, Rother C. 2012. A dual decomposition approach to feature correspondence. IEEE Transactions on Pattern Analysis and Machine Intelligence. 35(2), 259–271.","chicago":"Torresani, Lorenzo, Vladimir Kolmogorov, and Carsten Rother. “A Dual Decomposition Approach to Feature Correspondence.” IEEE Transactions on Pattern Analysis and Machine Intelligence. IEEE, 2012. https://doi.org/10.1109/TPAMI.2012.105."},"title":"A dual decomposition approach to feature correspondence","department":[{"_id":"VlKo"}],"author":[{"first_name":"Lorenzo","last_name":"Torresani","full_name":"Torresani, Lorenzo"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"first_name":"Carsten","last_name":"Rother","full_name":"Rother, Carsten"}],"publist_id":"3805","_id":"2931","project":[{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"status":"public","type":"journal_article","publication":"IEEE Transactions on Pattern Analysis and Machine Intelligence","language":[{"iso":"eng"}],"day":"08","year":"2012","publication_status":"published","date_created":"2018-12-11T12:00:24Z","volume":35,"date_published":"2012-05-08T00:00:00Z","issue":"2","doi":"10.1109/TPAMI.2012.105","page":"259 - 271","acknowledgement":"This research was funded in part by Microsoft Research.","oa_version":"None","abstract":[{"lang":"eng","text":"In this paper, we present a new approach for establishing correspondences between sparse image features related by an unknown nonrigid mapping and corrupted by clutter and occlusion, such as points extracted from images of different instances of the same object category. We formulate this matching task as an energy minimization problem by defining an elaborate objective function of the appearance and the spatial arrangement of the features. Optimization of this energy is an instance of graph matching, which is in general an NP-hard problem. We describe a novel graph matching optimization technique, which we refer to as dual decomposition (DD), and demonstrate on a variety of examples that this method outperforms existing graph matching algorithms. In the majority of our examples, DD is able to find the global minimum within a minute. The ability to globally optimize the objective allows us to accurately learn the parameters of our matching model from training examples. We show on several matching tasks that our learned model yields results superior to those of state-of-the-art methods.\r\n"}],"intvolume":" 35","month":"05","publisher":"IEEE","scopus_import":1,"quality_controlled":"1"},{"doi":"10.1016/j.dam.2012.05.025","issue":"15","date_published":"2012-10-01T00:00:00Z","volume":160,"date_created":"2018-12-11T12:01:29Z","page":"2246 - 2258","day":"01","language":[{"iso":"eng"}],"publication":"Discrete Applied Mathematics","year":"2012","publication_status":"published","month":"10","intvolume":" 160","scopus_import":1,"quality_controlled":"1","publisher":"Elsevier","oa":1,"main_file_link":[{"url":"http://arxiv.org/abs/1006.1990","open_access":"1"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"We consider the problem of minimizing a function represented as a sum of submodular terms. We assume each term allows an efficient computation of exchange capacities. This holds, for example, for terms depending on a small number of variables, or for certain cardinality-dependent terms. A naive application of submodular minimization algorithms would not exploit the existence of specialized exchange capacity subroutines for individual terms. To overcome this, we cast the problem as a submodular flow (SF) problem in an auxiliary graph in such a way that applying most existing SF algorithms would rely only on these subroutines. We then explore in more detail Iwata's capacity scaling approach for submodular flows (Iwata 1997 [19]). In particular, we show how to improve its complexity in the case when the function contains cardinality-dependent terms."}],"department":[{"_id":"VlKo"}],"title":"Minimizing a sum of submodular functions","author":[{"first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"}],"publist_id":"3582","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Kolmogorov, V. (2012). Minimizing a sum of submodular functions. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2012.05.025","ama":"Kolmogorov V. Minimizing a sum of submodular functions. Discrete Applied Mathematics. 2012;160(15):2246-2258. doi:10.1016/j.dam.2012.05.025","short":"V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 2246–2258.","ieee":"V. Kolmogorov, “Minimizing a sum of submodular functions,” Discrete Applied Mathematics, vol. 160, no. 15. Elsevier, pp. 2246–2258, 2012.","mla":"Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete Applied Mathematics, vol. 160, no. 15, Elsevier, 2012, pp. 2246–58, doi:10.1016/j.dam.2012.05.025.","ista":"Kolmogorov V. 2012. Minimizing a sum of submodular functions. Discrete Applied Mathematics. 160(15), 2246–2258.","chicago":"Kolmogorov, Vladimir. “Minimizing a Sum of Submodular Functions.” Discrete Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2012.05.025."},"date_updated":"2021-01-12T07:41:11Z","status":"public","type":"journal_article","_id":"3117"},{"status":"public","type":"journal_article","_id":"3257","department":[{"_id":"VlKo"}],"date_updated":"2023-02-23T11:04:49Z","intvolume":" 160","month":"03","main_file_link":[{"url":"http://arxiv.org/abs/1005.2305","open_access":"1"}],"scopus_import":1,"oa_version":"Preprint","abstract":[{"lang":"eng","text":"Consider a convex relaxation f̂ of a pseudo-Boolean function f. We say that the relaxation is totally half-integral if f̂(x) is a polyhedral function with half-integral extreme points x, and this property is preserved after adding an arbitrary combination of constraints of the form x i=x j, x i=1-x j, and x i=γ where γ∈{0,1,1/2} is a constant. A well-known example is the roof duality relaxation for quadratic pseudo-Boolean functions f. We argue that total half-integrality is a natural requirement for generalizations of roof duality to arbitrary pseudo-Boolean functions. Our contributions are as follows. First, we provide a complete characterization of totally half-integral relaxations f̂ by establishing a one-to-one correspondence with bisubmodular functions. Second, we give a new characterization of bisubmodular functions. Finally, we show some relationships between general totally half-integral relaxations and relaxations based on the roof duality. On the conceptual level, our results show that bisubmodular functions provide a natural generalization of the roof duality approach to higher-order terms. This can be viewed as a non-submodular analogue of the fact that submodular functions generalize the s-t minimum cut problem with non-negative weights to higher-order terms."}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"2934"}]},"volume":160,"issue":"4-5","language":[{"iso":"eng"}],"publication_status":"published","title":"Generalized roof duality and bisubmodular functions","external_id":{"arxiv":["1005.2305"]},"publist_id":"3397","author":[{"first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"V. Kolmogorov, “Generalized roof duality and bisubmodular functions,” Discrete Applied Mathematics, vol. 160, no. 4–5. Elsevier, pp. 416–426, 2012.","short":"V. Kolmogorov, Discrete Applied Mathematics 160 (2012) 416–426.","apa":"Kolmogorov, V. (2012). Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. Elsevier. https://doi.org/10.1016/j.dam.2011.10.026","ama":"Kolmogorov V. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 2012;160(4-5):416-426. doi:10.1016/j.dam.2011.10.026","mla":"Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” Discrete Applied Mathematics, vol. 160, no. 4–5, Elsevier, 2012, pp. 416–26, doi:10.1016/j.dam.2011.10.026.","ista":"Kolmogorov V. 2012. Generalized roof duality and bisubmodular functions. Discrete Applied Mathematics. 160(4–5), 416–426.","chicago":"Kolmogorov, Vladimir. “Generalized Roof Duality and Bisubmodular Functions.” Discrete Applied Mathematics. Elsevier, 2012. https://doi.org/10.1016/j.dam.2011.10.026."},"oa":1,"quality_controlled":"1","publisher":"Elsevier","date_created":"2018-12-11T12:02:18Z","doi":"10.1016/j.dam.2011.10.026","date_published":"2012-03-01T00:00:00Z","page":"416 - 426","publication":"Discrete Applied Mathematics","day":"01","year":"2012"},{"_id":"3124","type":"conference","conference":{"name":"ICML: International Conference on Machine Learning","start_date":"2012-06-26","end_date":"2012-07-01","location":"Edinburgh, Scotland"},"status":"public","pubrep_id":"565","date_updated":"2023-02-23T12:24:24Z","citation":{"ama":"Korc F, Kolmogorov V, Lampert C. Approximating marginals using discrete energy minimization. In: ICML; 2012.","apa":"Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals using discrete energy minimization. Presented at the ICML: International Conference on Machine Learning, Edinburgh, Scotland: ICML.","ieee":"F. Korc, V. Kolmogorov, and C. Lampert, “Approximating marginals using discrete energy minimization,” presented at the ICML: International Conference on Machine Learning, Edinburgh, Scotland, 2012.","short":"F. Korc, V. Kolmogorov, C. Lampert, in:, ICML, 2012.","mla":"Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization. ICML, 2012.","ista":"Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization. ICML: International Conference on Machine Learning, Inferning 2012, .","chicago":"Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. “Approximating Marginals Using Discrete Energy Minimization.” ICML, 2012."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"author":[{"full_name":"Korc, Filip","last_name":"Korc","id":"476A2FD6-F248-11E8-B48F-1D18A9856A87","first_name":"Filip"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"last_name":"Lampert","full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph"}],"publist_id":"3575","department":[{"_id":"ChLa"},{"_id":"VlKo"}],"title":"Approximating marginals using discrete energy minimization","file_date_updated":"2020-07-14T12:46:00Z","abstract":[{"text":"We consider the problem of inference in a graphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pairwise terms over a discretized domain. This allows the use of techniques originally developed for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can outperform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.\r\n","lang":"eng"}],"oa_version":"Submitted Version","alternative_title":["Inferning 2012"],"quality_controlled":"1","publisher":"ICML","oa":1,"month":"06","has_accepted_license":"1","year":"2012","publication_status":"published","day":"30","file":[{"file_id":"4889","checksum":"3d0d4246548c736857302aadb2ff5d15","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2018-12-12T10:11:34Z","file_name":"IST-2016-565-v1+1_DM-inferning2012.pdf","creator":"system","date_updated":"2020-07-14T12:46:00Z","file_size":305836}],"language":[{"iso":"eng"}],"date_published":"2012-06-30T00:00:00Z","related_material":{"record":[{"relation":"later_version","status":"public","id":"5396"}]},"date_created":"2018-12-11T12:01:31Z"},{"file_date_updated":"2020-07-14T12:46:44Z","title":"Approximating marginals using discrete energy minimization","department":[{"_id":"VlKo"},{"_id":"ChLa"}],"author":[{"full_name":"Korc, Filip","last_name":"Korc","first_name":"Filip","id":"476A2FD6-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph","last_name":"Lampert","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"citation":{"mla":"Korc, Filip, et al. Approximating Marginals Using Discrete Energy Minimization. IST Austria, 2012, doi:10.15479/AT:IST-2012-0003.","ieee":"F. Korc, V. Kolmogorov, and C. Lampert, Approximating marginals using discrete energy minimization. IST Austria, 2012.","short":"F. Korc, V. Kolmogorov, C. Lampert, Approximating Marginals Using Discrete Energy Minimization, IST Austria, 2012.","ama":"Korc F, Kolmogorov V, Lampert C. Approximating Marginals Using Discrete Energy Minimization. IST Austria; 2012. doi:10.15479/AT:IST-2012-0003","apa":"Korc, F., Kolmogorov, V., & Lampert, C. (2012). Approximating marginals using discrete energy minimization. IST Austria. https://doi.org/10.15479/AT:IST-2012-0003","chicago":"Korc, Filip, Vladimir Kolmogorov, and Christoph Lampert. Approximating Marginals Using Discrete Energy Minimization. IST Austria, 2012. https://doi.org/10.15479/AT:IST-2012-0003.","ista":"Korc F, Kolmogorov V, Lampert C. 2012. Approximating marginals using discrete energy minimization, IST Austria, 13p."},"date_updated":"2023-02-23T11:13:22Z","pubrep_id":"36","status":"public","type":"technical_report","_id":"5396","date_created":"2018-12-12T11:39:06Z","doi":"10.15479/AT:IST-2012-0003","date_published":"2012-07-23T00:00:00Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"3124"}]},"page":"13","language":[{"iso":"eng"}],"day":"23","file":[{"file_name":"IST-2012-0003_IST-2012-0003.pdf","date_created":"2018-12-12T11:53:29Z","creator":"system","file_size":618744,"date_updated":"2020-07-14T12:46:44Z","file_id":"5490","checksum":"7e0ba85ad123b13223aaf6cdde2d288c","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"publication_status":"published","year":"2012","has_accepted_license":"1","publication_identifier":{"issn":["2664-1690"]},"month":"07","oa":1,"publisher":"IST Austria","alternative_title":["IST Austria Technical Report"],"oa_version":"Published Version","abstract":[{"text":"We consider the problem of inference in agraphical model with binary variables. While in theory it is arguably preferable to compute marginal probabilities, in practice researchers often use MAP inference due to the availability of efficient discrete optimization algorithms. We bridge the gap between the two approaches by introducing the Discrete Marginals technique in which approximate marginals are obtained by minimizing an objective function with unary and pair-wise terms over a discretized domain. This allows the use of techniques originally devel-oped for MAP-MRF inference and learning. We explore two ways to set up the objective function - by discretizing the Bethe free energy and by learning it from training data. Experimental results show that for certain types of graphs a learned function can out-perform the Bethe approximation. We also establish a link between the Bethe free energy and submodular functions.","lang":"eng"}]}]