[{"day":"27","month":"12","language":[{"iso":"eng"}],"quality_controlled":"1","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."}],"conference":{"name":"COLT: Annual Conference on Learning Theory "},"oa":1,"year":"2017","type":"conference","date_updated":"2019-08-02T12:37:50Z","status":"public","page":"1 - 17","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Unknown","date_published":"2017-12-27T00:00:00Z","title":"A faster approximation algorithm for the Gibbs partition function","_id":"274","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1608.04223"}],"author":[{"last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"oa_version":"Submitted Version","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"citation":{"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.","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.","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.","ama":"Kolmogorov V. A faster approximation algorithm for the Gibbs partition function. In: Unknown; 2017:1-17.","chicago":"Kolmogorov, Vladimir. “A Faster Approximation Algorithm for the Gibbs Partition Function,” 1–17. Unknown, 2017."},"date_created":"2018-12-11T11:45:33Z","department":[{"_id":"VlKo"}],"alternative_title":["COLT"],"publist_id":"7628","publication_status":"epub_ahead"},{"day":"13","keyword":["graph matching","feature matching","QAP","MAP-inference"],"acknowledgement":"We thank Vladimir Kolmogorov and Stephan Saalfeld forinspiring discussions.","month":"02","open_data_release":"1","abstract":[{"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. ","lang":"eng"}],"datarep_id":"57","year":"2017","oa":1,"data_reuse_license":"cc_0","file_date_updated":"2018-12-12T13:02:54Z","date_updated":"2019-08-02T12:38:58Z","type":"research_data","ddc":["000"],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"IST Austria","date_published":"2017-02-13T00:00:00Z","title":"Graph matching problems for annotating C. Elegans","_id":"5561","author":[{"first_name":"Dagmar","last_name":"Kainmueller","full_name":"Kainmueller, Dagmar"},{"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"}],"oa_version":"Published Version","date_created":"2018-12-12T12:31:32Z","department":[{"_id":"VlKo"}],"citation":{"short":"D. Kainmueller, F. Jug, C. Rother, G. Meyers, Graph Matching Problems for Annotating C. Elegans, IST Austria, 2017.","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","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.","ista":"Kainmueller D, Jug F, Rother C, Meyers G. 2017. Graph matching problems for annotating C. Elegans, IST Austria,p.","ieee":"D. Kainmueller, F. Jug, C. Rother, and G. Meyers, *Graph matching problems for annotating C. Elegans*. IST Austria, 2017.","mla":"Kainmueller, Dagmar, et al. *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"},"file":[{"date_created":"2018-12-12T13:02:54Z","creator":"system","access_level":"open_access","file_name":"IST-2017-57-v1+1_wormMatchingProblems.zip","file_id":"5614","content_type":"application/zip","relation":"main_file","file_size":327042819,"open_access":1,"date_updated":"2018-12-12T13:02:54Z"}],"doi":"10.15479/AT:ISTA:57"},{"month":"04","quality_controlled":"1","type":"conference","oa":1,"year":"2016","date_published":"2016-04-28T00:00:00Z","page":"358 - 387","volume":9666,"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2016/100"}],"_id":"1231","author":[{"first_name":"Joel F","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","last_name":"Alwen","full_name":"Alwen, Joel F"},{"last_name":"Chen","full_name":"Chen, Binyi","first_name":"Binyi"},{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"},{"first_name":"Stefano","full_name":"Tessaro, Stefano","last_name":"Tessaro"}],"project":[{"grant_number":"259668","name":"Provable Security for Physical Cryptography","_id":"258C570E-B435-11E9-9278-68D0E5697425"},{"name":"Discrete Optimization in Computer Vision: Theory and Practice","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160"}],"citation":{"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.","short":"J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2016, pp. 358–387.","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","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.","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.","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."},"date_created":"2018-12-11T11:50:51Z","alternative_title":["LNCS"],"publist_id":"6103","doi":"10.1007/978-3-662-49896-5_13","intvolume":" 9666","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.","day":"28","language":[{"iso":"eng"}],"conference":{"start_date":"2016-05-08","end_date":"2016-05-12","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","location":"Vienna, Austria"},"abstract":[{"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).","lang":"eng"}],"date_updated":"2019-08-02T12:36:56Z","status":"public","publisher":"Springer","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","title":"On the complexity of scrypt and proofs of space in the parallel random oracle model","oa_version":"Submitted Version","department":[{"_id":"KrPi"},{"_id":"VlKo"}],"publication_status":"published"},{"title":"CSP for binary conservative relational structures","volume":75,"publication":"Algebra Universalis","date_published":"2016-02-01T00:00:00Z","publisher":"Springer","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","page":"75 - 84","status":"public","date_updated":"2019-01-24T13:03:40Z","type":"journal_article","year":"2016","oa":1,"abstract":[{"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).","lang":"eng"}],"quality_controlled":"1","month":"02","language":[{"iso":"eng"}],"intvolume":" 75","day":"01","doi":"10.1007/s00012-015-0358-8","issue":"1","publication_status":"published","publist_id":"5554","department":[{"_id":"VlKo"}],"date_created":"2018-12-11T11:53:01Z","citation":{"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.","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","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.","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.","short":"A. Kazda, Algebra Universalis 75 (2016) 75–84.","ama":"Kazda A. CSP for binary conservative relational structures. *Algebra Universalis*. 2016;75(1):75-84. doi:10.1007/s00012-015-0358-8"},"oa_version":"Preprint","author":[{"first_name":"Alexandr","id":"3B32BAA8-F248-11E8-B48F-1D18A9856A87","last_name":"Kazda","full_name":"Kazda, Alexandr"}],"main_file_link":[{"url":"http://arxiv.org/abs/1112.1099","open_access":"1"}],"_id":"1612"},{"intvolume":" 76","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.","day":"01","language":[{"iso":"eng"}],"abstract":[{"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.","lang":"eng"}],"date_updated":"2019-11-14T08:42:19Z","status":"public","publisher":"Springer","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Inference algorithms for pattern-based CRFs on sequence data","oa_version":"Preprint","department":[{"_id":"VlKo"}],"publication_status":"published","related_material":{"record":[{"relation":"earlier_version","id":"2272","status":"public"}]},"month":"09","quality_controlled":"1","type":"journal_article","year":"2016","external_id":{"arxiv":["1210.0508"]},"date_published":"2016-09-01T00:00:00Z","page":"17 - 46","volume":76,"publication":"Algorithmica","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1210.0508"}],"_id":"1794","author":[{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir"},{"full_name":"Takhanov, Rustem","last_name":"Takhanov","id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87","first_name":"Rustem"}],"project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","name":"Discrete Optimization in Computer Vision: Theory and Practice","grant_number":"616160"}],"date_created":"2018-12-11T11:54:02Z","citation":{"ista":"Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 76(1), 17–46.","ieee":"V. Kolmogorov and R. Takhanov, “Inference algorithms for pattern-based CRFs on sequence data,” *Algorithmica*, vol. 76, no. 1, pp. 17–46, 2016.","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","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.","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","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."},"publist_id":"5316","issue":"1","doi":"10.1007/s00453-015-0017-7"}]