---
_id: '274'
abstract:
- lang: eng
text: We consider the problem of estimating the partition function Z(β)=∑xexp(−β(H(x))
of a Gibbs distribution with a Hamilton H(⋅), or more precisely the logarithm
of the ratio q=lnZ(0)/Z(β). It has been recently shown how to approximate q with
high probability assuming the existence of an oracle that produces samples from
the Gibbs distribution for a given parameter value in [0,β]. The current best
known approach due to Huber [9] uses O(qlnn⋅[lnq+lnlnn+ε−2]) oracle calls on average
where ε is the desired accuracy of approximation and H(⋅) is assumed to lie in
{0}∪[1,n]. We improve the complexity to O(qlnn⋅ε−2) oracle calls. We also show
that the same complexity can be achieved if exact oracles are replaced with approximate
sampling oracles that are within O(ε2qlnn) variation distance from exact oracles.
Finally, we prove a lower bound of Ω(q⋅ε−2) oracle calls under a natural model
of computation.
alternative_title:
- COLT
author:
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
citation:
ama: 'Kolmogorov V. A faster approximation algorithm for the Gibbs partition function.
In: Unknown; 2017:1-17.'
apa: 'Kolmogorov, V. (2017). A faster approximation algorithm for the Gibbs partition
function (pp. 1–17). Presented at the COLT: Annual Conference on Learning Theory
, Unknown.'
chicago: Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition
Function,” 1–17. Unknown, 2017.
ieee: 'V. Kolmogorov, “A faster approximation algorithm for the Gibbs partition
function,” presented at the COLT: Annual Conference on Learning Theory , 2017,
pp. 1–17.'
ista: 'Kolmogorov V. 2017. A faster approximation algorithm for the Gibbs partition
function. COLT: Annual Conference on Learning Theory , COLT, 1–17.'
mla: Kolmogorov, Vladimir. *A Faster Approximation Algorithm for the Gibbs Partition
Function*. Unknown, 2017, pp. 1–17.
short: V. Kolmogorov, in:, Unknown, 2017, pp. 1–17.
conference:
name: 'COLT: Annual Conference on Learning Theory '
date_created: 2018-12-11T11:45:33Z
date_published: 2017-12-27T00:00:00Z
date_updated: 2019-08-02T12:37:50Z
day: '27'
department:
- _id: VlKo
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1608.04223
month: '12'
oa: 1
oa_version: Submitted Version
page: 1 - 17
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_status: epub_ahead
publisher: Unknown
publist_id: '7628'
quality_controlled: '1'
status: public
title: A faster approximation algorithm for the Gibbs partition function
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '5561'
abstract:
- lang: eng
text: 'Graph matching problems as described in "Active Graph Matching for Automatic
Joint Segmentation and Annotation of C. Elegans." by Kainmueller, Dagmar and Jug,
Florian and Rother, Carsten and Myers, Gene, MICCAI 2014. Problems are in OpenGM2
hdf5 format (see http://hciweb2.iwr.uni-heidelberg.de/opengm/) and a custom text
format used by the feature matching solver described in "Feature Correspondence
via Graph Matching: Models and Global Optimization." by Lorenzo Torresani, Vladimir
Kolmogorov and Carsten Rother, ECCV 2008, code at http://pub.ist.ac.at/~vnk/software/GraphMatching-v1.02.src.zip. '
acknowledgement: We thank Vladimir Kolmogorov and Stephan Saalfeld forinspiring discussions.
author:
- first_name: Dagmar
full_name: Kainmueller, Dagmar
last_name: Kainmueller
- first_name: Florian
full_name: Jug, Florian
last_name: Jug
- first_name: Carsten
full_name: Rother, Carsten
last_name: Rother
- first_name: Gene
full_name: Meyers, Gene
last_name: Meyers
citation:
ama: Kainmueller D, Jug F, Rother C, Meyers G. *Graph Matching Problems for Annotating
C. Elegans*. IST Austria; 2017. doi:10.15479/AT:ISTA:57
apa: Kainmueller, D., Jug, F., Rother, C., & Meyers, G. (2017). *Graph matching
problems for annotating C. Elegans*. IST Austria. https://doi.org/10.15479/AT:ISTA:57
chicago: Kainmueller, Dagmar, Florian Jug, Carsten Rother, and Gene Meyers. *Graph
Matching Problems for Annotating C. Elegans*. IST Austria, 2017. https://doi.org/10.15479/AT:ISTA:57.
ieee: D. Kainmueller, F. Jug, C. Rother, and G. Meyers, *Graph matching problems
for annotating C. Elegans*. IST Austria, 2017.
ista: Kainmueller D, Jug F, Rother C, Meyers G. 2017. Graph matching problems for
annotating C. Elegans, IST Austria,p.
mla: Kainmueller, Dagmar, et al. *Graph Matching Problems for Annotating C. Elegans*.
IST Austria, 2017, doi:10.15479/AT:ISTA:57.
short: D. Kainmueller, F. Jug, C. Rother, G. Meyers, Graph Matching Problems for
Annotating C. Elegans, IST Austria, 2017.
data_reuse_license: cc_0
datarep_id: '57'
date_created: 2018-12-12T12:31:32Z
date_published: 2017-02-13T00:00:00Z
date_updated: 2019-08-02T12:38:58Z
day: '13'
ddc:
- '000'
department:
- _id: VlKo
doi: 10.15479/AT:ISTA:57
file:
- access_level: open_access
content_type: application/zip
creator: system
date_created: 2018-12-12T13:02:54Z
date_updated: 2018-12-12T13:02:54Z
file_id: '5614'
file_name: IST-2017-57-v1+1_wormMatchingProblems.zip
file_size: 327042819
open_access: 1
relation: main_file
file_date_updated: 2018-12-12T13:02:54Z
keyword:
- graph matching
- feature matching
- QAP
- MAP-inference
month: '02'
oa: 1
oa_version: Published Version
open_data_release: '1'
publisher: IST Austria
status: public
title: Graph matching problems for annotating C. Elegans
type: research_data
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_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
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
- 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: 2019-08-02T12:36:56Z
day: '28'
department:
- _id: KrPi
- _id: VlKo
doi: 10.1007/978-3-662-49896-5_13
intvolume: ' 9666'
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
grant_number: '259668'
name: Provable Security for Physical Cryptography
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_status: published
publisher: Springer
publist_id: '6103'
quality_controlled: '1'
status: public
title: On the complexity of scrypt and proofs of space in the parallel random oracle
model
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9666
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).
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*, *75*(1), 75–84. https://doi.org/10.1007/s00012-015-0358-8
chicago: 'Kazda, Alexandr. “CSP for Binary Conservative Relational Structures.”
*Algebra Universalis* 75, no. 1 (2016): 75–84. https://doi.org/10.1007/s00012-015-0358-8.'
ieee: A. Kazda, “CSP for binary conservative relational structures,” *Algebra
Universalis*, vol. 75, no. 1, 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.
date_created: 2018-12-11T11:53:01Z
date_published: 2016-02-01T00:00:00Z
date_updated: 2019-01-24T13:03:40Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/s00012-015-0358-8
intvolume: ' 75'
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'
status: public
title: CSP for binary conservative relational structures
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 75
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.
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*, *76*(1), 17–46. 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* 76, no. 1 (2016): 17–46. 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, 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.
date_created: 2018-12-11T11:54:02Z
date_published: 2016-09-01T00:00:00Z
date_updated: 2019-11-14T08:42:19Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/s00453-015-0017-7
external_id:
arxiv:
- '1210.0508'
intvolume: ' 76'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1210.0508
month: '09'
oa_version: Preprint
page: 17 - 46
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
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
status: public
title: Inference algorithms for pattern-based CRFs on sequence data
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 76
year: '2016'
...