---
_id: '641'
abstract:
- lang: eng
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.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Vera
full_name: Trajkovska, Vera
last_name: Trajkovska
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Freddie
full_name: Åström, Freddie
last_name: Åström
- first_name: Stefanie
full_name: Petra, Stefanie
last_name: Petra
citation:
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'
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'
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.
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.'
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.
short: V. Trajkovska, P. Swoboda, F. Åström, S. Petra, in:, F. Lauze, Y. Dong, A.
Bjorholm Dahl (Eds.), Springer, 2017, pp. 323–334.
conference:
end_date: 2017-06-08
location: Kolding, Denmark
name: 'SSVM: Scale Space and Variational Methods in Computer Vision'
start_date: 2017-06-04
date_created: 2018-12-11T11:47:39Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2025-09-11T07:20:56Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-319-58771-4_26
editor:
- first_name: François
full_name: Lauze, François
last_name: Lauze
- first_name: Yiqiu
full_name: Dong, Yiqiu
last_name: Dong
- first_name: Anders
full_name: Bjorholm Dahl, Anders
last_name: Bjorholm Dahl
external_id:
isi:
- '000432210900026'
intvolume: ' 10302'
isi: 1
language:
- iso: eng
month: '01'
oa_version: None
page: 323 - 334
publication_identifier:
isbn:
- 978-331958770-7
publication_status: published
publisher: Springer
publist_id: '7147'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Graphical model parameter learning by inverse linear programming
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 10302
year: '2017'
...
---
_id: '915'
abstract:
- lang: eng
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.
article_processing_charge: No
author:
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Bjoern
full_name: Andres, Bjoern
last_name: Andres
citation:
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'
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'
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.
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.'
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.'
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.
short: P. Swoboda, B. Andres, in:, IEEE, 2017, pp. 4990–4999.
conference:
end_date: 2017-07-26
location: Honolulu, HA, United States
name: 'CVPR: Computer Vision and Pattern Recognition'
start_date: 2017-07-21
corr_author: '1'
date_created: 2018-12-11T11:49:11Z
date_published: 2017-07-01T00:00:00Z
date_updated: 2024-11-04T13:52:34Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.1109/CVPR.2017.530
ec_funded: 1
external_id:
isi:
- '000418371405009'
file:
- access_level: open_access
checksum: 7e51dacefa693574581a32da3eff63dc
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T12:52:46Z
date_updated: 2020-07-14T12:48:15Z
file_id: '5849'
file_name: Swoboda_A_Message_Passing_CVPR_2017_paper.pdf
file_size: 883264
relation: main_file
file_date_updated: 2020-07-14T12:48:15Z
has_accepted_license: '1'
intvolume: ' 2017'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 4990-4999
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
isbn:
- 978-153860457-1
publication_status: published
publisher: IEEE
publist_id: '6526'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A message passing algorithm for the minimum cost multicut problem
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2017
year: '2017'
...
---
_id: '916'
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.
article_processing_charge: No
author:
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Carsten
full_name: Rother, Carsten
last_name: Rother
- first_name: Carsten
full_name: Abu Alhaija, Carsten
last_name: Abu Alhaija
- first_name: Dagmar
full_name: Kainmueller, Dagmar
last_name: Kainmueller
- first_name: Bogdan
full_name: Savchynskyy, Bogdan
last_name: Savchynskyy
citation:
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'
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.
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.'
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.'
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.
short: P. Swoboda, C. Rother, C. Abu Alhaija, D. Kainmueller, B. Savchynskyy, in:,
IEEE, 2017, pp. 7062–7071.
conference:
end_date: 2017-07-26
location: Honolulu, HA, United States
name: 'CVPR: Computer Vision and Pattern Recognition'
start_date: 2017-07-21
corr_author: '1'
date_created: 2018-12-11T11:49:11Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2024-11-04T13:52:34Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.1109/CVPR.2017.747
ec_funded: 1
external_id:
isi:
- '000418371407018'
file:
- access_level: open_access
checksum: e38a2740daad1ea178465843b5072906
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T12:49:38Z
date_updated: 2020-07-14T12:48:15Z
file_id: '5848'
file_name: 2017_CVPR_Swoboda2.pdf
file_size: 944332
relation: main_file
file_date_updated: 2020-07-14T12:48:15Z
has_accepted_license: '1'
intvolume: ' 2017'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 7062-7071
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
isbn:
- 978-153860457-1
publication_status: published
publisher: IEEE
publist_id: '6525'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A study of lagrangean decompositions and dual ascent solvers for graph matching
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2017
year: '2017'
...
---
_id: '917'
abstract:
- lang: eng
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.
article_processing_charge: No
author:
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Jan
full_name: Kuske, Jan
last_name: Kuske
- first_name: Bogdan
full_name: Savchynskyy, Bogdan
last_name: Savchynskyy
citation:
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'
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'
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.
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.'
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.'
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.
short: P. Swoboda, J. Kuske, B. Savchynskyy, in:, IEEE, 2017, pp. 4950–4960.
conference:
end_date: 2017-07-26
location: Honolulu, HA, United States
name: 'CVPR: Computer Vision and Pattern Recognition'
start_date: 2017-07-21
corr_author: '1'
date_created: 2018-12-11T11:49:11Z
date_published: 2017-07-01T00:00:00Z
date_updated: 2024-11-04T13:52:34Z
day: '01'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.1109/CVPR.2017.526
ec_funded: 1
external_id:
isi:
- '000418371405005'
file:
- access_level: open_access
checksum: 72fd291046bd8e5717961bd68f6b6f03
content_type: application/pdf
creator: dernst
date_created: 2019-01-18T12:45:55Z
date_updated: 2020-07-14T12:48:15Z
file_id: '5847'
file_name: 2017_CVPR_Swoboda.pdf
file_size: 898652
relation: main_file
file_date_updated: 2020-07-14T12:48:15Z
has_accepted_license: '1'
intvolume: ' 2017'
isi: 1
language:
- iso: eng
month: '07'
oa: 1
oa_version: Submitted Version
page: 4950-4960
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
isbn:
- 978-153860457-1
publication_status: published
publisher: IEEE
publist_id: '6524'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A dual ascent framework for Lagrangean decomposition of combinatorial problems
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 2017
year: '2017'
...
---
_id: '644'
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 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.
article_processing_charge: No
arxiv: 1
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.
SIAM Journal on Computing. 2017;46(3):1087-1110. 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
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.
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.
ista: Kolmogorov V, Krokhin A, Rolinek M. 2017. The complexity of general-valued
CSPs. SIAM Journal on Computing. 46(3), 1087–1110.
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.
short: V. Kolmogorov, A. Krokhin, M. Rolinek, SIAM Journal on Computing 46 (2017)
1087–1110.
date_created: 2018-12-11T11:47:40Z
date_published: 2017-06-29T00:00:00Z
date_updated: 2025-09-23T13:45:56Z
day: '29'
department:
- _id: VlKo
doi: 10.1137/16M1091836
ec_funded: 1
external_id:
arxiv:
- '1502.07327'
isi:
- '000404774300010'
intvolume: ' 46'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1502.07327
month: '06'
oa: 1
oa_version: Preprint
page: 1087 - 1110
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: SIAM Journal on Computing
publication_status: published
publisher: SIAM
publist_id: '7138'
quality_controlled: '1'
related_material:
record:
- id: '1637'
relation: other
status: public
scopus_import: '1'
status: public
title: The complexity of general-valued CSPs
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 46
year: '2017'
...
---
_id: '646'
abstract:
- lang: eng
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.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Jan
full_name: Kuske, Jan
last_name: Kuske
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
- first_name: Stefanie
full_name: Petra, Stefanie
last_name: Petra
citation:
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'
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'
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.
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.'
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.'
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.
short: J. Kuske, P. Swoboda, S. Petra, in:, F. Lauze, Y. Dong, A. Bjorholm Dahl
(Eds.), Springer, 2017, pp. 235–246.
conference:
end_date: 2017-06-08
location: Kolding, Denmark
name: 'SSVM: Scale Space and Variational Methods in Computer Vision'
start_date: 2017-06-04
date_created: 2018-12-11T11:47:41Z
date_published: 2017-06-01T00:00:00Z
date_updated: 2025-09-11T07:16:00Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-319-58771-4_19
ec_funded: 1
editor:
- first_name: François
full_name: Lauze, François
last_name: Lauze
- first_name: Yiqiu
full_name: Dong, Yiqiu
last_name: Dong
- first_name: Anders
full_name: Bjorholm Dahl, Anders
last_name: Bjorholm Dahl
external_id:
arxiv:
- '1703.03769'
isi:
- '000432210900019'
intvolume: ' 10302'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1703.03769
month: '06'
oa: 1
oa_version: Submitted Version
page: 235 - 246
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
isbn:
- 978-331958770-7
publication_status: published
publisher: Springer
publist_id: '7132'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A novel convex relaxation for non binary discrete tomography
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 10302
year: '2017'
...
---
OA_place: publisher
_id: '992'
abstract:
- lang: eng
text: "An instance of the Constraint Satisfaction Problem (CSP) is given by a finite
set of\r\nvariables, a finite domain of labels, and a set of constraints, each
constraint acting on\r\na subset of the variables. The goal is to find an assignment
of labels to its variables\r\nthat satisfies all constraints (or decide whether
one exists). If we allow more general\r\n“soft” constraints, which come with (possibly
infinite) costs of particular assignments,\r\nwe obtain instances from a richer
class called Valued Constraint Satisfaction Problem\r\n(VCSP). There the goal
is to find an assignment with minimum total cost.\r\nIn this thesis, we focus
(assuming that P\r\n6\r\n=\r\nNP) on classifying computational com-\r\nplexity
of CSPs and VCSPs under certain restricting conditions. Two results are the core\r\ncontent
of the work. In one of them, we consider VCSPs parametrized by a constraint\r\nlanguage,
that is the set of “soft” constraints allowed to form the instances, and finish\r\nthe
complexity classification modulo (missing pieces of) complexity classification
for\r\nanalogously parametrized CSP. The other result is a generalization of Edmonds’
perfect\r\nmatching algorithm. This generalization contributes to complexity classfications
in two\r\nways. First, it gives a new (largest known) polynomial-time solvable
class of Boolean\r\nCSPs in which every variable may appear in at most two constraints
and second, it\r\nsettles full classification of Boolean CSPs with planar drawing
(again parametrized by a\r\nconstraint language)."
acknowledgement: FP7/2007-2013/ERC grant agreement no 616160
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
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
chicago: Rolinek, Michal. “Complexity of Constraint Satisfaction.” Institute of
Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_815.
ieee: M. Rolinek, “Complexity of constraint satisfaction,” Institute of Science
and Technology Austria, 2017.
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.
corr_author: '1'
date_created: 2018-12-11T11:49:35Z
date_published: 2017-05-01T00:00:00Z
date_updated: 2026-04-08T14:17:06Z
day: '01'
ddc:
- '004'
degree_awarded: PhD
department:
- _id: VlKo
doi: 10.15479/AT:ISTA:th_815
ec_funded: 1
file:
- access_level: open_access
checksum: 81761fb939acb7585c36629f765b4373
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:07:55Z
date_updated: 2020-07-14T12:48:18Z
file_id: '4654'
file_name: IST-2017-815-v1+3_final_blank_signature_maybe_pdfa.pdf
file_size: 786145
relation: main_file
- access_level: closed
checksum: 2b2d7e1d6c1c79a9795a7aa0f860baf3
content_type: application/zip
creator: dernst
date_created: 2019-04-05T08:43:24Z
date_updated: 2020-07-14T12:48:18Z
file_id: '6208'
file_name: 2017_Thesis_Rolinek_source.zip
file_size: 5936337
relation: source_file
file_date_updated: 2020-07-14T12:48:18Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '97'
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6407'
pubrep_id: '815'
status: public
supervisor:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
title: Complexity of constraint satisfaction
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2017'
...
---
_id: '1193'
abstract:
- lang: eng
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.
acknowledgement: European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant
agreement no 616160
article_number: '7782993'
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
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'
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.
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.
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.'
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.
short: V. Kolmogorov, in:, Proceedings - Annual IEEE Symposium on Foundations of
Computer Science, IEEE, 2016.
conference:
end_date: 2016-09-11
location: 'New Brunswick, NJ, USA '
name: 'FOCS: Foundations of Computer Science'
start_date: 2016-09-09
date_created: 2018-12-11T11:50:38Z
date_published: 2016-12-15T00:00:00Z
date_updated: 2025-09-22T09:44:20Z
day: '15'
department:
- _id: VlKo
doi: 10.1109/FOCS.2016.88
ec_funded: 1
external_id:
arxiv:
- '1506.08547'
isi:
- '000391198500082'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1506.08547v7
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Proceedings - Annual IEEE Symposium on Foundations of Computer Science
publication_status: published
publisher: IEEE
publist_id: '6158'
quality_controlled: '1'
related_material:
record:
- id: '5975'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Commutativity in the algorithmic Lovasz local lemma
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 2016-December
year: '2016'
...
---
_id: '1231'
abstract:
- lang: eng
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).'
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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Binyi
full_name: Chen, Binyi
last_name: Chen
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- 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
- first_name: Stefano
full_name: Tessaro, Stefano
last_name: Tessaro
citation:
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'
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.
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.'
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.'
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.
short: J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S.
Tessaro, in:, Springer, 2016, pp. 358–387.
conference:
end_date: 2016-05-12
location: Vienna, Austria
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2016-05-08
date_created: 2018-12-11T11:50:51Z
date_published: 2016-04-28T00:00:00Z
date_updated: 2025-09-22T09:22:54Z
day: '28'
department:
- _id: KrPi
- _id: VlKo
doi: 10.1007/978-3-662-49896-5_13
ec_funded: 1
external_id:
isi:
- '000389727200013'
intvolume: ' 9666'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/100
month: '04'
oa: 1
oa_version: Submitted Version
page: 358 - 387
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
- _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: Springer
publist_id: '6103'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the complexity of scrypt and proofs of space in the parallel random oracle
model
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9666
year: '2016'
...
---
_id: '1353'
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.
acknowledgement: 'Libor Barto and Alexandr Kazda were supported by the the Grant Agency
of the Czech Republic, grant GACR 13-01832S. '
article_processing_charge: No
arxiv: 1
author:
- first_name: Libor
full_name: Barto, Libor
last_name: Barto
- first_name: Alexandr
full_name: Kazda, Alexandr
id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87
last_name: Kazda
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
chicago: Barto, Libor, and Alexandr Kazda. “Deciding Absorption.” International
Journal of Algebra and Computation. World Scientific Publishing, 2016. 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.
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.
short: L. Barto, A. Kazda, International Journal of Algebra and Computation 26 (2016)
1033–1060.
date_created: 2018-12-11T11:51:32Z
date_published: 2016-07-20T00:00:00Z
date_updated: 2025-09-22T08:10:54Z
day: '20'
department:
- _id: VlKo
doi: 10.1142/S0218196716500430
external_id:
arxiv:
- '1512.07009'
isi:
- '000383151800008'
intvolume: ' 26'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1512.07009
month: '07'
oa: 1
oa_version: Preprint
page: 1033 - 1060
publication: International Journal of Algebra and Computation
publication_status: published
publisher: World Scientific Publishing
publist_id: '5893'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deciding absorption
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 26
year: '2016'
...
---
_id: '1377'
abstract:
- lang: eng
text: We consider the problem of minimizing the continuous valued total variation
subject to different unary terms on trees and propose fast direct algorithms based
on dynamic programming to solve these problems. We treat both the convex and the
nonconvex case and derive worst-case complexities that are equal to or better
than existing methods. We show applications to total variation based two dimensional
image processing and computer vision problems based on a Lagrangian decomposition
approach. The resulting algorithms are very effcient, offer a high degree of parallelism,
and come along with memory requirements which are only in the order of the number
of image pixels.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Thomas
full_name: Pock, Thomas
last_name: Pock
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
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
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.
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.
ista: Kolmogorov V, Pock T, Rolinek M. 2016. Total variation on a tree. SIAM Journal
on Imaging Sciences. 9(2), 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.
short: V. Kolmogorov, T. Pock, M. Rolinek, SIAM Journal on Imaging Sciences 9 (2016)
605–636.
date_created: 2018-12-11T11:51:40Z
date_published: 2016-05-03T00:00:00Z
date_updated: 2025-09-22T07:34:48Z
day: '03'
department:
- _id: VlKo
doi: 10.1137/15M1010257
ec_funded: 1
external_id:
arxiv:
- '1502.07770'
isi:
- '000385275400005'
intvolume: ' 9'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1502.07770
month: '05'
oa: 1
oa_version: Preprint
page: 605 - 636
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: SIAM Journal on Imaging Sciences
publication_status: published
publisher: 'Society for Industrial and Applied Mathematics '
publist_id: '5834'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Total variation on a tree
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9
year: '2016'
...
---
_id: '1612'
abstract:
- lang: eng
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).
article_processing_charge: No
arxiv: 1
author:
- first_name: Alexandr
full_name: Kazda, Alexandr
id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87
last_name: Kazda
citation:
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.
ieee: A. Kazda, “CSP for binary conservative relational structures,” Algebra
Universalis, vol. 75, no. 1. Springer, pp. 75–84, 2016.
ista: Kazda A. 2016. CSP for binary conservative relational structures. Algebra
Universalis. 75(1), 75–84.
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.
corr_author: '1'
date_created: 2018-12-11T11:53:01Z
date_published: 2016-02-01T00:00:00Z
date_updated: 2025-09-18T11:00:04Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/s00012-015-0358-8
external_id:
arxiv:
- '1112.1099'
isi:
- '000375422500006'
intvolume: ' 75'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1112.1099
month: '02'
oa: 1
oa_version: Preprint
page: 75 - 84
publication: Algebra Universalis
publication_status: published
publisher: Springer
publist_id: '5554'
quality_controlled: '1'
scopus_import: '1'
status: public
title: CSP for binary conservative relational structures
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 75
year: '2016'
...
---
_id: '5557'
abstract:
- lang: eng
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."
article_processing_charge: No
author:
- first_name: Paul
full_name: Swoboda, Paul
id: 446560C6-F248-11E8-B48F-1D18A9856A87
last_name: Swoboda
citation:
ama: Swoboda P. Synthetic discrete tomography problems. 2016. doi: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
chicago: Swoboda, Paul. “Synthetic Discrete Tomography Problems.” Institute of Science
and Technology Austria, 2016. https://doi.org/10.15479/AT:ISTA:46.
ieee: P. Swoboda, “Synthetic discrete tomography problems.” Institute of Science
and Technology Austria, 2016.
ista: Swoboda P. 2016. Synthetic discrete tomography problems, Institute of Science
and Technology Austria, 10.15479/AT:ISTA:46.
mla: Swoboda, Paul. Synthetic Discrete Tomography Problems. Institute of
Science and Technology Austria, 2016, doi:10.15479/AT:ISTA:46.
short: P. Swoboda, (2016).
contributor:
- contributor_type: data_collector
first_name: Jan
last_name: Kuske
datarep_id: '46'
date_created: 2018-12-12T12:31:31Z
date_published: 2016-09-20T00:00:00Z
date_updated: 2024-02-21T13:50:21Z
day: '20'
ddc:
- '006'
department:
- _id: VlKo
doi: 10.15479/AT:ISTA:46
file:
- access_level: open_access
checksum: aa5a16a0dc888da7186fb8fc45e88439
content_type: application/zip
creator: system
date_created: 2018-12-12T13:05:19Z
date_updated: 2020-07-14T12:47:02Z
file_id: '5645'
file_name: IST-2016-46-v1+1_discrete_tomography_synthetic.zip
file_size: 36058401
relation: main_file
file_date_updated: 2020-07-14T12:47:02Z
has_accepted_license: '1'
keyword:
- discrete tomography
license: https://creativecommons.org/publicdomain/zero/1.0/
month: '09'
oa: 1
oa_version: Published Version
publisher: Institute of Science and Technology Austria
status: public
title: Synthetic discrete tomography problems
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
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2016'
...
---
_id: '1794'
abstract:
- lang: eng
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.
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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Rustem
full_name: Takhanov, Rustem
id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87
last_name: Takhanov
citation:
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
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
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.
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.
ista: Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs
on sequence data. Algorithmica. 76(1), 17–46.
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.
short: V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46.
corr_author: '1'
date_created: 2018-12-11T11:54:02Z
date_published: 2016-09-01T00:00:00Z
date_updated: 2025-09-29T14:28:47Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/s00453-015-0017-7
ec_funded: 1
external_id:
arxiv:
- '1210.0508'
isi:
- '000381149500002'
intvolume: ' 76'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1210.0508
month: '09'
oa: 1
oa_version: Preprint
page: 17 - 46
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Algorithmica
publication_status: published
publisher: Springer
publist_id: '5316'
quality_controlled: '1'
related_material:
record:
- id: '2272'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Inference algorithms for pattern-based CRFs on sequence data
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 76
year: '2016'
...
---
_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. "
article_processing_charge: No
arxiv: 1
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: 2025-09-23T14:14:57Z
day: '01'
department:
- _id: VlKo
doi: 10.1137/130945648
external_id:
arxiv:
- '1311.4219'
isi:
- '000353967100001'
intvolume: ' 44'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 44
year: '2015'
...
---
_id: '1636'
abstract:
- lang: eng
text: "Constraint Satisfaction Problem (CSP) is a fundamental algorithmic problem
that appears in many areas of Computer Science. It can be equivalently stated
as computing a homomorphism R→ΓΓ between two relational structures, e.g. between
two directed graphs. Analyzing its complexity has been a prominent research direction,
especially for the fixed template CSPs where the right side ΓΓ is fixed and the
left side R is unconstrained.\r\n\r\nFar fewer results are known for the hybrid
setting that restricts both sides simultaneously. It assumes that R belongs to
a certain class of relational structures (called a structural restriction in this
paper). We study which structural restrictions are effective, i.e. there exists
a fixed template ΓΓ (from a certain class of languages) for which the problem
is tractable when R is restricted, and NP-hard otherwise. We provide a characterization
for structural restrictions that are closed under inverse homomorphisms. The criterion
is based on the chromatic number of a relational structure defined in this paper;
it generalizes the standard chromatic number of a graph.\r\n\r\nAs our main tool,
we use the algebraic machinery developed for fixed template CSPs. To apply it
to our case, we introduce a new construction called a “lifted language”. We also
give a characterization for structural restrictions corresponding to minor-closed
families of graphs, extend results to certain Valued CSPs (namely conservative
valued languages), and state implications for (valued) CSPs with ordered variables
and for the maximum weight independent set problem on some restricted families
of graphs."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
- first_name: Rustem
full_name: Takhanov, Rustem
last_name: Takhanov
citation:
ama: 'Kolmogorov V, Rolinek M, Takhanov R. Effectiveness of structural restrictions
for hybrid CSPs. In: 26th International Symposium. Vol 9472. Springer Nature;
2015:566-577. doi:10.1007/978-3-662-48971-0_48'
apa: 'Kolmogorov, V., Rolinek, M., & Takhanov, R. (2015). Effectiveness of structural
restrictions for hybrid CSPs. In 26th International Symposium (Vol. 9472,
pp. 566–577). Nagoya, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-48971-0_48'
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.
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.
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.
conference:
end_date: 2015-12-11
location: Nagoya, Japan
name: 'ISAAC: International Symposium on Algorithms and Computation'
start_date: 2015-12-09
date_created: 2018-12-11T11:53:10Z
date_published: 2015-12-01T00:00:00Z
date_updated: 2025-09-23T08:39:38Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-662-48971-0_48
ec_funded: 1
external_id:
arxiv:
- '1504.07067'
isi:
- '000375151300048'
intvolume: ' 9472'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1504.07067
month: '12'
oa: 1
oa_version: Preprint
page: 566 - 577
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: 26th International Symposium
publication_identifier:
isbn:
- 978-3-662-48970-3
publication_status: published
publisher: Springer Nature
publist_id: '5519'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Effectiveness of structural restrictions for hybrid CSPs
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9472
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
article_processing_charge: No
arxiv: 1
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
corr_author: '1'
date_created: 2018-12-11T11:53:10Z
date_published: 2015-12-01T00:00:00Z
date_updated: 2025-09-23T13:45:57Z
day: '01'
department:
- _id: VlKo
doi: 10.1109/FOCS.2015.80
ec_funded: 1
external_id:
arxiv:
- '1502.07327'
isi:
- '000379204700071'
isi: 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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
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: 2025-09-23T09:55:25Z
day: '01'
department:
- _id: VlKo
- _id: KrPi
doi: 10.1007/978-3-662-48000-7_29
ec_funded: 1
external_id:
isi:
- '000364183100029'
intvolume: ' 9216'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9216
year: '2015'
...
---
_id: '1859'
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. "
article_processing_charge: No
arxiv: 1
author:
- first_name: Neel
full_name: Shah, Neel
id: 31ABAF80-F248-11E8-B48F-1D18A9856A87
last_name: Shah
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
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'
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.
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.'
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.
short: N. Shah, V. Kolmogorov, C. Lampert, in:, IEEE, 2015, pp. 2737–2745.
conference:
end_date: 2015-06-12
location: Boston, MA, USA
name: 'CVPR: Computer Vision and Pattern Recognition'
start_date: 2015-06-07
corr_author: '1'
date_created: 2018-12-11T11:54:24Z
date_published: 2015-06-01T00:00:00Z
date_updated: 2025-06-11T07:20:12Z
day: '01'
department:
- _id: VlKo
- _id: ChLa
doi: 10.1109/CVPR.2015.7298890
ec_funded: 1
external_id:
arxiv:
- '1408.6804'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1408.6804
month: '06'
oa: 1
oa_version: Preprint
page: 2737 - 2745
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'
publication_status: published
publisher: IEEE
publist_id: '5240'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A multi-plane block-coordinate Frank-Wolfe algorithm for training structural
SVMs with a costly max-oracle
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
OA_place: repository
OA_type: green
_id: '1841'
abstract:
- lang: eng
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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
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
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
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.
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.
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.
short: V. Kolmogorov, IEEE Transactions on Pattern Analysis and Machine Intelligence
37 (2015) 919–930.
corr_author: '1'
date_created: 2018-12-11T11:54:18Z
date_published: 2015-05-01T00:00:00Z
date_updated: 2025-09-22T14:33:14Z
day: '01'
department:
- _id: VlKo
doi: 10.1109/TPAMI.2014.2363465
ec_funded: 1
external_id:
arxiv:
- '1309.5655'
isi:
- '000352533000002'
intvolume: ' 37'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1309.5655
month: '05'
oa: 1
oa_version: Preprint
page: 919 - 930
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: IEEE Transactions on Pattern Analysis and Machine Intelligence
publication_status: published
publisher: IEEE
publist_id: '5261'
quality_controlled: '1'
related_material:
record:
- id: '2273'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: A new look at reweighted message passing
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 37
year: '2015'
...