--- _id: '2271' 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. 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. " author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Johan full_name: Thapper, Johan last_name: Thapper - first_name: Stanislav full_name: Živný, Stanislav last_name: Živný citation: 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 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 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. 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. 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. 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. short: V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015) 1–36. date_created: 2018-12-11T11:56:41Z date_published: 2015-02-01T00:00:00Z date_updated: 2023-02-23T10:46:30Z day: '01' department: - _id: VlKo doi: 10.1137/130945648 external_id: arxiv: - '1311.4219' intvolume: ' 44' issue: '1' language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1311.4219 month: '02' oa: 1 oa_version: Preprint page: 1 - 36 publication: SIAM Journal on Computing publication_status: published publisher: SIAM publist_id: '4673' quality_controlled: '1' related_material: record: - id: '2518' relation: earlier_version status: public scopus_import: 1 status: public title: The power of linear programming for general-valued CSPs type: journal_article user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 44 year: '2015' ... --- _id: '1637' 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. alternative_title: - 56th Annual Symposium on Foundations of Computer Science author: - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Andrei full_name: Krokhin, Andrei last_name: Krokhin - first_name: Michal full_name: Rolinek, Michal id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87 last_name: Rolinek citation: 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' 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. 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.' ista: 'Kolmogorov V, Krokhin A, Rolinek M. 2015. The complexity of general-valued CSPs. FOCS: Foundations of Computer Science, 56th Annual Symposium on Foundations of Computer Science, , 1246–1258.' mla: Kolmogorov, Vladimir, et al. The Complexity of General-Valued CSPs. IEEE, 2015, pp. 1246–58, doi:10.1109/FOCS.2015.80. short: V. Kolmogorov, A. Krokhin, M. Rolinek, in:, IEEE, 2015, pp. 1246–1258. conference: end_date: 2015-10-20 location: Berkeley, CA, United States name: 'FOCS: Foundations of Computer Science' start_date: 2015-10-18 date_created: 2018-12-11T11:53:10Z date_published: 2015-12-01T00:00:00Z date_updated: 2023-02-23T12:44:26Z day: '01' department: - _id: VlKo doi: 10.1109/FOCS.2015.80 ec_funded: 1 language: - iso: eng main_file_link: - open_access: '1' url: http://arxiv.org/abs/1502.07327 month: '12' oa: 1 oa_version: Preprint page: 1246 - 1258 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' publication_status: published publisher: IEEE publist_id: '5518' quality_controlled: '1' related_material: record: - id: '644' relation: other status: public scopus_import: 1 status: public title: The complexity of general-valued CSPs type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2015' ... --- _id: '1675' 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). alternative_title: - LNCS article_processing_charge: No author: - first_name: Stefan full_name: Dziembowski, Stefan last_name: Dziembowski - first_name: Sebastian full_name: Faust, Sebastian last_name: Faust - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov - first_name: Krzysztof Z full_name: Pietrzak, Krzysztof Z id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87 last_name: Pietrzak orcid: 0000-0002-9139-1654 citation: 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' 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. 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.' 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. short: S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, in:, 35th Annual Cryptology Conference, Springer, 2015, pp. 585–605. conference: end_date: 2015-08-20 location: Santa Barbara, CA, United States name: 'CRYPTO: International Cryptology Conference' start_date: 2015-08-16 date_created: 2018-12-11T11:53:24Z date_published: 2015-08-01T00:00:00Z date_updated: 2024-03-20T08:31:49Z day: '01' department: - _id: VlKo - _id: KrPi doi: 10.1007/978-3-662-48000-7_29 ec_funded: 1 intvolume: ' 9216' language: - iso: eng main_file_link: - open_access: '1' url: https://eprint.iacr.org/2013/796.pdf month: '08' oa: 1 oa_version: Preprint page: 585 - 605 project: - _id: 25FBA906-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '616160' name: 'Discrete Optimization in Computer Vision: Theory and Practice' - _id: 258C570E-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '259668' name: Provable Security for Physical Cryptography publication: 35th Annual Cryptology Conference publication_identifier: isbn: - '9783662479995' issn: - 0302-9743 publication_status: published publisher: Springer publist_id: '5474' pubrep_id: '671' quality_controlled: '1' related_material: record: - id: '2274' relation: earlier_version status: public scopus_import: '1' status: public title: Proofs of space type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 9216 year: '2015' ... --- _id: '2275' 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" author: - first_name: Carl full_name: Olsson, Carl last_name: Olsson - first_name: Johannes full_name: Ulen, Johannes last_name: Ulen - first_name: Yuri full_name: Boykov, Yuri last_name: Boykov - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: 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' 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. 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.' ista: 'Olsson C, Ulen J, Boykov Y, Kolmogorov V. 2014. Partial enumeration and curvature regularization. ICCV: International Conference on Computer Vision, 2936–2943.' mla: Olsson, Carl, et al. Partial Enumeration and Curvature Regularization. IEEE, 2014, pp. 2936–43, doi:10.1109/ICCV.2013.365. short: C. Olsson, J. Ulen, Y. Boykov, V. Kolmogorov, in:, IEEE, 2014, pp. 2936–2943. conference: end_date: 2013-12-08 location: Sydney, Australia name: 'ICCV: International Conference on Computer Vision' start_date: 2013-12-01 date_created: 2018-12-11T11:56:42Z date_published: 2014-03-03T00:00:00Z date_updated: 2021-01-12T06:56:28Z day: '03' ddc: - '000' department: - _id: VlKo doi: 10.1109/ICCV.2013.365 file: - access_level: open_access checksum: 4a74b5c92d6dcd2348c2c10ec8dd18bf content_type: application/pdf creator: system date_created: 2018-12-12T10:09:30Z date_updated: 2020-07-14T12:45:36Z file_id: '4754' file_name: IST-2016-566-v1+1_iccv13_part_enumeration.pdf file_size: 378601 relation: main_file file_date_updated: 2020-07-14T12:45:36Z has_accepted_license: '1' language: - iso: eng month: '03' oa: 1 oa_version: Submitted Version page: 2936 - 2943 publication_status: published publisher: IEEE publist_id: '4669' pubrep_id: '566' quality_controlled: '1' scopus_import: 1 status: public title: Partial enumeration and curvature regularization type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ... --- _id: '7038' article_processing_charge: No author: - first_name: Kristóf full_name: Huszár, Kristóf id: 33C26278-F248-11E8-B48F-1D18A9856A87 last_name: Huszár orcid: 0000-0002-5445-5057 - first_name: Michal full_name: Rolinek, Michal id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87 last_name: Rolinek citation: 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. chicago: Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction to Mathematical Games. IST Austria, n.d. ieee: K. Huszár and M. Rolinek, Playful Math - An introduction to mathematical games. IST Austria. ista: Huszár K, Rolinek M. Playful Math - An introduction to mathematical games, IST Austria, 5p. mla: Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction to Mathematical Games. IST Austria. short: K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games, IST Austria, n.d. date_created: 2019-11-18T15:57:05Z date_published: 2014-06-30T00:00:00Z date_updated: 2020-07-14T23:11:45Z day: '30' ddc: - '510' department: - _id: VlKo - _id: UlWa file: - access_level: open_access checksum: 2b94e5e1f4c3fe8ab89b12806276fb09 content_type: application/pdf creator: dernst date_created: 2019-11-18T15:57:51Z date_updated: 2020-07-14T12:47:48Z file_id: '7039' file_name: 2014_Playful_Math_Huszar.pdf file_size: 511233 relation: main_file file_date_updated: 2020-07-14T12:47:48Z has_accepted_license: '1' language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: '5' publication_status: draft publisher: IST Austria status: public title: Playful Math - An introduction to mathematical games type: working_paper user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2014' ...