[{"date_updated":"2024-02-28T12:59:37Z","department":[{"_id":"UlWa"}],"citation":{"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.","mla":"Goaoc, Xavier, et al. “Bounding Helly Numbers via Betti Numbers.” A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, edited by Martin Loebl et al., Springer, 2017, pp. 407–47, doi:10.1007/978-3-319-44479-6_17.","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2017). Bounding helly numbers via betti numbers. In M. Loebl, J. Nešetřil, & R. Thomas (Eds.), A Journey through Discrete Mathematics: A Tribute to Jiri Matousek (pp. 407–447). Springer. https://doi.org/10.1007/978-3-319-44479-6_17","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.","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. A Journey through Discrete Mathematics: A Tribute to Jiri Matousek. A Journey Through Discrete Mathematics. Springer; 2017:407-447. doi:10.1007/978-3-319-44479-6_17","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Bounding Helly Numbers via Betti Numbers.” In A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, edited by Martin Loebl, Jaroslav Nešetřil, and Robin Thomas, 407–47. A Journey Through Discrete Mathematics. Springer, 2017. https://doi.org/10.1007/978-3-319-44479-6_17.","ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding helly numbers via betti numbers,” in A Journey through Discrete Mathematics: A Tribute to Jiri Matousek, M. Loebl, J. Nešetřil, and R. Thomas, Eds. Springer, 2017, pp. 407–447."},"user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","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"}],"publication_status":"published","series_title":"A Journey Through Discrete Mathematics","date_published":"2017-10-06T00:00:00Z","publisher":"Springer","title":"Bounding helly numbers via betti numbers","oa":1,"day":"06","year":"2017","page":"407 - 447","doi":"10.1007/978-3-319-44479-6_17","related_material":{"record":[{"relation":"earlier_version","id":"1512","status":"public"}]},"scopus_import":1,"editor":[{"first_name":"Martin","last_name":"Loebl","full_name":"Loebl, Martin"},{"full_name":"Nešetřil, Jaroslav","first_name":"Jaroslav","last_name":"Nešetřil"},{"first_name":"Robin","last_name":"Thomas","full_name":"Thomas, Robin"}],"publist_id":"7399","publication":"A Journey through Discrete Mathematics: A Tribute to Jiri Matousek","quality_controlled":"1","oa_version":"Published Version","author":[{"full_name":"Goaoc, Xavier","first_name":"Xavier","last_name":"Goaoc"},{"full_name":"Paták, Pavel","first_name":"Pavel","last_name":"Paták"},{"full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","last_name":"Patakova","first_name":"Zuzana"},{"last_name":"Tancer","first_name":"Martin","orcid":"0000-0002-1191-6714","full_name":"Tancer, Martin"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","last_name":"Wagner","first_name":"Uli","orcid":"0000-0002-1494-0568"}],"month":"10","language":[{"iso":"eng"}],"date_created":"2018-12-11T11:46:24Z","_id":"424","type":"book_chapter","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1310.4613v3"}],"status":"public","publication_identifier":{"isbn":["978-331944479-6"]}},{"article_processing_charge":"No","volume":2017,"language":[{"iso":"eng"}],"month":"01","author":[{"full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","first_name":"Dan-Adrian","last_name":"Alistarh"},{"first_name":"Demjan","last_name":"Grubic","full_name":"Grubic, Demjan"},{"first_name":"Jerry","last_name":"Li","full_name":"Li, Jerry"},{"full_name":"Tomioka, Ryota","first_name":"Ryota","last_name":"Tomioka"},{"full_name":"Vojnović, Milan","first_name":"Milan","last_name":"Vojnović"}],"oa_version":"Submitted Version","quality_controlled":"1","conference":{"location":"Long Beach, CA, United States","name":"NIPS: Neural Information Processing System","start_date":"2017-12-04","end_date":"2017-12-09"},"status":"public","publication_identifier":{"issn":["10495258"]},"main_file_link":[{"url":"https://arxiv.org/abs/1610.02132","open_access":"1"}],"_id":"431","type":"conference","date_created":"2018-12-11T11:46:26Z","title":"QSGD: Communication-efficient SGD via gradient quantization and encoding","date_published":"2017-01-01T00:00:00Z","publisher":"Neural Information Processing Systems Foundation","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"}],"publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1610.02132"]},"alternative_title":["Advances in Neural Information Processing Systems"],"citation":{"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.","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.","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.","apa":"Alistarh, D.-A., Grubic, D., Li, J., Tomioka, R., & 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.","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.","mla":"Alistarh, Dan-Adrian, et al. QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding. Vol. 2017, Neural Information Processing Systems Foundation, 2017, pp. 1710–21.","short":"D.-A. Alistarh, D. Grubic, J. Li, R. Tomioka, M. Vojnović, in:, Neural Information Processing Systems Foundation, 2017, pp. 1710–1721."},"date_updated":"2023-10-17T11:48:03Z","department":[{"_id":"DaAl"}],"intvolume":" 2017","publist_id":"7392","arxiv":1,"day":"01","year":"2017","page":"1710-1721","oa":1},{"publication_identifier":{"isbn":["978-151085514-4"]},"status":"public","type":"conference","_id":"432","date_created":"2018-12-11T11:46:26Z","conference":{"name":"ICML: International Conference on Machine Learning","location":"Sydney, Australia","start_date":"2017-08-06","end_date":"2017-08-11"},"author":[{"full_name":"Zhang, Hantian","last_name":"Zhang","first_name":"Hantian"},{"first_name":"Jerry","last_name":"Li","full_name":"Li, Jerry"},{"full_name":"Kara, Kaan","last_name":"Kara","first_name":"Kaan"},{"orcid":"0000-0003-3650-940X","last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Liu, Ji","first_name":"Ji","last_name":"Liu"},{"first_name":"Ce","last_name":"Zhang","full_name":"Zhang, Ce"}],"oa_version":"Submitted Version","quality_controlled":"1","volume":" 70","article_processing_charge":"No","language":[{"iso":"eng"}],"file":[{"file_name":"2017_ICML_Zhang.pdf","content_type":"application/pdf","date_updated":"2020-07-14T12:46:26Z","date_created":"2019-01-22T08:23:58Z","creator":"dernst","checksum":"86156ba7f4318e47cef3eb9092593c10","file_id":"5869","file_size":849345,"access_level":"open_access","relation":"main_file"}],"has_accepted_license":"1","month":"01","year":"2017","page":"4035 - 4043","day":"01","oa":1,"publication":"Proceedings of Machine Learning Research","publist_id":"7391","scopus_import":"1","alternative_title":["PMLR Press"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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.","mla":"Zhang, Hantian, et al. “ZipML: Training Linear Models with End-to-End Low Precision, and a Little Bit of Deep Learning.” Proceedings of Machine Learning Research, vol. 70, ML Research Press, 2017, pp. 4035–43.","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 Proceedings of Machine Learning Research, Sydney, Australia, 2017, vol. 70, pp. 4035–4043.","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.","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 Proceedings of Machine Learning Research, 70:4035–43. ML Research Press, 2017.","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: Proceedings of Machine Learning Research. Vol 70. ML Research Press; 2017:4035-4043.","apa":"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. In Proceedings of Machine Learning Research (Vol. 70, pp. 4035–4043). Sydney, Australia: ML Research Press."},"department":[{"_id":"DaAl"}],"date_updated":"2023-10-17T12:31:15Z","title":"ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning","file_date_updated":"2020-07-14T12:46:26Z","date_published":"2017-01-01T00:00:00Z","publisher":"ML Research Press","ddc":["000"],"publication_status":"published","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"}]},{"date_updated":"2021-01-12T07:56:59Z","department":[{"_id":"LeSa"}],"quality_controlled":"1","citation":{"ieee":"L. A. Sazanov, “Structure of respiratory complex I: ‘Minimal’ bacterial and ‘de luxe’ mammalian versions,” in Mechanisms of primary energy transduction in biology , M. Wikström, Ed. Royal Society of Chemistry, 2017, pp. 25–59.","apa":"Sazanov, L. A. (2017). Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions. In M. Wikström (Ed.), Mechanisms of primary energy transduction in biology (pp. 25–59). Royal Society of Chemistry. https://doi.org/10.1039/9781788010405-00025","chicago":"Sazanov, Leonid A. “Structure of Respiratory Complex I: ‘Minimal’ Bacterial and ‘de Luxe’ Mammalian Versions.” In Mechanisms of Primary Energy Transduction in Biology , edited by Mårten Wikström, 25–59. Mechanisms of Primary Energy Transduction in Biology . Royal Society of Chemistry, 2017. https://doi.org/10.1039/9781788010405-00025.","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.","ama":"Sazanov LA. Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions. In: Wikström M, ed. Mechanisms of Primary Energy Transduction in Biology . Mechanisms of Primary Energy Transduction in Biology . Royal Society of Chemistry; 2017:25-59. doi:10.1039/9781788010405-00025","mla":"Sazanov, Leonid A. “Structure of Respiratory Complex I: ‘Minimal’ Bacterial and ‘de Luxe’ Mammalian Versions.” Mechanisms of Primary Energy Transduction in Biology , edited by Mårten Wikström, Royal Society of Chemistry, 2017, pp. 25–59, doi:10.1039/9781788010405-00025.","short":"L.A. Sazanov, in:, M. Wikström (Ed.), Mechanisms of Primary Energy Transduction in Biology , Royal Society of Chemistry, 2017, pp. 25–59."},"oa_version":"None","author":[{"id":"338D39FE-F248-11E8-B48F-1D18A9856A87","full_name":"Sazanov, Leonid A","last_name":"Sazanov","first_name":"Leonid A","orcid":"0000-0002-0977-7989"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","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."}],"publication_status":"published","month":"11","series_title":"Mechanisms of Primary Energy Transduction in Biology ","date_published":"2017-11-29T00:00:00Z","language":[{"iso":"eng"}],"publisher":"Royal Society of Chemistry","title":"Structure of respiratory complex I: “Minimal” bacterial and “de luxe” mammalian versions","date_created":"2018-12-11T11:46:30Z","type":"book_chapter","_id":"444","doi":"10.1039/9781788010405-00025","publication_identifier":{"isbn":["978-1-78262-865-1"]},"status":"public","page":"25 - 59","year":"2017","day":"29","editor":[{"first_name":"Mårten","last_name":"Wikström","full_name":"Wikström, Mårten"}],"publist_id":"7379","publication":"Mechanisms of primary energy transduction in biology "},{"day":"23","year":"2017","page":"299 - 325","doi":"10.30757/ALEA.v14-17","oa":1,"publist_id":"7376","intvolume":" 9","publication":"Revista Latino-Americana de Probabilidade e Estatística","scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"LaEr"},{"_id":"JaMa"}],"date_updated":"2023-10-10T13:10:32Z","citation":{"mla":"Ferrari, Patrik, and Peter Nejjar. “Fluctuations of the Competition Interface in Presence of Shocks.” Revista Latino-Americana de Probabilidade e Estatística, vol. 9, Instituto Nacional de Matematica Pura e Aplicada, 2017, pp. 299–325, doi:10.30757/ALEA.v14-17.","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,” Revista Latino-Americana de Probabilidade e Estatística, vol. 9. Instituto Nacional de Matematica Pura e Aplicada, pp. 299–325, 2017.","apa":"Ferrari, P., & Nejjar, P. (2017). Fluctuations of the competition interface in presence of shocks. Revista Latino-Americana de Probabilidade e Estatística. Instituto Nacional de Matematica Pura e Aplicada. https://doi.org/10.30757/ALEA.v14-17","ama":"Ferrari P, Nejjar P. Fluctuations of the competition interface in presence of shocks. Revista Latino-Americana de Probabilidade e Estatística. 2017;9:299-325. doi:10.30757/ALEA.v14-17","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.","chicago":"Ferrari, Patrik, and Peter Nejjar. “Fluctuations of the Competition Interface in Presence of Shocks.” Revista Latino-Americana de Probabilidade e Estatística. Instituto Nacional de Matematica Pura e Aplicada, 2017. https://doi.org/10.30757/ALEA.v14-17."},"publisher":"Instituto Nacional de Matematica Pura e Aplicada","date_published":"2017-03-23T00:00:00Z","title":"Fluctuations of the competition interface in presence of shocks","publication_status":"published","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)."}],"status":"public","main_file_link":[{"url":"http://alea.impa.br/articles/v14/14-17.pdf","open_access":"1"}],"date_created":"2018-12-11T11:46:31Z","article_type":"original","_id":"447","type":"journal_article","ec_funded":1,"author":[{"last_name":"Ferrari","first_name":"Patrik","full_name":"Ferrari, Patrik"},{"last_name":"Nejjar","first_name":"Peter","full_name":"Nejjar, Peter","id":"4BF426E2-F248-11E8-B48F-1D18A9856A87"}],"project":[{"name":"Random matrices, universality and disordered quantum systems","grant_number":"338804","_id":"258DCDE6-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"quality_controlled":"1","oa_version":"Submitted Version","language":[{"iso":"eng"}],"volume":9,"article_processing_charge":"No","month":"03"},{"issue":"9","file":[{"file_size":977192,"access_level":"open_access","creator":"system","file_id":"5052","checksum":"99a2474088e20ac74b1882c4fbbb45b1","relation":"main_file","file_name":"IST-2018-965-v1+1_2017_Duellberg_Ensembles_of.pdf","date_updated":"2020-07-14T12:46:31Z","date_created":"2018-12-12T10:14:03Z","content_type":"application/pdf"}],"has_accepted_license":"1","month":"11","article_processing_charge":"No","volume":113,"language":[{"iso":"eng"}],"oa_version":"Published Version","quality_controlled":"1","author":[{"first_name":"Todd","last_name":"Fallesen","full_name":"Fallesen, Todd"},{"first_name":"Johanna","last_name":"Roostalu","full_name":"Roostalu, Johanna"},{"full_name":"Düllberg, Christian F","id":"459064DC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-6335-9748","last_name":"Düllberg","first_name":"Christian F"},{"full_name":"Pruessner, Gunnar","first_name":"Gunnar","last_name":"Pruessner"},{"last_name":"Surrey","first_name":"Thomas","full_name":"Surrey, Thomas"}],"pubrep_id":"965","_id":"453","type":"journal_article","article_type":"original","date_created":"2018-12-11T11:46:33Z","status":"public","ddc":["570"],"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"}],"publication_status":"published","title":"Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement","publisher":"Biophysical Society","file_date_updated":"2020-07-14T12:46:31Z","date_published":"2017-11-07T00:00:00Z","citation":{"apa":"Fallesen, T., Roostalu, J., Düllberg, C. F., Pruessner, G., & Surrey, T. (2017). Ensembles of bidirectional kinesin Cin8 produce additive forces in both directions of movement. Biophysical Journal. Biophysical Society. https://doi.org/10.1016/j.bpj.2017.09.006","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. Biophysical Journal. 2017;113(9):2055-2067. doi:10.1016/j.bpj.2017.09.006","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.” Biophysical Journal. Biophysical Society, 2017. https://doi.org/10.1016/j.bpj.2017.09.006.","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.","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,” Biophysical Journal, vol. 113, no. 9. Biophysical Society, pp. 2055–2067, 2017.","mla":"Fallesen, Todd, et al. “Ensembles of Bidirectional Kinesin Cin8 Produce Additive Forces in Both Directions of Movement.” Biophysical Journal, vol. 113, no. 9, Biophysical Society, 2017, pp. 2055–67, doi:10.1016/j.bpj.2017.09.006.","short":"T. Fallesen, J. Roostalu, C.F. Düllberg, G. Pruessner, T. Surrey, Biophysical Journal 113 (2017) 2055–2067."},"date_updated":"2021-01-12T07:59:28Z","department":[{"_id":"MaLo"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"publication":"Biophysical Journal","intvolume":" 113","publist_id":"7369","oa":1,"day":"07","year":"2017","doi":"10.1016/j.bpj.2017.09.006","page":"2055 - 2067","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). "},{"abstract":[{"lang":"eng","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 > n^{1.5}. "}],"publication_status":"published","ddc":["000","004","006"],"file_date_updated":"2018-12-12T10:16:02Z","date_published":"2016-08-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","title":"Conditionally optimal algorithms for generalized Büchi Games","date_updated":"2025-06-02T08:53:50Z","department":[{"_id":"KrCh"}],"citation":{"apa":"Chatterjee, K., Dvorák, W., Henzinger, M. H., & 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. https://doi.org/10.4230/LIPIcs.MFCS.2016.25","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. https://doi.org/10.4230/LIPIcs.MFCS.2016.25.","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.","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:10.4230/LIPIcs.MFCS.2016.25","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.","mla":"Chatterjee, Krishnendu, et al. Conditionally Optimal Algorithms for Generalized Büchi Games. Vol. 58, 25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPIcs.MFCS.2016.25."},"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LIPIcs"],"scopus_import":"1","intvolume":" 58","publist_id":"6317","oa":1,"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","year":"2016","doi":"10.4230/LIPIcs.MFCS.2016.25","day":"01","has_accepted_license":"1","month":"08","file":[{"date_updated":"2018-12-12T10:16:02Z","date_created":"2018-12-12T10:16:02Z","content_type":"application/pdf","file_name":"IST-2017-779-v1+1_LIPIcs-MFCS-2016-25.pdf","relation":"main_file","file_size":632786,"access_level":"open_access","creator":"system","file_id":"5187"}],"article_number":"25","language":[{"iso":"eng"}],"article_processing_charge":"No","volume":58,"project":[{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"},{"name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","call_identifier":"FWF"},{"call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307"}],"quality_controlled":"1","oa_version":"Published Version","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"full_name":"Dvorák, Wolfgang","first_name":"Wolfgang","last_name":"Dvorák"},{"first_name":"Monika H","last_name":"Henzinger","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H"},{"first_name":"Veronika","last_name":"Loitzenbauer","full_name":"Loitzenbauer, Veronika"}],"pubrep_id":"779","ec_funded":1,"conference":{"start_date":"2016-08-22","end_date":"2016-08-26","location":"Krakow, Poland","name":"MFCS: Mathematical Foundations of Computer Science (SG)"},"date_created":"2018-12-11T11:49:58Z","_id":"1068","type":"conference","status":"public"},{"oa_version":"Published Version","project":[{"call_identifier":"FWF","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","call_identifier":"FP7"}],"quality_controlled":"1","author":[{"last_name":"Chonev","first_name":"Ventsislav K","full_name":"Chonev, Ventsislav K","id":"36CBE2E6-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Ouaknine, Joël","first_name":"Joël","last_name":"Ouaknine"},{"full_name":"Worrell, James","last_name":"Worrell","first_name":"James"}],"article_number":"100","file":[{"date_updated":"2018-12-12T10:16:26Z","date_created":"2018-12-12T10:16:26Z","content_type":"application/pdf","file_name":"IST-2017-778-v1+1_LIPIcs-ICALP-2016-100.pdf","relation":"main_file","file_size":521415,"access_level":"open_access","creator":"system","file_id":"5213"}],"has_accepted_license":"1","month":"08","volume":55,"language":[{"iso":"eng"}],"_id":"1069","type":"conference","date_created":"2018-12-11T11:49:59Z","status":"public","pubrep_id":"778","conference":{"name":"ICALP: Automata, Languages and Programming","location":"Rome, Italy","start_date":"2016-07-12","end_date":"2016-07-15"},"ec_funded":1,"citation":{"mla":"Chonev, Ventsislav K., et al. On the Skolem Problem for Continuous Linear Dynamical Systems. Vol. 55, 100, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016, doi:10.4230/LIPIcs.ICALP.2016.100.","short":"V.K. Chonev, J. Ouaknine, J. Worrell, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016.","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.","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:10.4230/LIPIcs.ICALP.2016.100","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. https://doi.org/10.4230/LIPIcs.ICALP.2016.100.","apa":"Chonev, V. K., Ouaknine, J., & 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. https://doi.org/10.4230/LIPIcs.ICALP.2016.100"},"department":[{"_id":"KrCh"}],"date_updated":"2021-01-12T06:48:03Z","alternative_title":["LIPIcs"],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["004","006"],"publication_status":"published","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."}],"title":"On the skolem problem for continuous linear dynamical systems","file_date_updated":"2018-12-12T10:16:26Z","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik","date_published":"2016-08-01T00:00:00Z","oa":1,"doi":"10.4230/LIPIcs.ICALP.2016.100","day":"01","year":"2016","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).","scopus_import":1,"publist_id":"6314","intvolume":" 55"},{"status":"public","type":"conference","_id":"1070","date_created":"2018-12-11T11:49:59Z","conference":{"start_date":"2016-07-12","end_date":"2016-07-15","location":"Rome, Italy","name":"ICALP: Automata, Languages and Programming"},"ec_funded":1,"pubrep_id":"812","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X"},{"full_name":"Doyen, Laurent","last_name":"Doyen","first_name":"Laurent"}],"oa_version":"Published Version","quality_controlled":"1","project":[{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification"}],"volume":55,"language":[{"iso":"eng"}],"article_number":"98","file":[{"relation":"main_file","file_size":546133,"access_level":"open_access","creator":"system","file_id":"4714","date_updated":"2018-12-12T10:08:52Z","date_created":"2018-12-12T10:08:52Z","content_type":"application/pdf","file_name":"IST-2017-812-v1+1_LIPIcs-ICALP-2016-98.pdf"}],"month":"01","has_accepted_license":"1","day":"01","year":"2016","doi":"10.4230/LIPIcs.ICALP.2016.98","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","oa":1,"publist_id":"6313","intvolume":" 55","scopus_import":1,"alternative_title":["LIPIcs"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Chatterjee, Krishnendu, and Laurent Doyen. Computation Tree Logic for Synchronization Properties. Vol. 55, 98, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016, doi:10.4230/LIPIcs.ICALP.2016.98.","short":"K. Chatterjee, L. Doyen, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016.","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.","ista":"Chatterjee K, Doyen L. 2016. Computation tree logic for synchronization properties. ICALP: Automata, Languages and Programming, LIPIcs, vol. 55, 98.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Computation Tree Logic for Synchronization Properties,” Vol. 55. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016. https://doi.org/10.4230/LIPIcs.ICALP.2016.98.","ama":"Chatterjee K, Doyen L. Computation tree logic for synchronization properties. In: Vol 55. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik; 2016. doi:10.4230/LIPIcs.ICALP.2016.98","apa":"Chatterjee, K., & 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. https://doi.org/10.4230/LIPIcs.ICALP.2016.98"},"department":[{"_id":"KrCh"}],"date_updated":"2021-01-12T06:48:03Z","title":"Computation tree logic for synchronization properties","date_published":"2016-01-01T00:00:00Z","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik","file_date_updated":"2018-12-12T10:08:52Z","ddc":["005"],"publication_status":"published","abstract":[{"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. ","lang":"eng"}]},{"pubrep_id":"777","conference":{"name":"ESA: European Symposium on Algorithms","location":"Aarhus, Denmark","end_date":"2016-08-24","start_date":"2016-08-22"},"ec_funded":1,"_id":"1071","type":"conference","date_created":"2018-12-11T11:49:59Z","status":"public","article_number":"28","file":[{"relation":"main_file","creator":"system","file_id":"5084","file_size":579225,"access_level":"open_access","content_type":"application/pdf","date_updated":"2018-12-12T10:14:31Z","date_created":"2018-12-12T10:14:31Z","file_name":"IST-2017-777-v1+1_LIPIcs-ESA-2016-28.pdf"}],"has_accepted_license":"1","month":"08","volume":57,"language":[{"iso":"eng"}],"oa_version":"Published Version","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","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","call_identifier":"FWF"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"quality_controlled":"1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"last_name":"Ibsen-Jensen","first_name":"Rasmus","orcid":"0000-0003-4783-0389","id":"3B699956-F248-11E8-B48F-1D18A9856A87","full_name":"Ibsen-Jensen, Rasmus"},{"orcid":"0000-0002-8943-0722","first_name":"Andreas","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":1,"related_material":{"record":[{"id":"821","relation":"dissertation_contains","status":"public"}]},"publist_id":"6312","intvolume":" 57","oa":1,"year":"2016","day":"01","doi":"10.4230/LIPIcs.ESA.2016.28","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).","ddc":["004","006"],"publication_status":"published","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. "}],"title":"Optimal reachability and a space time tradeoff for distance queries in constant treewidth graphs","date_published":"2016-08-01T00:00:00Z","file_date_updated":"2018-12-12T10:14:31Z","publisher":"Schloss Dagstuhl- Leibniz-Zentrum fur Informatik","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.","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.","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. https://doi.org/10.4230/LIPIcs.ESA.2016.28.","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:10.4230/LIPIcs.ESA.2016.28","apa":"Chatterjee, K., Ibsen-Jensen, R., & 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. https://doi.org/10.4230/LIPIcs.ESA.2016.28","mla":"Chatterjee, Krishnendu, et al. Optimal Reachability and a Space Time Tradeoff for Distance Queries in Constant Treewidth Graphs. Vol. 57, 28, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016, doi:10.4230/LIPIcs.ESA.2016.28.","short":"K. Chatterjee, R. Ibsen-Jensen, A. Pavlogiannis, in:, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik, 2016."},"department":[{"_id":"KrCh"}],"date_updated":"2023-09-07T12:01:58Z","alternative_title":["LIPIcs"],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"}},{"title":"Cellular mechanisms for cargo delivery and polarity maintenance at different polar domains in plant cells","publisher":"Nature Publishing Group","date_published":"2016-07-19T00:00:00Z","file_date_updated":"2018-12-12T10:13:33Z","ddc":["580"],"publication_status":"published","abstract":[{"lang":"eng","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."}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"citation":{"short":"Ł. Łangowski, K.T. Wabnik, H. Li, S. Vanneste, S. Naramoto, H. Tanaka, J. Friml, Cell Discovery 2 (2016).","mla":"Łangowski, Łukasz, et al. “Cellular Mechanisms for Cargo Delivery and Polarity Maintenance at Different Polar Domains in Plant Cells.” Cell Discovery, vol. 2, 16018, Nature Publishing Group, 2016, doi:10.1038/celldisc.2016.18.","ieee":"Ł. Łangowski et al., “Cellular mechanisms for cargo delivery and polarity maintenance at different polar domains in plant cells,” Cell Discovery, vol. 2. Nature Publishing Group, 2016.","apa":"Łangowski, Ł., Wabnik, K. T., 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. Nature Publishing Group. https://doi.org/10.1038/celldisc.2016.18","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.","ama":"Łangowski Ł, Wabnik KT, Li H, et al. Cellular mechanisms for cargo delivery and polarity maintenance at different polar domains in plant cells. Cell Discovery. 2016;2. doi:10.1038/celldisc.2016.18","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.” Cell Discovery. Nature Publishing Group, 2016. https://doi.org/10.1038/celldisc.2016.18."},"department":[{"_id":"EvBe"},{"_id":"JiFr"}],"date_updated":"2021-01-12T06:48:08Z","publication":"Cell Discovery","publist_id":"6299","intvolume":" 2","scopus_import":1,"doi":"10.1038/celldisc.2016.18","year":"2016","day":"19","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.","oa":1,"volume":2,"language":[{"iso":"eng"}],"article_number":"16018","file":[{"content_type":"application/pdf","date_created":"2018-12-12T10:13:33Z","date_updated":"2018-12-12T10:13:33Z","file_name":"IST-2017-757-v1+1_celldisc201618.pdf","relation":"main_file","file_id":"5017","creator":"system","access_level":"open_access","file_size":5261671}],"month":"07","has_accepted_license":"1","author":[{"full_name":"Łangowski, Łukasz","first_name":"Łukasz","last_name":"Łangowski"},{"full_name":"Wabnik, Krzysztof T","id":"4DE369A4-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-7263-0560","first_name":"Krzysztof T","last_name":"Wabnik"},{"first_name":"Hongjiang","last_name":"Li","orcid":"0000-0001-5039-9660","id":"33CA54A6-F248-11E8-B48F-1D18A9856A87","full_name":"Li, Hongjiang"},{"full_name":"Vanneste, Steffen","last_name":"Vanneste","first_name":"Steffen"},{"full_name":"Naramoto, Satoshi","last_name":"Naramoto","first_name":"Satoshi"},{"full_name":"Tanaka, Hirokazu","last_name":"Tanaka","first_name":"Hirokazu"},{"orcid":"0000-0002-8302-7596","last_name":"Friml","first_name":"Jirí","full_name":"Friml, Jirí","id":"4159519E-F248-11E8-B48F-1D18A9856A87"}],"oa_version":"Published Version","quality_controlled":"1","project":[{"_id":"25716A02-B435-11E9-9278-68D0E5697425","grant_number":"282300","name":"Polarity and subcellular dynamics in plants","call_identifier":"FP7"}],"ec_funded":1,"pubrep_id":"757","status":"public","_id":"1081","type":"journal_article","date_created":"2018-12-11T11:50:02Z"},{"abstract":[{"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.","lang":"eng"}],"publication_status":"published","month":"12","publisher":"Neural Information Processing Systems","date_published":"2016-12-01T00:00:00Z","language":[{"iso":"eng"}],"volume":29,"title":"Relevant sparse codes with variational information bottleneck","date_updated":"2021-01-12T06:48:09Z","department":[{"_id":"GaTk"}],"quality_controlled":"1","oa_version":"Preprint","citation":{"apa":"Chalk, M. J., Marre, O., & 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.","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.","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.","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.","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.","mla":"Chalk, Matthew J., et al. Relevant Sparse Codes with Variational Information Bottleneck. Vol. 29, Neural Information Processing Systems, 2016, pp. 1965–73.","short":"M.J. Chalk, O. Marre, G. Tkačik, in:, Neural Information Processing Systems, 2016, pp. 1965–1973."},"author":[{"orcid":"0000-0001-7782-4436","last_name":"Chalk","first_name":"Matthew J","full_name":"Chalk, Matthew J","id":"2BAAC544-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Olivier","last_name":"Marre","full_name":"Marre, Olivier"},{"orcid":"0000-0002-6699-1455","first_name":"Gasper","last_name":"Tkacik","full_name":"Tkacik, Gasper","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","alternative_title":["Advances in Neural Information Processing Systems"],"related_material":{"link":[{"relation":"other","url":"https://papers.nips.cc/paper/6101-relevant-sparse-codes-with-variational-information-bottleneck"}]},"scopus_import":1,"intvolume":" 29","publist_id":"6298","conference":{"end_date":"2016-12-10","start_date":"2016-12-05","location":"Barcelona, Spain","name":"NIPS: Neural Information Processing Systems"},"date_created":"2018-12-11T11:50:03Z","oa":1,"_id":"1082","type":"conference","year":"2016","status":"public","day":"01","main_file_link":[{"url":"https://arxiv.org/abs/1605.07332","open_access":"1"}],"page":"1965-1973"},{"date_created":"2018-12-11T11:50:03Z","type":"journal_article","_id":"1083","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. ","year":"2016","day":"12","status":"public","doi":"10.1093/cercor/bhw090","page":"2318 - 2334","publist_id":"6297","intvolume":" 27","publication":"Cerebral Cortex","quality_controlled":"1","department":[{"_id":"RySh"}],"date_updated":"2021-01-12T06:48:09Z","oa_version":"None","citation":{"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.","mla":"Booker, Sam, et al. “KCTD12 Auxiliary Proteins Modulate Kinetics of GABAB Receptor-Mediated Inhibition in Cholecystokinin-Containing Interneurons.” Cerebral Cortex, vol. 27, no. 3, Oxford University Press, 2016, pp. 2318–34, doi:10.1093/cercor/bhw090.","ieee":"S. Booker et al., “KCTD12 auxiliary proteins modulate kinetics of GABAB receptor-mediated inhibition in Cholecystokinin-containing interneurons,” Cerebral Cortex, 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. Cerebral Cortex. 2016;27(3):2318-2334. doi:10.1093/cercor/bhw090","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.” Cerebral Cortex. Oxford University Press, 2016. https://doi.org/10.1093/cercor/bhw090.","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. Cerebral Cortex. Oxford University Press. https://doi.org/10.1093/cercor/bhw090"},"author":[{"full_name":"Booker, Sam","last_name":"Booker","first_name":"Sam"},{"full_name":"Althof, Daniel","last_name":"Althof","first_name":"Daniel"},{"last_name":"Gross","first_name":"Anna","full_name":"Gross, Anna"},{"full_name":"Loreth, Desiree","first_name":"Desiree","last_name":"Loreth"},{"full_name":"Müller, Johanna","last_name":"Müller","first_name":"Johanna"},{"full_name":"Unger, Andreas","first_name":"Andreas","last_name":"Unger"},{"full_name":"Fakler, Bernd","first_name":"Bernd","last_name":"Fakler"},{"full_name":"Varro, Andrea","last_name":"Varro","first_name":"Andrea"},{"full_name":"Watanabe, Masahiko","last_name":"Watanabe","first_name":"Masahiko"},{"full_name":"Gassmann, Martin","last_name":"Gassmann","first_name":"Martin"},{"last_name":"Bettler","first_name":"Bernhard","full_name":"Bettler, Bernhard"},{"last_name":"Shigemoto","first_name":"Ryuichi","orcid":"0000-0001-8761-9444","id":"499F3ABC-F248-11E8-B48F-1D18A9856A87","full_name":"Shigemoto, Ryuichi"},{"first_name":"Imre","last_name":"Vida","full_name":"Vida, Imre"},{"first_name":"Ákos","last_name":"Kulik","full_name":"Kulik, Ákos"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","month":"04","publication_status":"published","abstract":[{"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. ","lang":"eng"}],"issue":"3","publisher":"Oxford University Press","language":[{"iso":"eng"}],"date_published":"2016-04-12T00:00:00Z","volume":27,"title":"KCTD12 auxiliary proteins modulate kinetics of GABAB receptor-mediated inhibition in Cholecystokinin-containing interneurons"},{"oa":1,"year":"2016","doi":"10.4230/LIPIcs.MFCS.2016.24","day":"01","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.","scopus_import":1,"intvolume":" 58","publist_id":"6286","citation":{"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.","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. https://doi.org/10.4230/LIPIcs.MFCS.2016.24.","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.","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:10.4230/LIPIcs.MFCS.2016.24","apa":"Chatterjee, K., Henzinger, T. A., & 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. https://doi.org/10.4230/LIPIcs.MFCS.2016.24","short":"K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.","mla":"Chatterjee, Krishnendu, et al. Nested Weighted Limit-Average Automata of Bounded Width. Vol. 58, 24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPIcs.MFCS.2016.24."},"date_updated":"2021-01-12T06:48:12Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","alternative_title":["LIPIcs"],"ddc":["004"],"abstract":[{"lang":"eng","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."}],"publication_status":"published","title":"Nested weighted limit-average automata of bounded width","file_date_updated":"2018-12-12T10:17:31Z","date_published":"2016-08-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"1090","type":"conference","date_created":"2018-12-11T11:50:05Z","status":"public","pubrep_id":"795","ec_funded":1,"conference":{"name":"MFCS: Mathematical Foundations of Computer Science (SG)","location":"Krakow; Poland","start_date":"2016-08-22","end_date":"2016-08-26"},"oa_version":"Published Version","project":[{"call_identifier":"FWF","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23"},{"call_identifier":"FWF","name":"The Wittgenstein Prize","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification"}],"quality_controlled":"1","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A"},{"last_name":"Otop","first_name":"Jan","full_name":"Otop, Jan","id":"2FC5DA74-F248-11E8-B48F-1D18A9856A87"}],"file":[{"file_id":"5286","creator":"system","access_level":"open_access","file_size":564560,"relation":"main_file","file_name":"IST-2017-795-v1+1_LIPIcs-MFCS-2016-24.pdf","content_type":"application/pdf","date_created":"2018-12-12T10:17:31Z","date_updated":"2018-12-12T10:17:31Z"}],"article_number":"24","month":"08","has_accepted_license":"1","volume":58,"language":[{"iso":"eng"}]},{"alternative_title":["LIPIcs"],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"citation":{"mla":"Daca, Przemyslaw, et al. Linear Distances between Markov Chains. Vol. 59, 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPIcs.CONCUR.2016.20.","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.","ista":"Daca P, Henzinger TA, Kretinsky J, Petrov T. 2016. Linear distances between Markov chains. CONCUR: Concurrency Theory, LIPIcs, vol. 59, 20.","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. https://doi.org/10.4230/LIPIcs.CONCUR.2016.20.","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:10.4230/LIPIcs.CONCUR.2016.20","apa":"Daca, P., Henzinger, T. A., Kretinsky, J., & 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. https://doi.org/10.4230/LIPIcs.CONCUR.2016.20"},"department":[{"_id":"ToHe"},{"_id":"KrCh"},{"_id":"CaGu"}],"date_updated":"2023-09-07T11:58:33Z","title":"Linear distances between Markov chains","date_published":"2016-08-01T00:00:00Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file_date_updated":"2018-12-12T10:11:39Z","ddc":["004"],"publication_status":"published","abstract":[{"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. ","lang":"eng"}],"doi":"10.4230/LIPIcs.CONCUR.2016.20","year":"2016","day":"01","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.","oa":1,"publist_id":"6283","intvolume":" 59","scopus_import":1,"related_material":{"record":[{"id":"1155","relation":"dissertation_contains","status":"public"}]},"author":[{"first_name":"Przemyslaw","last_name":"Daca","full_name":"Daca, Przemyslaw","id":"49351290-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","orcid":"0000−0002−2985−7724","first_name":"Thomas A","last_name":"Henzinger"},{"last_name":"Kretinsky","first_name":"Jan","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","full_name":"Kretinsky, Jan"},{"first_name":"Tatjana","last_name":"Petrov","orcid":"0000-0002-9041-0905","id":"3D5811FC-F248-11E8-B48F-1D18A9856A87","full_name":"Petrov, Tatjana"}],"oa_version":"Published Version","project":[{"call_identifier":"FP7","name":"Quantitative Reactive Modeling","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425"},{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"name":"The Wittgenstein Prize","grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"quality_controlled":"1","volume":59,"language":[{"iso":"eng"}],"article_number":"20","file":[{"relation":"main_file","file_size":501827,"access_level":"open_access","creator":"system","file_id":"4895","date_updated":"2018-12-12T10:11:39Z","date_created":"2018-12-12T10:11:39Z","content_type":"application/pdf","file_name":"IST-2017-794-v1+1_LIPIcs-CONCUR-2016-20.pdf"}],"has_accepted_license":"1","month":"08","status":"public","type":"conference","_id":"1093","date_created":"2018-12-11T11:50:06Z","conference":{"name":"CONCUR: Concurrency Theory","location":"Quebec City; Canada","end_date":"2016-08-26","start_date":"2016-08-23"},"ec_funded":1,"pubrep_id":"794"},{"intvolume":" 1474","publist_id":"6281","publication":"High-Resolution Imaging of Cellular Proteins","acknowledgement":"We thank Prof. Elek Molnár for providing us a pan-AMPAR anti-body used in Fig.2 and Dr. Ludek Lovicar for technical assistance in scanning electron microscope imaging. This work was supported by the European Union (HBP—Project Ref. 604102). ","day":"12","page":"203 - 216","year":"2016","doi":"10.1007/978-1-4939-6352-2_12","publisher":"Springer","date_published":"2016-08-12T00:00:00Z","title":"Immunogold protein localization on grid-glued freeze-fracture replicas","abstract":[{"lang":"eng","text":"Immunogold labeling of freeze-fracture replicas has recently been used for high-resolution visualization of protein localization in electron microscopy. This method has higher labeling efficiency than conventional immunogold methods for membrane molecules allowing precise quantitative measurements. However, one of the limitations of freeze-fracture replica immunolabeling is difficulty in keeping structural orientation and identifying labeled profiles in complex tissues like brain. The difficulty is partly due to fragmentation of freeze-fracture replica preparations during labeling procedures and limited morphological clues on the replica surface. To overcome these issues, we introduce here a grid-glued replica method combined with SEM observation. This method allows histological staining before dissolving the tissue and easy handling of replicas during immunogold labeling, and keeps the whole replica surface intact without fragmentation. The procedure described here is also useful for matched double-replica analysis allowing further identification of labeled profiles in corresponding P-face and E-face."}],"publication_status":"published","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","alternative_title":["Methods in Molecular Biology"],"date_updated":"2023-09-05T14:09:01Z","department":[{"_id":"RySh"}],"citation":{"ieee":"H. Harada and R. Shigemoto, “Immunogold protein localization on grid-glued freeze-fracture replicas,” in High-Resolution Imaging of Cellular Proteins, vol. 1474, Springer, 2016, pp. 203–216.","ama":"Harada H, Shigemoto R. Immunogold protein localization on grid-glued freeze-fracture replicas. In: High-Resolution Imaging of Cellular Proteins. Vol 1474. Springer; 2016:203-216. doi:10.1007/978-1-4939-6352-2_12","ista":"Harada H, Shigemoto R. 2016.Immunogold protein localization on grid-glued freeze-fracture replicas. In: High-Resolution Imaging of Cellular Proteins. Methods in Molecular Biology, vol. 1474, 203–216.","chicago":"Harada, Harumi, and Ryuichi Shigemoto. “Immunogold Protein Localization on Grid-Glued Freeze-Fracture Replicas.” In High-Resolution Imaging of Cellular Proteins, 1474:203–16. Springer, 2016. https://doi.org/10.1007/978-1-4939-6352-2_12.","apa":"Harada, H., & Shigemoto, R. (2016). Immunogold protein localization on grid-glued freeze-fracture replicas. In High-Resolution Imaging of Cellular Proteins (Vol. 1474, pp. 203–216). Springer. https://doi.org/10.1007/978-1-4939-6352-2_12","mla":"Harada, Harumi, and Ryuichi Shigemoto. “Immunogold Protein Localization on Grid-Glued Freeze-Fracture Replicas.” High-Resolution Imaging of Cellular Proteins, vol. 1474, Springer, 2016, pp. 203–16, doi:10.1007/978-1-4939-6352-2_12.","short":"H. Harada, R. Shigemoto, in:, High-Resolution Imaging of Cellular Proteins, Springer, 2016, pp. 203–216."},"ec_funded":1,"status":"public","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"]},"date_created":"2018-12-11T11:50:06Z","_id":"1094","type":"book_chapter","language":[{"iso":"eng"}],"article_processing_charge":"No","acknowledged_ssus":[{"_id":"EM-Fac"}],"volume":1474,"month":"08","author":[{"id":"2E55CDF2-F248-11E8-B48F-1D18A9856A87","full_name":"Harada, Harumi","last_name":"Harada","first_name":"Harumi","orcid":"0000-0001-7429-7896"},{"last_name":"Shigemoto","first_name":"Ryuichi","orcid":"0000-0001-8761-9444","id":"499F3ABC-F248-11E8-B48F-1D18A9856A87","full_name":"Shigemoto, Ryuichi"}],"quality_controlled":"1","project":[{"_id":"25CD3DD2-B435-11E9-9278-68D0E5697425","grant_number":"604102","name":"Localization of ion channels and receptors by two and three-dimensional immunoelectron microscopic approaches","call_identifier":"FP7"}],"oa_version":"None"},{"_id":"1095","type":"conference","date_created":"2018-12-11T11:50:07Z","status":"public","pubrep_id":"793","conference":{"start_date":"2016-08-23","end_date":"2016-08-26","location":"Quebec City; Canada","name":"CONCUR: Concurrency Theory"},"ec_funded":1,"oa_version":"Published Version","project":[{"grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","name":"Quantitative Reactive Modeling"},{"call_identifier":"FWF","name":"The Wittgenstein Prize","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211"}],"quality_controlled":"1","author":[{"full_name":"Haas, Andreas","first_name":"Andreas","last_name":"Haas"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","first_name":"Thomas A","last_name":"Henzinger","orcid":"0000−0002−2985−7724"},{"last_name":"Holzer","first_name":"Andreas","full_name":"Holzer, Andreas"},{"full_name":"Kirsch, Christoph","first_name":"Christoph","last_name":"Kirsch"},{"first_name":"Michael","last_name":"Lippautz","full_name":"Lippautz, Michael"},{"full_name":"Payer, Hannes","first_name":"Hannes","last_name":"Payer"},{"last_name":"Sezgin","first_name":"Ali","full_name":"Sezgin, Ali","id":"4C7638DA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Sokolova","first_name":"Ana","full_name":"Sokolova, Ana"},{"full_name":"Veith, Helmut","first_name":"Helmut","last_name":"Veith"}],"article_number":"6","file":[{"file_name":"IST-2017-793-v1+1_LIPIcs-CONCUR-2016-6.pdf","content_type":"application/pdf","date_created":"2018-12-12T10:10:10Z","date_updated":"2018-12-12T10:10:10Z","file_id":"4795","creator":"system","access_level":"open_access","file_size":589747,"relation":"main_file"}],"has_accepted_license":"1","month":"08","volume":59,"language":[{"iso":"eng"}],"oa":1,"day":"01","year":"2016","doi":"10.4230/LIPIcs.CONCUR.2016.6","acknowledgement":"This work has been supported by the National Research Network RiSE on Rigorous Systems Engineering\r\n(Austrian Science Fund (FWF): S11402-N23, S11403-N23, S11404-N23, S11411-N23), a Google\r\nPhD Fellowship, an Erwin Schrödinger Fellowship (Austrian Science Fund (FWF): J3696-N26), EPSRC\r\ngrants EP/H005633/1 and EP/K008528/1, the Vienna Science and Technology Fund (WWTF) trough\r\ngrant PROSEED, the European Research Council (ERC) under grant 267989 (QUAREM) and by the\r\nAustrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award).","scopus_import":1,"publication":"Leibniz International Proceedings in Informatics","publist_id":"6280","intvolume":" 59","citation":{"chicago":"Haas, Andreas, Thomas A Henzinger, Andreas Holzer, Christoph Kirsch, Michael Lippautz, Hannes Payer, Ali Sezgin, Ana Sokolova, and Helmut Veith. “Local Linearizability for Concurrent Container-Type Data Structures.” In Leibniz International Proceedings in Informatics, Vol. 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. https://doi.org/10.4230/LIPIcs.CONCUR.2016.6.","ama":"Haas A, Henzinger TA, Holzer A, et al. Local linearizability for concurrent container-type data structures. In: Leibniz International Proceedings in Informatics. Vol 59. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2016. doi:10.4230/LIPIcs.CONCUR.2016.6","ista":"Haas A, Henzinger TA, Holzer A, Kirsch C, Lippautz M, Payer H, Sezgin A, Sokolova A, Veith H. 2016. Local linearizability for concurrent container-type data structures. Leibniz International Proceedings in Informatics. CONCUR: Concurrency Theory, LIPIcs, vol. 59, 6.","apa":"Haas, A., Henzinger, T. A., Holzer, A., Kirsch, C., Lippautz, M., Payer, H., … Veith, H. (2016). Local linearizability for concurrent container-type data structures. In Leibniz International Proceedings in Informatics (Vol. 59). Quebec City; Canada: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2016.6","ieee":"A. Haas et al., “Local linearizability for concurrent container-type data structures,” in Leibniz International Proceedings in Informatics, Quebec City; Canada, 2016, vol. 59.","mla":"Haas, Andreas, et al. “Local Linearizability for Concurrent Container-Type Data Structures.” Leibniz International Proceedings in Informatics, vol. 59, 6, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, doi:10.4230/LIPIcs.CONCUR.2016.6.","short":"A. Haas, T.A. Henzinger, A. Holzer, C. Kirsch, M. Lippautz, H. Payer, A. Sezgin, A. Sokolova, H. Veith, in:, Leibniz International Proceedings in Informatics, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016."},"department":[{"_id":"ToHe"}],"date_updated":"2021-01-12T06:48:14Z","alternative_title":["LIPIcs"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","ddc":["004"],"publication_status":"published","abstract":[{"text":" The semantics of concurrent data structures is usually given by a sequential specification and a consistency condition. Linearizability is the most popular consistency condition due to its simplicity and general applicability. Nevertheless, for applications that do not require all guarantees offered by linearizability, recent research has focused on improving performance and scalability of concurrent data structures by relaxing their semantics. In this paper, we present local linearizability, a relaxed consistency condition that is applicable to container-type concurrent data structures like pools, queues, and stacks. While linearizability requires that the effect of each operation is observed by all threads at the same time, local linearizability only requires that for each thread T, the effects of its local insertion operations and the effects of those removal operations that remove values inserted by T are observed by all threads at the same time. We investigate theoretical and practical properties of local linearizability and its relationship to many existing consistency conditions. We present a generic implementation method for locally linearizable data structures that uses existing linearizable data structures as building blocks. Our implementations show performance and scalability improvements over the original building blocks and outperform the fastest existing container-type implementations. ","lang":"eng"}],"title":"Local linearizability for concurrent container-type data structures","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_published":"2016-08-01T00:00:00Z","file_date_updated":"2018-12-12T10:10:10Z"},{"language":[{"iso":"eng"}],"date_published":"2016-06-20T00:00:00Z","publisher":"Cell Press","title":"Actin rings of power","volume":37,"month":"06","publication_status":"published","issue":"6","author":[{"id":"3436488C-F248-11E8-B48F-1D18A9856A87","full_name":"Schwayer, Cornelia","last_name":"Schwayer","first_name":"Cornelia","orcid":"0000-0001-5130-2226"},{"first_name":"Mateusz K","last_name":"Sikora","id":"2F74BCDE-F248-11E8-B48F-1D18A9856A87","full_name":"Sikora, Mateusz K"},{"first_name":"Jana","last_name":"Slovakova","id":"30F3F2F0-F248-11E8-B48F-1D18A9856A87","full_name":"Slovakova, Jana"},{"last_name":"Kardos","first_name":"Roland","id":"4039350E-F248-11E8-B48F-1D18A9856A87","full_name":"Kardos, Roland"},{"id":"39427864-F248-11E8-B48F-1D18A9856A87","full_name":"Heisenberg, Carl-Philipp J","first_name":"Carl-Philipp J","last_name":"Heisenberg","orcid":"0000-0002-0912-4566"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"CaHe"}],"quality_controlled":"1","date_updated":"2023-09-07T12:56:41Z","citation":{"ieee":"C. Schwayer, M. K. Sikora, J. Slovakova, R. Kardos, and C.-P. J. Heisenberg, “Actin rings of power,” Developmental Cell, vol. 37, no. 6. Cell Press, pp. 493–506, 2016.","ama":"Schwayer C, Sikora MK, Slovakova J, Kardos R, Heisenberg C-PJ. Actin rings of power. Developmental Cell. 2016;37(6):493-506. doi:10.1016/j.devcel.2016.05.024","chicago":"Schwayer, Cornelia, Mateusz K Sikora, Jana Slovakova, Roland Kardos, and Carl-Philipp J Heisenberg. “Actin Rings of Power.” Developmental Cell. Cell Press, 2016. https://doi.org/10.1016/j.devcel.2016.05.024.","ista":"Schwayer C, Sikora MK, Slovakova J, Kardos R, Heisenberg C-PJ. 2016. Actin rings of power. Developmental Cell. 37(6), 493–506.","apa":"Schwayer, C., Sikora, M. K., Slovakova, J., Kardos, R., & Heisenberg, C.-P. J. (2016). Actin rings of power. Developmental Cell. Cell Press. https://doi.org/10.1016/j.devcel.2016.05.024","short":"C. Schwayer, M.K. Sikora, J. Slovakova, R. Kardos, C.-P.J. Heisenberg, Developmental Cell 37 (2016) 493–506.","mla":"Schwayer, Cornelia, et al. “Actin Rings of Power.” Developmental Cell, vol. 37, no. 6, Cell Press, 2016, pp. 493–506, doi:10.1016/j.devcel.2016.05.024."},"oa_version":"None","publist_id":"6279","intvolume":" 37","publication":"Developmental Cell","scopus_import":1,"related_material":{"record":[{"id":"7186","relation":"part_of_dissertation","status":"public"}]},"page":"493 - 506","day":"20","year":"2016","status":"public","doi":"10.1016/j.devcel.2016.05.024","date_created":"2018-12-11T11:50:07Z","_id":"1096","type":"journal_article"},{"file":[{"content_type":"application/pdf","date_created":"2018-12-12T10:17:42Z","date_updated":"2018-12-12T10:17:42Z","file_name":"IST-2017-759-v1+1_copter.pdf","relation":"main_file","file_id":"5298","creator":"system","access_level":"open_access","file_size":33114420}],"article_number":"227","issue":"6","has_accepted_license":"1","month":"11","volume":35,"language":[{"iso":"eng"}],"oa_version":"Submitted Version","project":[{"call_identifier":"H2020","name":"Soft-bodied intelligence for Manipulation","grant_number":"645599","_id":"25082902-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","author":[{"full_name":"Du, Tao","first_name":"Tao","last_name":"Du"},{"full_name":"Schulz, Adriana","last_name":"Schulz","first_name":"Adriana"},{"full_name":"Zhu, Bo","last_name":"Zhu","first_name":"Bo"},{"id":"49876194-F248-11E8-B48F-1D18A9856A87","full_name":"Bickel, Bernd","last_name":"Bickel","first_name":"Bernd","orcid":"0000-0001-6511-9385"},{"full_name":"Matusik, Wojciech","first_name":"Wojciech","last_name":"Matusik"}],"pubrep_id":"759","conference":{"name":"SIGGRAPH Asia: Conference and Exhibition on Computer Graphics and Interactive Techniques in Asia","location":"Macao, China","end_date":"2016-12-08","start_date":"2016-12-05"},"ec_funded":1,"type":"conference","_id":"1097","date_created":"2018-12-11T11:50:07Z","status":"public","ddc":["006"],"publication_status":"published","abstract":[{"lang":"eng","text":"We present an interactive system for computational design, optimization, and fabrication of multicopters. Our computational approach allows non-experts to design, explore, and evaluate a wide range of different multicopters. We provide users with an intuitive interface for assembling a multicopter from a collection of components (e.g., propellers, motors, and carbon fiber rods). Our algorithm interactively optimizes shape and controller parameters of the current design to ensure its proper operation. In addition, we allow incorporating a variety of other metrics (such as payload, battery usage, size, and cost) into the design process and exploring tradeoffs between them. We show the efficacy of our method and system by designing, optimizing, fabricating, and operating multicopters with complex geometries and propeller configurations. We also demonstrate the ability of our optimization algorithm to improve the multicopter performance under different metrics."}],"title":"Computational multicopter design","file_date_updated":"2018-12-12T10:17:42Z","publisher":"ACM","date_published":"2016-11-01T00:00:00Z","citation":{"mla":"Du, Tao, et al. Computational Multicopter Design. Vol. 35, no. 6, 227, ACM, 2016, doi:10.1145/2980179.2982427.","short":"T. Du, A. Schulz, B. Zhu, B. Bickel, W. Matusik, in:, ACM, 2016.","ieee":"T. Du, A. Schulz, B. Zhu, B. Bickel, and W. Matusik, “Computational multicopter design,” presented at the SIGGRAPH Asia: Conference and Exhibition on Computer Graphics and Interactive Techniques in Asia, Macao, China, 2016, vol. 35, no. 6.","chicago":"Du, Tao, Adriana Schulz, Bo Zhu, Bernd Bickel, and Wojciech Matusik. “Computational Multicopter Design,” Vol. 35. ACM, 2016. https://doi.org/10.1145/2980179.2982427.","ista":"Du T, Schulz A, Zhu B, Bickel B, Matusik W. 2016. Computational multicopter design. SIGGRAPH Asia: Conference and Exhibition on Computer Graphics and Interactive Techniques in Asia, ACM Transactions on Graphics, vol. 35, 227.","ama":"Du T, Schulz A, Zhu B, Bickel B, Matusik W. Computational multicopter design. In: Vol 35. ACM; 2016. doi:10.1145/2980179.2982427","apa":"Du, T., Schulz, A., Zhu, B., Bickel, B., & Matusik, W. (2016). Computational multicopter design (Vol. 35). Presented at the SIGGRAPH Asia: Conference and Exhibition on Computer Graphics and Interactive Techniques in Asia, Macao, China: ACM. https://doi.org/10.1145/2980179.2982427"},"department":[{"_id":"BeBi"}],"date_updated":"2021-01-12T06:48:15Z","alternative_title":["ACM Transactions on Graphics"],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","scopus_import":1,"publist_id":"6278","intvolume":" 35","oa":1,"day":"01","year":"2016","doi":"10.1145/2980179.2982427","acknowledgement":"We thank Nobuyuki Umetani for his insightful suggestions in our discussions. We thank Alan Schultz and his colleagues at NRL for building the hexacopter and for the valuable discussions. We thank Randall Davis, Boris Katz, and Howard Shrobe at MIT for their advice. We are grateful to Nick Bandiera for preprocessing mechanical parts and providing 3D printing technical support; Charles Blouin from RCBenchmark for dynamometer hardware support; Brian Saavedra for the composition UI; Yingzhe Yuan for data acquisition and video recording in the experiments; Michael Foshey and David Kim for their comments on the draft of the paper. \r\n\r\n\r\nThis work was partially supported by Air Force Research Laboratory’s sponsorship of Julia: A Fresh Approach to Technical Computing and Data Processing (Sponsor Award ID FA8750-15-2- 0272, MIT Award ID 024831-00003), and NSF Expedition project (Sponsor Award ID CCF-1138967, MIT Award ID 020610-00002). The views expressed herein are not endorsed by the sponsors. This project has also received funding from the European Union’s Horizon 2020 research and innovation program under grant agreement No 645599. "},{"oa":1,"page":"3619-3627","year":"2016","day":"01","acknowledgement":"This work was in parts funded by the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no 308036.\r\n\r\n","scopus_import":1,"intvolume":" 29","publist_id":"6277","citation":{"short":"A. Pentina, R. Urner, in:, Neural Information Processing Systems, 2016, pp. 3619–3627.","mla":"Pentina, Anastasia, and Ruth Urner. Lifelong Learning with Weighted Majority Votes. Vol. 29, Neural Information Processing Systems, 2016, pp. 3619–27.","apa":"Pentina, A., & Urner, R. (2016). Lifelong learning with weighted majority votes (Vol. 29, pp. 3619–3627). Presented at the NIPS: Neural Information Processing Systems, Barcelona, Spain: Neural Information Processing Systems.","ama":"Pentina A, Urner R. Lifelong learning with weighted majority votes. In: Vol 29. Neural Information Processing Systems; 2016:3619-3627.","chicago":"Pentina, Anastasia, and Ruth Urner. “Lifelong Learning with Weighted Majority Votes,” 29:3619–27. Neural Information Processing Systems, 2016.","ista":"Pentina A, Urner R. 2016. Lifelong learning with weighted majority votes. NIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 29, 3619–3627.","ieee":"A. Pentina and R. Urner, “Lifelong learning with weighted majority votes,” presented at the NIPS: Neural Information Processing Systems, Barcelona, Spain, 2016, vol. 29, pp. 3619–3627."},"date_updated":"2021-01-12T06:48:15Z","department":[{"_id":"ChLa"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","alternative_title":["Advances in Neural Information Processing Systems"],"ddc":["006"],"abstract":[{"text":"Better understanding of the potential benefits of information transfer and representation learning is an important step towards the goal of building intelligent systems that are able to persist in the world and learn over time. In this work, we consider a setting where the learner encounters a stream of tasks but is able to retain only limited information from each encountered task, such as a learned predictor. In contrast to most previous works analyzing this scenario, we do not make any distributional assumptions on the task generating process. Instead, we formulate a complexity measure that captures the diversity of the observed tasks. We provide a lifelong learning algorithm with error guarantees for every observed task (rather than on average). We show sample complexity reductions in comparison to solving every task in isolation in terms of our task complexity measure. Further, our algorithmic framework can naturally be viewed as learning a representation from encountered tasks with a neural network.","lang":"eng"}],"publication_status":"published","title":"Lifelong learning with weighted majority votes","publisher":"Neural Information Processing Systems","date_published":"2016-12-01T00:00:00Z","file_date_updated":"2018-12-12T10:12:43Z","_id":"1098","type":"conference","date_created":"2018-12-11T11:50:08Z","status":"public","pubrep_id":"775","ec_funded":1,"conference":{"location":"Barcelona, Spain","name":"NIPS: Neural Information Processing Systems","start_date":"2016-12-05","end_date":"2016-12-10"},"oa_version":"Published Version","quality_controlled":"1","project":[{"call_identifier":"FP7","_id":"2532554C-B435-11E9-9278-68D0E5697425","grant_number":"308036","name":"Lifelong Learning of Visual Scene Understanding"}],"author":[{"id":"42E87FC6-F248-11E8-B48F-1D18A9856A87","full_name":"Pentina, Anastasia","last_name":"Pentina","first_name":"Anastasia"},{"full_name":"Urner, Ruth","first_name":"Ruth","last_name":"Urner"}],"file":[{"access_level":"open_access","file_size":237111,"file_id":"4961","creator":"system","relation":"main_file","file_name":"IST-2017-775-v1+1_main.pdf","date_created":"2018-12-12T10:12:42Z","date_updated":"2018-12-12T10:12:42Z","content_type":"application/pdf"},{"file_name":"IST-2017-775-v1+2_supplementary.pdf","content_type":"application/pdf","date_created":"2018-12-12T10:12:43Z","date_updated":"2018-12-12T10:12:43Z","file_id":"4962","creator":"system","access_level":"open_access","file_size":185818,"relation":"main_file"}],"has_accepted_license":"1","month":"12","volume":29,"language":[{"iso":"eng"}]}]