[{"ec_funded":1,"pubrep_id":"486","license":"https://creativecommons.org/licenses/by/4.0/","status":"public","_id":"2035","type":"journal_article","date_created":"2018-12-11T11:55:20Z","volume":15,"language":[{"iso":"eng"}],"file":[{"date_updated":"2020-07-14T12:45:26Z","date_created":"2018-12-12T10:08:10Z","content_type":"application/pdf","file_name":"IST-2016-486-v1+1_s10208-014-9223-y.pdf","relation":"main_file","file_size":1317546,"access_level":"open_access","creator":"system","file_id":"4670","checksum":"3566f3a8b0c1bc550e62914a88c584ff"}],"issue":"5","has_accepted_license":"1","month":"10","author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Jablonski, Grzegorz","id":"4483EF78-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3536-9866","first_name":"Grzegorz","last_name":"Jablonski"},{"last_name":"Mrozek","first_name":"Marian","full_name":"Mrozek, Marian"}],"oa_version":"Published Version","project":[{"_id":"255D761E-B435-11E9-9278-68D0E5697425","grant_number":"318493","name":"Topological Complex Systems","call_identifier":"FP7"}],"quality_controlled":"1","publication":"Foundations of Computational Mathematics","publist_id":"5022","intvolume":"        15","scopus_import":1,"doi":"10.1007/s10208-014-9223-y","day":"01","page":"1213 - 1244","year":"2015","acknowledgement":"This research is partially supported by the Toposys project FP7-ICT-318493-STREP, by ESF under the ACAT Research Network Programme, by the Russian Government under mega project 11.G34.31.0053, and by the Polish National Science Center under Grant No. N201 419639.","oa":1,"title":"The persistent homology of a self-map","date_published":"2015-10-01T00:00:00Z","publisher":"Springer","file_date_updated":"2020-07-14T12:45:26Z","ddc":["000"],"publication_status":"published","abstract":[{"lang":"eng","text":"Considering a continuous self-map and the induced endomorphism on homology, we study the eigenvalues and eigenspaces of the latter. Taking a filtration of representations, we define the persistence of the eigenspaces, effectively introducing a hierarchical organization of the map. The algorithm that computes this information for a finite sample is proved to be stable, and to give the correct answer for a sufficiently dense sample. Results computed with an implementation of the algorithm provide evidence of its practical utility.\r\n"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"citation":{"mla":"Edelsbrunner, Herbert, et al. “The Persistent Homology of a Self-Map.” <i>Foundations of Computational Mathematics</i>, vol. 15, no. 5, Springer, 2015, pp. 1213–44, doi:<a href=\"https://doi.org/10.1007/s10208-014-9223-y\">10.1007/s10208-014-9223-y</a>.","short":"H. Edelsbrunner, G. Jablonski, M. Mrozek, Foundations of Computational Mathematics 15 (2015) 1213–1244.","ieee":"H. Edelsbrunner, G. Jablonski, and M. Mrozek, “The persistent homology of a self-map,” <i>Foundations of Computational Mathematics</i>, vol. 15, no. 5. Springer, pp. 1213–1244, 2015.","chicago":"Edelsbrunner, Herbert, Grzegorz Jablonski, and Marian Mrozek. “The Persistent Homology of a Self-Map.” <i>Foundations of Computational Mathematics</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s10208-014-9223-y\">https://doi.org/10.1007/s10208-014-9223-y</a>.","ista":"Edelsbrunner H, Jablonski G, Mrozek M. 2015. The persistent homology of a self-map. Foundations of Computational Mathematics. 15(5), 1213–1244.","ama":"Edelsbrunner H, Jablonski G, Mrozek M. The persistent homology of a self-map. <i>Foundations of Computational Mathematics</i>. 2015;15(5):1213-1244. doi:<a href=\"https://doi.org/10.1007/s10208-014-9223-y\">10.1007/s10208-014-9223-y</a>","apa":"Edelsbrunner, H., Jablonski, G., &#38; Mrozek, M. (2015). The persistent homology of a self-map. <i>Foundations of Computational Mathematics</i>. Springer. <a href=\"https://doi.org/10.1007/s10208-014-9223-y\">https://doi.org/10.1007/s10208-014-9223-y</a>"},"department":[{"_id":"HeEd"}],"date_updated":"2021-01-12T06:54:53Z"},{"date_published":"2015-02-01T00:00:00Z","language":[{"iso":"eng"}],"publisher":"Springer","title":"Collective excitations of Bose gases in the mean-field regime","volume":215,"abstract":[{"lang":"eng","text":"We study the spectrum of a large system of N identical bosons interacting via a two-body potential with strength 1/N. In this mean-field regime, Bogoliubov's theory predicts that the spectrum of the N-particle Hamiltonian can be approximated by that of an effective quadratic Hamiltonian acting on Fock space, which describes the fluctuations around a condensed state. Recently, Bogoliubov's theory has been justified rigorously in the case that the low-energy eigenvectors of the N-particle Hamiltonian display complete condensation in the unique minimizer of the corresponding Hartree functional. In this paper, we shall justify Bogoliubov's theory for the high-energy part of the spectrum of the N-particle Hamiltonian corresponding to (non-linear) excited states of the Hartree functional. Moreover, we shall extend the existing results on the excitation spectrum to the case of non-uniqueness and/or degeneracy of the Hartree minimizer. In particular, the latter covers the case of rotating Bose gases, when the rotation speed is large enough to break the symmetry and to produce multiple quantized vortices in the Hartree minimizer. "}],"month":"02","publication_status":"published","issue":"2","author":[{"full_name":"Nam, Phan","id":"404092F4-F248-11E8-B48F-1D18A9856A87","last_name":"Nam","first_name":"Phan"},{"orcid":"0000-0002-6781-0521","first_name":"Robert","last_name":"Seiringer","full_name":"Seiringer, Robert","id":"4AFD0470-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T06:55:13Z","department":[{"_id":"RoSe"}],"quality_controlled":"1","oa_version":"Preprint","citation":{"mla":"Nam, Phan, and Robert Seiringer. “Collective Excitations of Bose Gases in the Mean-Field Regime.” <i>Archive for Rational Mechanics and Analysis</i>, vol. 215, no. 2, Springer, 2015, pp. 381–417, doi:<a href=\"https://doi.org/10.1007/s00205-014-0781-6\">10.1007/s00205-014-0781-6</a>.","short":"P. Nam, R. Seiringer, Archive for Rational Mechanics and Analysis 215 (2015) 381–417.","apa":"Nam, P., &#38; Seiringer, R. (2015). Collective excitations of Bose gases in the mean-field regime. <i>Archive for Rational Mechanics and Analysis</i>. Springer. <a href=\"https://doi.org/10.1007/s00205-014-0781-6\">https://doi.org/10.1007/s00205-014-0781-6</a>","chicago":"Nam, Phan, and Robert Seiringer. “Collective Excitations of Bose Gases in the Mean-Field Regime.” <i>Archive for Rational Mechanics and Analysis</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s00205-014-0781-6\">https://doi.org/10.1007/s00205-014-0781-6</a>.","ista":"Nam P, Seiringer R. 2015. Collective excitations of Bose gases in the mean-field regime. Archive for Rational Mechanics and Analysis. 215(2), 381–417.","ama":"Nam P, Seiringer R. Collective excitations of Bose gases in the mean-field regime. <i>Archive for Rational Mechanics and Analysis</i>. 2015;215(2):381-417. doi:<a href=\"https://doi.org/10.1007/s00205-014-0781-6\">10.1007/s00205-014-0781-6</a>","ieee":"P. Nam and R. Seiringer, “Collective excitations of Bose gases in the mean-field regime,” <i>Archive for Rational Mechanics and Analysis</i>, vol. 215, no. 2. Springer, pp. 381–417, 2015."},"intvolume":"       215","publist_id":"4951","publication":"Archive for Rational Mechanics and Analysis","scopus_import":1,"status":"public","day":"01","year":"2015","doi":"10.1007/s00205-014-0781-6","main_file_link":[{"url":"http://arxiv.org/abs/1402.1153","open_access":"1"}],"page":"381 - 417","oa":1,"date_created":"2018-12-11T11:55:37Z","type":"journal_article","_id":"2085"},{"publication":"Communications in Mathematical Physics","publist_id":"4818","intvolume":"       333","scopus_import":1,"day":"01","status":"public","year":"2015","main_file_link":[{"url":"http://arxiv.org/abs/1309.5106","open_access":"1"}],"doi":"10.1007/s00220-014-2119-5","page":"1365 - 1416","_id":"2166","type":"journal_article","date_created":"2018-12-11T11:56:05Z","oa":1,"volume":333,"title":"The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case","date_published":"2015-02-01T00:00:00Z","publisher":"Springer","language":[{"iso":"eng"}],"issue":"3","month":"02","publication_status":"published","abstract":[{"lang":"eng","text":"We consider the spectral statistics of large random band matrices on mesoscopic energy scales. We show that the correlation function of the local eigenvalue density exhibits a universal power law behaviour that differs from the Wigner-Dyson- Mehta statistics. This law had been predicted in the physics literature by Altshuler and Shklovskii in (Zh Eksp Teor Fiz (Sov Phys JETP) 91(64):220(127), 1986); it describes the correlations of the eigenvalue density in general metallic sampleswith weak disorder. Our result rigorously establishes the Altshuler-Shklovskii formulas for band matrices. In two dimensions, where the leading term vanishes owing to an algebraic cancellation, we identify the first non-vanishing term and show that it differs substantially from the prediction of Kravtsov and Lerner in (Phys Rev Lett 74:2563-2566, 1995). The proof is given in the current paper and its companion (Ann. H. Poincaré. arXiv:1309.5107, 2014). "}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","full_name":"Erdös, László","last_name":"Erdös","first_name":"László","orcid":"0000-0001-5366-9603"},{"last_name":"Knowles","first_name":"Antti","full_name":"Knowles, Antti"}],"oa_version":"Preprint","citation":{"ama":"Erdös L, Knowles A. The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case. <i>Communications in Mathematical Physics</i>. 2015;333(3):1365-1416. doi:<a href=\"https://doi.org/10.1007/s00220-014-2119-5\">10.1007/s00220-014-2119-5</a>","ista":"Erdös L, Knowles A. 2015. The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case. Communications in Mathematical Physics. 333(3), 1365–1416.","chicago":"Erdös, László, and Antti Knowles. “The Altshuler-Shklovskii Formulas for Random Band Matrices I: The Unimodular Case.” <i>Communications in Mathematical Physics</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s00220-014-2119-5\">https://doi.org/10.1007/s00220-014-2119-5</a>.","apa":"Erdös, L., &#38; Knowles, A. (2015). The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case. <i>Communications in Mathematical Physics</i>. Springer. <a href=\"https://doi.org/10.1007/s00220-014-2119-5\">https://doi.org/10.1007/s00220-014-2119-5</a>","ieee":"L. Erdös and A. Knowles, “The Altshuler-Shklovskii formulas for random band matrices I: the unimodular case,” <i>Communications in Mathematical Physics</i>, vol. 333, no. 3. Springer, pp. 1365–1416, 2015.","mla":"Erdös, László, and Antti Knowles. “The Altshuler-Shklovskii Formulas for Random Band Matrices I: The Unimodular Case.” <i>Communications in Mathematical Physics</i>, vol. 333, no. 3, Springer, 2015, pp. 1365–416, doi:<a href=\"https://doi.org/10.1007/s00220-014-2119-5\">10.1007/s00220-014-2119-5</a>.","short":"L. Erdös, A. Knowles, Communications in Mathematical Physics 333 (2015) 1365–1416."},"department":[{"_id":"LaEr"}],"quality_controlled":"1","date_updated":"2021-01-12T06:55:43Z"},{"volume":44,"language":[{"iso":"eng"}],"issue":"1","month":"02","author":[{"full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","first_name":"Vladimir"},{"first_name":"Johan","last_name":"Thapper","full_name":"Thapper, Johan"},{"full_name":"Živný, Stanislav","first_name":"Stanislav","last_name":"Živný"}],"oa_version":"Preprint","quality_controlled":"1","main_file_link":[{"url":"http://arxiv.org/abs/1311.4219","open_access":"1"}],"status":"public","_id":"2271","type":"journal_article","date_created":"2018-12-11T11:56:41Z","title":"The power of linear programming for general-valued CSPs","date_published":"2015-02-01T00:00:00Z","publisher":"SIAM","abstract":[{"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. ","lang":"eng"}],"publication_status":"published","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1311.4219"]},"citation":{"mla":"Kolmogorov, Vladimir, et al. “The Power of Linear Programming for General-Valued CSPs.” <i>SIAM Journal on Computing</i>, vol. 44, no. 1, SIAM, 2015, pp. 1–36, doi:<a href=\"https://doi.org/10.1137/130945648\">10.1137/130945648</a>.","short":"V. Kolmogorov, J. Thapper, S. Živný, SIAM Journal on Computing 44 (2015) 1–36.","apa":"Kolmogorov, V., Thapper, J., &#38; Živný, S. (2015). The power of linear programming for general-valued CSPs. <i>SIAM Journal on Computing</i>. SIAM. <a href=\"https://doi.org/10.1137/130945648\">https://doi.org/10.1137/130945648</a>","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.","chicago":"Kolmogorov, Vladimir, Johan Thapper, and Stanislav Živný. “The Power of Linear Programming for General-Valued CSPs.” <i>SIAM Journal on Computing</i>. SIAM, 2015. <a href=\"https://doi.org/10.1137/130945648\">https://doi.org/10.1137/130945648</a>.","ama":"Kolmogorov V, Thapper J, Živný S. The power of linear programming for general-valued CSPs. <i>SIAM Journal on Computing</i>. 2015;44(1):1-36. doi:<a href=\"https://doi.org/10.1137/130945648\">10.1137/130945648</a>","ieee":"V. Kolmogorov, J. Thapper, and S. Živný, “The power of linear programming for general-valued CSPs,” <i>SIAM Journal on Computing</i>, vol. 44, no. 1. SIAM, pp. 1–36, 2015."},"date_updated":"2023-02-23T10:46:30Z","department":[{"_id":"VlKo"}],"publication":"SIAM Journal on Computing","intvolume":"        44","publist_id":"4673","arxiv":1,"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"2518"}]},"scopus_import":1,"page":"1 - 36","day":"01","year":"2015","doi":"10.1137/130945648","oa":1},{"status":"public","day":"01","year":"2015","doi":"10.1109/tit.2015.2453315","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1304.5220"}],"page":"4838-4851","oa":1,"date_created":"2019-07-31T06:50:34Z","type":"journal_article","_id":"6736","arxiv":1,"intvolume":"        61","publication":"IEEE Transactions on Information Theory","author":[{"full_name":"Mondelli, Marco","id":"27EB676C-8706-11E9-9510-7717E6697425","orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli"},{"first_name":"Hamed","last_name":"Hassani","full_name":"Hassani, Hamed"},{"first_name":"Rudiger","last_name":"Urbanke","full_name":"Urbanke, Rudiger"}],"external_id":{"arxiv":["1304.5220"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","quality_controlled":"1","date_updated":"2021-01-12T08:08:45Z","oa_version":"Preprint","citation":{"apa":"Mondelli, M., Hassani, H., &#38; Urbanke, R. (2015). Scaling exponent of list decoders with applications to polar codes. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/tit.2015.2453315\">https://doi.org/10.1109/tit.2015.2453315</a>","ama":"Mondelli M, Hassani H, Urbanke R. Scaling exponent of list decoders with applications to polar codes. <i>IEEE Transactions on Information Theory</i>. 2015;61(9):4838-4851. doi:<a href=\"https://doi.org/10.1109/tit.2015.2453315\">10.1109/tit.2015.2453315</a>","chicago":"Mondelli, Marco, Hamed Hassani, and Rudiger Urbanke. “Scaling Exponent of List Decoders with Applications to Polar Codes.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2015. <a href=\"https://doi.org/10.1109/tit.2015.2453315\">https://doi.org/10.1109/tit.2015.2453315</a>.","ista":"Mondelli M, Hassani H, Urbanke R. 2015. Scaling exponent of list decoders with applications to polar codes. IEEE Transactions on Information Theory. 61(9), 4838–4851.","ieee":"M. Mondelli, H. Hassani, and R. Urbanke, “Scaling exponent of list decoders with applications to polar codes,” <i>IEEE Transactions on Information Theory</i>, vol. 61, no. 9. IEEE, pp. 4838–4851, 2015.","short":"M. Mondelli, H. Hassani, R. Urbanke, IEEE Transactions on Information Theory 61 (2015) 4838–4851.","mla":"Mondelli, Marco, et al. “Scaling Exponent of List Decoders with Applications to Polar Codes.” <i>IEEE Transactions on Information Theory</i>, vol. 61, no. 9, IEEE, 2015, pp. 4838–51, doi:<a href=\"https://doi.org/10.1109/tit.2015.2453315\">10.1109/tit.2015.2453315</a>."},"publisher":"IEEE","language":[{"iso":"eng"}],"date_published":"2015-09-01T00:00:00Z","title":"Scaling exponent of list decoders with applications to polar codes","volume":61,"month":"09","publication_status":"published","abstract":[{"lang":"eng","text":"Motivated by the significant performance gains which polar codes experience under successive cancellation list decoding, their scaling exponent is studied as a function of the list size. In particular, the error probability is fixed, and the tradeoff between the block length and back-off from capacity is analyzed. A lower bound is provided on the error probability under MAP decoding with list size L for any binary-input memoryless output-symmetric channel and for any class of linear codes such that their minimum distance is unbounded as the block length grows large. Then, it is shown that under MAP decoding, although the introduction of a list can significantly improve the involved constants, the scaling exponent itself, i.e., the speed at which capacity is approached, stays unaffected for any finite list size. In particular, this result applies to polar codes, since their minimum distance tends to infinity as the block length increases. A similar result is proved for genie-aided successive cancellation decoding when transmission takes place over the binary erasure channel, namely, the scaling exponent remains constant for any fixed number of helps from the genie. Note that since genie-aided successive cancellation decoding might be strictly worse than successive cancellation list decoding, the problem of establishing the scaling exponent of the latter remains open."}],"issue":"9"},{"date_updated":"2021-01-12T08:08:46Z","quality_controlled":"1","extern":"1","citation":{"apa":"Mondelli, M., Hassani, H., Sason, I., &#38; Urbanke, R. (2015). Achieving Marton’s region for broadcast channels using polar codes. <i>IEEE Transactions on Information Theory</i>. IEEE. <a href=\"https://doi.org/10.1109/tit.2014.2368555\">https://doi.org/10.1109/tit.2014.2368555</a>","ista":"Mondelli M, Hassani H, Sason I, Urbanke R. 2015. Achieving Marton’s region for broadcast channels using polar codes. IEEE Transactions on Information Theory. 61(2), 783–800.","ama":"Mondelli M, Hassani H, Sason I, Urbanke R. Achieving Marton’s region for broadcast channels using polar codes. <i>IEEE Transactions on Information Theory</i>. 2015;61(2):783-800. doi:<a href=\"https://doi.org/10.1109/tit.2014.2368555\">10.1109/tit.2014.2368555</a>","chicago":"Mondelli, Marco, Hamed Hassani, Igal Sason, and Rudiger Urbanke. “Achieving Marton’s Region for Broadcast Channels Using Polar Codes.” <i>IEEE Transactions on Information Theory</i>. IEEE, 2015. <a href=\"https://doi.org/10.1109/tit.2014.2368555\">https://doi.org/10.1109/tit.2014.2368555</a>.","ieee":"M. Mondelli, H. Hassani, I. Sason, and R. Urbanke, “Achieving Marton’s region for broadcast channels using polar codes,” <i>IEEE Transactions on Information Theory</i>, vol. 61, no. 2. IEEE, pp. 783–800, 2015.","mla":"Mondelli, Marco, et al. “Achieving Marton’s Region for Broadcast Channels Using Polar Codes.” <i>IEEE Transactions on Information Theory</i>, vol. 61, no. 2, IEEE, 2015, pp. 783–800, doi:<a href=\"https://doi.org/10.1109/tit.2014.2368555\">10.1109/tit.2014.2368555</a>.","short":"M. Mondelli, H. Hassani, I. Sason, R. Urbanke, IEEE Transactions on Information Theory 61 (2015) 783–800."},"oa_version":"Preprint","author":[{"last_name":"Mondelli","first_name":"Marco","orcid":"0000-0002-3242-7020","id":"27EB676C-8706-11E9-9510-7717E6697425","full_name":"Mondelli, Marco"},{"full_name":"Hassani, Hamed","last_name":"Hassani","first_name":"Hamed"},{"first_name":"Igal","last_name":"Sason","full_name":"Sason, Igal"},{"first_name":"Rudiger","last_name":"Urbanke","full_name":"Urbanke, Rudiger"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1401.6060"]},"abstract":[{"lang":"eng","text":"This paper presents polar coding schemes for the two-user discrete memoryless broadcast channel (DM-BC) which achieve Marton's region with both common and private messages. This is the best achievable rate region known to date, and it is tight for all classes of two-user DM-BCs whose capacity regions are known. To accomplish this task, we first construct polar codes for both the superposition as well as binning strategy. By combining these two schemes, we obtain Marton's region with private messages only. Finally, we show how to handle the case of common information. The proposed coding schemes possess the usual advantages of polar codes, i.e., they have low encoding and decoding complexity and a superpolynomial decay rate of the error probability. We follow the lead of Goela, Abbe, and Gastpar, who recently introduced polar codes emulating the superposition and binning schemes. To align the polar indices, for both schemes, their solution involves some degradedness constraints that are assumed to hold between the auxiliary random variables and channel outputs. To remove these constraints, we consider the transmission of k blocks and employ a chaining construction that guarantees the proper alignment of the polarized indices. The techniques described in this paper are quite general, and they can be adopted to many other multiterminal scenarios whenever there polar indices need to be aligned."}],"month":"02","publication_status":"published","issue":"2","date_published":"2015-02-01T00:00:00Z","language":[{"iso":"eng"}],"publisher":"IEEE","title":"Achieving Marton’s region for broadcast channels using polar codes","volume":61,"date_created":"2019-07-31T07:03:38Z","oa":1,"_id":"6737","type":"journal_article","year":"2015","status":"public","day":"01","doi":"10.1109/tit.2014.2368555","page":"783-800","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1401.6060"}],"intvolume":"        61","arxiv":1,"publication":"IEEE Transactions on Information Theory"},{"author":[{"first_name":"Anna W.","last_name":"Santure","full_name":"Santure, Anna W."},{"first_name":"Jocelyn","last_name":"Poissant","full_name":"Poissant, Jocelyn"},{"first_name":"Isabelle","last_name":"De Cauwer","full_name":"De Cauwer, Isabelle"},{"full_name":"van Oers, Kees","first_name":"Kees","last_name":"van Oers"},{"orcid":"0000-0001-8982-8813","first_name":"Matthew Richard","last_name":"Robinson","full_name":"Robinson, Matthew Richard","id":"E5D42276-F5DA-11E9-8E24-6303E6697425"},{"last_name":"Quinn","first_name":"John L.","full_name":"Quinn, John L."},{"first_name":"Martien A. M.","last_name":"Groenen","full_name":"Groenen, Martien A. M."},{"first_name":"Marcel E.","last_name":"Visser","full_name":"Visser, Marcel E."},{"last_name":"Sheldon","first_name":"Ben C.","full_name":"Sheldon, Ben C."},{"last_name":"Slate","first_name":"Jon","full_name":"Slate, Jon"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2021-01-12T08:15:12Z","extern":"1","quality_controlled":"1","citation":{"ama":"Santure AW, Poissant J, De Cauwer I, et al. Replicated analysis of the genetic architecture of quantitative traits in two wild great tit populations. <i>Molecular Ecology</i>. 2015;24:6148-6162. doi:<a href=\"https://doi.org/10.1111/mec.13452\">10.1111/mec.13452</a>","ista":"Santure AW, Poissant J, De Cauwer I, van Oers K, Robinson MR, Quinn JL, Groenen MAM, Visser ME, Sheldon BC, Slate J. 2015. Replicated analysis of the genetic architecture of quantitative traits in two wild great tit populations. Molecular Ecology. 24, 6148–6162.","chicago":"Santure, Anna W., Jocelyn Poissant, Isabelle De Cauwer, Kees van Oers, Matthew Richard Robinson, John L. Quinn, Martien A. M. Groenen, Marcel E. Visser, Ben C. Sheldon, and Jon Slate. “Replicated Analysis of the Genetic Architecture of Quantitative Traits in Two Wild Great Tit Populations.” <i>Molecular Ecology</i>. Wiley, 2015. <a href=\"https://doi.org/10.1111/mec.13452\">https://doi.org/10.1111/mec.13452</a>.","apa":"Santure, A. W., Poissant, J., De Cauwer, I., van Oers, K., Robinson, M. R., Quinn, J. L., … Slate, J. (2015). Replicated analysis of the genetic architecture of quantitative traits in two wild great tit populations. <i>Molecular Ecology</i>. Wiley. <a href=\"https://doi.org/10.1111/mec.13452\">https://doi.org/10.1111/mec.13452</a>","ieee":"A. W. Santure <i>et al.</i>, “Replicated analysis of the genetic architecture of quantitative traits in two wild great tit populations,” <i>Molecular Ecology</i>, vol. 24. Wiley, pp. 6148–6162, 2015.","short":"A.W. Santure, J. Poissant, I. De Cauwer, K. van Oers, M.R. Robinson, J.L. Quinn, M.A.M. Groenen, M.E. Visser, B.C. Sheldon, J. Slate, Molecular Ecology 24 (2015) 6148–6162.","mla":"Santure, Anna W., et al. “Replicated Analysis of the Genetic Architecture of Quantitative Traits in Two Wild Great Tit Populations.” <i>Molecular Ecology</i>, vol. 24, Wiley, 2015, pp. 6148–62, doi:<a href=\"https://doi.org/10.1111/mec.13452\">10.1111/mec.13452</a>."},"oa_version":"Published Version","publisher":"Wiley","language":[{"iso":"eng"}],"date_published":"2015-12-10T00:00:00Z","article_processing_charge":"No","title":"Replicated analysis of the genetic architecture of quantitative traits in two wild great tit populations","volume":24,"abstract":[{"lang":"eng","text":"Currently, there is much debate on the genetic architecture of quantitative traits in wild populations. Is trait variation influenced by many genes of small effect or by a few genes of major effect? Where is additive genetic variation located in the genome? Do the same loci cause similar phenotypic variation in different populations? Great tits (Parus major) have been studied extensively in long‐term studies across Europe and consequently are considered an ecological ‘model organism’. Recently, genomic resources have been developed for the great tit, including a custom SNP chip and genetic linkage map. In this study, we used a suite of approaches to investigate the genetic architecture of eight quantitative traits in two long‐term study populations of great tits—one in the Netherlands and the other in the United Kingdom. Overall, we found little evidence for the presence of genes of large effects in either population. Instead, traits appeared to be influenced by many genes of small effect, with conservative estimates of the number of contributing loci ranging from 31 to 310. Despite concordance between population‐specific heritabilities, we found no evidence for the presence of loci having similar effects in both populations. While population‐specific genetic architectures are possible, an undetected shared architecture cannot be rejected because of limited power to map loci of small and moderate effects. This study is one of few examples of genetic architecture analysis in replicated wild populations and highlights some of the challenges and limitations researchers will face when attempting similar molecular quantitative genetic studies in free‐living populations."}],"month":"12","publication_status":"published","main_file_link":[{"url":"https://doi.org/10.1111/mec.13452","open_access":"1"}],"page":"6148-6162","publication_identifier":{"issn":["0962-1083"]},"day":"10","doi":"10.1111/mec.13452","year":"2015","status":"public","oa":1,"date_created":"2020-04-30T10:51:01Z","type":"journal_article","_id":"7739","article_type":"original","intvolume":"        24","publication":"Molecular Ecology"},{"oa":1,"year":"2015","day":"07","doi":"10.1098/rspb.2015.0689","intvolume":"       282","publication":"Proceedings of the Royal Society B: Biological Sciences","extern":"1","date_updated":"2021-01-12T08:15:12Z","citation":{"short":"M.J. Adams, M.R. Robinson, M.-E. Mannarelli, B.J. Hatchwell, Proceedings of the Royal Society B: Biological Sciences 282 (2015).","mla":"Adams, Mark James, et al. “Social Genetic and Social Environment Effects on Parental and Helper Care in a Cooperatively Breeding Bird.” <i>Proceedings of the Royal Society B: Biological Sciences</i>, vol. 282, no. 1810, 20150689, The Royal Society, 2015, doi:<a href=\"https://doi.org/10.1098/rspb.2015.0689\">10.1098/rspb.2015.0689</a>.","ieee":"M. J. Adams, M. R. Robinson, M.-E. Mannarelli, and B. J. Hatchwell, “Social genetic and social environment effects on parental and helper care in a cooperatively breeding bird,” <i>Proceedings of the Royal Society B: Biological Sciences</i>, vol. 282, no. 1810. The Royal Society, 2015.","apa":"Adams, M. J., Robinson, M. R., Mannarelli, M.-E., &#38; Hatchwell, B. J. (2015). Social genetic and social environment effects on parental and helper care in a cooperatively breeding bird. <i>Proceedings of the Royal Society B: Biological Sciences</i>. The Royal Society. <a href=\"https://doi.org/10.1098/rspb.2015.0689\">https://doi.org/10.1098/rspb.2015.0689</a>","ista":"Adams MJ, Robinson MR, Mannarelli M-E, Hatchwell BJ. 2015. Social genetic and social environment effects on parental and helper care in a cooperatively breeding bird. Proceedings of the Royal Society B: Biological Sciences. 282(1810), 20150689.","ama":"Adams MJ, Robinson MR, Mannarelli M-E, Hatchwell BJ. Social genetic and social environment effects on parental and helper care in a cooperatively breeding bird. <i>Proceedings of the Royal Society B: Biological Sciences</i>. 2015;282(1810). doi:<a href=\"https://doi.org/10.1098/rspb.2015.0689\">10.1098/rspb.2015.0689</a>","chicago":"Adams, Mark James, Matthew Richard Robinson, Maria-Elena Mannarelli, and Ben J. Hatchwell. “Social Genetic and Social Environment Effects on Parental and Helper Care in a Cooperatively Breeding Bird.” <i>Proceedings of the Royal Society B: Biological Sciences</i>. The Royal Society, 2015. <a href=\"https://doi.org/10.1098/rspb.2015.0689\">https://doi.org/10.1098/rspb.2015.0689</a>."},"external_id":{"pmid":["26063846"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","abstract":[{"text":"Phenotypes expressed in a social context are not only a function of the individual, but can also be shaped by the phenotypes of social partners. These social effects may play a major role in the evolution of cooperative breeding if social partners differ in the quality of care they provide and if individual carers adjust their effort in relation to that of other carers. When applying social effects models to wild study systems, it is also important to explore sources of individual plasticity that could masquerade as social effects. We studied offspring provisioning rates of parents and helpers in a wild population of long-tailed tits Aegithalos caudatus using a quantitative genetic framework to identify these social effects and partition them into genetic, permanent environment and current environment components. Controlling for other effects, individuals were consistent in their provisioning effort at a given nest, but adjusted their effort based on who was in their social group, indicating the presence of social effects. However, these social effects differed between years and social contexts, indicating a current environment effect, rather than indicating a genetic or permanent environment effect. While this study reveals the importance of examining environmental and genetic sources of social effects, the framework we present is entirely general, enabling a greater understanding of potentially important social effects within any ecological population.","lang":"eng"}],"pmid":1,"date_published":"2015-07-07T00:00:00Z","publisher":"The Royal Society","title":"Social genetic and social environment effects on parental and helper care in a cooperatively breeding bird","date_created":"2020-04-30T10:58:07Z","article_type":"original","type":"journal_article","_id":"7741","status":"public","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1098/rspb.2015.0689"}],"publication_identifier":{"issn":["0962-8452","1471-2954"]},"quality_controlled":"1","oa_version":"Published Version","author":[{"full_name":"Adams, Mark James","last_name":"Adams","first_name":"Mark James"},{"id":"E5D42276-F5DA-11E9-8E24-6303E6697425","full_name":"Robinson, Matthew Richard","first_name":"Matthew Richard","last_name":"Robinson","orcid":"0000-0001-8982-8813"},{"first_name":"Maria-Elena","last_name":"Mannarelli","full_name":"Mannarelli, Maria-Elena"},{"full_name":"Hatchwell, Ben J.","last_name":"Hatchwell","first_name":"Ben J."}],"month":"07","article_number":"20150689","issue":"1810","language":[{"iso":"eng"}],"volume":282,"article_processing_charge":"No"},{"day":"01","doi":"10.5802/jep.18","year":"2015","page":"65 - 115","oa":1,"publication":"Journal de l'Ecole Polytechnique - Mathematiques","publist_id":"7344","intvolume":"         2","scopus_import":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"short":"CC BY-ND (4.0)","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode","image":"/image/cc_by_nd.png"},"citation":{"mla":"Lewin, Mathieu, et al. “Derivation of Nonlinear Gibbs Measures from Many-Body Quantum Mechanics.” <i>Journal de l’Ecole Polytechnique - Mathematiques</i>, vol. 2, Ecole Polytechnique, 2015, pp. 65–115, doi:<a href=\"https://doi.org/10.5802/jep.18\">10.5802/jep.18</a>.","short":"M. Lewin, P. Nam, N. Rougerie, Journal de l’Ecole Polytechnique - Mathematiques 2 (2015) 65–115.","apa":"Lewin, M., Nam, P., &#38; Rougerie, N. (2015). Derivation of nonlinear gibbs measures from many-body quantum mechanics. <i>Journal de l’Ecole Polytechnique - Mathematiques</i>. Ecole Polytechnique. <a href=\"https://doi.org/10.5802/jep.18\">https://doi.org/10.5802/jep.18</a>","chicago":"Lewin, Mathieu, Phan Nam, and Nicolas Rougerie. “Derivation of Nonlinear Gibbs Measures from Many-Body Quantum Mechanics.” <i>Journal de l’Ecole Polytechnique - Mathematiques</i>. Ecole Polytechnique, 2015. <a href=\"https://doi.org/10.5802/jep.18\">https://doi.org/10.5802/jep.18</a>.","ista":"Lewin M, Nam P, Rougerie N. 2015. Derivation of nonlinear gibbs measures from many-body quantum mechanics. Journal de l’Ecole Polytechnique - Mathematiques. 2, 65–115.","ama":"Lewin M, Nam P, Rougerie N. Derivation of nonlinear gibbs measures from many-body quantum mechanics. <i>Journal de l’Ecole Polytechnique - Mathematiques</i>. 2015;2:65-115. doi:<a href=\"https://doi.org/10.5802/jep.18\">10.5802/jep.18</a>","ieee":"M. Lewin, P. Nam, and N. Rougerie, “Derivation of nonlinear gibbs measures from many-body quantum mechanics,” <i>Journal de l’Ecole Polytechnique - Mathematiques</i>, vol. 2. Ecole Polytechnique, pp. 65–115, 2015."},"department":[{"_id":"RoSe"}],"date_updated":"2021-01-12T08:00:52Z","title":"Derivation of nonlinear gibbs measures from many-body quantum mechanics","publisher":"Ecole Polytechnique","file_date_updated":"2020-07-14T12:46:35Z","date_published":"2015-01-01T00:00:00Z","ddc":["539"],"publication_status":"published","abstract":[{"text":"We prove that nonlinear Gibbs measures can be obtained from the corresponding many-body, grand-canonical, quantum Gibbs states, in a mean-field limit where the temperature T diverges and the interaction strength behaves as 1/T. We proceed by characterizing the interacting Gibbs state as minimizing a functional counting the free-energy relatively to the non-interacting case. We then perform an infinite-dimensional analogue of phase-space semiclassical analysis, using fine properties of the quantum relative entropy, the link between quantum de Finetti measures and upper/lower symbols in a coherent state basis, as well as Berezin-Lieb type inequalities. Our results cover the measure built on the defocusing nonlinear Schrödinger functional on a finite interval, as well as smoother interactions in dimensions d 2.","lang":"eng"}],"license":"https://creativecommons.org/licenses/by-nd/4.0/","status":"public","type":"journal_article","_id":"473","date_created":"2018-12-11T11:46:40Z","ec_funded":1,"pubrep_id":"951","author":[{"last_name":"Lewin","first_name":"Mathieu","full_name":"Lewin, Mathieu"},{"id":"404092F4-F248-11E8-B48F-1D18A9856A87","full_name":"Phan Thanh, Nam","last_name":"Phan Thanh","first_name":"Nam"},{"full_name":"Rougerie, Nicolas","first_name":"Nicolas","last_name":"Rougerie"}],"oa_version":"Published Version","quality_controlled":"1","project":[{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"volume":2,"language":[{"iso":"eng"}],"file":[{"date_created":"2018-12-12T10:12:53Z","date_updated":"2020-07-14T12:46:35Z","content_type":"application/pdf","file_name":"IST-2018-951-v1+1_2015_Thanh-Nam_Derivation_of.pdf","relation":"main_file","access_level":"open_access","file_size":1084254,"file_id":"4974","checksum":"a40eb4016717ddc9927154798a4c164a","creator":"system"}],"month":"01","has_accepted_license":"1"},{"day":"24","doi":"10.1016/j.ic.2015.03.010","page":"25 - 52","year":"2015","oa":1,"publication":"Information and Computation","intvolume":"       242","publist_id":"7296","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"2279"}]},"scopus_import":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ieee":"K. Chatterjee, L. Doyen, M. Randour, and J. Raskin, “Looking at mean-payoff and total-payoff through windows,” <i>Information and Computation</i>, vol. 242, no. 6. Elsevier, pp. 25–52, 2015.","apa":"Chatterjee, K., Doyen, L., Randour, M., &#38; Raskin, J. (2015). Looking at mean-payoff and total-payoff through windows. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">https://doi.org/10.1016/j.ic.2015.03.010</a>","chicago":"Chatterjee, Krishnendu, Laurent Doyen, Mickael Randour, and Jean Raskin. “Looking at Mean-Payoff and Total-Payoff through Windows.” <i>Information and Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">https://doi.org/10.1016/j.ic.2015.03.010</a>.","ama":"Chatterjee K, Doyen L, Randour M, Raskin J. Looking at mean-payoff and total-payoff through windows. <i>Information and Computation</i>. 2015;242(6):25-52. doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">10.1016/j.ic.2015.03.010</a>","ista":"Chatterjee K, Doyen L, Randour M, Raskin J. 2015. Looking at mean-payoff and total-payoff through windows. Information and Computation. 242(6), 25–52.","short":"K. Chatterjee, L. Doyen, M. Randour, J. Raskin, Information and Computation 242 (2015) 25–52.","mla":"Chatterjee, Krishnendu, et al. “Looking at Mean-Payoff and Total-Payoff through Windows.” <i>Information and Computation</i>, vol. 242, no. 6, Elsevier, 2015, pp. 25–52, doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.010\">10.1016/j.ic.2015.03.010</a>."},"date_updated":"2023-02-23T10:36:02Z","department":[{"_id":"KrCh"}],"title":"Looking at mean-payoff and total-payoff through windows","date_published":"2015-03-24T00:00:00Z","publisher":"Elsevier","abstract":[{"text":"We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window.","lang":"eng"}],"publication_status":"published","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1302.4248"}],"status":"public","type":"journal_article","_id":"523","date_created":"2018-12-11T11:46:57Z","ec_funded":1,"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"},{"first_name":"Mickael","last_name":"Randour","full_name":"Randour, Mickael"},{"full_name":"Raskin, Jean","first_name":"Jean","last_name":"Raskin"}],"oa_version":"Preprint","project":[{"_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407"},{"name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","volume":242,"language":[{"iso":"eng"}],"issue":"6","month":"03"},{"scopus_import":1,"related_material":{"record":[{"status":"public","id":"5403","relation":"earlier_version"}]},"arxiv":1,"publist_id":"7295","intvolume":"       242","publication":"Information and Computation","oa":1,"page":"2 - 24","day":"11","doi":"10.1016/j.ic.2015.03.009","year":"2015","publication_status":"published","abstract":[{"text":"We consider concurrent games played by two players on a finite-state graph, where in every round the players simultaneously choose a move, and the current state along with the joint moves determine the successor state. We study the most fundamental objective for concurrent games, namely, mean-payoff or limit-average objective, where a reward is associated to each transition, and the goal of player 1 is to maximize the long-run average of the rewards, and the objective of player 2 is strictly the opposite (i.e., the games are zero-sum). The path constraint for player 1 could be qualitative, i.e., the mean-payoff is the maximal reward, or arbitrarily close to it; or quantitative, i.e., a given threshold between the minimal and maximal reward. We consider the computation of the almost-sure (resp. positive) winning sets, where player 1 can ensure that the path constraint is satisfied with probability 1 (resp. positive probability). Almost-sure winning with qualitative constraint exactly corresponds to the question of whether there exists a strategy to ensure that the payoff is the maximal reward of the game. Our main results for qualitative path constraints are as follows: (1) we establish qualitative determinacy results that show that for every state either player 1 has a strategy to ensure almost-sure (resp. positive) winning against all player-2 strategies, or player 2 has a spoiling strategy to falsify almost-sure (resp. positive) winning against all player-1 strategies; (2) we present optimal strategy complexity results that precisely characterize the classes of strategies required for almost-sure and positive winning for both players; and (3) we present quadratic time algorithms to compute the almost-sure and the positive winning sets, matching the best known bound of the algorithms for much simpler problems (such as reachability objectives). For quantitative constraints we show that a polynomial time solution for the almost-sure or the positive winning set would imply a solution to a long-standing open problem (of solving the value problem of turn-based deterministic mean-payoff games) that is not known to be solvable in polynomial time.","lang":"eng"}],"publisher":"Elsevier","date_published":"2015-10-11T00:00:00Z","title":"Qualitative analysis of concurrent mean payoff games","department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:24:45Z","citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, Information and Computation 242 (2015) 2–24.","mla":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” <i>Information and Computation</i>, vol. 242, no. 6, Elsevier, 2015, pp. 2–24, doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">10.1016/j.ic.2015.03.009</a>.","ista":"Chatterjee K, Ibsen-Jensen R. 2015. Qualitative analysis of concurrent mean payoff games. Information and Computation. 242(6), 2–24.","ama":"Chatterjee K, Ibsen-Jensen R. Qualitative analysis of concurrent mean payoff games. <i>Information and Computation</i>. 2015;242(6):2-24. doi:<a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">10.1016/j.ic.2015.03.009</a>","chicago":"Chatterjee, Krishnendu, and Rasmus Ibsen-Jensen. “Qualitative Analysis of Concurrent Mean Payoff Games.” <i>Information and Computation</i>. Elsevier, 2015. <a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">https://doi.org/10.1016/j.ic.2015.03.009</a>.","apa":"Chatterjee, K., &#38; Ibsen-Jensen, R. (2015). Qualitative analysis of concurrent mean payoff games. <i>Information and Computation</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ic.2015.03.009\">https://doi.org/10.1016/j.ic.2015.03.009</a>","ieee":"K. Chatterjee and R. Ibsen-Jensen, “Qualitative analysis of concurrent mean payoff games,” <i>Information and Computation</i>, vol. 242, no. 6. Elsevier, pp. 2–24, 2015."},"external_id":{"arxiv":["1409.5306"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T11:46:57Z","type":"journal_article","_id":"524","status":"public","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1409.5306"}],"month":"10","issue":"6","language":[{"iso":"eng"}],"volume":242,"quality_controlled":"1","oa_version":"Preprint","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389"}]},{"language":[{"iso":"eng"}],"publisher":"IST Austria","date_published":"2015-01-12T00:00:00Z","file_date_updated":"2020-07-14T12:46:52Z","title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. \r\nThere have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector.  \r\nWe consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics.\r\nOur problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).\r\nOur main results are algorithms for the decision problem which are always polynomial in the size of the MDP. We also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions.\r\nFinally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem."}],"publication_status":"published","month":"01","has_accepted_license":"1","ddc":["004"],"file":[{"access_level":"open_access","file_size":689863,"checksum":"e4869a584567c506349abda9c8ec7db3","file_id":"5533","creator":"system","relation":"main_file","file_name":"IST-2015-318-v1+1_main.pdf","date_created":"2018-12-12T11:54:11Z","date_updated":"2020-07-14T12:46:52Z","content_type":"application/pdf"}],"author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"full_name":"Komarkova, Zuzana","first_name":"Zuzana","last_name":"Komarkova"},{"orcid":"0000-0002-8122-2881","first_name":"Jan","last_name":"Kretinsky","full_name":"Kretinsky, Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["IST Austria Technical Report"],"date_updated":"2023-02-23T12:26:16Z","department":[{"_id":"KrCh"}],"citation":{"short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">10.15479/AT:IST-2015-318-v1-1</a>.","apa":"Chatterjee, K., Komarkova, Z., &#38; Kretinsky, J. (2015). <i>Unifying two views on multiple mean-payoff objectives in Markov decision processes</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">https://doi.org/10.15479/AT:IST-2015-318-v1-1</a>","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 41p.","chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">https://doi.org/10.15479/AT:IST-2015-318-v1-1</a>.","ama":"Chatterjee K, Komarkova Z, Kretinsky J. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v1-1\">10.15479/AT:IST-2015-318-v1-1</a>","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, <i>Unifying two views on multiple mean-payoff objectives in Markov decision processes</i>. IST Austria, 2015."},"oa_version":"Published Version","pubrep_id":"318","related_material":{"record":[{"status":"public","relation":"later_version","id":"1657"},{"status":"public","relation":"later_version","id":"466"},{"relation":"later_version","id":"5435","status":"public"}]},"page":"41","year":"2015","publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2015-318-v1-1","day":"12","status":"public","oa":1,"date_created":"2018-12-12T11:39:17Z","type":"technical_report","_id":"5429"},{"title":"Faster algorithms for quantitative verification in constant treewidth graphs","file_date_updated":"2020-07-14T12:46:52Z","language":[{"iso":"eng"}],"publisher":"IST Austria","date_published":"2015-02-10T00:00:00Z","file":[{"date_created":"2018-12-12T11:53:21Z","date_updated":"2020-07-14T12:46:52Z","content_type":"application/pdf","file_name":"IST-2015-319-v1+1_long.pdf","relation":"main_file","access_level":"open_access","file_size":1089651,"checksum":"62c6ea01e342553dcafb88a070fb1ad5","file_id":"5482","creator":"system"}],"ddc":["000"],"month":"02","has_accepted_license":"1","publication_status":"published","abstract":[{"lang":"eng","text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean- payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let n denote the number of nodes of a graph, m the number of edges (for constant treewidth graphs m = O ( n ) ) and W the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a mul- tiplicative factor of ∊ in time O ( n · log( n/∊ )) and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time O ( n · log( | a · b · n | )) = O ( n · log( n · W )) , when the output is a b , as compared to the previously best known algorithm with running time O ( n 2 · log( n · W )) . Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in O ( n 2 · m ) time and the associated decision problem can be solved in O ( n · m ) time, improving the previous known O ( n 3 · m · log( n · W )) and O ( n 2 · m ) bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires O ( n · log n ) time, improving the previous known O ( n 4 · log( n · W )) bound. We have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks."}],"alternative_title":["IST Austria Technical Report"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"orcid":"0000-0003-4783-0389","last_name":"Ibsen-Jensen","first_name":"Rasmus","full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","first_name":"Andreas","last_name":"Pavlogiannis"}],"oa_version":"Published Version","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">https://doi.org/10.15479/AT:IST-2015-319-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 31p.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">10.15479/AT:IST-2015-319-v1-1</a>","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2015). <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">https://doi.org/10.15479/AT:IST-2015-319-v1-1</a>","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-319-v1-1\">10.15479/AT:IST-2015-319-v1-1</a>."},"department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:26:22Z","related_material":{"record":[{"relation":"later_version","id":"1607","status":"public"},{"status":"public","relation":"later_version","id":"5437"}]},"pubrep_id":"319","page":"31","publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2015-319-v1-1","status":"public","day":"10","year":"2015","type":"technical_report","_id":"5430","date_created":"2018-12-12T11:39:17Z","oa":1},{"pubrep_id":"322","date_created":"2018-12-12T11:39:17Z","oa":1,"_id":"5431","type":"technical_report","page":"25","publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2015-322-v1-1","status":"public","day":"19","year":"2015","publication_status":"published","month":"02","has_accepted_license":"1","abstract":[{"text":"We consider finite-state concurrent stochastic games, played by k>=2 players for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. We consider reachability objectives that given a target set of states require that some state in the target set is visited, and the dual safety objectives that given a target set require that only states in the target set are visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed.\r\n\r\n Our main results are as follows: We show that in two-player zero-sum concurrent stochastic games (with reachability objective for one player and the complementary safety objective for the other player): (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary. In general we study the class of non-zero-sum games admitting epsilon-Nash equilibria. We show that if there is at least one player with reachability objective, then doubly-exponential patience is needed in general for epsilon-Nash equilibrium strategies, whereas in contrast if all players have safety objectives, then the optimal bound on patience for epsilon-Nash equilibrium strategies is only exponential.","lang":"eng"}],"ddc":["005","519"],"file":[{"relation":"main_file","file_id":"5491","checksum":"bfb858262c30445b8e472c40069178a2","creator":"system","access_level":"open_access","file_size":661015,"content_type":"application/pdf","date_created":"2018-12-12T11:53:31Z","date_updated":"2020-07-14T12:46:53Z","file_name":"IST-2015-322-v1+1_safetygames.pdf"}],"publisher":"IST Austria","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:53Z","date_published":"2015-02-19T00:00:00Z","title":"The patience of concurrent stochastic games with safety and reachability objectives","department":[{"_id":"KrCh"}],"date_updated":"2021-01-12T08:02:13Z","citation":{"ista":"Chatterjee K, Ibsen-Jensen R, Hansen K. 2015. The patience of concurrent stochastic games with safety and reachability objectives, IST Austria, 25p.","ama":"Chatterjee K, Ibsen-Jensen R, Hansen K. <i>The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">10.15479/AT:IST-2015-322-v1-1</a>","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Kristoffer Hansen. <i>The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">https://doi.org/10.15479/AT:IST-2015-322-v1-1</a>.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Hansen, K. (2015). <i>The patience of concurrent stochastic games with safety and reachability objectives</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">https://doi.org/10.15479/AT:IST-2015-322-v1-1</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and K. Hansen, <i>The patience of concurrent stochastic games with safety and reachability objectives</i>. IST Austria, 2015.","short":"K. Chatterjee, R. Ibsen-Jensen, K. Hansen, The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. <i>The Patience of Concurrent Stochastic Games with Safety and Reachability Objectives</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-322-v1-1\">10.15479/AT:IST-2015-322-v1-1</a>."},"oa_version":"Published Version","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus","last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389"},{"first_name":"Kristoffer","last_name":"Hansen","full_name":"Hansen, Kristoffer"}],"alternative_title":["IST Austria Technical Report"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"year":"2015","day":"19","status":"public","page":"29","publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2015-323-v1-1","oa":1,"date_created":"2018-12-12T11:39:18Z","type":"technical_report","_id":"5432","pubrep_id":"323","related_material":{"record":[{"relation":"earlier_version","id":"5421","status":"public"},{"relation":"later_version","id":"5440","status":"public"}]},"author":[{"first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu"},{"last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus"},{"first_name":"Martin","last_name":"Nowak","full_name":"Nowak, Martin"}],"alternative_title":["IST Austria Technical Report"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:26:33Z","oa_version":"Published Version","citation":{"apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Nowak, M. (2015). <i>The complexity of evolutionary games on graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">https://doi.org/10.15479/AT:IST-2015-323-v1-1</a>","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Martin Nowak. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">https://doi.org/10.15479/AT:IST-2015-323-v1-1</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Nowak M. 2015. The complexity of evolutionary games on graphs, IST Austria, 29p.","ama":"Chatterjee K, Ibsen-Jensen R, Nowak M. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">10.15479/AT:IST-2015-323-v1-1</a>","ieee":"K. Chatterjee, R. Ibsen-Jensen, and M. Nowak, <i>The complexity of evolutionary games on graphs</i>. IST Austria, 2015.","short":"K. Chatterjee, R. Ibsen-Jensen, M. Nowak, The Complexity of Evolutionary Games on Graphs, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. <i>The Complexity of Evolutionary Games on Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-323-v1-1\">10.15479/AT:IST-2015-323-v1-1</a>."},"publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:53Z","language":[{"iso":"eng"}],"date_published":"2015-02-19T00:00:00Z","title":"The complexity of evolutionary games on graphs","month":"02","publication_status":"published","has_accepted_license":"1","abstract":[{"text":"Evolution occurs in populations of reproducing individuals. The structure of the population affects the outcome of the evolutionary process. Evolutionary graph theory is a powerful approach to study this phenomenon. There are two graphs. The interaction graph specifies who interacts with whom in the context of evolution.The replacement graph specifies who competes with whom for reproduction. \r\nThe vertices of the two graphs are the same, and each vertex corresponds to an individual of the population. A key quantity is the fixation probability of a new mutant. It is defined as the probability that a newly introduced mutant (on a single vertex) generates a lineage of offspring which eventually takes over the entire population of resident individuals. The basic computational questions are as follows: (i) the qualitative question asks whether the fixation probability is positive; and (ii) the quantitative approximation question asks for an approximation of the fixation probability. \r\nOur main results are:\r\n(1) We show that the qualitative question is NP-complete and the quantitative approximation question is #P-hard in the special case when the interaction and the replacement graphs coincide and even with the restriction that the resident individuals do not reproduce (which corresponds to an invading population taking over an empty structure).\r\n(2) We show that in general the qualitative question is PSPACE-complete and the quantitative approximation question is PSPACE-hard and can be solved in exponential time.\r\n","lang":"eng"}],"file":[{"relation":"main_file","file_id":"5519","checksum":"546c1b291d545e7b24aaaf4199dac671","creator":"system","access_level":"open_access","file_size":576347,"content_type":"application/pdf","date_created":"2018-12-12T11:53:57Z","date_updated":"2020-07-14T12:46:53Z","file_name":"IST-2015-323-v1+1_main.pdf"}],"ddc":["005","576"]},{"pubrep_id":"326","publication_identifier":{"issn":["2664-1690"]},"page":"16","day":"19","status":"public","year":"2015","type":"technical_report","_id":"5434","date_created":"2018-12-12T11:39:18Z","oa":1,"title":"Optimal cost indefinite-horizon reachability in goal DEC-POMDPs","date_published":"2015-02-19T00:00:00Z","publisher":"IST Austria","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:53Z","file":[{"date_created":"2018-12-12T11:53:14Z","date_updated":"2020-07-14T12:46:53Z","content_type":"application/pdf","file_name":"IST-2015-326-v1+1_main.pdf","relation":"main_file","access_level":"open_access","file_size":378162,"file_id":"5475","checksum":"8542fd0b10aed7811cd41077b8ccb632","creator":"system"},{"file_name":"IST-2015-326-v1+2_authors.txt","content_type":"text/plain","date_updated":"2020-07-14T12:46:53Z","date_created":"2019-04-16T13:00:33Z","creator":"dernst","file_id":"6317","checksum":"84c31c537bdaf7a91909f18d25d640ab","file_size":64,"access_level":"closed","relation":"main_file"}],"ddc":["000"],"month":"02","has_accepted_license":"1","publication_status":"published","abstract":[{"text":"DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new method to solve the problem that extends methods for finite-horizon DEC- POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show our approach presents promising results.","lang":"eng"}],"alternative_title":["IST Austria Technical Report"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Anonymous, 1","first_name":"1","last_name":"Anonymous"},{"full_name":"Anonymous, 2","last_name":"Anonymous","first_name":"2"}],"citation":{"short":"1 Anonymous, 2 Anonymous, Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs, IST Austria, 2015.","mla":"Anonymous, 1, and 2 Anonymous. <i>Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs</i>. IST Austria, 2015.","apa":"Anonymous, 1, &#38; Anonymous, 2. (2015). <i>Optimal cost indefinite-horizon reachability in goal DEC-POMDPs</i>. IST Austria.","ista":"Anonymous 1, Anonymous 2. 2015. Optimal cost indefinite-horizon reachability in goal DEC-POMDPs, IST Austria, 16p.","chicago":"Anonymous, 1, and 2 Anonymous. <i>Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs</i>. IST Austria, 2015.","ama":"Anonymous 1, Anonymous 2. <i>Optimal Cost Indefinite-Horizon Reachability in Goal DEC-POMDPs</i>. IST Austria; 2015.","ieee":"1 Anonymous and 2 Anonymous, <i>Optimal cost indefinite-horizon reachability in goal DEC-POMDPs</i>. IST Austria, 2015."},"oa_version":"Published Version","date_updated":"2020-07-14T23:04:59Z"},{"author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Komarkova, Zuzana","first_name":"Zuzana","last_name":"Komarkova"},{"first_name":"Jan","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["IST Austria Technical Report"],"date_updated":"2023-02-23T12:26:00Z","department":[{"_id":"KrCh"}],"citation":{"short":"K. Chatterjee, Z. Komarkova, J. Kretinsky, Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v2-1\">10.15479/AT:IST-2015-318-v2-1</a>.","ieee":"K. Chatterjee, Z. Komarkova, and J. Kretinsky, <i>Unifying two views on multiple mean-payoff objectives in Markov decision processes</i>. IST Austria, 2015.","apa":"Chatterjee, K., Komarkova, Z., &#38; Kretinsky, J. (2015). <i>Unifying two views on multiple mean-payoff objectives in Markov decision processes</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-318-v2-1\">https://doi.org/10.15479/AT:IST-2015-318-v2-1</a>","chicago":"Chatterjee, Krishnendu, Zuzana Komarkova, and Jan Kretinsky. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-318-v2-1\">https://doi.org/10.15479/AT:IST-2015-318-v2-1</a>.","ama":"Chatterjee K, Komarkova Z, Kretinsky J. <i>Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-318-v2-1\">10.15479/AT:IST-2015-318-v2-1</a>","ista":"Chatterjee K, Komarkova Z, Kretinsky J. 2015. Unifying two views on multiple mean-payoff objectives in Markov decision processes, IST Austria, 51p."},"oa_version":"Published Version","publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:53Z","date_published":"2015-02-23T00:00:00Z","language":[{"iso":"eng"}],"title":"Unifying two views on multiple mean-payoff objectives in Markov decision processes","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) with multiple limit-average (or mean-payoff) objectives. \r\nThere have been two different views: (i) the expectation semantics, where the goal is to optimize the expected mean-payoff objective, and (ii) the satisfaction semantics, where the goal is to maximize the probability of runs such that the mean-payoff value stays above a given vector.  \r\nWe consider the problem where the goal is to optimize the expectation under the constraint that the satisfaction semantics is ensured, and thus consider a generalization that unifies the existing semantics. Our problem captures the notion of optimization with respect to strategies that are risk-averse (i.e., ensures certain probabilistic guarantee).\r\nOur main results are algorithms for the decision problem which are always polynomial in the size of the MDP.\r\nWe also show that an approximation of the Pareto-curve can be computed in time polynomial in the size of the MDP, and the approximation factor, but exponential in the number of dimensions. Finally, we present a complete characterization of the strategy complexity (in terms of memory bounds and randomization) required to solve our problem."}],"publication_status":"published","has_accepted_license":"1","month":"02","file":[{"date_updated":"2020-07-14T12:46:53Z","date_created":"2018-12-12T11:54:03Z","content_type":"application/pdf","file_name":"IST-2015-318-v2+1_main.pdf","relation":"main_file","file_size":717630,"access_level":"open_access","creator":"system","file_id":"5525","checksum":"75284adec80baabdfe71ff9ebbc27445"}],"ddc":["004"],"day":"23","status":"public","page":"51","year":"2015","doi":"10.15479/AT:IST-2015-318-v2-1","publication_identifier":{"issn":["2664-1690"]},"oa":1,"date_created":"2018-12-12T11:39:19Z","type":"technical_report","_id":"5435","related_material":{"record":[{"relation":"later_version","id":"1657","status":"public"},{"status":"public","relation":"later_version","id":"466"},{"relation":"earlier_version","id":"5429","status":"public"}]},"pubrep_id":"327"},{"related_material":{"record":[{"id":"1656","relation":"later_version","status":"public"},{"status":"public","relation":"later_version","id":"467"},{"status":"public","id":"5415","relation":"earlier_version"}]},"pubrep_id":"331","day":"24","page":"29","year":"2015","status":"public","publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2015-170-v2-2","oa":1,"date_created":"2018-12-12T11:39:19Z","type":"technical_report","_id":"5436","language":[{"iso":"eng"}],"file_date_updated":"2020-07-14T12:46:54Z","date_published":"2015-04-24T00:00:00Z","publisher":"IST Austria","title":"Nested weighted automata","abstract":[{"text":"Recently there has been a significant effort to handle quantitative properties in formal verification and synthesis. While weighted automata over finite and infinite words provide a natural and flexible framework to express quantitative properties, perhaps surprisingly, some basic system properties such as average response time cannot be expressed using weighted automata, nor in any other know decidable formalism. In this work, we introduce nested weighted automata as a natural extension of weighted automata which makes it possible to express important quantitative properties such as average response time.\r\nIn nested weighted automata, a master automaton spins off and collects results from weighted slave automata, each of which computes a quantity along a finite portion of an infinite word. Nested weighted automata can be viewed as the quantitative analogue of monitor automata, which are used in run-time verification. We establish an almost complete decidability picture for the basic decision problems about nested weighted automata, and illustrate their applicability in several domains. In particular, nested weighted automata can be used to decide average response time properties.","lang":"eng"}],"month":"04","publication_status":"published","has_accepted_license":"1","ddc":["000"],"file":[{"file_name":"IST-2015-170-v2+2_report.pdf","content_type":"application/pdf","date_created":"2018-12-12T11:54:19Z","date_updated":"2020-07-14T12:46:54Z","checksum":"3c402f47d3669c28d04d1af405a08e3f","file_id":"5541","creator":"system","access_level":"open_access","file_size":569991,"relation":"main_file"}],"author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"},{"id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","full_name":"Otop, Jan","last_name":"Otop","first_name":"Jan"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["IST Austria Technical Report"],"date_updated":"2023-02-23T12:25:21Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"citation":{"short":"K. Chatterjee, T.A. Henzinger, J. Otop, Nested Weighted Automata, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. <i>Nested Weighted Automata</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">10.15479/AT:IST-2015-170-v2-2</a>.","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, <i>Nested weighted automata</i>. IST Austria, 2015.","ista":"Chatterjee K, Henzinger TA, Otop J. 2015. Nested weighted automata, IST Austria, 29p.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. <i>Nested Weighted Automata</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">https://doi.org/10.15479/AT:IST-2015-170-v2-2</a>.","ama":"Chatterjee K, Henzinger TA, Otop J. <i>Nested Weighted Automata</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">10.15479/AT:IST-2015-170-v2-2</a>","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2015). <i>Nested weighted automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-170-v2-2\">https://doi.org/10.15479/AT:IST-2015-170-v2-2</a>"},"oa_version":"Published Version"},{"department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:26:05Z","citation":{"short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs, IST Austria, 2015.","mla":"Chatterjee, Krishnendu, et al. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">10.15479/AT:IST-2015-330-v2-1</a>.","ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria, 2015.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2015). <i>Faster algorithms for quantitative verification in constant treewidth graphs</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">https://doi.org/10.15479/AT:IST-2015-330-v2-1</a>","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">https://doi.org/10.15479/AT:IST-2015-330-v2-1</a>.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. <i>Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-330-v2-1\">10.15479/AT:IST-2015-330-v2-1</a>","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2015. Faster algorithms for quantitative verification in constant treewidth graphs, IST Austria, 27p."},"oa_version":"Published Version","author":[{"orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus"},{"full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8943-0722","first_name":"Andreas","last_name":"Pavlogiannis"}],"alternative_title":["IST Austria Technical Report"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","month":"04","has_accepted_license":"1","abstract":[{"lang":"eng","text":"We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. \r\nThe algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let $n$ denote the number of nodes of a graph, $m$ the number of edges (for constant treewidth graphs $m=O(n)$) and $W$ the largest absolute value of the weights.\r\nOur main theoretical results are as follows.\r\nFirst, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of $\\epsilon$ in time $O(n \\cdot \\log (n/\\epsilon))$ and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time $O(n \\cdot \\log (|a\\cdot b|))=O(n\\cdot\\log (n\\cdot W))$, when the output is $\\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \\cdot \\log (n\\cdot W))$. Third, for the minimum initial credit problem we show that (i)~for general graphs the problem can be solved in $O(n^2\\cdot m)$ time and the associated decision problem can be solved in $O(n\\cdot m)$ time, improving the previous known $O(n^3\\cdot m\\cdot \\log (n\\cdot W))$ and $O(n^2 \\cdot m)$ bounds, respectively; and (ii)~for constant treewidth graphs we present an algorithm that requires $O(n\\cdot \\log n)$ time, improving the previous known $O(n^4 \\cdot \\log (n \\cdot W))$ bound.\r\nWe have implemented some of our algorithms and show that they present a significant speedup on standard benchmarks. "}],"file":[{"relation":"main_file","access_level":"open_access","file_size":1072137,"checksum":"f5917c20f84018b362d385c000a2e123","file_id":"5473","creator":"system","date_created":"2018-12-12T11:53:12Z","date_updated":"2020-07-14T12:46:54Z","content_type":"application/pdf","file_name":"IST-2015-330-v2+1_main.pdf"}],"ddc":["000"],"file_date_updated":"2020-07-14T12:46:54Z","language":[{"iso":"eng"}],"publisher":"IST Austria","date_published":"2015-04-27T00:00:00Z","title":"Faster algorithms for quantitative verification in constant treewidth graphs","date_created":"2018-12-12T11:39:19Z","oa":1,"type":"technical_report","_id":"5437","year":"2015","day":"27","publication_identifier":{"issn":["2664-1690"]},"status":"public","page":"27","doi":"10.15479/AT:IST-2015-330-v2-1","pubrep_id":"333","related_material":{"record":[{"relation":"later_version","id":"1607","status":"public"},{"id":"5430","relation":"earlier_version","status":"public"}]}},{"alternative_title":["IST Austria Technical Report"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"},{"first_name":"Rasmus","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus"},{"full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Otop"}],"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Edit Distance for Pushdown Automata</i>. IST Austria, 2015, doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">10.15479/AT:IST-2015-334-v1-1</a>.","short":"K. Chatterjee, T.A. Henzinger, R. Ibsen-Jensen, J. Otop, Edit Distance for Pushdown Automata, IST Austria, 2015.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, Rasmus Ibsen-Jensen, and Jan Otop. <i>Edit Distance for Pushdown Automata</i>. IST Austria, 2015. <a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">https://doi.org/10.15479/AT:IST-2015-334-v1-1</a>.","ista":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. 2015. Edit distance for pushdown automata, IST Austria, 15p.","ama":"Chatterjee K, Henzinger TA, Ibsen-Jensen R, Otop J. <i>Edit Distance for Pushdown Automata</i>. IST Austria; 2015. doi:<a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">10.15479/AT:IST-2015-334-v1-1</a>","apa":"Chatterjee, K., Henzinger, T. A., Ibsen-Jensen, R., &#38; Otop, J. (2015). <i>Edit distance for pushdown automata</i>. IST Austria. <a href=\"https://doi.org/10.15479/AT:IST-2015-334-v1-1\">https://doi.org/10.15479/AT:IST-2015-334-v1-1</a>","ieee":"K. Chatterjee, T. A. Henzinger, R. Ibsen-Jensen, and J. Otop, <i>Edit distance for pushdown automata</i>. IST Austria, 2015."},"oa_version":"Published Version","department":[{"_id":"KrCh"}],"date_updated":"2023-02-23T12:20:08Z","title":"Edit distance for pushdown automata","publisher":"IST Austria","file_date_updated":"2020-07-14T12:46:55Z","language":[{"iso":"eng"}],"date_published":"2015-05-05T00:00:00Z","file":[{"date_created":"2018-12-12T11:53:56Z","date_updated":"2020-07-14T12:46:55Z","content_type":"application/pdf","file_name":"IST-2015-334-v1+1_report.pdf","relation":"main_file","access_level":"open_access","file_size":422573,"file_id":"5518","checksum":"8a5f2d77560e552af87eb1982437a43b","creator":"system"}],"ddc":["004"],"month":"05","has_accepted_license":"1","publication_status":"published","abstract":[{"text":"The edit distance between two words w1, w2 is the minimal number of word operations (letter insertions, deletions, and substitutions) necessary to transform w1 to w2. The edit distance generalizes to languages L1, L2, where the edit distance is the minimal number k such that for every word from L1 there exists a word in L2 with edit distance at most k. We study the edit distance computation problem between pushdown automata and their subclasses.\r\nThe problem of computing edit distance to a pushdown automaton is undecidable, and in practice, the interesting question is to compute the edit distance from a pushdown automaton (the implementation, a standard model for programs with recursion) to a regular language (the specification). In this work, we present a complete picture of decidability and complexity for deciding whether, for a given threshold k, the edit distance from a pushdown automaton to a finite automaton is at most k. ","lang":"eng"}],"year":"2015","status":"public","day":"05","publication_identifier":{"issn":["2664-1690"]},"doi":"10.15479/AT:IST-2015-334-v1-1","page":"15","_id":"5438","type":"technical_report","oa":1,"date_created":"2018-12-12T11:39:20Z","related_material":{"record":[{"id":"1610","relation":"later_version","status":"public"},{"id":"465","relation":"later_version","status":"public"}]},"pubrep_id":"334"}]