[{"oa_version":"Preprint","intvolume":" 16","title":"Absorption and directed Jónsson terms","status":"public","_id":"10864","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","abstract":[{"lang":"eng","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."}],"type":"book_chapter","date_published":"2018-03-21T00:00:00Z","page":"203-220","citation":{"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.","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.","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.","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","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.","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.","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"},"publication":"Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science","article_processing_charge":"No","day":"21","series_title":"OCTR","scopus_import":"1","volume":16,"date_created":"2022-03-18T10:30:32Z","date_updated":"2023-09-05T15:37:18Z","author":[{"full_name":"Kazda, Alexandr","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","first_name":"Alexandr","last_name":"Kazda"},{"full_name":"Kozik, Marcin","first_name":"Marcin","last_name":"Kozik"},{"full_name":"McKenzie, Ralph","first_name":"Ralph","last_name":"McKenzie"},{"first_name":"Matthew","last_name":"Moore","full_name":"Moore, Matthew"}],"publisher":"Springer Nature","editor":[{"first_name":"J","last_name":"Czelakowski","full_name":"Czelakowski, J"}],"department":[{"_id":"VlKo"}],"publication_status":"published","acknowledgement":"The second author was supported by National Science Center grant DEC-2011-/01/B/ST6/01006.","year":"2018","place":"Cham","language":[{"iso":"eng"}],"doi":"10.1007/978-3-319-74772-9_7","quality_controlled":"1","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/1502.01072","open_access":"1"}],"external_id":{"arxiv":["1502.01072"]},"publication_identifier":{"eissn":["2211-2766"],"isbn":["9783319747712"],"eisbn":["9783319747729"],"issn":["2211-2758"]},"month":"03"},{"month":"12","isi":1,"quality_controlled":"1","project":[{"call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160"}],"external_id":{"arxiv":["1602.03124"],"isi":["000468036500007"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.03124"}],"language":[{"iso":"eng"}],"doi":"10.1145/3230649","article_number":"22","ec_funded":1,"publication_status":"published","department":[{"_id":"VlKo"}],"publisher":"ACM","year":"2018","date_updated":"2023-09-20T11:20:26Z","date_created":"2019-02-17T22:59:25Z","volume":15,"author":[{"first_name":"Alexandr","last_name":"Kazda","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","full_name":"Kazda, Alexandr"},{"last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","full_name":"Kolmogorov, Vladimir"},{"full_name":"Rolinek, Michal","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","first_name":"Michal","last_name":"Rolinek"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1192"}]},"scopus_import":"1","day":"01","article_processing_charge":"No","article_type":"original","publication":"ACM Transactions on Algorithms","citation":{"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","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.","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","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.","short":"A. Kazda, V. Kolmogorov, M. Rolinek, ACM Transactions on Algorithms 15 (2018).","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.","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."},"date_published":"2018-12-01T00:00:00Z","type":"journal_article","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."}],"issue":"2","title":"Even delta-matroids and the complexity of planar boolean CSPs","status":"public","intvolume":" 15","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"6032","oa_version":"Preprint"},{"date_updated":"2023-09-20T11:20:26Z","date_created":"2018-12-11T11:50:38Z","author":[{"last_name":"Kazda","first_name":"Alexandr","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","full_name":"Kazda, Alexandr"},{"full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov"},{"first_name":"Michal","last_name":"Rolinek","id":"3CB3BC06-F248-11E8-B48F-1D18A9856A87","full_name":"Rolinek, Michal"}],"related_material":{"record":[{"id":"6032","relation":"later_version","status":"public"}]},"publication_status":"published","publisher":"SIAM","department":[{"_id":"VlKo"}],"year":"2017","publist_id":"6159","ec_funded":1,"language":[{"iso":"eng"}],"conference":{"end_date":"2017-01019","location":"Barcelona, Spain","start_date":"2017-01-16","name":"SODA: Symposium on Discrete Algorithms"},"doi":"10.1137/1.9781611974782.20","quality_controlled":"1","isi":1,"project":[{"grant_number":"616160","_id":"25FBA906-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1602.03124"}],"external_id":{"isi":["000426965800020"]},"oa":1,"month":"01","publication_identifier":{"isbn":["978-161197478-2"]},"oa_version":"Submitted Version","title":"Even delta-matroids and the complexity of planar Boolean CSPs","status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"1192","abstract":[{"lang":"eng","text":"The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Knowing that edge CSP is tractable for even Δ-matroid constraints allows us to extend the tractability result to a larger class of Δ-matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary."}],"type":"conference","date_published":"2017-01-01T00:00:00Z","page":"307 - 326","citation":{"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","ieee":"A. Kazda, V. Kolmogorov, and M. Rolinek, “Even delta-matroids and the complexity of planar Boolean CSPs,” presented at the SODA: Symposium on Discrete Algorithms, Barcelona, Spain, 2017, pp. 307–326.","apa":"Kazda, A., Kolmogorov, V., & Rolinek, M. (2017). Even delta-matroids and the complexity of planar Boolean CSPs (pp. 307–326). Presented at the SODA: Symposium on Discrete Algorithms, Barcelona, Spain: SIAM. https://doi.org/10.1137/1.9781611974782.20","ista":"Kazda A, Kolmogorov V, Rolinek M. 2017. Even delta-matroids and the complexity of planar Boolean CSPs. SODA: Symposium on Discrete Algorithms, 307–326.","short":"A. Kazda, V. Kolmogorov, M. Rolinek, in:, SIAM, 2017, pp. 307–326.","mla":"Kazda, Alexandr, et al. Even Delta-Matroids and the Complexity of Planar Boolean CSPs. SIAM, 2017, pp. 307–26, doi:10.1137/1.9781611974782.20.","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."},"day":"01","article_processing_charge":"No"},{"scopus_import":1,"day":"20","page":"1033 - 1060","citation":{"ama":"Barto L, Kazda A. Deciding absorption. International Journal of Algebra and Computation. 2016;26(5):1033-1060. doi:10.1142/S0218196716500430","apa":"Barto, L., & Kazda, A. (2016). Deciding absorption. International Journal of Algebra and Computation. World Scientific Publishing. https://doi.org/10.1142/S0218196716500430","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.","ista":"Barto L, Kazda A. 2016. Deciding absorption. International Journal of Algebra and Computation. 26(5), 1033–1060.","short":"L. Barto, A. Kazda, International Journal of Algebra and Computation 26 (2016) 1033–1060.","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.","chicago":"Barto, Libor, and Alexandr Kazda. “Deciding Absorption.” International Journal of Algebra and Computation. World Scientific Publishing, 2016. https://doi.org/10.1142/S0218196716500430."},"publication":"International Journal of Algebra and Computation","date_published":"2016-07-20T00:00:00Z","type":"journal_article","issue":"5","abstract":[{"lang":"eng","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."}],"intvolume":" 26","title":"Deciding absorption","status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"1353","oa_version":"Preprint","month":"07","quality_controlled":"1","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1512.07009"}],"oa":1,"language":[{"iso":"eng"}],"doi":"10.1142/S0218196716500430","publist_id":"5893","publisher":"World Scientific Publishing","department":[{"_id":"VlKo"}],"publication_status":"published","acknowledgement":"Libor Barto and Alexandr Kazda were supported by the the Grant Agency of the Czech Republic, grant GACR 13-01832S. ","year":"2016","volume":26,"date_updated":"2021-01-12T06:50:06Z","date_created":"2018-12-11T11:51:32Z","author":[{"first_name":"Libor","last_name":"Barto","full_name":"Barto, Libor"},{"full_name":"Kazda, Alexandr","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","last_name":"Kazda","first_name":"Alexandr"}]},{"day":"01","month":"02","scopus_import":1,"language":[{"iso":"eng"}],"date_published":"2016-02-01T00:00:00Z","doi":"10.1007/s00012-015-0358-8","page":"75 - 84","quality_controlled":"1","oa":1,"citation":{"ama":"Kazda A. CSP for binary conservative relational structures. Algebra Universalis. 2016;75(1):75-84. doi:10.1007/s00012-015-0358-8","ista":"Kazda A. 2016. CSP for binary conservative relational structures. Algebra Universalis. 75(1), 75–84.","apa":"Kazda, A. (2016). CSP for binary conservative relational structures. Algebra Universalis. Springer. https://doi.org/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.","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.","short":"A. Kazda, Algebra Universalis 75 (2016) 75–84.","chicago":"Kazda, Alexandr. “CSP for Binary Conservative Relational Structures.” Algebra Universalis. Springer, 2016. https://doi.org/10.1007/s00012-015-0358-8."},"main_file_link":[{"url":"http://arxiv.org/abs/1112.1099","open_access":"1"}],"publication":"Algebra Universalis","publist_id":"5554","issue":"1","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"}],"type":"journal_article","oa_version":"Preprint","volume":75,"date_updated":"2021-01-12T06:52:00Z","date_created":"2018-12-11T11:53:01Z","author":[{"full_name":"Kazda, Alexandr","first_name":"Alexandr","last_name":"Kazda","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87"}],"department":[{"_id":"VlKo"}],"publisher":"Springer","intvolume":" 75","status":"public","title":"CSP for binary conservative relational structures","publication_status":"published","year":"2016","_id":"1612","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87"}]