[{"title":"Strongly aligned molecules inside helium droplets in the near-adiabatic regime","publisher":"AIP Publishing","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","isi":1,"author":[{"last_name":"Shepperson","first_name":"Benjamin","full_name":"Shepperson, Benjamin"},{"full_name":"Chatterley, Adam","first_name":"Adam","last_name":"Chatterley"},{"last_name":"Søndergaard","first_name":"Anders","full_name":"Søndergaard, Anders"},{"first_name":"Lars","last_name":"Christiansen","full_name":"Christiansen, Lars"},{"full_name":"Lemeshko, Mikhail","orcid":"0000-0002-6990-7802","first_name":"Mikhail","id":"37CB05FA-F248-11E8-B48F-1D18A9856A87","last_name":"Lemeshko"},{"full_name":"Stapelfeldt, Henrik","first_name":"Henrik","last_name":"Stapelfeldt"}],"day":"01","external_id":{"isi":["000405089400047"]},"volume":147,"quality_controlled":"1","publist_id":"6403","article_processing_charge":"No","language":[{"iso":"eng"}],"department":[{"_id":"MiLe"}],"type":"journal_article","date_created":"2018-12-11T11:49:36Z","publication":"The Journal of Chemical Physics","month":"06","publication_identifier":{"issn":["00219606"]},"oa":1,"status":"public","_id":"996","article_number":"013946","year":"2017","date_updated":"2024-02-28T13:02:26Z","abstract":[{"text":"Iodine (I 2  ) molecules embedded in He nanodroplets are aligned by a 160 ps long laser pulse. The highest degree of alignment, occurring at the peak of the pulse and quantified by ⟨cos 2 θ 2D ⟩ , is measured as a function of the laser intensity. The results are well described by ⟨cos 2 θ 2D ⟩  calculated for a gas of isolated molecules each with an effective rotational constant of 0.6 times the gas-phase value, and at a temperature of 0.4 K. Theoretical analysis using the angulon quasiparticle to describe rotating molecules in superfluid helium rationalizes why the alignment mechanism is similar to that of isolated molecules with an effective rotational constant. A major advantage of molecules in He droplets is that their 0.4 K temperature leads to stronger alignment than what can generally be achieved for gas phase molecules -- here demonstrated by a direct comparison of the droplet results to measurements on a ∼  1 K supersonic beam of isolated molecules. This point is further illustrated for more complex system by measurements on 1,4-diiodobenzene and 1,4-dibromobenzene. For all three molecular species studied the highest values of ⟨cos 2 θ 2D ⟩  achieved in He droplets exceed 0.96. ","lang":"eng"}],"issue":"1","intvolume":"       147","citation":{"ista":"Shepperson B, Chatterley A, Søndergaard A, Christiansen L, Lemeshko M, Stapelfeldt H. 2017. Strongly aligned molecules inside helium droplets in the near-adiabatic regime. The Journal of Chemical Physics. 147(1), 013946.","apa":"Shepperson, B., Chatterley, A., Søndergaard, A., Christiansen, L., Lemeshko, M., &#38; Stapelfeldt, H. (2017). Strongly aligned molecules inside helium droplets in the near-adiabatic regime. <i>The Journal of Chemical Physics</i>. AIP Publishing. <a href=\"https://doi.org/10.1063/1.4983703\">https://doi.org/10.1063/1.4983703</a>","mla":"Shepperson, Benjamin, et al. “Strongly Aligned Molecules inside Helium Droplets in the Near-Adiabatic Regime.” <i>The Journal of Chemical Physics</i>, vol. 147, no. 1, 013946, AIP Publishing, 2017, doi:<a href=\"https://doi.org/10.1063/1.4983703\">10.1063/1.4983703</a>.","chicago":"Shepperson, Benjamin, Adam Chatterley, Anders Søndergaard, Lars Christiansen, Mikhail Lemeshko, and Henrik Stapelfeldt. “Strongly Aligned Molecules inside Helium Droplets in the Near-Adiabatic Regime.” <i>The Journal of Chemical Physics</i>. AIP Publishing, 2017. <a href=\"https://doi.org/10.1063/1.4983703\">https://doi.org/10.1063/1.4983703</a>.","short":"B. Shepperson, A. Chatterley, A. Søndergaard, L. Christiansen, M. Lemeshko, H. Stapelfeldt, The Journal of Chemical Physics 147 (2017).","ama":"Shepperson B, Chatterley A, Søndergaard A, Christiansen L, Lemeshko M, Stapelfeldt H. Strongly aligned molecules inside helium droplets in the near-adiabatic regime. <i>The Journal of Chemical Physics</i>. 2017;147(1). doi:<a href=\"https://doi.org/10.1063/1.4983703\">10.1063/1.4983703</a>","ieee":"B. Shepperson, A. Chatterley, A. Søndergaard, L. Christiansen, M. Lemeshko, and H. Stapelfeldt, “Strongly aligned molecules inside helium droplets in the near-adiabatic regime,” <i>The Journal of Chemical Physics</i>, vol. 147, no. 1. AIP Publishing, 2017."},"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1704.03684"}],"date_published":"2017-06-01T00:00:00Z","oa_version":"Submitted Version","publication_status":"published","doi":"10.1063/1.4983703"},{"external_id":{"arxiv":["1705.05162"],"isi":["000417132100007"]},"quality_controlled":"1","volume":119,"publist_id":"6401","article_processing_charge":"No","article_type":"original","language":[{"iso":"eng"}],"department":[{"_id":"MiLe"},{"_id":"RoSe"}],"type":"journal_article","date_created":"2018-12-11T11:49:36Z","publication":"Physical Review Letters","title":"Emergence of non-abelian magnetic monopoles in a quantum impurity problem","publisher":"American Physical Society","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"},{"grant_number":"694227","_id":"25C6DC12-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Analysis of quantum many-body systems"},{"name":"Quantum rotations in the presence of a many-body environment","call_identifier":"FWF","grant_number":"P29902","_id":"26031614-B435-11E9-9278-68D0E5697425"}],"isi":1,"author":[{"first_name":"Enderalp","orcid":"0000-0001-5973-0874","last_name":"Yakaboylu","id":"38CB71F6-F248-11E8-B48F-1D18A9856A87","full_name":"Yakaboylu, Enderalp"},{"first_name":"Andreas","orcid":"0000-0003-3146-6746","last_name":"Deuchert","id":"4DA65CD0-F248-11E8-B48F-1D18A9856A87","full_name":"Deuchert, Andreas"},{"full_name":"Lemeshko, Mikhail","last_name":"Lemeshko","id":"37CB05FA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6990-7802","first_name":"Mikhail"}],"day":"06","intvolume":"       119","citation":{"ista":"Yakaboylu E, Deuchert A, Lemeshko M. 2017. Emergence of non-abelian magnetic monopoles in a quantum impurity problem. Physical Review Letters. 119(23), 235301.","apa":"Yakaboylu, E., Deuchert, A., &#38; Lemeshko, M. (2017). Emergence of non-abelian magnetic monopoles in a quantum impurity problem. <i>Physical Review Letters</i>. American Physical Society. <a href=\"https://doi.org/10.1103/PhysRevLett.119.235301\">https://doi.org/10.1103/PhysRevLett.119.235301</a>","mla":"Yakaboylu, Enderalp, et al. “Emergence of Non-Abelian Magnetic Monopoles in a Quantum Impurity Problem.” <i>Physical Review Letters</i>, vol. 119, no. 23, 235301, American Physical Society, 2017, doi:<a href=\"https://doi.org/10.1103/PhysRevLett.119.235301\">10.1103/PhysRevLett.119.235301</a>.","chicago":"Yakaboylu, Enderalp, Andreas Deuchert, and Mikhail Lemeshko. “Emergence of Non-Abelian Magnetic Monopoles in a Quantum Impurity Problem.” <i>Physical Review Letters</i>. American Physical Society, 2017. <a href=\"https://doi.org/10.1103/PhysRevLett.119.235301\">https://doi.org/10.1103/PhysRevLett.119.235301</a>.","short":"E. Yakaboylu, A. Deuchert, M. Lemeshko, Physical Review Letters 119 (2017).","ieee":"E. Yakaboylu, A. Deuchert, and M. Lemeshko, “Emergence of non-abelian magnetic monopoles in a quantum impurity problem,” <i>Physical Review Letters</i>, vol. 119, no. 23. American Physical Society, 2017.","ama":"Yakaboylu E, Deuchert A, Lemeshko M. Emergence of non-abelian magnetic monopoles in a quantum impurity problem. <i>Physical Review Letters</i>. 2017;119(23). doi:<a href=\"https://doi.org/10.1103/PhysRevLett.119.235301\">10.1103/PhysRevLett.119.235301</a>"},"scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1705.05162","open_access":"1"}],"date_published":"2017-12-06T00:00:00Z","oa_version":"Preprint","publication_status":"published","doi":"10.1103/PhysRevLett.119.235301","ec_funded":1,"month":"12","publication_identifier":{"issn":["0031-9007"]},"oa":1,"status":"public","_id":"997","article_number":"235301","year":"2017","date_updated":"2023-10-10T13:31:54Z","abstract":[{"lang":"eng","text":"Recently it was shown that molecules rotating in superfluid helium can be described in terms of the angulon quasiparticles (Phys. Rev. Lett. 118, 095301 (2017)). Here we demonstrate that in the experimentally realized regime the angulon can be seen as a point charge on a 2-sphere interacting with a gauge field of a non-abelian magnetic monopole. Unlike in several other settings, the gauge fields of the angulon problem emerge in the real coordinate space, as opposed to the momentum space or some effective parameter space. Furthermore, we find a topological transition associated with making the monopole abelian, which takes place in the vicinity of the previously reported angulon instabilities. These results pave the way for studying topological phenomena in experiments on molecules trapped in superfluid helium nanodroplets, as well as on other realizations of orbital impurity problems."}],"arxiv":1,"issue":"23"},{"ec_funded":1,"month":"04","oa":1,"publication_identifier":{"isbn":["978-153860457-1"]},"status":"public","_id":"998","year":"2017","date_updated":"2023-09-22T09:51:58Z","abstract":[{"lang":"eng","text":"A major open problem on the road to artificial intelligence is the development of incrementally learning systems that learn about more and more concepts over time from a stream of data. In this work, we introduce a new training strategy, iCaRL, that allows learning in such a class-incremental way: only the training data for a small number of classes has to be present at the same time and new classes can be added progressively. iCaRL learns strong classifiers and a data representation simultaneously. This distinguishes it from earlier works that were fundamentally limited to fixed data representations and therefore incompatible with deep learning architectures. We show by experiments on CIFAR-100 and ImageNet ILSVRC 2012 data that iCaRL can learn many classes incrementally over a long period of time where other strategies quickly fail. "}],"intvolume":"      2017","citation":{"chicago":"Rebuffi, Sylvestre Alvise, Alexander Kolesnikov, Georg Sperl, and Christoph Lampert. “ICaRL: Incremental Classifier and Representation Learning,” 2017:5533–42. IEEE, 2017. <a href=\"https://doi.org/10.1109/CVPR.2017.587\">https://doi.org/10.1109/CVPR.2017.587</a>.","ista":"Rebuffi SA, Kolesnikov A, Sperl G, Lampert C. 2017. iCaRL: Incremental classifier and representation learning. CVPR: Computer Vision and Pattern Recognition vol. 2017, 5533–5542.","mla":"Rebuffi, Sylvestre Alvise, et al. <i>ICaRL: Incremental Classifier and Representation Learning</i>. Vol. 2017, IEEE, 2017, pp. 5533–42, doi:<a href=\"https://doi.org/10.1109/CVPR.2017.587\">10.1109/CVPR.2017.587</a>.","apa":"Rebuffi, S. A., Kolesnikov, A., Sperl, G., &#38; Lampert, C. (2017). iCaRL: Incremental classifier and representation learning (Vol. 2017, pp. 5533–5542). Presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States: IEEE. <a href=\"https://doi.org/10.1109/CVPR.2017.587\">https://doi.org/10.1109/CVPR.2017.587</a>","ieee":"S. A. Rebuffi, A. Kolesnikov, G. Sperl, and C. Lampert, “iCaRL: Incremental classifier and representation learning,” presented at the CVPR: Computer Vision and Pattern Recognition, Honolulu, HA, United States, 2017, vol. 2017, pp. 5533–5542.","ama":"Rebuffi SA, Kolesnikov A, Sperl G, Lampert C. iCaRL: Incremental classifier and representation learning. In: Vol 2017. IEEE; 2017:5533-5542. doi:<a href=\"https://doi.org/10.1109/CVPR.2017.587\">10.1109/CVPR.2017.587</a>","short":"S.A. Rebuffi, A. Kolesnikov, G. Sperl, C. Lampert, in:, IEEE, 2017, pp. 5533–5542."},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1611.07725"}],"scopus_import":"1","date_published":"2017-04-14T00:00:00Z","oa_version":"Submitted Version","publication_status":"published","conference":{"start_date":"2017-07-21","name":"CVPR: Computer Vision and Pattern Recognition","end_date":"2017-07-26","location":"Honolulu, HA, United States"},"doi":"10.1109/CVPR.2017.587","title":"iCaRL: Incremental classifier and representation learning","publisher":"IEEE","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"grant_number":"308036","_id":"2532554C-B435-11E9-9278-68D0E5697425","name":"Lifelong Learning of Visual Scene Understanding","call_identifier":"FP7"}],"author":[{"full_name":"Rebuffi, Sylvestre Alvise","first_name":"Sylvestre Alvise","last_name":"Rebuffi"},{"first_name":"Alexander","last_name":"Kolesnikov","id":"2D157DB6-F248-11E8-B48F-1D18A9856A87","full_name":"Kolesnikov, Alexander"},{"full_name":"Sperl, Georg","id":"4DD40360-F248-11E8-B48F-1D18A9856A87","last_name":"Sperl","first_name":"Georg"},{"full_name":"Lampert, Christoph","first_name":"Christoph","orcid":"0000-0001-8622-7887","last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"}],"isi":1,"day":"14","external_id":{"isi":["000418371405066"]},"quality_controlled":"1","volume":2017,"publist_id":"6400","article_processing_charge":"No","language":[{"iso":"eng"}],"department":[{"_id":"ChLa"},{"_id":"ChWo"}],"type":"conference","page":"5533 - 5542","date_created":"2018-12-11T11:49:37Z"},{"external_id":{"isi":["000683309502093"]},"quality_controlled":"1","volume":70,"publist_id":"6399","article_processing_charge":"No","type":"conference","language":[{"iso":"eng"}],"department":[{"_id":"ChLa"}],"date_created":"2018-12-11T11:49:37Z","page":"2807 - 2816","alternative_title":["PMLR"],"publisher":"ML Research Press","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Multi-task learning with labeled and unlabeled tasks","project":[{"grant_number":"308036","_id":"2532554C-B435-11E9-9278-68D0E5697425","name":"Lifelong Learning of Visual Scene Understanding","call_identifier":"FP7"}],"author":[{"full_name":"Pentina, Anastasia","first_name":"Anastasia","id":"42E87FC6-F248-11E8-B48F-1D18A9856A87","last_name":"Pentina"},{"last_name":"Lampert","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","first_name":"Christoph","full_name":"Lampert, Christoph"}],"isi":1,"day":"08","intvolume":"        70","citation":{"apa":"Pentina, A., &#38; Lampert, C. (2017). Multi-task learning with labeled and unlabeled tasks (Vol. 70, pp. 2807–2816). Presented at the ICML: International Conference on Machine Learning, Sydney, Australia: ML Research Press.","mla":"Pentina, Anastasia, and Christoph Lampert. <i>Multi-Task Learning with Labeled and Unlabeled Tasks</i>. Vol. 70, ML Research Press, 2017, pp. 2807–16.","ista":"Pentina A, Lampert C. 2017. Multi-task learning with labeled and unlabeled tasks. ICML: International Conference on Machine Learning, PMLR, vol. 70, 2807–2816.","chicago":"Pentina, Anastasia, and Christoph Lampert. “Multi-Task Learning with Labeled and Unlabeled Tasks,” 70:2807–16. ML Research Press, 2017.","ama":"Pentina A, Lampert C. Multi-task learning with labeled and unlabeled tasks. In: Vol 70. ML Research Press; 2017:2807-2816.","ieee":"A. Pentina and C. Lampert, “Multi-task learning with labeled and unlabeled tasks,” presented at the ICML: International Conference on Machine Learning, Sydney, Australia, 2017, vol. 70, pp. 2807–2816.","short":"A. Pentina, C. Lampert, in:, ML Research Press, 2017, pp. 2807–2816."},"scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1602.06518","open_access":"1"}],"oa_version":"Submitted Version","date_published":"2017-06-08T00:00:00Z","publication_status":"published","conference":{"end_date":"2017-08-11","location":"Sydney, Australia","start_date":"2017-08-06","name":"ICML: International Conference on Machine Learning"},"month":"06","ec_funded":1,"status":"public","publication_identifier":{"isbn":["9781510855144"]},"oa":1,"_id":"999","date_updated":"2023-10-17T11:53:32Z","abstract":[{"lang":"eng","text":"In multi-task learning, a learner is given a collection of prediction tasks and needs to solve all of them. In contrast to previous work, which required that annotated training data must be available for all tasks, we consider a new setting, in which for some tasks, potentially most of them, only unlabeled training data is provided. Consequently, to solve all tasks, information must be transferred between tasks with labels and tasks without labels. Focusing on an instance-based transfer method we analyze two variants of this setting: when the set of labeled tasks is fixed, and when it can be actively selected by the learner. We state and prove a generalization bound that covers both scenarios and derive from it an algorithm for making the choice of labeled tasks (in the active case) and for transferring information between the tasks in a principled way. We also illustrate the effectiveness of the algorithm on synthetic and real data. "}],"year":"2017"},{"_id":"424","abstract":[{"text":"We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b, d) such that the following holds. If F is a finite family of subsets of Rd such that βi(∩G)≤b for any G⊊F and every 0 ≤ i ≤ [d/2]-1 then F has Helly number at most h(b, d). Here βi denotes the reduced Z2-Betti numbers (with singular homology). These topological conditions are sharp: not controlling any of these [d/2] first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map C*(K)→C*(Rd).","lang":"eng"}],"date_updated":"2024-02-28T12:59:37Z","year":"2017","month":"10","status":"public","oa":1,"publication_identifier":{"isbn":["978-331944479-6"]},"oa_version":"Published Version","date_published":"2017-10-06T00:00:00Z","doi":"10.1007/978-3-319-44479-6_17","publication_status":"published","citation":{"ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding helly numbers via betti numbers,” in <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>, M. Loebl, J. Nešetřil, and R. Thomas, Eds. Springer, 2017, pp. 407–447.","ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Bounding helly numbers via betti numbers. In: Loebl M, Nešetřil J, Thomas R, eds. <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>. A Journey Through Discrete Mathematics. Springer; 2017:407-447. doi:<a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">10.1007/978-3-319-44479-6_17</a>","short":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, M. Loebl, J. Nešetřil, R. Thomas (Eds.), A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, Springer, 2017, pp. 407–447.","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2017). Bounding helly numbers via betti numbers. In M. Loebl, J. Nešetřil, &#38; R. Thomas (Eds.), <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i> (pp. 407–447). Springer. <a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">https://doi.org/10.1007/978-3-319-44479-6_17</a>","ista":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2017.Bounding helly numbers via betti numbers. In: A Journey through Discrete Mathematics: A Tribute to Jiri Matousek. , 407–447.","mla":"Goaoc, Xavier, et al. “Bounding Helly Numbers via Betti Numbers.” <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>, edited by Martin Loebl et al., Springer, 2017, pp. 407–47, doi:<a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">10.1007/978-3-319-44479-6_17</a>.","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Bounding Helly Numbers via Betti Numbers.” In <i>A Journey through Discrete Mathematics: A Tribute to Jiri Matousek</i>, edited by Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, 407–47. A Journey Through Discrete Mathematics. Springer, 2017. <a href=\"https://doi.org/10.1007/978-3-319-44479-6_17\">https://doi.org/10.1007/978-3-319-44479-6_17</a>."},"main_file_link":[{"url":"https://arxiv.org/abs/1310.4613v3","open_access":"1"}],"scopus_import":1,"author":[{"full_name":"Goaoc, Xavier","last_name":"Goaoc","first_name":"Xavier"},{"last_name":"Paták","first_name":"Pavel","full_name":"Paták, Pavel"},{"full_name":"Patakova, Zuzana","last_name":"Patakova","orcid":"0000-0002-3975-1683","first_name":"Zuzana"},{"last_name":"Tancer","orcid":"0000-0002-1191-6714","first_name":"Martin","full_name":"Tancer, Martin"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner"}],"day":"06","series_title":"A Journey Through Discrete Mathematics","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","publisher":"Springer","title":"Bounding helly numbers via betti numbers","type":"book_chapter","department":[{"_id":"UlWa"}],"language":[{"iso":"eng"}],"publication":"A Journey through Discrete Mathematics: A Tribute to Jiri Matousek","page":"407 - 447","date_created":"2018-12-11T11:46:24Z","quality_controlled":"1","editor":[{"full_name":"Loebl, Martin","first_name":"Martin","last_name":"Loebl"},{"first_name":"Jaroslav","last_name":"Nešetřil","full_name":"Nešetřil, Jaroslav"},{"last_name":"Thomas","first_name":"Robin","full_name":"Thomas, Robin"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"1512"}]},"publist_id":"7399"},{"type":"conference","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"date_created":"2018-12-11T11:46:26Z","page":"1710-1721","external_id":{"arxiv":["1610.02132"]},"quality_controlled":"1","volume":2017,"publist_id":"7392","article_processing_charge":"No","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian"},{"first_name":"Demjan","last_name":"Grubic","full_name":"Grubic, Demjan"},{"first_name":"Jerry","last_name":"Li","full_name":"Li, Jerry"},{"first_name":"Ryota","last_name":"Tomioka","full_name":"Tomioka, Ryota"},{"first_name":"Milan","last_name":"Vojnović","full_name":"Vojnović, Milan"}],"day":"01","alternative_title":["Advances in Neural Information Processing Systems"],"publisher":"Neural Information Processing Systems Foundation","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"QSGD: Communication-efficient SGD via gradient quantization and encoding","oa_version":"Submitted Version","date_published":"2017-01-01T00:00:00Z","conference":{"name":"NIPS: Neural Information Processing System","start_date":"2017-12-04","location":"Long Beach, CA, United States","end_date":"2017-12-09"},"publication_status":"published","intvolume":"      2017","citation":{"ama":"Alistarh D-A, Grubic D, Li J, Tomioka R, Vojnović M. QSGD: Communication-efficient SGD via gradient quantization and encoding. In: Vol 2017. Neural Information Processing Systems Foundation; 2017:1710-1721.","ieee":"D.-A. Alistarh, D. Grubic, J. Li, R. Tomioka, and M. Vojnović, “QSGD: Communication-efficient SGD via gradient quantization and encoding,” presented at the NIPS: Neural Information Processing System, Long Beach, CA, United States, 2017, vol. 2017, pp. 1710–1721.","short":"D.-A. Alistarh, D. Grubic, J. Li, R. Tomioka, M. Vojnović, in:, Neural Information Processing Systems Foundation, 2017, pp. 1710–1721.","mla":"Alistarh, Dan-Adrian, et al. <i>QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding</i>. Vol. 2017, Neural Information Processing Systems Foundation, 2017, pp. 1710–21.","apa":"Alistarh, D.-A., Grubic, D., Li, J., Tomioka, R., &#38; Vojnović, M. (2017). QSGD: Communication-efficient SGD via gradient quantization and encoding (Vol. 2017, pp. 1710–1721). Presented at the NIPS: Neural Information Processing System, Long Beach, CA, United States: Neural Information Processing Systems Foundation.","ista":"Alistarh D-A, Grubic D, Li J, Tomioka R, Vojnović M. 2017. QSGD: Communication-efficient SGD via gradient quantization and encoding. NIPS: Neural Information Processing System, Advances in Neural Information Processing Systems, vol. 2017, 1710–1721.","chicago":"Alistarh, Dan-Adrian, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnović. “QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding,” 2017:1710–21. Neural Information Processing Systems Foundation, 2017."},"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1610.02132"}],"_id":"431","date_updated":"2023-10-17T11:48:03Z","abstract":[{"text":"Parallel implementations of stochastic gradient descent (SGD) have received significant research attention, thanks to its excellent scalability properties. A fundamental barrier when parallelizing SGD is the high bandwidth cost of communicating gradient updates between nodes; consequently, several lossy compresion heuristics have been proposed, by which nodes only communicate quantized gradients. Although effective in practice, these heuristics do not always converge. In this paper, we propose Quantized SGD (QSGD), a family of compression schemes with convergence guarantees and good practical performance. QSGD allows the user to smoothly trade off communication bandwidth and convergence time: nodes can adjust the number of bits sent per iteration, at the cost of possibly higher variance. We show that this trade-off is inherent, in the sense that improving it past some threshold would violate information-theoretic lower bounds. QSGD guarantees convergence for convex and non-convex objectives, under asynchrony, and can be extended to stochastic variance-reduced techniques. When applied to training deep neural networks for image classification and automated speech recognition, QSGD leads to significant reductions in end-to-end training time. For instance, on 16GPUs, we can train the ResNet-152 network to full accuracy on ImageNet 1.8 × faster than the full-precision variant. ","lang":"eng"}],"arxiv":1,"year":"2017","month":"01","status":"public","oa":1,"publication_identifier":{"issn":["10495258"]}},{"page":"4035 - 4043","date_created":"2018-12-11T11:46:26Z","publication":"Proceedings of Machine Learning Research","has_accepted_license":"1","language":[{"iso":"eng"}],"department":[{"_id":"DaAl"}],"type":"conference","publist_id":"7391","article_processing_charge":"No","quality_controlled":"1","volume":" 70","day":"01","file":[{"creator":"dernst","file_id":"5869","checksum":"86156ba7f4318e47cef3eb9092593c10","access_level":"open_access","date_updated":"2020-07-14T12:46:26Z","file_name":"2017_ICML_Zhang.pdf","date_created":"2019-01-22T08:23:58Z","relation":"main_file","content_type":"application/pdf","file_size":849345}],"author":[{"full_name":"Zhang, Hantian","last_name":"Zhang","first_name":"Hantian"},{"full_name":"Li, Jerry","first_name":"Jerry","last_name":"Li"},{"first_name":"Kaan","last_name":"Kara","full_name":"Kara, Kaan"},{"full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian"},{"first_name":"Ji","last_name":"Liu","full_name":"Liu, Ji"},{"last_name":"Zhang","first_name":"Ce","full_name":"Zhang, Ce"}],"title":"ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning","publisher":"ML Research Press","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["PMLR Press"],"conference":{"name":"ICML: International  Conference  on  Machine Learning","start_date":"2017-08-06","location":"Sydney, Australia","end_date":"2017-08-11"},"publication_status":"published","date_published":"2017-01-01T00:00:00Z","oa_version":"Submitted Version","ddc":["000"],"file_date_updated":"2020-07-14T12:46:26Z","scopus_import":"1","citation":{"ieee":"H. Zhang, J. Li, K. Kara, D.-A. Alistarh, J. Liu, and C. Zhang, “ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning,” in <i>Proceedings of Machine Learning Research</i>, Sydney, Australia, 2017, vol. 70, pp. 4035–4043.","ama":"Zhang H, Li J, Kara K, Alistarh D-A, Liu J, Zhang C. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. In: <i>Proceedings of Machine Learning Research</i>. Vol 70. ML Research Press; 2017:4035-4043.","short":"H. Zhang, J. Li, K. Kara, D.-A. Alistarh, J. Liu, C. Zhang, in:, Proceedings of Machine Learning Research, ML Research Press, 2017, pp. 4035–4043.","chicago":"Zhang, Hantian, Jerry Li, Kaan Kara, Dan-Adrian Alistarh, Ji Liu, and Ce Zhang. “ZipML: Training Linear Models with End-to-End Low Precision, and a Little Bit of Deep Learning.” In <i>Proceedings of Machine Learning Research</i>, 70:4035–43. ML Research Press, 2017.","ista":"Zhang H, Li J, Kara K, Alistarh D-A, Liu J, Zhang C. 2017. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. Proceedings of Machine Learning Research. ICML: International  Conference  on  Machine Learning, PMLR Press, vol. 70, 4035–4043.","mla":"Zhang, Hantian, et al. “ZipML: Training Linear Models with End-to-End Low Precision, and a Little Bit of Deep Learning.” <i>Proceedings of Machine Learning Research</i>, vol. 70, ML Research Press, 2017, pp. 4035–43.","apa":"Zhang, H., Li, J., Kara, K., Alistarh, D.-A., Liu, J., &#38; Zhang, C. (2017). ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. In <i>Proceedings of Machine Learning Research</i> (Vol. 70, pp. 4035–4043). Sydney, Australia: ML Research Press."},"year":"2017","date_updated":"2023-10-17T12:31:15Z","abstract":[{"text":"Recently there has been significant interest in training machine-learning models at low precision: by reducing precision, one can reduce computation and communication by one order of magnitude. We examine training at reduced precision, both from a theoretical and practical perspective, and ask: is it possible to train models at end-to-end low precision with provable guarantees? Can this lead to consistent order-of-magnitude speedups? We mainly focus on linear models, and the answer is yes for linear models. We develop a simple framework called ZipML based on one simple but novel strategy called double sampling. Our ZipML framework is able to execute training at low precision with no bias, guaranteeing convergence, whereas naive quanti- zation would introduce significant bias. We val- idate our framework across a range of applica- tions, and show that it enables an FPGA proto- type that is up to 6.5 × faster than an implemen- tation using full 32-bit precision. We further de- velop a variance-optimal stochastic quantization strategy and show that it can make a significant difference in a variety of settings. When applied to linear models together with double sampling, we save up to another 1.7 × in data movement compared with uniform quantization. When training deep networks with quantized models, we achieve higher accuracy than the state-of-the- art XNOR-Net. ","lang":"eng"}],"_id":"432","publication_identifier":{"isbn":["978-151085514-4"]},"oa":1,"status":"public","month":"01"},{"publist_id":"7379","quality_controlled":"1","editor":[{"full_name":"Wikström, Mårten","first_name":"Mårten","last_name":"Wikström"}],"citation":{"apa":"Sazanov, L. A. (2017). Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions. In M. Wikström (Ed.), <i>Mechanisms of primary energy transduction in biology </i> (pp. 25–59). Royal Society of Chemistry. <a href=\"https://doi.org/10.1039/9781788010405-00025\">https://doi.org/10.1039/9781788010405-00025</a>","mla":"Sazanov, Leonid A. “Structure of Respiratory Complex I: ‘Minimal’ Bacterial and ‘de Luxe’ Mammalian Versions.” <i>Mechanisms of Primary Energy Transduction in Biology </i>, edited by Mårten Wikström, Royal Society of Chemistry, 2017, pp. 25–59, doi:<a href=\"https://doi.org/10.1039/9781788010405-00025\">10.1039/9781788010405-00025</a>.","ista":"Sazanov LA. 2017.Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions. In: Mechanisms of primary energy transduction in biology . , 25–59.","chicago":"Sazanov, Leonid A. “Structure of Respiratory Complex I: ‘Minimal’ Bacterial and ‘de Luxe’ Mammalian Versions.” In <i>Mechanisms of Primary Energy Transduction in Biology </i>, edited by Mårten Wikström, 25–59. Mechanisms of Primary Energy Transduction in Biology . Royal Society of Chemistry, 2017. <a href=\"https://doi.org/10.1039/9781788010405-00025\">https://doi.org/10.1039/9781788010405-00025</a>.","ieee":"L. A. Sazanov, “Structure of respiratory complex I: ‘Minimal’ bacterial and ‘de luxe’ mammalian versions,” in <i>Mechanisms of primary energy transduction in biology </i>, M. Wikström, Ed. Royal Society of Chemistry, 2017, pp. 25–59.","ama":"Sazanov LA. Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions. In: Wikström M, ed. <i>Mechanisms of Primary Energy Transduction in Biology </i>. Mechanisms of Primary Energy Transduction in Biology . Royal Society of Chemistry; 2017:25-59. doi:<a href=\"https://doi.org/10.1039/9781788010405-00025\">10.1039/9781788010405-00025</a>","short":"L.A. Sazanov, in:, M. Wikström (Ed.), Mechanisms of Primary Energy Transduction in Biology , Royal Society of Chemistry, 2017, pp. 25–59."},"publication":"Mechanisms of primary energy transduction in biology ","page":"25 - 59","date_created":"2018-12-11T11:46:30Z","doi":"10.1039/9781788010405-00025","publication_status":"published","department":[{"_id":"LeSa"}],"date_published":"2017-11-29T00:00:00Z","language":[{"iso":"eng"}],"oa_version":"None","type":"book_chapter","publication_identifier":{"isbn":["978-1-78262-865-1"]},"title":"Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Royal Society of Chemistry","status":"public","series_title":"Mechanisms of Primary Energy Transduction in Biology ","month":"11","year":"2017","day":"29","abstract":[{"lang":"eng","text":"Complex I (NADH:ubiquinone oxidoreductase) plays a central role in cellular energy generation, contributing to the proton motive force used to produce ATP. It couples the transfer of two electrons between NADH and quinone to translocation of four protons across the membrane. It is the largest protein assembly of bacterial and mitochondrial respiratory chains, composed, in mammals, of up to 45 subunits with a total molecular weight of ∼1 MDa. Bacterial enzyme is about half the size, providing the important “minimal” model of complex I. The l-shaped complex consists of a hydrophilic arm, where electron transfer occurs, and a membrane arm, where proton translocation takes place. Previously, we have solved the crystal structures of the hydrophilic domain of complex I from Thermus thermophilus and of the membrane domain from Escherichia coli, followed by the atomic structure of intact, entire complex I from T. thermophilus. Recently, we have solved by cryo-EM a first complete atomic structure of mammalian (ovine) mitochondrial complex I. Core subunits are well conserved from the bacterial version, whilst supernumerary subunits form an interlinked, stabilizing shell around the core. Subunits containing additional cofactors, including Zn ion, NADPH and phosphopantetheine, probably have regulatory roles. Dysfunction of mitochondrial complex I is implicated in many human neurodegenerative diseases. The structure of mammalian enzyme provides many insights into complex I mechanism, assembly, maturation and dysfunction, allowing detailed molecular analysis of disease-causing mutations."}],"date_updated":"2021-01-12T07:56:59Z","_id":"444","author":[{"full_name":"Sazanov, Leonid A","id":"338D39FE-F248-11E8-B48F-1D18A9856A87","last_name":"Sazanov","orcid":"0000-0002-0977-7989","first_name":"Leonid A"}]},{"scopus_import":"1","main_file_link":[{"url":"http://alea.impa.br/articles/v14/14-17.pdf","open_access":"1"}],"citation":{"short":"P. Ferrari, P. Nejjar, Revista Latino-Americana de Probabilidade e Estatística 9 (2017) 299–325.","ieee":"P. Ferrari and P. Nejjar, “Fluctuations of the competition interface in presence of shocks,” <i>Revista Latino-Americana de Probabilidade e Estatística</i>, vol. 9. Instituto Nacional de Matematica Pura e Aplicada, pp. 299–325, 2017.","ama":"Ferrari P, Nejjar P. Fluctuations of the competition interface in presence of shocks. <i>Revista Latino-Americana de Probabilidade e Estatística</i>. 2017;9:299-325. doi:<a href=\"https://doi.org/10.30757/ALEA.v14-17\">10.30757/ALEA.v14-17</a>","chicago":"Ferrari, Patrik, and Peter Nejjar. “Fluctuations of the Competition Interface in Presence of Shocks.” <i>Revista Latino-Americana de Probabilidade e Estatística</i>. Instituto Nacional de Matematica Pura e Aplicada, 2017. <a href=\"https://doi.org/10.30757/ALEA.v14-17\">https://doi.org/10.30757/ALEA.v14-17</a>.","apa":"Ferrari, P., &#38; Nejjar, P. (2017). Fluctuations of the competition interface in presence of shocks. <i>Revista Latino-Americana de Probabilidade e Estatística</i>. Instituto Nacional de Matematica Pura e Aplicada. <a href=\"https://doi.org/10.30757/ALEA.v14-17\">https://doi.org/10.30757/ALEA.v14-17</a>","ista":"Ferrari P, Nejjar P. 2017. Fluctuations of the competition interface in presence of shocks. Revista Latino-Americana de Probabilidade e Estatística. 9, 299–325.","mla":"Ferrari, Patrik, and Peter Nejjar. “Fluctuations of the Competition Interface in Presence of Shocks.” <i>Revista Latino-Americana de Probabilidade e Estatística</i>, vol. 9, Instituto Nacional de Matematica Pura e Aplicada, 2017, pp. 299–325, doi:<a href=\"https://doi.org/10.30757/ALEA.v14-17\">10.30757/ALEA.v14-17</a>."},"intvolume":"         9","doi":"10.30757/ALEA.v14-17","publication_status":"published","oa_version":"Submitted Version","date_published":"2017-03-23T00:00:00Z","status":"public","oa":1,"month":"03","ec_funded":1,"abstract":[{"lang":"eng","text":"We consider last passage percolation (LPP) models with exponentially distributed random variables, which are linked to the totally asymmetric simple exclusion process (TASEP). The competition interface for LPP was introduced and studied in Ferrari and Pimentel (2005a) for cases where the corresponding exclusion process had a rarefaction fan. Here we consider situations with a shock and determine the law of the fluctuations of the competition interface around its deter- ministic law of large number position. We also study the multipoint distribution of the LPP around the shock, extending our one-point result of Ferrari and Nejjar (2015)."}],"date_updated":"2023-10-10T13:10:32Z","year":"2017","_id":"447","article_type":"original","article_processing_charge":"No","publist_id":"7376","quality_controlled":"1","volume":9,"publication":"Revista Latino-Americana de Probabilidade e Estatística","page":"299 - 325","date_created":"2018-12-11T11:46:31Z","type":"journal_article","department":[{"_id":"LaEr"},{"_id":"JaMa"}],"language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Instituto Nacional de Matematica Pura e Aplicada","title":"Fluctuations of the competition interface in presence of shocks","day":"23","author":[{"last_name":"Ferrari","first_name":"Patrik","full_name":"Ferrari, Patrik"},{"id":"4BF426E2-F248-11E8-B48F-1D18A9856A87","last_name":"Nejjar","first_name":"Peter","full_name":"Nejjar, Peter"}],"project":[{"name":"Random matrices, universality and disordered quantum systems","call_identifier":"FP7","grant_number":"338804","_id":"258DCDE6-B435-11E9-9278-68D0E5697425"}]},{"_id":"453","abstract":[{"text":"Most kinesin motors move in only one direction along microtubules. Members of the kinesin-5 subfamily were initially described as unidirectional plus-end-directed motors and shown to produce piconewton forces. However, some fungal kinesin-5 motors are bidirectional. The force production of a bidirectional kinesin-5 has not yet been measured. Therefore, it remains unknown whether the mechanism of the unconventional minus-end-directed motility differs fundamentally from that of plus-end-directed stepping. Using force spectroscopy, we have measured here the forces that ensembles of purified budding yeast kinesin-5 Cin8 produce in microtubule gliding assays in both plus- and minus-end direction. Correlation analysis of pause forces demonstrated that individual Cin8 molecules produce additive forces in both directions of movement. In ensembles, Cin8 motors were able to produce single-motor forces up to a magnitude of ∼1.5 pN. Hence, these properties appear to be conserved within the kinesin-5 subfamily. Force production was largely independent of the directionality of movement, indicating similarities between the motility mechanisms for both directions. These results provide constraints for the development of models for the bidirectional motility mechanism of fission yeast kinesin-5 and provide insight into the function of this mitotic motor.","lang":"eng"}],"issue":"9","date_updated":"2021-01-12T07:59:28Z","year":"2017","month":"11","status":"public","oa":1,"oa_version":"Published Version","date_published":"2017-11-07T00:00:00Z","doi":"10.1016/j.bpj.2017.09.006","publication_status":"published","citation":{"ama":"Fallesen T, Roostalu J, Düllberg CF, Pruessner G, Surrey T. Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement. <i>Biophysical Journal</i>. 2017;113(9):2055-2067. doi:<a href=\"https://doi.org/10.1016/j.bpj.2017.09.006\">10.1016/j.bpj.2017.09.006</a>","ieee":"T. Fallesen, J. Roostalu, C. F. Düllberg, G. Pruessner, and T. Surrey, “Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement,” <i>Biophysical Journal</i>, vol. 113, no. 9. Biophysical Society, pp. 2055–2067, 2017.","short":"T. Fallesen, J. Roostalu, C.F. Düllberg, G. Pruessner, T. Surrey, Biophysical Journal 113 (2017) 2055–2067.","chicago":"Fallesen, Todd, Johanna Roostalu, Christian F Düllberg, Gunnar Pruessner, and Thomas Surrey. “Ensembles of Bidirectional Kinesin Cin8 Produce Additive Forces in Both Directions of Movement.” <i>Biophysical Journal</i>. Biophysical Society, 2017. <a href=\"https://doi.org/10.1016/j.bpj.2017.09.006\">https://doi.org/10.1016/j.bpj.2017.09.006</a>.","apa":"Fallesen, T., Roostalu, J., Düllberg, C. F., Pruessner, G., &#38; Surrey, T. (2017). Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement. <i>Biophysical Journal</i>. Biophysical Society. <a href=\"https://doi.org/10.1016/j.bpj.2017.09.006\">https://doi.org/10.1016/j.bpj.2017.09.006</a>","mla":"Fallesen, Todd, et al. “Ensembles of Bidirectional Kinesin Cin8 Produce Additive Forces in Both Directions of Movement.” <i>Biophysical Journal</i>, vol. 113, no. 9, Biophysical Society, 2017, pp. 2055–67, doi:<a href=\"https://doi.org/10.1016/j.bpj.2017.09.006\">10.1016/j.bpj.2017.09.006</a>.","ista":"Fallesen T, Roostalu J, Düllberg CF, Pruessner G, Surrey T. 2017. Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement. Biophysical Journal. 113(9), 2055–2067."},"intvolume":"       113","file_date_updated":"2020-07-14T12:46:31Z","ddc":["570"],"author":[{"full_name":"Fallesen, Todd","first_name":"Todd","last_name":"Fallesen"},{"last_name":"Roostalu","first_name":"Johanna","full_name":"Roostalu, Johanna"},{"id":"459064DC-F248-11E8-B48F-1D18A9856A87","last_name":"Düllberg","first_name":"Christian F","orcid":"0000-0001-6335-9748","full_name":"Düllberg, Christian F"},{"first_name":"Gunnar","last_name":"Pruessner","full_name":"Pruessner, Gunnar"},{"last_name":"Surrey","first_name":"Thomas","full_name":"Surrey, Thomas"}],"file":[{"access_level":"open_access","file_id":"5052","creator":"system","checksum":"99a2474088e20ac74b1882c4fbbb45b1","date_created":"2018-12-12T10:14:03Z","date_updated":"2020-07-14T12:46:31Z","file_name":"IST-2018-965-v1+1_2017_Duellberg_Ensembles_of.pdf","file_size":977192,"relation":"main_file","content_type":"application/pdf"}],"acknowledgement":"The plasmid for full-length kinesin-1 was a gift from G. Holzwarth and J. Macosko with permission from J. Howard. We thank I. Lueke and N. I. Cade for technical assistance. G.P. thanks the Francis Crick Institute, and in particular the Surrey and Salbreux groups, for their hospitality during his sabbatical stay, as well as Imperial College London for making it possible. This work was supported by the Francis Crick Institute, which receives its core funding from Cancer Research UK (FC001163), the United Kingdom Medical Research Council (FC001163), and the Wellcome Trust (FC001163), and by Imperial College London. J.R. was also supported by a Sir Henry Wellcome Postdoctoral Fellowship (100145/Z/12/Z) and T.S. by the European Research Council (Advanced Grant, project 323042). ","day":"07","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Biophysical Society","title":"Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement","type":"journal_article","department":[{"_id":"MaLo"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","publication":"Biophysical Journal","date_created":"2018-12-11T11:46:33Z","page":"2055 - 2067","quality_controlled":"1","volume":113,"article_type":"original","article_processing_charge":"No","pubrep_id":"965","publist_id":"7369"},{"title":"Conditionally optimal algorithms for generalized Büchi Games","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","license":"https://creativecommons.org/licenses/by/3.0/","alternative_title":["LIPIcs"],"tmp":{"name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","short":"CC BY (3.0)","image":"/images/cc_by.png"},"day":"01","acknowledgement":"K. C., M. H., and W. D. are partially supported by the Vienna Science and Technology Fund (WWTF) through project ICT15-003. K. C. is partially supported by the Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE) and an ERC Start grant (279307","file":[{"date_updated":"2018-12-12T10:16:02Z","file_name":"IST-2017-779-v1+1_LIPIcs-MFCS-2016-25.pdf","date_created":"2018-12-12T10:16:02Z","file_id":"5187","creator":"system","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_size":632786}],"author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu"},{"full_name":"Dvorák, Wolfgang","last_name":"Dvorák","first_name":"Wolfgang"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"Loitzenbauer, Veronika","first_name":"Veronika","last_name":"Loitzenbauer"}],"project":[{"name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"}],"pubrep_id":"779","article_processing_charge":"No","publist_id":"6317","volume":58,"quality_controlled":"1","date_created":"2018-12-11T11:49:58Z","has_accepted_license":"1","department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"type":"conference","oa":1,"status":"public","ec_funded":1,"month":"08","year":"2016","abstract":[{"text":"Games on graphs provide the appropriate framework to study several central problems in computer science, such as verification and synthesis of reactive systems. One of the most basic objectives for games on graphs is the liveness (or Büchi) objective that given a target set of vertices requires that some vertex in the target set is visited infinitely often. We study generalized Büchi objectives (i.e., conjunction of liveness objectives), and implications between two generalized Büchi objectives (known as GR(1) objectives), that arise in numerous applications in computer-aided verification. We present improved algorithms and conditional super-linear lower bounds based on widely believed assumptions about the complexity of (A1) combinatorial Boolean matrix multiplication and (A2) CNF-SAT. We consider graph games with n vertices, m edges, and generalized Büchi objectives with k conjunctions. First, we present an algorithm with running time O(k*n^2), improving the previously known O(k*n*m) and O(k^2*n^2) worst-case bounds. Our algorithm is optimal for dense graphs under (A1). Second, we show that the basic algorithm for the problem is optimal for sparse graphs when the target sets have constant size under (A2). Finally, we consider GR(1) objectives, with k_1 conjunctions in the antecedent and k_2 conjunctions in the consequent, and present an O(k_1 k_2 n^{2.5})-time algorithm, improving the previously known O(k_1*k_2*n*m)-time algorithm for m &gt; n^{1.5}. ","lang":"eng"}],"date_updated":"2025-06-02T08:53:50Z","_id":"1068","article_number":"25","ddc":["000","004","006"],"file_date_updated":"2018-12-12T10:16:02Z","scopus_import":"1","citation":{"ama":"Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. Conditionally optimal algorithms for generalized Büchi Games. In: Vol 58. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2016.25\">10.4230/LIPIcs.MFCS.2016.25</a>","ieee":"K. Chatterjee, W. Dvorák, M. H. Henzinger, and V. Loitzenbauer, “Conditionally optimal algorithms for generalized Büchi Games,” presented at the MFCS: Mathematical Foundations of Computer Science (SG), Krakow, Poland, 2016, vol. 58.","short":"K. Chatterjee, W. Dvorák, M.H. Henzinger, V. Loitzenbauer, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.","chicago":"Chatterjee, Krishnendu, Wolfgang Dvorák, Monika H Henzinger, and Veronika Loitzenbauer. “Conditionally Optimal Algorithms for Generalized Büchi Games,” Vol. 58. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2016.25\">https://doi.org/10.4230/LIPIcs.MFCS.2016.25</a>.","mla":"Chatterjee, Krishnendu, et al. <i>Conditionally Optimal Algorithms for Generalized Büchi Games</i>. Vol. 58, 25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2016.25\">10.4230/LIPIcs.MFCS.2016.25</a>.","ista":"Chatterjee K, Dvorák W, Henzinger MH, Loitzenbauer V. 2016. Conditionally optimal algorithms for generalized Büchi Games. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 58, 25.","apa":"Chatterjee, K., Dvorák, W., Henzinger, M. H., &#38; Loitzenbauer, V. (2016). Conditionally optimal algorithms for generalized Büchi Games (Vol. 58). Presented at the MFCS: Mathematical Foundations of Computer Science (SG), Krakow, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2016.25\">https://doi.org/10.4230/LIPIcs.MFCS.2016.25</a>"},"intvolume":"        58","doi":"10.4230/LIPIcs.MFCS.2016.25","publication_status":"published","conference":{"end_date":"2016-08-26","location":"Krakow, Poland","start_date":"2016-08-22","name":"MFCS: Mathematical Foundations of Computer Science (SG)"},"date_published":"2016-08-01T00:00:00Z","oa_version":"Published Version"},{"citation":{"mla":"Chonev, Ventsislav K., et al. <i>On the Skolem Problem for Continuous Linear Dynamical Systems</i>. Vol. 55, 100, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2016.100\">10.4230/LIPIcs.ICALP.2016.100</a>.","apa":"Chonev, V. K., Ouaknine, J., &#38; Worrell, J. (2016). On the skolem problem for continuous linear dynamical systems (Vol. 55). Presented at the ICALP: Automata, Languages and Programming, Rome, Italy: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2016.100\">https://doi.org/10.4230/LIPIcs.ICALP.2016.100</a>","ista":"Chonev VK, Ouaknine J, Worrell J. 2016. On the skolem problem for continuous linear dynamical systems. ICALP: Automata, Languages and Programming, LIPIcs, vol. 55, 100.","chicago":"Chonev, Ventsislav K, Joël Ouaknine, and James Worrell. “On the Skolem Problem for Continuous Linear Dynamical Systems,” Vol. 55. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2016.100\">https://doi.org/10.4230/LIPIcs.ICALP.2016.100</a>.","short":"V.K. Chonev, J. Ouaknine, J. Worrell, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016.","ama":"Chonev VK, Ouaknine J, Worrell J. On the skolem problem for continuous linear dynamical systems. In: Vol 55. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik; 2016. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2016.100\">10.4230/LIPIcs.ICALP.2016.100</a>","ieee":"V. K. Chonev, J. Ouaknine, and J. Worrell, “On the skolem problem for continuous linear dynamical systems,” presented at the ICALP: Automata, Languages and Programming, Rome, Italy, 2016, vol. 55."},"intvolume":"        55","file_date_updated":"2018-12-12T10:16:26Z","scopus_import":1,"ddc":["004","006"],"oa_version":"Published Version","date_published":"2016-08-01T00:00:00Z","conference":{"start_date":"2016-07-12","name":"ICALP: Automata, Languages and Programming","end_date":"2016-07-15","location":"Rome, Italy"},"publication_status":"published","doi":"10.4230/LIPIcs.ICALP.2016.100","month":"08","ec_funded":1,"status":"public","oa":1,"article_number":"100","_id":"1069","date_updated":"2021-01-12T06:48:03Z","abstract":[{"lang":"eng","text":"The Continuous Skolem Problem asks whether a real-valued function satisfying a linear differen-\r\ntial equation has a zero in a given interval of real numbers. This is a fundamental reachability\r\nproblem for continuous linear dynamical systems, such as linear hybrid automata and continuous-\r\ntime Markov chains. Decidability of the problem is currently open – indeed decidability is open\r\neven for the sub-problem in which a zero is sought in a bounded interval. In this paper we show\r\ndecidability of the bounded problem subject to Schanuel’s Conjecture, a unifying conjecture in\r\ntranscendental number theory. We furthermore analyse the unbounded problem in terms of the\r\nfrequencies of the differential equation, that is, the imaginary parts of the characteristic roots.\r\nWe show that the unbounded problem can be reduced to the bounded problem if there is at most\r\none rationally linearly independent frequency, or if there are two rationally linearly independent\r\nfrequencies and all characteristic roots are simple. We complete the picture by showing that de-\r\ncidability of the unbounded problem in the case of two (or more) rationally linearly independent\r\nfrequencies would entail a major new effectiveness result in Diophantine approximation, namely\r\ncomputability of the Diophantine-approximation types of all real algebraic numbers."}],"year":"2016","volume":55,"quality_controlled":"1","publist_id":"6314","pubrep_id":"778","type":"conference","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"has_accepted_license":"1","date_created":"2018-12-11T11:49:59Z","alternative_title":["LIPIcs"],"publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","title":"On the skolem problem for continuous linear dynamical systems","project":[{"name":"Rigorous Systems Engineering","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425"}],"author":[{"first_name":"Ventsislav K","last_name":"Chonev","id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87","full_name":"Chonev, Ventsislav K"},{"full_name":"Ouaknine, Joël","last_name":"Ouaknine","first_name":"Joël"},{"first_name":"James","last_name":"Worrell","full_name":"Worrell, James"}],"file":[{"file_size":521415,"relation":"main_file","content_type":"application/pdf","date_created":"2018-12-12T10:16:26Z","file_name":"IST-2017-778-v1+1_LIPIcs-ICALP-2016-100.pdf","date_updated":"2018-12-12T10:16:26Z","access_level":"open_access","creator":"system","file_id":"5213"}],"acknowledgement":"Ventsislav Chonev is supported by Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Start grant (279307:  Graph Games), and ERC Advanced Grant (267989: QUAREM).","day":"01","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"}},{"volume":55,"quality_controlled":"1","pubrep_id":"812","publist_id":"6313","type":"conference","department":[{"_id":"KrCh"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","date_created":"2018-12-11T11:49:59Z","alternative_title":["LIPIcs"],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik","title":"Computation tree logic for synchronization properties","author":[{"full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"}],"project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003"}],"file":[{"content_type":"application/pdf","relation":"main_file","file_size":546133,"file_name":"IST-2017-812-v1+1_LIPIcs-ICALP-2016-98.pdf","date_updated":"2018-12-12T10:08:52Z","date_created":"2018-12-12T10:08:52Z","file_id":"4714","creator":"system","access_level":"open_access"}],"acknowledgement":"This research was partially supported by Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE), ERC Start grant (279307: Graph Games), Vienna Science and Technology Fund (WWTF) through project ICT15-003, and European project Cassting (FP7-601148).\r\n\r\nWe thank Stefan Göller and anonymous reviewers for their insightful\r\ncomments and suggestions.\r\n","day":"01","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"citation":{"short":"K. Chatterjee, L. Doyen, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016.","ama":"Chatterjee K, Doyen L. Computation tree logic for synchronization properties. In: Vol 55. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik; 2016. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2016.98\">10.4230/LIPIcs.ICALP.2016.98</a>","ieee":"K. Chatterjee and L. Doyen, “Computation tree logic for synchronization properties,” presented at the ICALP: Automata, Languages and Programming, Rome, Italy, 2016, vol. 55.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Computation Tree Logic for Synchronization Properties,” Vol. 55. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2016.98\">https://doi.org/10.4230/LIPIcs.ICALP.2016.98</a>.","apa":"Chatterjee, K., &#38; Doyen, L. (2016). Computation tree logic for synchronization properties (Vol. 55). Presented at the ICALP: Automata, Languages and Programming, Rome, Italy: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2016.98\">https://doi.org/10.4230/LIPIcs.ICALP.2016.98</a>","ista":"Chatterjee K, Doyen L. 2016. Computation tree logic for synchronization properties. ICALP: Automata, Languages and Programming, LIPIcs, vol. 55, 98.","mla":"Chatterjee, Krishnendu, and Laurent Doyen. <i>Computation Tree Logic for Synchronization Properties</i>. Vol. 55, 98, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ICALP.2016.98\">10.4230/LIPIcs.ICALP.2016.98</a>."},"intvolume":"        55","scopus_import":1,"file_date_updated":"2018-12-12T10:08:52Z","ddc":["005"],"oa_version":"Published Version","date_published":"2016-01-01T00:00:00Z","doi":"10.4230/LIPIcs.ICALP.2016.98","publication_status":"published","conference":{"start_date":"2016-07-12","name":"ICALP: Automata, Languages and Programming","end_date":"2016-07-15","location":"Rome, Italy"},"month":"01","ec_funded":1,"status":"public","oa":1,"article_number":"98","_id":"1070","abstract":[{"lang":"eng","text":"We present a logic that extends CTL (Computation Tree Logic) with operators that express synchronization properties. A property is synchronized in a system if it holds in all paths of a certain length. The new logic is obtained by using the same path quantifiers and temporal operators as in CTL, but allowing a different order of the quantifiers. This small syntactic variation induces a logic that can express non-regular properties for which known extensions of MSO with equality of path length are undecidable. We show that our variant of CTL is decidable and that the model-checking problem is in Delta_3^P = P^{NP^NP}, and is DP-hard. We analogously consider quantifier exchange in extensions of CTL, and we present operators defined using basic operators of CTL* that express the occurrence of infinitely many synchronization points. We show that the model-checking problem remains in Delta_3^P. The distinguishing power of CTL and of our new logic coincide if the Next operator is allowed in the logics, thus the classical bisimulation quotient can be used for state-space reduction before model checking. "}],"date_updated":"2021-01-12T06:48:03Z","year":"2016"},{"date_created":"2018-12-11T11:49:59Z","has_accepted_license":"1","language":[{"iso":"eng"}],"department":[{"_id":"KrCh"}],"type":"conference","publist_id":"6312","pubrep_id":"777","related_material":{"record":[{"id":"821","relation":"dissertation_contains","status":"public"}]},"volume":57,"quality_controlled":"1","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"day":"01","acknowledgement":"The research was partly supported by Austrian Science Fund (FWF) Grant No P23499-N23, FWF NFN Grant No S11407-N23 (RiSE/SHiNE) and ERC Start grant (279307: Graph Games).","file":[{"date_updated":"2018-12-12T10:14:31Z","file_name":"IST-2017-777-v1+1_LIPIcs-ESA-2016-28.pdf","date_created":"2018-12-12T10:14:31Z","creator":"system","file_id":"5084","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_size":579225}],"project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425"}],"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"full_name":"Ibsen-Jensen, Rasmus","id":"3B699956-F248-11E8-B48F-1D18A9856A87","last_name":"Ibsen-Jensen","orcid":"0000-0003-4783-0389","first_name":"Rasmus"},{"last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas"}],"title":"Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","alternative_title":["LIPIcs"],"conference":{"name":"ESA: European Symposium on Algorithms","start_date":"2016-08-22","location":"Aarhus, Denmark","end_date":"2016-08-24"},"publication_status":"published","doi":"10.4230/LIPIcs.ESA.2016.28","date_published":"2016-08-01T00:00:00Z","oa_version":"Published Version","ddc":["004","006"],"scopus_import":1,"file_date_updated":"2018-12-12T10:14:31Z","citation":{"ieee":"K. Chatterjee, R. Ibsen-Jensen, and A. Pavlogiannis, “Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs,” presented at the ESA: European Symposium on Algorithms, Aarhus, Denmark, 2016, vol. 57.","ama":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs. In: Vol 57. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik; 2016. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2016.28\">10.4230/LIPIcs.ESA.2016.28</a>","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016.","mla":"Chatterjee, Krishnendu, et al. <i>Optimal Reachability and a Space Time Tradeoff for Distance Queries in Constant Treewidth Graphs</i>. Vol. 57, 28, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2016.28\">10.4230/LIPIcs.ESA.2016.28</a>.","ista":"Chatterjee K, Ibsen-Jensen R, Pavlogiannis A. 2016. Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs. ESA: European Symposium on Algorithms, LIPIcs, vol. 57, 28.","apa":"Chatterjee, K., Ibsen-Jensen, R., &#38; Pavlogiannis, A. (2016). Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs (Vol. 57). Presented at the ESA: European Symposium on Algorithms, Aarhus, Denmark: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2016.28\">https://doi.org/10.4230/LIPIcs.ESA.2016.28</a>","chicago":"Chatterjee, Krishnendu, Rasmus Ibsen-Jensen, and Andreas Pavlogiannis. “Optimal Reachability and a Space Time Tradeoff for Distance Queries in Constant Treewidth Graphs,” Vol. 57. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2016.28\">https://doi.org/10.4230/LIPIcs.ESA.2016.28</a>."},"intvolume":"        57","year":"2016","date_updated":"2023-09-07T12:01:58Z","abstract":[{"lang":"eng","text":"We consider data-structures for answering reachability and distance queries on constant-treewidth graphs with n nodes, on the standard RAM computational model with wordsize W=Theta(log n). Our first contribution is a data-structure that after O(n) preprocessing time, allows (1) pair reachability queries in O(1) time; and (2) single-source reachability queries in O(n/log n) time. This is (asymptotically) optimal and is faster than DFS/BFS when answering more than a constant number of single-source queries. The data-structure uses at all times O(n) space. Our second contribution is a space-time tradeoff data-structure for distance queries. For any epsilon in [1/2,1], we provide a data-structure with polynomial preprocessing time that allows pair queries in O(n^{1-\\epsilon} alpha(n)) time, where alpha is the inverse of the Ackermann function, and at all times uses O(n^epsilon) space. The input graph G is not considered in the space complexity. "}],"_id":"1071","article_number":"28","oa":1,"status":"public","ec_funded":1,"month":"08"},{"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"Nature Publishing Group","title":"Cellular mechanisms for cargo delivery and polarity maintenance at different polar domains in plant cells","acknowledgement":"We thank Bonnie Bartel, Jenny Russinova and Niko Geldner\r\nfor sharing published material, Martine de Cock and Annick\r\nBleys for help in preparing the manuscript. This work was\r\nsupported by the European Research Council (project\r\nERC-2011-StG-20101109-PSDP); Czech Science Foundation\r\nGAČR (GA13-40637S); project CEITEC—Central European\r\nInstitute of Technology (CZ.1.05/1.1.00/02.0068). SV is a\r\npostdoctoral fellow of the Research Foundation-Flanders.\r\nSN is a Project Assistant Professor supported by the Japanese\r\nSociety for the Promotion of Science (JSPS; 30612022 to SN),\r\nthe NC-CARP project of the Ministry of Education, Culture,\r\nSports, Science and Technology in Japan to SN.","day":"19","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"author":[{"full_name":"Łangowski, Łukasz","first_name":"Łukasz","last_name":"Łangowski"},{"last_name":"Wabnik","id":"4DE369A4-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof T","orcid":"0000-0001-7263-0560","full_name":"Wabnik, Krzysztof T"},{"full_name":"Li, Hongjiang","last_name":"Li","id":"33CA54A6-F248-11E8-B48F-1D18A9856A87","first_name":"Hongjiang","orcid":"0000-0001-5039-9660"},{"full_name":"Vanneste, Steffen","last_name":"Vanneste","first_name":"Steffen"},{"last_name":"Naramoto","first_name":"Satoshi","full_name":"Naramoto, Satoshi"},{"last_name":"Tanaka","first_name":"Hirokazu","full_name":"Tanaka, Hirokazu"},{"id":"4159519E-F248-11E8-B48F-1D18A9856A87","last_name":"Friml","first_name":"Jirí","orcid":"0000-0002-8302-7596","full_name":"Friml, Jirí"}],"project":[{"call_identifier":"FP7","name":"Polarity and subcellular dynamics in plants","_id":"25716A02-B435-11E9-9278-68D0E5697425","grant_number":"282300"}],"file":[{"relation":"main_file","content_type":"application/pdf","file_size":5261671,"file_name":"IST-2017-757-v1+1_celldisc201618.pdf","date_updated":"2018-12-12T10:13:33Z","date_created":"2018-12-12T10:13:33Z","file_id":"5017","creator":"system","access_level":"open_access"}],"pubrep_id":"757","publist_id":"6299","quality_controlled":"1","volume":2,"has_accepted_license":"1","publication":"Cell Discovery","date_created":"2018-12-11T11:50:02Z","type":"journal_article","department":[{"_id":"EvBe"},{"_id":"JiFr"}],"language":[{"iso":"eng"}],"status":"public","oa":1,"month":"07","ec_funded":1,"abstract":[{"text":"The asymmetric localization of proteins in the plasma membrane domains of eukaryotic cells is a fundamental manifestation of cell polarity that is central to multicellular organization and developmental patterning. In plants, the mechanisms underlying the polar localization of cargo proteins are still largely unknown and appear to be fundamentally distinct from those operating in mammals. Here, we present a systematic, quantitative comparative analysis of the polar delivery and subcellular localization of proteins that characterize distinct polar plasma membrane domains in plant cells. The combination of microscopic analyses and computational modeling revealed a mechanistic framework common to diverse polar cargos and underlying the establishment and maintenance of apical, basal, and lateral polar domains in plant cells. This mechanism depends on the polar secretion, constitutive endocytic recycling, and restricted lateral diffusion of cargos within the plasma membrane. Moreover, our observations suggest that polar cargo distribution involves the individual protein potential to form clusters within the plasma membrane and interact with the extracellular matrix. Our observations provide insights into the shared cellular mechanisms of polar cargo delivery and polarity maintenance in plant cells.","lang":"eng"}],"date_updated":"2021-01-12T06:48:08Z","year":"2016","article_number":"16018","_id":"1081","file_date_updated":"2018-12-12T10:13:33Z","scopus_import":1,"ddc":["580"],"intvolume":"         2","citation":{"ista":"Łangowski Ł, Wabnik KT, Li H, Vanneste S, Naramoto S, Tanaka H, Friml J. 2016. Cellular mechanisms for cargo delivery and polarity maintenance at different polar domains in plant cells. Cell Discovery. 2, 16018.","apa":"Łangowski, Ł., Wabnik, K. T., Li, H., Vanneste, S., Naramoto, S., Tanaka, H., &#38; Friml, J. (2016). Cellular mechanisms for cargo delivery and polarity maintenance at different polar domains in plant cells. <i>Cell Discovery</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/celldisc.2016.18\">https://doi.org/10.1038/celldisc.2016.18</a>","mla":"Łangowski, Łukasz, et al. “Cellular Mechanisms for Cargo Delivery and Polarity Maintenance at Different Polar Domains in Plant Cells.” <i>Cell Discovery</i>, vol. 2, 16018, Nature Publishing Group, 2016, doi:<a href=\"https://doi.org/10.1038/celldisc.2016.18\">10.1038/celldisc.2016.18</a>.","chicago":"Łangowski, Łukasz, Krzysztof T Wabnik, Hongjiang Li, Steffen Vanneste, Satoshi Naramoto, Hirokazu Tanaka, and Jiří Friml. “Cellular Mechanisms for Cargo Delivery and Polarity Maintenance at Different Polar Domains in Plant Cells.” <i>Cell Discovery</i>. Nature Publishing Group, 2016. <a href=\"https://doi.org/10.1038/celldisc.2016.18\">https://doi.org/10.1038/celldisc.2016.18</a>.","short":"Ł. Łangowski, K.T. Wabnik, H. Li, S. Vanneste, S. Naramoto, H. Tanaka, J. Friml, Cell Discovery 2 (2016).","ieee":"Ł. Łangowski <i>et al.</i>, “Cellular mechanisms for cargo delivery and polarity maintenance at different polar domains in plant cells,” <i>Cell Discovery</i>, vol. 2. Nature Publishing Group, 2016.","ama":"Łangowski Ł, Wabnik KT, Li H, et al. Cellular mechanisms for cargo delivery and polarity maintenance at different polar domains in plant cells. <i>Cell Discovery</i>. 2016;2. doi:<a href=\"https://doi.org/10.1038/celldisc.2016.18\">10.1038/celldisc.2016.18</a>"},"doi":"10.1038/celldisc.2016.18","publication_status":"published","oa_version":"Published Version","date_published":"2016-07-19T00:00:00Z"},{"article_processing_charge":"No","volume":43,"quality_controlled":"1","publication":"2016 Computing in Cardiology Conference","page":"309-312","date_created":"2022-03-03T10:43:10Z","department":[{"_id":"CampIT"}],"language":[{"iso":"eng"}],"type":"conference","title":"SCP-ECG V3.0: An enhanced standard communication protocol for computer-assisted electrocardiography","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Computing in Cardiology","day":"01","acknowledgement":"The authors are thankful to Drs. Roger Abaecherli, Nikus Kjell, Paul Kligfield, Jay Mason, Patrice Nony, Vito Starc, Anders Thurin and the late Galen Wagner for their in depth review and constructive comments.","author":[{"full_name":"Rubel, Paul","last_name":"Rubel","first_name":"Paul"},{"full_name":"Pani, Danilo","first_name":"Danilo","last_name":"Pani"},{"id":"45BF87EE-F248-11E8-B48F-1D18A9856A87","last_name":"Schlögl","orcid":"0000-0002-5621-8100","first_name":"Alois","full_name":"Schlögl, Alois"},{"last_name":"Fayn","first_name":"Jocelyne","full_name":"Fayn, Jocelyne"},{"last_name":"Badilini","first_name":"Fabio","full_name":"Badilini, Fabio"},{"full_name":"Macfarlane, Peter","last_name":"Macfarlane","first_name":"Peter"},{"full_name":"Varri, Alpo","first_name":"Alpo","last_name":"Varri"}],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.22489/cinc.2016.090-500"}],"citation":{"short":"P. Rubel, D. Pani, A. Schlögl, J. Fayn, F. Badilini, P. Macfarlane, A. Varri, in:, 2016 Computing in Cardiology Conference, Computing in Cardiology, 2016, pp. 309–312.","ama":"Rubel P, Pani D, Schlögl A, et al. SCP-ECG V3.0: An enhanced standard communication protocol for computer-assisted electrocardiography. In: <i>2016 Computing in Cardiology Conference</i>. Vol 43. Computing in Cardiology; 2016:309-312. doi:<a href=\"https://doi.org/10.22489/cinc.2016.090-500\">10.22489/cinc.2016.090-500</a>","ieee":"P. Rubel <i>et al.</i>, “SCP-ECG V3.0: An enhanced standard communication protocol for computer-assisted electrocardiography,” in <i>2016 Computing in Cardiology Conference</i>, Vancouver, Canada, 2016, vol. 43, pp. 309–312.","apa":"Rubel, P., Pani, D., Schlögl, A., Fayn, J., Badilini, F., Macfarlane, P., &#38; Varri, A. (2016). SCP-ECG V3.0: An enhanced standard communication protocol for computer-assisted electrocardiography. In <i>2016 Computing in Cardiology Conference</i> (Vol. 43, pp. 309–312). Vancouver, Canada: Computing in Cardiology. <a href=\"https://doi.org/10.22489/cinc.2016.090-500\">https://doi.org/10.22489/cinc.2016.090-500</a>","ista":"Rubel P, Pani D, Schlögl A, Fayn J, Badilini F, Macfarlane P, Varri A. 2016. SCP-ECG V3.0: An enhanced standard communication protocol for computer-assisted electrocardiography. 2016 Computing in Cardiology Conference. CinC: Computing in Cardiology vol. 43, 309–312.","mla":"Rubel, Paul, et al. “SCP-ECG V3.0: An Enhanced Standard Communication Protocol for Computer-Assisted Electrocardiography.” <i>2016 Computing in Cardiology Conference</i>, vol. 43, Computing in Cardiology, 2016, pp. 309–12, doi:<a href=\"https://doi.org/10.22489/cinc.2016.090-500\">10.22489/cinc.2016.090-500</a>.","chicago":"Rubel, Paul, Danilo Pani, Alois Schlögl, Jocelyne Fayn, Fabio Badilini, Peter Macfarlane, and Alpo Varri. “SCP-ECG V3.0: An Enhanced Standard Communication Protocol for Computer-Assisted Electrocardiography.” In <i>2016 Computing in Cardiology Conference</i>, 43:309–12. Computing in Cardiology, 2016. <a href=\"https://doi.org/10.22489/cinc.2016.090-500\">https://doi.org/10.22489/cinc.2016.090-500</a>."},"intvolume":"        43","doi":"10.22489/cinc.2016.090-500","publication_status":"published","conference":{"location":"Vancouver, Canada","end_date":"2016-09-14","name":"CinC: Computing in Cardiology","start_date":"2016-09-11"},"date_published":"2016-03-01T00:00:00Z","oa_version":"Published Version","publication_identifier":{"issn":["2325-887X"]},"oa":1,"status":"public","month":"03","year":"2016","abstract":[{"text":"The main goal of the SCP-ECG standard is to address ECG data and related metadata structuring, semantics and syntax, with the objective of facilitating interoperability and thus supporting and promoting the exchange of the relevant information for unary and serial ECG diagnosis. Starting with version V3.0, the standard now also provides support for the storage of continuous, long-term ECG recordings and affords a repository for selected ECG sequences and the related metadata to accommodate stress tests, drug trials and protocol-based ECG recordings. The global and per-lead measurements sections have been extended and three new sections have been introduced for storing beat-by-beat and/or spike-by-spike measurements\r\nand annotations. The used terminology and the provided measurements and annotations have been harmonized with the ISO/IEEE 11073-10102 Annotated ECG standard. Emphasis has also been put on harmonizing the Universal Statement Codes with the CDISC and the categorized AHA statement codes and similarly the drug and implanted devices codes with the ATC and NASPE/BPEG codes. ","lang":"eng"}],"date_updated":"2022-03-04T07:34:45Z","_id":"10810"},{"oa_version":"Preprint","type":"conference","department":[{"_id":"GaTk"}],"date_published":"2016-12-01T00:00:00Z","language":[{"iso":"eng"}],"publication_status":"published","conference":{"start_date":"2016-12-05","name":"NIPS: Neural Information Processing Systems","end_date":"2016-12-10","location":"Barcelona, Spain"},"date_created":"2018-12-11T11:50:03Z","page":"1965-1973","intvolume":"        29","citation":{"chicago":"Chalk, Matthew J, Olivier Marre, and Gašper Tkačik. “Relevant Sparse Codes with Variational Information Bottleneck,” 29:1965–73. Neural Information Processing Systems, 2016.","apa":"Chalk, M. J., Marre, O., &#38; Tkačik, G. (2016). Relevant sparse codes with variational information bottleneck (Vol. 29, pp. 1965–1973). Presented at the NIPS: Neural Information Processing Systems, Barcelona, Spain: Neural Information Processing Systems.","ista":"Chalk MJ, Marre O, Tkačik G. 2016. Relevant sparse codes with variational information bottleneck. NIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 29, 1965–1973.","mla":"Chalk, Matthew J., et al. <i>Relevant Sparse Codes with Variational Information Bottleneck</i>. Vol. 29, Neural Information Processing Systems, 2016, pp. 1965–73.","ieee":"M. J. Chalk, O. Marre, and G. Tkačik, “Relevant sparse codes with variational information bottleneck,” presented at the NIPS: Neural Information Processing Systems, Barcelona, Spain, 2016, vol. 29, pp. 1965–1973.","ama":"Chalk MJ, Marre O, Tkačik G. Relevant sparse codes with variational information bottleneck. In: Vol 29. Neural Information Processing Systems; 2016:1965-1973.","short":"M.J. Chalk, O. Marre, G. Tkačik, in:, Neural Information Processing Systems, 2016, pp. 1965–1973."},"volume":29,"quality_controlled":"1","related_material":{"link":[{"url":"https://papers.nips.cc/paper/6101-relevant-sparse-codes-with-variational-information-bottleneck","relation":"other"}]},"publist_id":"6298","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1605.07332"}],"scopus_import":1,"author":[{"full_name":"Chalk, Matthew J","first_name":"Matthew J","orcid":"0000-0001-7782-4436","last_name":"Chalk","id":"2BAAC544-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Marre","first_name":"Olivier","full_name":"Marre, Olivier"},{"first_name":"Gasper","orcid":"0000-0002-6699-1455","last_name":"Tkacik","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","full_name":"Tkacik, Gasper"}],"_id":"1082","abstract":[{"lang":"eng","text":"In many applications, it is desirable to extract only the relevant aspects of data. A principled way to do this is the information bottleneck (IB) method, where one seeks a code that maximises information about a relevance variable, Y, while constraining the information encoded about the original data, X. Unfortunately however, the IB method is computationally demanding when data are high-dimensional and/or non-gaussian. Here we propose an approximate variational scheme for maximising a lower bound on the IB objective, analogous to variational EM. Using this method, we derive an IB algorithm to recover features that are both relevant and sparse. Finally, we demonstrate how kernelised versions of the algorithm can be used to address a broad range of problems with non-linear relation between X and Y."}],"date_updated":"2021-01-12T06:48:09Z","year":"2016","day":"01","alternative_title":["Advances in Neural Information Processing Systems"],"month":"12","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"Neural Information Processing Systems","status":"public","oa":1,"title":"Relevant sparse codes with variational information bottleneck"},{"date_created":"2018-12-11T11:50:03Z","page":"2318 - 2334","publication":"Cerebral Cortex","publication_status":"published","doi":"10.1093/cercor/bhw090","language":[{"iso":"eng"}],"date_published":"2016-04-12T00:00:00Z","department":[{"_id":"RySh"}],"type":"journal_article","oa_version":"None","publist_id":"6297","citation":{"apa":"Booker, S., Althof, D., Gross, A., Loreth, D., Müller, J., Unger, A., … Kulik, Á. (2016). KCTD12 auxiliary proteins modulate kinetics of GABAB receptor-mediated inhibition in Cholecystokinin-containing interneurons. <i>Cerebral Cortex</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/cercor/bhw090\">https://doi.org/10.1093/cercor/bhw090</a>","mla":"Booker, Sam, et al. “KCTD12 Auxiliary Proteins Modulate Kinetics of GABAB Receptor-Mediated Inhibition in Cholecystokinin-Containing Interneurons.” <i>Cerebral Cortex</i>, vol. 27, no. 3, Oxford University Press, 2016, pp. 2318–34, doi:<a href=\"https://doi.org/10.1093/cercor/bhw090\">10.1093/cercor/bhw090</a>.","ista":"Booker S, Althof D, Gross A, Loreth D, Müller J, Unger A, Fakler B, Varro A, Watanabe M, Gassmann M, Bettler B, Shigemoto R, Vida I, Kulik Á. 2016. KCTD12 auxiliary proteins modulate kinetics of GABAB receptor-mediated inhibition in Cholecystokinin-containing interneurons. Cerebral Cortex. 27(3), 2318–2334.","chicago":"Booker, Sam, Daniel Althof, Anna Gross, Desiree Loreth, Johanna Müller, Andreas Unger, Bernd Fakler, et al. “KCTD12 Auxiliary Proteins Modulate Kinetics of GABAB Receptor-Mediated Inhibition in Cholecystokinin-Containing Interneurons.” <i>Cerebral Cortex</i>. Oxford University Press, 2016. <a href=\"https://doi.org/10.1093/cercor/bhw090\">https://doi.org/10.1093/cercor/bhw090</a>.","short":"S. Booker, D. Althof, A. Gross, D. Loreth, J. Müller, A. Unger, B. Fakler, A. Varro, M. Watanabe, M. Gassmann, B. Bettler, R. Shigemoto, I. Vida, Á. Kulik, Cerebral Cortex 27 (2016) 2318–2334.","ieee":"S. Booker <i>et al.</i>, “KCTD12 auxiliary proteins modulate kinetics of GABAB receptor-mediated inhibition in Cholecystokinin-containing interneurons,” <i>Cerebral Cortex</i>, vol. 27, no. 3. Oxford University Press, pp. 2318–2334, 2016.","ama":"Booker S, Althof D, Gross A, et al. KCTD12 auxiliary proteins modulate kinetics of GABAB receptor-mediated inhibition in Cholecystokinin-containing interneurons. <i>Cerebral Cortex</i>. 2016;27(3):2318-2334. doi:<a href=\"https://doi.org/10.1093/cercor/bhw090\">10.1093/cercor/bhw090</a>"},"intvolume":"        27","quality_controlled":"1","volume":27,"day":"12","year":"2016","date_updated":"2021-01-12T06:48:09Z","abstract":[{"lang":"eng","text":" Cholecystokinin-expressing interneurons (CCK-INs) mediate behavior state-dependent inhibition in cortical circuits and themselves receive strong GABAergic input. However, it remains unclear to what extent GABABreceptors (GABABRs) contribute to their inhibitory control. Using immunoelectron microscopy, we found that CCK-INs in the rat hippocampus possessed high levels of dendritic GABABRs and KCTD12 auxiliary proteins, whereas postsynaptic effector Kir3 channels were present at lower levels. Consistently, whole-cell recordings revealed slow GABABR-mediated inhibitory postsynaptic currents (IPSCs) in most CCK-INs. In spite of the higher surface density of GABABRs in CCK-INs than in CA1 principal cells, the amplitudes of IPSCs were comparable, suggesting that the expression of Kir3 channels is the limiting factor for the GABABR currents in these INs. Morphological analysis showed that CCK-INs were diverse, comprising perisomatic-targeting basket cells (BCs), as well as dendrite-targeting (DT) interneurons, including a previously undescribed DT type. GABABR-mediated IPSCs in CCK-INs were large in BCs, but small in DT subtypes. In response to prolonged activation, GABABR-mediated currents displayed strong desensitization, which was absent in KCTD12-deficient mice. This study highlights that GABABRs differentially control CCK-IN subtypes, and the kinetics and desensitization of GABABR-mediated currents are modulated by KCTD12 proteins. "}],"acknowledgement":"This work was supported by the Deutsche Forschungsgemeinschaft (DFG SFB 780 A2, A.K.; SFB TR3 I.V. and EXC 257, I.V.; FOR 2143, A.K. and I.V.), Spemann Graduate School (D.A.), BIOSS-2 (A6, A.K.), the Swiss National Science Foundation (3100A0-117816, B.B.), The McNaught Bequest (S.A.B. and I.V.), and Tenovus Scotland (I.V.).\r\n\r\n\r\nWe thank Cheryl Hutton and Chinmaya Sadangi for their contributions to neuronal reconstruction as well as Natalie Wernet, Sigrun Nestel, Anikó Schneider, Ina Wolter, and Ulrich Noeller for their excellent technical support. VGAT-Venus transgenic rats were generated by Drs Y. Yanagawa, M. Hirabayashi, and Y. Kawaguchi in National Institute for Physiological Sciences, Okazaki, Japan, using pCS2-Venus provided by Dr A. Miyawaki. The monoclonal mouse CCK antibody was generously provided by Dr G.V. Ohning, CURE Center, UCLA, CA. ","issue":"3","_id":"1083","author":[{"first_name":"Sam","last_name":"Booker","full_name":"Booker, Sam"},{"last_name":"Althof","first_name":"Daniel","full_name":"Althof, Daniel"},{"last_name":"Gross","first_name":"Anna","full_name":"Gross, Anna"},{"last_name":"Loreth","first_name":"Desiree","full_name":"Loreth, Desiree"},{"full_name":"Müller, Johanna","last_name":"Müller","first_name":"Johanna"},{"full_name":"Unger, Andreas","last_name":"Unger","first_name":"Andreas"},{"full_name":"Fakler, Bernd","last_name":"Fakler","first_name":"Bernd"},{"full_name":"Varro, Andrea","last_name":"Varro","first_name":"Andrea"},{"full_name":"Watanabe, Masahiko","last_name":"Watanabe","first_name":"Masahiko"},{"full_name":"Gassmann, Martin","first_name":"Martin","last_name":"Gassmann"},{"last_name":"Bettler","first_name":"Bernhard","full_name":"Bettler, Bernhard"},{"full_name":"Shigemoto, Ryuichi","first_name":"Ryuichi","orcid":"0000-0001-8761-9444","last_name":"Shigemoto","id":"499F3ABC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Vida, Imre","last_name":"Vida","first_name":"Imre"},{"first_name":"Ákos","last_name":"Kulik","full_name":"Kulik, Ákos"}],"title":"KCTD12 auxiliary proteins modulate kinetics of GABAB receptor-mediated inhibition in Cholecystokinin-containing interneurons","publisher":"Oxford University Press","status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","month":"04"},{"status":"public","oa":1,"month":"08","ec_funded":1,"abstract":[{"text":" While weighted automata provide a natural framework to express quantitative properties, many basic properties like average response time cannot be expressed with weighted automata. Nested weighted automata extend weighted automata and consist of a master automaton and a set of slave automata that are invoked by the master automaton. Nested weighted automata are strictly more expressive than weighted automata (e.g., average response time can be expressed with nested weighted automata), but the basic decision questions have higher complexity (e.g., for deterministic automata, the emptiness question for nested weighted automata is PSPACE-hard, whereas the corresponding complexity for weighted automata is PTIME). We consider a natural subclass of nested weighted automata where at any point at most a bounded number k of slave automata can be active. We focus on automata whose master value function is the limit average. We show that these nested weighted automata with bounded width are strictly more expressive than weighted automata (e.g., average response time with no overlapping requests can be expressed with bound k=1, but not with non-nested weighted automata). We show that the complexity of the basic decision problems (i.e., emptiness and universality) for the subclass with k constant matches the complexity for weighted automata. Moreover, when k is part of the input given in unary we establish PSPACE-completeness.","lang":"eng"}],"date_updated":"2021-01-12T06:48:12Z","year":"2016","article_number":"24","_id":"1090","file_date_updated":"2018-12-12T10:17:31Z","scopus_import":1,"ddc":["004"],"citation":{"short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.","ama":"Chatterjee K, Henzinger TA, Otop J. Nested weighted limit-average automata of bounded width. In: Vol 58. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2016.24\">10.4230/LIPIcs.MFCS.2016.24</a>","ieee":"K. Chatterjee, T. A. Henzinger, and J. Otop, “Nested weighted limit-average automata of bounded width,” presented at the MFCS: Mathematical Foundations of Computer Science (SG), Krakow; Poland, 2016, vol. 58.","ista":"Chatterjee K, Henzinger TA, Otop J. 2016. Nested weighted limit-average automata of bounded width. MFCS: Mathematical Foundations of Computer Science (SG), LIPIcs, vol. 58, 24.","apa":"Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2016). Nested weighted limit-average automata of bounded width (Vol. 58). Presented at the MFCS: Mathematical Foundations of Computer Science (SG), Krakow; Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2016.24\">https://doi.org/10.4230/LIPIcs.MFCS.2016.24</a>","mla":"Chatterjee, Krishnendu, et al. <i>Nested Weighted Limit-Average Automata of Bounded Width</i>. Vol. 58, 24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:<a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2016.24\">10.4230/LIPIcs.MFCS.2016.24</a>.","chicago":"Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Nested Weighted Limit-Average Automata of Bounded Width,” Vol. 58. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.MFCS.2016.24\">https://doi.org/10.4230/LIPIcs.MFCS.2016.24</a>."},"intvolume":"        58","doi":"10.4230/LIPIcs.MFCS.2016.24","publication_status":"published","conference":{"start_date":"2016-08-22","name":"MFCS: Mathematical Foundations of Computer Science (SG)","end_date":"2016-08-26","location":"Krakow; Poland"},"oa_version":"Published Version","date_published":"2016-08-01T00:00:00Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","title":"Nested weighted limit-average automata of bounded width","alternative_title":["LIPIcs"],"acknowledgement":"This research was supported in part by the Austrian Science Fund (FWF) under grants S11402-N23\r\n(RiSE/SHiNE) and Z211-N23 (Wittgenstein Award), ERC Start grant (279307: Graph Games), Vienna\r\nScience and Technology Fund (WWTF) through project ICT15-003 and by the National Science Centre\r\n(NCN), Poland under grant 2014/15/D/ST6/04543.","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"day":"01","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","orcid":"0000−0002−2985−7724"},{"full_name":"Otop, Jan","first_name":"Jan","last_name":"Otop","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"project":[{"name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Efficient Algorithms for Computer Aided Verification","_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003"}],"file":[{"date_updated":"2018-12-12T10:17:31Z","file_name":"IST-2017-795-v1+1_LIPIcs-MFCS-2016-24.pdf","date_created":"2018-12-12T10:17:31Z","file_id":"5286","creator":"system","access_level":"open_access","content_type":"application/pdf","relation":"main_file","file_size":564560}],"pubrep_id":"795","publist_id":"6286","volume":58,"quality_controlled":"1","has_accepted_license":"1","date_created":"2018-12-11T11:50:05Z","type":"conference","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"language":[{"iso":"eng"}]},{"alternative_title":["LIPIcs"],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","title":"Linear distances between Markov chains","author":[{"id":"49351290-F248-11E8-B48F-1D18A9856A87","last_name":"Daca","first_name":"Przemyslaw","full_name":"Daca, Przemyslaw"},{"full_name":"Henzinger, Thomas A","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0002-8122-2881","first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","last_name":"Kretinsky","full_name":"Kretinsky, Jan"},{"orcid":"0000-0002-9041-0905","first_name":"Tatjana","id":"3D5811FC-F248-11E8-B48F-1D18A9856A87","last_name":"Petrov","full_name":"Petrov, Tatjana"}],"project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989"},{"name":"Rigorous Systems Engineering","call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","call_identifier":"FWF","name":"The Wittgenstein Prize"}],"file":[{"relation":"main_file","content_type":"application/pdf","file_size":501827,"creator":"system","file_id":"4895","access_level":"open_access","file_name":"IST-2017-794-v1+1_LIPIcs-CONCUR-2016-20.pdf","date_updated":"2018-12-12T10:11:39Z","date_created":"2018-12-12T10:11:39Z"}],"acknowledgement":"This research was funded in part by the European Research Council (ERC) under grant agreement 267989\r\n(QUAREM), the Austrian Science Fund (FWF) under grants project S11402-N23 (RiSE and SHiNE)\r\nand Z211-N23 (Wittgenstein Award), by the Czech Science Foundation Grant No. P202/12/G061, and\r\nby the SNSF Advanced Postdoc. Mobility Fellowship – grant number P300P2_161067.","tmp":{"short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"day":"01","volume":59,"quality_controlled":"1","related_material":{"record":[{"id":"1155","relation":"dissertation_contains","status":"public"}]},"pubrep_id":"794","publist_id":"6283","type":"conference","department":[{"_id":"ToHe"},{"_id":"KrCh"},{"_id":"CaGu"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","date_created":"2018-12-11T11:50:06Z","month":"08","ec_funded":1,"status":"public","oa":1,"article_number":"20","_id":"1093","abstract":[{"lang":"eng","text":"We introduce a general class of distances (metrics) between Markov chains, which are based on linear behaviour. This class encompasses distances given topologically (such as the total variation distance or trace distance) as well as by temporal logics or automata. We investigate which of the distances can be approximated by observing the systems, i.e. by black-box testing or simulation, and we provide both negative and positive results. "}],"date_updated":"2023-09-07T11:58:33Z","year":"2016","citation":{"ista":"Daca P, Henzinger TA, Kretinsky J, Petrov T. 2016. Linear distances between Markov chains. CONCUR: Concurrency Theory, LIPIcs, vol. 59, 20.","mla":"Daca, Przemyslaw, et al. <i>Linear Distances between Markov Chains</i>. Vol. 59, 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.20\">10.4230/LIPIcs.CONCUR.2016.20</a>.","apa":"Daca, P., Henzinger, T. A., Kretinsky, J., &#38; Petrov, T. (2016). Linear distances between Markov chains (Vol. 59). Presented at the CONCUR: Concurrency Theory, Quebec City; Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.20\">https://doi.org/10.4230/LIPIcs.CONCUR.2016.20</a>","chicago":"Daca, Przemyslaw, Thomas A Henzinger, Jan Kretinsky, and Tatjana Petrov. “Linear Distances between Markov Chains,” Vol. 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.20\">https://doi.org/10.4230/LIPIcs.CONCUR.2016.20</a>.","short":"P. Daca, T.A. Henzinger, J. Kretinsky, T. Petrov, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.","ieee":"P. Daca, T. A. Henzinger, J. Kretinsky, and T. Petrov, “Linear distances between Markov chains,” presented at the CONCUR: Concurrency Theory, Quebec City; Canada, 2016, vol. 59.","ama":"Daca P, Henzinger TA, Kretinsky J, Petrov T. Linear distances between Markov chains. In: Vol 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2016.20\">10.4230/LIPIcs.CONCUR.2016.20</a>"},"intvolume":"        59","file_date_updated":"2018-12-12T10:11:39Z","scopus_import":1,"ddc":["004"],"oa_version":"Published Version","date_published":"2016-08-01T00:00:00Z","doi":"10.4230/LIPIcs.CONCUR.2016.20","conference":{"end_date":"2016-08-26","location":"Quebec City; Canada","start_date":"2016-08-23","name":"CONCUR: Concurrency Theory"},"publication_status":"published"}]