---
_id: '2270'
abstract:
- lang: eng
text: "Representation languages for coalitional games are a key research area in
algorithmic game theory. There is an inher-\r\nent tradeoff between how general
a language is, allowing it to capture more elaborate games, and how hard
\ it is computationally to optimize and solve such games. One prominent such
\ language is the simple yet expressive\r\nWeighted Graph Games (WGGs) representation
(Deng and Papadimitriou 1994), which maintains knowledge about synergies between
agents in the form of an edge weighted graph. We consider the problem of finding
\ the optimal coalition structure in WGGs. The agents in such games are vertices
in a graph, and the value of a coalition is the sum of the weights of the edges
present between coalition members. The optimal coalition structure is a partition
of the agents to coalitions, that maximizes the sum of utilities obtained by the
coalitions. We show that finding the optimal coalition structure is not
only hard for general graphs, but is also intractable for restricted families
such as planar graphs which are amenable for many other combinatorial problems.
\ We then provide algorithms with constant factor approximations for planar, minorfree
and bounded degree graphs."
author:
- first_name: Yoram
full_name: Bachrach, Yoram
last_name: Bachrach
- first_name: Pushmeet
full_name: Kohli, Pushmeet
last_name: Kohli
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Morteza
full_name: Zadimoghaddam, Morteza
last_name: Zadimoghaddam
citation:
ama: 'Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. Optimal Coalition Structures
in Cooperative Graph Games. In: AAAI Press; 2013:81-87.'
apa: 'Bachrach, Y., Kohli, P., Kolmogorov, V., & Zadimoghaddam, M. (2013). Optimal
Coalition Structures in Cooperative Graph Games (pp. 81–87). Presented at the
AAAI: Conference on Artificial Intelligence, Bellevue, WA, United States: AAAI
Press.'
chicago: Bachrach, Yoram, Pushmeet Kohli, Vladimir Kolmogorov, and Morteza Zadimoghaddam.
“Optimal Coalition Structures in Cooperative Graph Games,” 81–87. AAAI Press,
2013.
ieee: 'Y. Bachrach, P. Kohli, V. Kolmogorov, and M. Zadimoghaddam, “Optimal Coalition
Structures in Cooperative Graph Games,” presented at the AAAI: Conference on Artificial
Intelligence, Bellevue, WA, United States, 2013, pp. 81–87.'
ista: 'Bachrach Y, Kohli P, Kolmogorov V, Zadimoghaddam M. 2013. Optimal Coalition
Structures in Cooperative Graph Games. AAAI: Conference on Artificial Intelligence,
81–87.'
mla: Bachrach, Yoram, et al. Optimal Coalition Structures in Cooperative Graph
Games. AAAI Press, 2013, pp. 81–87.
short: Y. Bachrach, P. Kohli, V. Kolmogorov, M. Zadimoghaddam, in:, AAAI Press,
2013, pp. 81–87.
conference:
end_date: 2013-07-18
location: Bellevue, WA, United States
name: 'AAAI: Conference on Artificial Intelligence'
start_date: 2013-07-14
date_created: 2018-12-11T11:56:41Z
date_published: 2013-12-31T00:00:00Z
date_updated: 2021-01-12T06:56:25Z
day: '31'
department:
- _id: VlKo
external_id:
arxiv:
- '1108.5248'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1108.5248
month: '12'
oa: 1
oa_version: None
page: 81-87
publication_status: published
publisher: AAAI Press
publist_id: '4674'
quality_controlled: '1'
status: public
title: Optimal Coalition Structures in Cooperative Graph Games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2273'
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 Diusion (MSD) and a faster
Sequential Tree-Reweighted Message Passing (TRW-S). Importantly, our derivation
is simpler than the original derivation of TRW-S, and does not involve a decomposition
into trees. This allows easy generalizations. We present such a generalization
for the case of higher-order graphical models, and test it on several real-world
problems with promising results.
author:
- first_name: Vladimir
full_name: Vladimir Kolmogorov
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: Kolmogorov V. Reweighted Message Passing Revisited. IST Austria; 2013.
apa: Kolmogorov, V. (2013). Reweighted message passing revisited. IST Austria.
chicago: Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST
Austria, 2013.
ieee: V. Kolmogorov, Reweighted message passing revisited. IST Austria, 2013.
ista: Kolmogorov V. 2013. Reweighted message passing revisited, IST Austria,p.
mla: Kolmogorov, Vladimir. Reweighted Message Passing Revisited. IST Austria,
2013.
short: V. Kolmogorov, Reweighted Message Passing Revisited, IST Austria, 2013.
date_created: 2018-12-11T11:56:42Z
date_published: 2013-09-22T00:00:00Z
date_updated: 2019-01-24T13:07:32Z
day: '22'
department:
- _id: VlKo
extern: 0
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1309.5655
month: '09'
oa: 1
publication_status: published
publisher: IST Austria
publist_id: '4671'
quality_controlled: 0
status: public
title: Reweighted message passing revisited
type: report
year: '2013'
...
---
_id: '2276'
abstract:
- lang: eng
text: The problem of minimizing the Potts energy function frequently occurs in computer
vision applications. One way to tackle this NP-hard problem was proposed by Kovtun
[19, 20]. It identifies a part of an optimal solution by running k maxflow computations,
where k is the number of labels. The number of “labeled” pixels can be significant
in some applications, e.g. 50-93% in our tests for stereo. We show how to reduce
the runtime to O (log k) maxflow computations (or one parametric maxflow computation).
Furthermore, the output of our algorithm allows to speed-up the subsequent alpha
expansion for the unlabeled part, or can be used as it is for time-critical applications.
To derive our technique, we generalize the algorithm of Felzenszwalb et al. [7]
for Tree Metrics . We also show a connection to k-submodular functions from combinatorial
optimization, and discuss k-submodular relaxations for general energy functions.
author:
- first_name: Igor
full_name: Gridchyn, Igor
id: 4B60654C-F248-11E8-B48F-1D18A9856A87
last_name: Gridchyn
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Gridchyn I, Kolmogorov V. Potts model, parametric maxflow and k-submodular
functions. In: IEEE; 2013:2320-2327. doi:10.1109/ICCV.2013.288'
apa: 'Gridchyn, I., & Kolmogorov, V. (2013). Potts model, parametric maxflow
and k-submodular functions (pp. 2320–2327). Presented at the ICCV: International
Conference on Computer Vision, Sydney, Australia: IEEE. https://doi.org/10.1109/ICCV.2013.288'
chicago: Gridchyn, Igor, and Vladimir Kolmogorov. “Potts Model, Parametric Maxflow
and k-Submodular Functions,” 2320–27. IEEE, 2013. https://doi.org/10.1109/ICCV.2013.288.
ieee: 'I. Gridchyn and V. Kolmogorov, “Potts model, parametric maxflow and k-submodular
functions,” presented at the ICCV: International Conference on Computer Vision,
Sydney, Australia, 2013, pp. 2320–2327.'
ista: 'Gridchyn I, Kolmogorov V. 2013. Potts model, parametric maxflow and k-submodular
functions. ICCV: International Conference on Computer Vision, 2320–2327.'
mla: Gridchyn, Igor, and Vladimir Kolmogorov. Potts Model, Parametric Maxflow
and k-Submodular Functions. IEEE, 2013, pp. 2320–27, doi:10.1109/ICCV.2013.288.
short: I. Gridchyn, V. Kolmogorov, in:, IEEE, 2013, pp. 2320–2327.
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:43Z
date_published: 2013-12-01T00:00:00Z
date_updated: 2021-01-12T06:56:28Z
day: '01'
department:
- _id: JoCs
- _id: VlKo
doi: 10.1109/ICCV.2013.288
external_id:
arxiv:
- '1310.1771'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1310.1771
month: '12'
oa: 1
oa_version: Preprint
page: 2320 - 2327
publication_status: published
publisher: IEEE
publist_id: '4668'
quality_controlled: '1'
status: public
title: Potts model, parametric maxflow and k-submodular functions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2518'
abstract:
- lang: eng
text: A class of valued constraint satisfaction problems (VCSPs) is characterised
by a valued constraint language, a fixed set of cost functions on a finite domain.
An instance of the problem is specified by a sum of cost functions from the language
with the goal to minimise the sum. We study which classes of finite-valued languages
can be solved exactly by the basic linear programming relaxation (BLP). Thapper
and Živný showed [20] that if BLP solves the language then the language admits
a binary commutative fractional polymorphism. We prove that the converse is also
true. This leads to a necessary and a sufficient condition which can be checked
in polynomial time for a given language. In contrast, the previous necessary and
sufficient condition due to [20] involved infinitely many inequalities. More recently,
Thapper and Živný [21] showed (using, in particular, a technique introduced in
this paper) that core languages that do not satisfy our condition are NP-hard.
Taken together, these results imply that a finite-valued language can either be
solved using Linear Programming or is NP-hard.
alternative_title:
- LNCS
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Kolmogorov V. The power of linear programming for finite-valued CSPs: A constructive
characterization. In: Vol 7965. Springer; 2013:625-636. doi:10.1007/978-3-642-39206-1_53'
apa: 'Kolmogorov, V. (2013). The power of linear programming for finite-valued CSPs:
A constructive characterization (Vol. 7965, pp. 625–636). Presented at the ICALP:
Automata, Languages and Programming, Riga, Latvia: Springer. https://doi.org/10.1007/978-3-642-39206-1_53'
chicago: 'Kolmogorov, Vladimir. “The Power of Linear Programming for Finite-Valued
CSPs: A Constructive Characterization,” 7965:625–36. Springer, 2013. https://doi.org/10.1007/978-3-642-39206-1_53.'
ieee: 'V. Kolmogorov, “The power of linear programming for finite-valued CSPs: A
constructive characterization,” presented at the ICALP: Automata, Languages and
Programming, Riga, Latvia, 2013, vol. 7965, no. 1, pp. 625–636.'
ista: 'Kolmogorov V. 2013. The power of linear programming for finite-valued CSPs:
A constructive characterization. ICALP: Automata, Languages and Programming, LNCS,
vol. 7965, 625–636.'
mla: 'Kolmogorov, Vladimir. The Power of Linear Programming for Finite-Valued
CSPs: A Constructive Characterization. Vol. 7965, no. 1, Springer, 2013, pp.
625–36, doi:10.1007/978-3-642-39206-1_53.'
short: V. Kolmogorov, in:, Springer, 2013, pp. 625–636.
conference:
end_date: 2013-07-12
location: Riga, Latvia
name: 'ICALP: Automata, Languages and Programming'
start_date: 2013-07-08
date_created: 2018-12-11T11:58:08Z
date_published: 2013-07-01T00:00:00Z
date_updated: 2023-02-23T10:35:42Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-642-39206-1_53
external_id:
arxiv:
- '1207.7213'
intvolume: ' 7965'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1207.7213
month: '07'
oa: 1
oa_version: Preprint
page: 625 - 636
publication_status: published
publisher: Springer
publist_id: '4383'
quality_controlled: '1'
related_material:
record:
- id: '2271'
relation: later_version
status: public
scopus_import: 1
status: public
title: 'The power of linear programming for finite-valued CSPs: A constructive characterization'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7965
year: '2013'
...
---
_id: '2828'
abstract:
- lang: eng
text: 'We study the complexity of valued constraint satisfaction problems (VCSPs)
parametrized by a constraint language, a fixed set of cost functions over a finite
domain. An instance of the problem is specified by a sum of cost functions from
the language and the goal is to minimize the sum. Under the unique games conjecture,
the approximability of finite-valued VCSPs is well understood, see Raghavendra
[2008]. However, there is no characterization of finite-valued VCSPs, let alone
general-valued VCSPs, that can be solved exactly in polynomial time, thus giving
insights from a combinatorial optimization perspective. We consider the case of
languages containing all possible unary cost functions. In the case of languages
consisting of only {0, ∞}-valued cost functions (i.e., relations), such languages
have been called conservative and studied by Bulatov [2003, 2011] and recently
by Barto [2011]. Since we study valued languages, we call a language conservative
if it contains all finite-valued unary cost functions. The computational complexity
of conservative valued languages has been studied by Cohen et al. [2006] for languages
over Boolean domains, by Deineko et al. [2008] for {0, 1}-valued languages (a.k.a
Max-CSP), and by Takhanov [2010a] for {0, ∞}-valued languages containing all finite-valued
unary cost functions (a.k.a. Min-Cost-Hom). We prove a Schaefer-like dichotomy
theorem for conservative valued languages: if all cost functions in the language
satisfy a certain condition (specified by a complementary combination of STP and
MJN multimor-phisms), then any instance can be solved in polynomial time (via
a new algorithm developed in this article), otherwise the language is NP-hard.
This is the first complete complexity classification of general-valued constraint
languages over non-Boolean domains. It is a common phenomenon that complexity
classifications of problems over non-Boolean domains are significantly harder
than the Boolean cases. The polynomial-time algorithm we present for the tractable
cases is a generalization of the submodular minimization problem and a result
of Cohen et al. [2008]. Our results generalize previous results by Takhanov [2010a]
and (a subset of results) by Cohen et al. [2006] and Deineko et al. [2008]. Moreover,
our results do not rely on any computer-assisted search as in Deineko et al. [2008],
and provide a powerful tool for proving hardness of finite-valued and general-valued
languages.'
article_number: '10'
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Stanislav
full_name: Živný, Stanislav
last_name: Živný
citation:
ama: Kolmogorov V, Živný S. The complexity of conservative valued CSPs. Journal
of the ACM. 2013;60(2). doi:10.1145/2450142.2450146
apa: Kolmogorov, V., & Živný, S. (2013). The complexity of conservative valued
CSPs. Journal of the ACM. ACM. https://doi.org/10.1145/2450142.2450146
chicago: Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative
Valued CSPs.” Journal of the ACM. ACM, 2013. https://doi.org/10.1145/2450142.2450146.
ieee: V. Kolmogorov and S. Živný, “The complexity of conservative valued CSPs,”
Journal of the ACM, vol. 60, no. 2. ACM, 2013.
ista: Kolmogorov V, Živný S. 2013. The complexity of conservative valued CSPs. Journal
of the ACM. 60(2), 10.
mla: Kolmogorov, Vladimir, and Stanislav Živný. “The Complexity of Conservative
Valued CSPs.” Journal of the ACM, vol. 60, no. 2, 10, ACM, 2013, doi:10.1145/2450142.2450146.
short: V. Kolmogorov, S. Živný, Journal of the ACM 60 (2013).
date_created: 2018-12-11T11:59:48Z
date_published: 2013-04-02T00:00:00Z
date_updated: 2021-01-12T07:00:00Z
day: '02'
department:
- _id: VlKo
doi: 10.1145/2450142.2450146
external_id:
arxiv:
- '1110.2809'
intvolume: ' 60'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1110.2809
month: '04'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '3971'
quality_controlled: '1'
scopus_import: 1
status: public
title: The complexity of conservative valued CSPs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 60
year: '2013'
...
---
_id: '2901'
abstract:
- lang: eng
text: ' We introduce the M-modes problem for graphical models: predicting the M
label configurations of highest probability that are at the same time local maxima
of the probability landscape. M-modes have multiple possible applications: because
they are intrinsically diverse, they provide a principled alternative to non-maximum
suppression techniques for structured prediction, they can act as codebook vectors
for quantizing the configuration space, or they can form component centers for
mixture model approximation. We present two algorithms for solving the M-modes
problem. The first algorithm solves the problem in polynomial time when the underlying
graphical model is a simple chain. The second algorithm solves the problem for
junction chains. In synthetic and real dataset, we demonstrate how M-modes can
improve the performance of prediction. We also use the generated modes as a tool
to understand the topography of the probability distribution of configurations,
for example with relation to the training set size and amount of noise in the
data. '
alternative_title:
- ' JMLR: W&CP'
author:
- first_name: Chao
full_name: Chen, Chao
id: 3E92416E-F248-11E8-B48F-1D18A9856A87
last_name: Chen
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Zhu
full_name: Yan, Zhu
last_name: Yan
- first_name: Dimitris
full_name: Metaxas, Dimitris
last_name: Metaxas
- first_name: Christoph
full_name: Lampert, Christoph
id: 40C20FD2-F248-11E8-B48F-1D18A9856A87
last_name: Lampert
orcid: 0000-0001-8622-7887
citation:
ama: 'Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. Computing the M most probable
modes of a graphical model. In: Vol 31. JMLR; 2013:161-169.'
apa: 'Chen, C., Kolmogorov, V., Yan, Z., Metaxas, D., & Lampert, C. (2013).
Computing the M most probable modes of a graphical model (Vol. 31, pp. 161–169).
Presented at the AISTATS: Conference on Uncertainty in Artificial Intelligence,
Scottsdale, AZ, United States: JMLR.'
chicago: Chen, Chao, Vladimir Kolmogorov, Zhu Yan, Dimitris Metaxas, and Christoph
Lampert. “Computing the M Most Probable Modes of a Graphical Model,” 31:161–69.
JMLR, 2013.
ieee: 'C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, and C. Lampert, “Computing the
M most probable modes of a graphical model,” presented at the AISTATS: Conference
on Uncertainty in Artificial Intelligence, Scottsdale, AZ, United States, 2013,
vol. 31, pp. 161–169.'
ista: 'Chen C, Kolmogorov V, Yan Z, Metaxas D, Lampert C. 2013. Computing the M
most probable modes of a graphical model. AISTATS: Conference on Uncertainty
in Artificial Intelligence, JMLR: W&CP, vol. 31, 161–169.'
mla: Chen, Chao, et al. Computing the M Most Probable Modes of a Graphical Model.
Vol. 31, JMLR, 2013, pp. 161–69.
short: C. Chen, V. Kolmogorov, Z. Yan, D. Metaxas, C. Lampert, in:, JMLR, 2013,
pp. 161–169.
conference:
end_date: 2013-05-01
location: Scottsdale, AZ, United States
name: ' AISTATS: Conference on Uncertainty in Artificial Intelligence'
start_date: 2013-04-29
date_created: 2018-12-11T12:00:14Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T07:00:35Z
day: '01'
department:
- _id: HeEd
- _id: VlKo
- _id: ChLa
intvolume: ' 31'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://jmlr.org/proceedings/papers/v31/chen13a.html
month: '01'
oa: 1
oa_version: None
page: 161 - 169
publication_status: published
publisher: JMLR
publist_id: '3846'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computing the M most probable modes of a graphical model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 31
year: '2013'
...
---
_id: '2272'
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) x1...xn is
the sum of terms over intervals [i,j] where each term is non-zero only if the
substring xi...xj equals a prespecified pattern α. Such CRFs can be naturally
applied to many sequence tagging problems.\r\nWe present efficient algorithms
for the three standard inference tasks in a CRF, namely computing (i) the partition
function, (ii) marginals, and (iii) computing the MAP. Their complexities are
respectively O(nL), O(nLℓmax) and O(nLmin{|D|,log(ℓmax+1)}) where L is the combined
length of input patterns, ℓmax is the maximum length of a pattern, and D is the
input alphabet. This improves on the previous algorithms of (Ye et al., 2009)
whose complexities are respectively O(nL|D|), O(n|Γ|L2ℓ2max) and O(nL|D|), where
|Γ| is the number of input patterns.\r\nIn addition, we give an efficient algorithm
for sampling. Finally, we consider the case of non-positive weights. (Komodakis
& Paragios, 2009) gave an O(nL) algorithm for computing the MAP. We present
a modification that has the same worst-case complexity but can beat it in the
best case. "
alternative_title:
- JMLR
article_processing_charge: No
author:
- first_name: Rustem
full_name: Takhanov, Rustem
id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87
last_name: Takhanov
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Takhanov R, Kolmogorov V. Inference algorithms for pattern-based CRFs on sequence
data. In: ICML’13 Proceedings of the 30th International Conference on International.
Vol 28. ML Research Press; 2013:145-153.'
apa: 'Takhanov, R., & Kolmogorov, V. (2013). Inference algorithms for pattern-based
CRFs on sequence data. In ICML’13 Proceedings of the 30th International Conference
on International (Vol. 28, pp. 145–153). Atlanta, GA, USA: ML Research Press.'
chicago: Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based
CRFs on Sequence Data.” In ICML’13 Proceedings of the 30th International Conference
on International, 28:145–53. ML Research Press, 2013.
ieee: R. Takhanov and V. Kolmogorov, “Inference algorithms for pattern-based CRFs
on sequence data,” in ICML’13 Proceedings of the 30th International Conference
on International, Atlanta, GA, USA, 2013, vol. 28, no. 3, pp. 145–153.
ista: 'Takhanov R, Kolmogorov V. 2013. Inference algorithms for pattern-based CRFs
on sequence data. ICML’13 Proceedings of the 30th International Conference on
International. ICML: International Conference on Machine Learning, JMLR, vol.
28, 145–153.'
mla: Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based
CRFs on Sequence Data.” ICML’13 Proceedings of the 30th International Conference
on International, vol. 28, no. 3, ML Research Press, 2013, pp. 145–53.
short: R. Takhanov, V. Kolmogorov, in:, ICML’13 Proceedings of the 30th International
Conference on International, ML Research Press, 2013, pp. 145–153.
conference:
end_date: 2013-06-21
location: Atlanta, GA, USA
name: 'ICML: International Conference on Machine Learning'
start_date: 2013-06-16
date_created: 2018-12-11T11:56:41Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2023-10-17T09:51:32Z
day: '01'
department:
- _id: VlKo
intvolume: ' 28'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://proceedings.mlr.press/v28/takhanov13.pdf?CFID=105472548&CFTOKEN=5c5859b5d97b4439-27B4AC58-BA92-A964-B598CAACEE6CC515
month: '06'
oa: 1
oa_version: Submitted Version
page: 145 - 153
publication: ICML'13 Proceedings of the 30th International Conference on International
publication_status: published
publisher: ML Research Press
publist_id: '4672'
quality_controlled: '1'
related_material:
record:
- id: '1794'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Inference algorithms for pattern-based CRFs on sequence data
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 28
year: '2013'
...
---
_id: '2274'
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.\r\n\r\nIn this work, we put forward an
alternative concept for PoWs -- so-called proofs of space (PoS), where a service
requestor must dedicate a significant amount of disk space as opposed to computation.
We construct secure PoS schemes in the random oracle model, using graphs with
high "pebbling complexity" and Merkle hash-trees. "
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.
IST Austria; 2013.
apa: Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2013). Proofs
of Space. IST Austria.
chicago: Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof
Z Pietrzak. Proofs of Space. IST Austria, 2013.
ieee: S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, Proofs of
Space. IST Austria, 2013.
ista: Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2013. Proofs of Space,
IST Austria,p.
mla: Dziembowski, Stefan, et al. Proofs of Space. IST Austria, 2013.
short: S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, Proofs of Space,
IST Austria, 2013.
date_created: 2018-12-11T11:56:42Z
date_published: 2013-11-28T00:00:00Z
date_updated: 2024-03-20T08:31:49Z
day: '28'
ddc:
- '530'
department:
- _id: VlKo
- _id: KrPi
file:
- access_level: open_access
checksum: 37b61637b62fc079d9141c59d9f1a94f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:16:11Z
date_updated: 2020-07-14T12:45:36Z
file_id: '5197'
file_name: IST-2016-671-v1+1_796.pdf
file_size: 405870
relation: main_file
file_date_updated: 2020-07-14T12:45:36Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
publication_status: published
publisher: IST Austria
publist_id: '4670'
pubrep_id: '671'
related_material:
record:
- id: '1675'
relation: later_version
status: public
scopus_import: 1
status: public
title: Proofs of Space
type: report
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2930'
abstract:
- lang: eng
text: "In this paper we investigate k-submodular functions. This natural family
of discrete functions includes submodular and bisubmodular functions as the special
cases k = 1 and k = 2 respectively.\r\n\r\nIn particular we generalize the known
Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts
that the minimum of the (bi)submodular function can be found by solving a maximization
problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron,
prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm
to construct the vertices of the polyhedron.\r\n"
acknowledgement: "We would like to thank Andrei Krokhin for encourag- ing our cooperation,
for helpful discussions, and for his critical reading of the manuscript.\r\n"
alternative_title:
- LNCS
author:
- first_name: Anna
full_name: Huber, Anna
last_name: Huber
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Huber A, Kolmogorov V. Towards minimizing k-submodular functions. In: Vol
7422. Springer; 2012:451-462. doi:10.1007/978-3-642-32147-4_40'
apa: 'Huber, A., & Kolmogorov, V. (2012). Towards minimizing k-submodular functions
(Vol. 7422, pp. 451–462). Presented at the ISCO: International Symposium on Combinatorial
Optimization, Athens, Greece: Springer. https://doi.org/10.1007/978-3-642-32147-4_40'
chicago: Huber, Anna, and Vladimir Kolmogorov. “Towards Minimizing K-Submodular
Functions,” 7422:451–62. Springer, 2012. https://doi.org/10.1007/978-3-642-32147-4_40.
ieee: 'A. Huber and V. Kolmogorov, “Towards minimizing k-submodular functions,”
presented at the ISCO: International Symposium on Combinatorial Optimization,
Athens, Greece, 2012, vol. 7422, pp. 451–462.'
ista: 'Huber A, Kolmogorov V. 2012. Towards minimizing k-submodular functions. ISCO:
International Symposium on Combinatorial Optimization, LNCS, vol. 7422, 451–462.'
mla: Huber, Anna, and Vladimir Kolmogorov. Towards Minimizing K-Submodular Functions.
Vol. 7422, Springer, 2012, pp. 451–62, doi:10.1007/978-3-642-32147-4_40.
short: A. Huber, V. Kolmogorov, in:, Springer, 2012, pp. 451–462.
conference:
end_date: 2012-04-21
location: Athens, Greece
name: 'ISCO: International Symposium on Combinatorial Optimization'
start_date: 2012-04-19
date_created: 2018-12-11T12:00:24Z
date_published: 2012-04-01T00:00:00Z
date_updated: 2021-01-12T07:00:46Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/978-3-642-32147-4_40
intvolume: ' 7422'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1309.5469
month: '04'
oa: 1
oa_version: Preprint
page: 451 - 462
publication_status: published
publisher: Springer
publist_id: '3806'
quality_controlled: '1'
scopus_import: 1
status: public
title: Towards minimizing k-submodular functions
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 7422
year: '2012'
...
---
_id: '2928'
abstract:
- lang: eng
text: ' This paper addresses the problem of approximate MAP-MRF inference in
general graphical models. Following [36], we consider a family of linear programming
relaxations of the problem where each relaxation is specified by a set of nested
pairs of factors for which the marginalization constraint needs to be enforced.
We develop a generalization of the TRW-S algorithm [9] for this problem, where
we use a decomposition into junction chains, monotonic w.r.t. some ordering on
the nodes. This generalizes the monotonic chains in [9] in a natural way. We also
show how to deal with nested factors in an efficient way. Experiments show an
improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on
a number of computer vision and natural language processing problems. '
article_processing_charge: No
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Thomas
full_name: Schoenemann, Thomas
last_name: Schoenemann
citation:
ama: Kolmogorov V, Schoenemann T. Generalized sequential tree-reweighted message
passing. arXiv. 2012.
apa: Kolmogorov, V., & Schoenemann, T. (2012). Generalized sequential tree-reweighted
message passing. arXiv. ArXiv.
chicago: Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted
Message Passing.” ArXiv. ArXiv, 2012.
ieee: V. Kolmogorov and T. Schoenemann, “Generalized sequential tree-reweighted
message passing,” arXiv. ArXiv, 2012.
ista: Kolmogorov V, Schoenemann T. 2012. Generalized sequential tree-reweighted
message passing. arXiv, .
mla: Kolmogorov, Vladimir, and Thomas Schoenemann. “Generalized Sequential Tree-Reweighted
Message Passing.” ArXiv, ArXiv, 2012.
short: V. Kolmogorov, T. Schoenemann, ArXiv (2012).
date_created: 2018-12-11T12:00:23Z
date_published: 2012-05-29T00:00:00Z
date_updated: 2021-01-12T07:00:45Z
day: '29'
department:
- _id: VlKo
external_id:
arxiv:
- '1205.6352'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1205.6352
month: '05'
oa: 1
oa_version: Preprint
page: '16'
publication: arXiv
publication_status: published
publisher: ArXiv
publist_id: '3809'
status: public
title: Generalized sequential tree-reweighted message passing
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2012'
...