--- _id: '10045' abstract: - lang: eng text: "Given a fixed finite metric space (V,μ), the {\\em minimum 0-extension problem}, denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai: if metric μ is {\\em orientable modular} then 0-Ext[μ] can be solved in polynomial time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as L♮-convex functions. We consider a more general version of the problem in which unary functions fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where set F⊆(V2) is fixed. We extend the complexity classification above by providing an explicit condition on (μ,F) for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs.\r\n" acknowledgement: We thank the anonymous reviewers for their careful reading of our manuscript and their many insightful comments and suggestions. Open access funding provided by Institute of Science and Technology (IST Austria). article_number: '2109.10203' article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Martin full_name: Dvorak, Martin id: 40ED02A8-C8B4-11E9-A9C0-453BE6697425 last_name: Dvorak orcid: 0000-0001-5293-214X - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete convexity. Mathematical Programming. 2024. doi:10.1007/s10107-024-02064-5 apa: Dvorak, M., & Kolmogorov, V. (2024). Generalized minimum 0-extension problem and discrete convexity. Mathematical Programming. Springer Nature. https://doi.org/10.1007/s10107-024-02064-5 chicago: Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” Mathematical Programming. Springer Nature, 2024. https://doi.org/10.1007/s10107-024-02064-5. ieee: M. Dvorak and V. Kolmogorov, “Generalized minimum 0-extension problem and discrete convexity,” Mathematical Programming. Springer Nature, 2024. ista: Dvorak M, Kolmogorov V. 2024. Generalized minimum 0-extension problem and discrete convexity. Mathematical Programming., 2109.10203. mla: Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem and Discrete Convexity.” Mathematical Programming, 2109.10203, Springer Nature, 2024, doi:10.1007/s10107-024-02064-5. short: M. Dvorak, V. Kolmogorov, Mathematical Programming (2024). date_created: 2021-09-27T10:48:23Z date_published: 2024-03-07T00:00:00Z date_updated: 2024-03-19T08:20:31Z day: '07' ddc: - '004' department: - _id: GradSch - _id: VlKo doi: 10.1007/s10107-024-02064-5 external_id: arxiv: - '2109.10203' file: - access_level: open_access checksum: e7e83065f7bc18b9c188bf93b5ca5db6 content_type: application/pdf creator: mdvorak date_created: 2021-09-27T10:54:51Z date_updated: 2021-09-27T10:54:51Z file_id: '10046' file_name: Generalized-0-Ext.pdf file_size: 603672 relation: main_file success: 1 file_date_updated: 2021-09-27T10:54:51Z has_accepted_license: '1' keyword: - minimum 0-extension problem - metric labeling problem - discrete metric spaces - metric extensions - computational complexity - valued constraint satisfaction problems - discrete convex analysis - L-convex functions language: - iso: eng month: '03' oa: 1 oa_version: Preprint publication: Mathematical Programming publication_identifier: eissn: - 1436-4646 issn: - 0025-5610 publication_status: epub_ahead publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Generalized minimum 0-extension problem and discrete convexity tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2024' ... --- _id: '14084' abstract: - lang: eng text: "A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We will consider sampling problems which come from Gibbs distributions, which are families of probability distributions over a discrete space Ω with probability mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max] and H(ω) ∈ {0} ∪ [1, n].\r\nThe partition function is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log Z(β_max))/Z(β_min)\r\nWe develop a number of algorithms to estimate the counts c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²) samples for integer-valued distributions (ignoring some second-order terms and parameters), We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs and perfect matchings in a graph." acknowledgement: We thank Heng Guo for helpful explanations of algorithms for sampling connected subgraphs and matchings, Maksym Serbyn for bringing to our attention the Wang-Landau algorithm and its use in physics. alternative_title: - LIPIcs article_number: '72' article_processing_charge: Yes author: - first_name: David G. full_name: Harris, David G. last_name: Harris - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Harris DG, Kolmogorov V. Parameter estimation for Gibbs distributions. In: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.72' apa: 'Harris, D. G., & Kolmogorov, V. (2023). Parameter estimation for Gibbs distributions. In 50th International Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.72' chicago: Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.72. ieee: D. G. Harris and V. Kolmogorov, “Parameter estimation for Gibbs distributions,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261. ista: 'Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 72.' mla: Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” 50th International Colloquium on Automata, Languages, and Programming, vol. 261, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.72. short: D.G. Harris, V. Kolmogorov, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. conference: end_date: 2023-07-14 location: Paderborn, Germany name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2023-07-10 date_created: 2023-08-20T22:01:14Z date_published: 2023-07-01T00:00:00Z date_updated: 2023-08-21T06:49:11Z day: '01' ddc: - '000' - '510' department: - _id: VlKo doi: 10.4230/LIPIcs.ICALP.2023.72 external_id: arxiv: - '2007.10824' file: - access_level: open_access checksum: 6dee0684245bb1c524b9c955db1e933d content_type: application/pdf creator: dernst date_created: 2023-08-21T06:45:16Z date_updated: 2023-08-21T06:45:16Z file_id: '14088' file_name: 2023_LIPIcsICALP_Harris.pdf file_size: 917791 relation: main_file success: 1 file_date_updated: 2023-08-21T06:45:16Z has_accepted_license: '1' intvolume: ' 261' language: - iso: eng month: '07' oa: 1 oa_version: Published Version publication: 50th International Colloquium on Automata, Languages, and Programming publication_identifier: isbn: - '9783959772785' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Parameter estimation for Gibbs distributions tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 261 year: '2023' ... --- _id: '13120' abstract: - lang: eng text: 'We formalized general (i.e., type-0) grammars using the Lean 3 proof assistant. We defined basic notions of rewrite rules and of words derived by a grammar, and used grammars to show closure of the class of type-0 languages under four operations: union, reversal, concatenation, and the Kleene star. The literature mostly focuses on Turing machine arguments, which are possibly more difficult to formalize. For the Kleene star, we could not follow the literature and came up with our own grammar-based construction.' acknowledgement: "Jasmin Blanchette: This research has received funding from the Netherlands Organization\r\nfor Scientific Research (NWO) under the Vidi program (project No. 016.Vidi.189.037, Lean Forward).\r\n__\r\nWe thank Vladimir Kolmogorov for making this collaboration possible. We\r\nthank Václav Končický for discussing ideas about the Kleene star construction. We thank Patrick Johnson, Floris van Doorn, and Damiano Testa for their small yet very valuable contributions to our code. We thank Eric Wieser for simplifying one of our proofs. We thank Mark Summerfield for suggesting textual improvements. We thank the anonymous reviewers for very helpful comments. Finally, we thank the Lean community for helping us with various technical issues and answering many questions. " alternative_title: - LIPIcs article_number: '15' article_processing_charge: No author: - first_name: Martin full_name: Dvorak, Martin id: 40ED02A8-C8B4-11E9-A9C0-453BE6697425 last_name: Dvorak orcid: 0000-0001-5293-214X - first_name: Jasmin full_name: Blanchette, Jasmin last_name: Blanchette citation: ama: 'Dvorak M, Blanchette J. Closure properties of general grammars - formally verified. In: 14th International Conference on Interactive Theorem Proving. Vol 268. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ITP.2023.15' apa: 'Dvorak, M., & Blanchette, J. (2023). Closure properties of general grammars - formally verified. In 14th International Conference on Interactive Theorem Proving (Vol. 268). Bialystok, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITP.2023.15' chicago: Dvorak, Martin, and Jasmin Blanchette. “Closure Properties of General Grammars - Formally Verified.” In 14th International Conference on Interactive Theorem Proving, Vol. 268. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ITP.2023.15. ieee: M. Dvorak and J. Blanchette, “Closure properties of general grammars - formally verified,” in 14th International Conference on Interactive Theorem Proving, Bialystok, Poland, 2023, vol. 268. ista: 'Dvorak M, Blanchette J. 2023. Closure properties of general grammars - formally verified. 14th International Conference on Interactive Theorem Proving. ITP: International Conference on Interactive Theorem Proving, LIPIcs, vol. 268, 15.' mla: Dvorak, Martin, and Jasmin Blanchette. “Closure Properties of General Grammars - Formally Verified.” 14th International Conference on Interactive Theorem Proving, vol. 268, 15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ITP.2023.15. short: M. Dvorak, J. Blanchette, in:, 14th International Conference on Interactive Theorem Proving, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. conference: end_date: 2023-08-04 location: Bialystok, Poland name: 'ITP: International Conference on Interactive Theorem Proving' start_date: 2023-07-31 date_created: 2023-06-05T07:29:05Z date_published: 2023-07-27T00:00:00Z date_updated: 2023-09-25T11:04:29Z day: '27' ddc: - '000' department: - _id: GradSch - _id: VlKo doi: 10.4230/LIPIcs.ITP.2023.15 external_id: arxiv: - '2302.06420' file: - access_level: open_access checksum: 773a0197f05b67feaa6cb1e17ec3642d content_type: application/pdf creator: dernst date_created: 2023-08-07T11:55:43Z date_updated: 2023-08-07T11:55:43Z file_id: '13982' file_name: 2023_LIPIcS_Dvorak.pdf file_size: 715976 relation: main_file success: 1 file_date_updated: 2023-08-07T11:55:43Z has_accepted_license: '1' intvolume: ' 268' language: - iso: eng month: '07' oa: 1 oa_version: Published Version publication: 14th International Conference on Interactive Theorem Proving publication_identifier: eissn: - 1868-8969 isbn: - '9783959772846' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' related_material: link: - relation: software url: https://github.com/madvorak/grammars/tree/publish scopus_import: '1' status: public title: Closure properties of general grammars - formally verified tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 268 year: '2023' ... --- _id: '14448' abstract: - lang: eng text: We consider the problem of solving LP relaxations of MAP-MRF inference problems, and in particular the method proposed recently in [16], [35]. As a key computational subroutine, it uses a variant of the Frank-Wolfe (FW) method to minimize a smooth convex function over a combinatorial polytope. We propose an efficient implementation of this subroutine based on in-face Frank-Wolfe directions, introduced in [4] in a different context. More generally, we define an abstract data structure for a combinatorial subproblem that enables in-face FW directions, and describe its specialization for tree-structured MAP-MRF inference subproblems. Experimental results indicate that the resulting method is the current state-of-art LP solver for some classes of problems. Our code is available at pub.ist.ac.at/~vnk/papers/IN-FACE-FW.html. article_processing_charge: No author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Kolmogorov V. Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions. In: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Vol 2023. IEEE; 2023:11980-11989. doi:10.1109/CVPR52729.2023.01153' apa: 'Kolmogorov, V. (2023). Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Vol. 2023, pp. 11980–11989). Vancouver, Canada: IEEE. https://doi.org/10.1109/CVPR52729.2023.01153' chicago: 'Kolmogorov, Vladimir. “Solving Relaxations of MAP-MRF Problems: Combinatorial in-Face Frank-Wolfe Directions.” In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2023:11980–89. IEEE, 2023. https://doi.org/10.1109/CVPR52729.2023.01153.' ieee: 'V. Kolmogorov, “Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions,” in Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, Vancouver, Canada, 2023, vol. 2023, pp. 11980–11989.' ista: 'Kolmogorov V. 2023. Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. CVPR: Conference on Computer Vision and Pattern Recognition vol. 2023, 11980–11989.' mla: 'Kolmogorov, Vladimir. “Solving Relaxations of MAP-MRF Problems: Combinatorial in-Face Frank-Wolfe Directions.” Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2023, IEEE, 2023, pp. 11980–89, doi:10.1109/CVPR52729.2023.01153.' short: V. Kolmogorov, in:, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE, 2023, pp. 11980–11989. conference: end_date: 2023-06-24 location: Vancouver, Canada name: 'CVPR: Conference on Computer Vision and Pattern Recognition' start_date: 2023-06-17 date_created: 2023-10-22T22:01:16Z date_published: 2023-08-22T00:00:00Z date_updated: 2023-10-31T12:01:24Z day: '22' department: - _id: VlKo doi: 10.1109/CVPR52729.2023.01153 external_id: arxiv: - '2010.09567' intvolume: ' 2023' language: - iso: eng main_file_link: - open_access: '1' url: ' https://doi.org/10.48550/arXiv.2010.09567' month: '08' oa: 1 oa_version: Preprint page: 11980-11989 publication: Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition publication_identifier: isbn: - '9798350301298' issn: - 1063-6919 publication_status: published publisher: IEEE quality_controlled: '1' scopus_import: '1' status: public title: 'Solving relaxations of MAP-MRF problems: Combinatorial in-face Frank-Wolfe directions' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 2023 year: '2023' ... --- _id: '10737' abstract: - lang: eng text: We consider two models for the sequence labeling (tagging) problem. The first one is a Pattern-Based Conditional Random Field (PB), in which the energy of a string (chain labeling) x=x1⁢…⁢xn∈Dn is a sum of terms over intervals [i,j] where each term is non-zero only if the substring xi⁢…⁢xj equals a prespecified word w∈Λ. The second model is a Weighted Context-Free Grammar (WCFG) frequently used for natural language processing. PB and WCFG encode local and non-local interactions respectively, and thus can be viewed as complementary. We propose a Grammatical Pattern-Based CRF model (GPB) that combines the two in a natural way. We argue that it has certain advantages over existing approaches such as the Hybrid model of Benedí and Sanchez that combines N-grams and WCFGs. The focus of this paper is to analyze the complexity of inference tasks in a GPB such as computing MAP. We present a polynomial-time algorithm for general GPBs and a faster version for a special case that we call Interaction Grammars. article_processing_charge: No article_type: original author: - first_name: Rustem full_name: Takhanov, Rustem id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87 last_name: Takhanov - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: Takhanov R, Kolmogorov V. Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. 2022;26(1):257-272. doi:10.3233/IDA-205623 apa: Takhanov, R., & Kolmogorov, V. (2022). Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. IOS Press. https://doi.org/10.3233/IDA-205623 chicago: Takhanov, Rustem, and Vladimir Kolmogorov. “Combining Pattern-Based CRFs and Weighted Context-Free Grammars.” Intelligent Data Analysis. IOS Press, 2022. https://doi.org/10.3233/IDA-205623. ieee: R. Takhanov and V. Kolmogorov, “Combining pattern-based CRFs and weighted context-free grammars,” Intelligent Data Analysis, vol. 26, no. 1. IOS Press, pp. 257–272, 2022. ista: Takhanov R, Kolmogorov V. 2022. Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. 26(1), 257–272. mla: Takhanov, Rustem, and Vladimir Kolmogorov. “Combining Pattern-Based CRFs and Weighted Context-Free Grammars.” Intelligent Data Analysis, vol. 26, no. 1, IOS Press, 2022, pp. 257–72, doi:10.3233/IDA-205623. short: R. Takhanov, V. Kolmogorov, Intelligent Data Analysis 26 (2022) 257–272. date_created: 2022-02-06T23:01:32Z date_published: 2022-01-14T00:00:00Z date_updated: 2023-08-02T14:09:41Z day: '14' department: - _id: VlKo doi: 10.3233/IDA-205623 external_id: arxiv: - '1404.5475' isi: - '000749997700015' intvolume: ' 26' isi: 1 issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1404.5475 month: '01' oa: 1 oa_version: Preprint page: 257-272 publication: Intelligent Data Analysis publication_identifier: eissn: - 1571-4128 issn: - 1088-467X publication_status: published publisher: IOS Press quality_controlled: '1' scopus_import: '1' status: public title: Combining pattern-based CRFs and weighted context-free grammars type: journal_article user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8 volume: 26 year: '2022' ...