[{"department":[{"_id":"KrCh"}],"title":"The subclonal evolution of cancer","author":[{"full_name":"Reiter, Johannes","last_name":"Reiter","first_name":"Johannes","orcid":"0000-0002-0170-7353","id":"4A918E98-F248-11E8-B48F-1D18A9856A87"}],"OA_place":"publisher","day":"01","status":"public","supervisor":[{"orcid":"0000-0002-4561-241X","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"}],"article_processing_charge":"No","type":"dissertation","citation":{"chicago":"Reiter, Johannes. “The Subclonal Evolution of Cancer.” Institute of Science and Technology Austria, 2015.","ama":"Reiter J. The subclonal evolution of cancer. 2015.","short":"J. Reiter, The Subclonal Evolution of Cancer, Institute of Science and Technology Austria, 2015.","ieee":"J. Reiter, “The subclonal evolution of cancer,” Institute of Science and Technology Austria, 2015.","apa":"Reiter, J. (2015). <i>The subclonal evolution of cancer</i>. Institute of Science and Technology Austria.","ista":"Reiter J. 2015. The subclonal evolution of cancer. Institute of Science and Technology Austria.","mla":"Reiter, Johannes. <i>The Subclonal Evolution of Cancer</i>. Institute of Science and Technology Austria, 2015."},"page":"183","corr_author":"1","year":"2015","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publisher":"Institute of Science and Technology Austria","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"2000"},{"status":"public","relation":"part_of_dissertation","id":"1709"},{"status":"public","id":"2858","relation":"part_of_dissertation"},{"status":"public","relation":"part_of_dissertation","id":"2816"},{"status":"public","id":"2247","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"3260","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"3157"}]},"date_created":"2018-12-11T11:51:48Z","month":"04","alternative_title":["ISTA Thesis"],"degree_awarded":"PhD","publication_status":"published","date_published":"2015-04-01T00:00:00Z","_id":"1400","abstract":[{"lang":"eng","text":"Cancer results from an uncontrolled growth of abnormal cells. Sequentially accumulated genetic and epigenetic alterations decrease cell death and increase cell replication. We used mathematical models to quantify the effect of driver gene mutations. The recently developed targeted therapies can lead to dramatic regressions. However, in solid cancers, clinical responses are often short-lived because resistant cancer cells evolve. We estimated that approximately 50 different mutations can confer resistance to a typical targeted therapeutic agent. We find that resistant cells are likely to be present in expanded subclones before the start of the treatment. The dominant strategy to prevent the evolution of resistance is combination therapy. Our analytical results suggest that in most patients, dual therapy, but not monotherapy, can result in long-term disease control. However, long-term control can only occur if there are no possible mutations in the genome that can cause cross-resistance to both drugs. Furthermore, we showed that simultaneous therapy with two drugs is much more likely to result in long-term disease control than sequential therapy with the same drugs. To improve our understanding of the underlying subclonal evolution we reconstruct the evolutionary history of a patient's cancer from next-generation sequencing data of spatially-distinct DNA samples. Using a quantitative measure of genetic relatedness, we found that pancreatic cancers and their metastases demonstrated a higher level of relatedness than that expected for any two cells randomly taken from a normal tissue. This minimal amount of genetic divergence among advanced lesions indicates that genetic heterogeneity, when quantitatively defined, is not a fundamental feature of the natural history of untreated pancreatic cancers. Our newly developed, phylogenomic tool Treeomics finds evidence for seeding patterns of metastases and can directly be used to discover rules governing the evolution of solid malignancies to transform cancer into a more predictable disease."}],"publist_id":"5807","date_updated":"2026-04-09T14:26:24Z","language":[{"iso":"eng"}],"oa_version":"None","publication_identifier":{"issn":["2663-337X"]}},{"publisher":"Institute of Science and Technology Austria","date_created":"2018-12-11T11:51:48Z","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publist_id":"5806","publication_identifier":{"issn":["2663-337X"]},"oa_version":"Published Version","degree_awarded":"PhD","doi":"10.15479/at:ista:1401","file":[{"creator":"dernst","file_id":"9177","date_updated":"2021-02-22T11:33:17Z","checksum":"3605b402bb6934e09ae4cf672c84baf7","success":1,"file_name":"2015_Thesis_Sharmanska.pdf","file_size":7964342,"date_created":"2021-02-22T11:33:17Z","relation":"main_file","content_type":"application/pdf","access_level":"open_access"},{"checksum":"e37593b3ee75bf3180629df2d6ca8f4e","file_name":"2015_Thesis_Sharmanska_pdfa.pdf","date_updated":"2021-11-17T13:47:24Z","creator":"cchlebak","file_id":"10297","relation":"main_file","content_type":"application/pdf","access_level":"closed","file_size":7372241,"date_created":"2021-11-16T14:40:45Z"}],"abstract":[{"text":"The human ability to recognize objects in complex scenes has driven research in the computer vision field over couple of decades. This thesis focuses on the object recognition task in images. That is, given the image, we want the computer system to be able to predict the class of the object that appears in the image. A recent successful attempt to bridge semantic understanding of the image perceived by humans and by computers uses attribute-based models. Attributes are semantic properties of the objects shared across different categories, which humans and computers can decide on. To explore the attribute-based models we take a statistical machine learning approach, and address two key learning challenges in view of object recognition task: learning augmented attributes as mid-level discriminative feature representation, and learning with attributes as privileged information. Our main contributions are parametric and non-parametric models and algorithms to solve these frameworks. In the parametric approach, we explore an autoencoder model combined with the large margin nearest neighbor principle for mid-level feature learning, and linear support vector machines for learning with privileged information. In the non-parametric approach, we propose a supervised Indian Buffet Process for automatic augmentation of semantic attributes, and explore the Gaussian Processes classification framework for learning with privileged information. A thorough experimental analysis shows the effectiveness of the proposed models in both parametric and non-parametric views.","lang":"eng"}],"publication_status":"published","author":[{"orcid":"0000-0003-0192-9308","first_name":"Viktoriia","id":"2EA6D09E-F248-11E8-B48F-1D18A9856A87","full_name":"Sharmanska, Viktoriia","last_name":"Sharmanska"}],"acknowledgement":"I would like to thank my supervisor, Christoph Lampert, for guidance throughout my studies and for patience in transforming me into a scientist, and my thesis committee, Chris Wojtan and Horst Bischof, for their help and advice. \r\n\r\nI would like to thank Elisabeth Hacker who perfectly assisted all my administrative needs and was always nice and friendly to me, and the campus team for making the IST Austria campus my second home. \r\nI was honored to collaborate with brilliant researchers and to learn from their experience. Undoubtedly, I learned most of all from Novi Quadrianto: brainstorming our projects and getting exciting results was the most enjoyable part of my work – thank you! I am also grateful to David Knowles, Zoubin Ghahramani, Daniel Hernández-Lobato, Kristian Kersting and Anastasia Pentina for the fantastic projects we worked on together, and to Kristen Grauman and Adriana Kovashka for the exceptional experience working with user studies. I would like to thank my colleagues at IST Austria and my office mates who shared their happy moods, scientific breakthroughs and thought-provoking conversations with me: Chao, Filip, Rustem, Asya, Sameh, Alex, Vlad, Mayu, Neel, Csaba, Thomas, Vladimir, Cristina, Alex Z., Avro, Amelie and Emilie, Andreas H. and Andreas E., Chris, Lena, Michael, Ali and Ipek, Vera, Igor, Katia. Special thanks to Morten for the countless games of table soccer we played together and the tournaments we teamed up for: we will definitely win next time:) A very warm hug to Asya for always being so inspiring and supportive to me, and for helping me to increase the proportion of female computer scientists in our group. ","department":[{"_id":"ChLa"},{"_id":"GradSch"}],"article_processing_charge":"No","type":"dissertation","oa":1,"citation":{"chicago":"Sharmanska, Viktoriia. “Learning with Attributes for Object Recognition: Parametric and Non-Parametrics Views.” Institute of Science and Technology Austria, 2015. <a href=\"https://doi.org/10.15479/at:ista:1401\">https://doi.org/10.15479/at:ista:1401</a>.","short":"V. Sharmanska, Learning with Attributes for Object Recognition: Parametric and Non-Parametrics Views, Institute of Science and Technology Austria, 2015.","ama":"Sharmanska V. Learning with attributes for object recognition: Parametric and non-parametrics views. 2015. doi:<a href=\"https://doi.org/10.15479/at:ista:1401\">10.15479/at:ista:1401</a>","ieee":"V. Sharmanska, “Learning with attributes for object recognition: Parametric and non-parametrics views,” Institute of Science and Technology Austria, 2015.","mla":"Sharmanska, Viktoriia. <i>Learning with Attributes for Object Recognition: Parametric and Non-Parametrics Views</i>. Institute of Science and Technology Austria, 2015, doi:<a href=\"https://doi.org/10.15479/at:ista:1401\">10.15479/at:ista:1401</a>.","apa":"Sharmanska, V. (2015). <i>Learning with attributes for object recognition: Parametric and non-parametrics views</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:1401\">https://doi.org/10.15479/at:ista:1401</a>","ista":"Sharmanska V. 2015. Learning with attributes for object recognition: Parametric and non-parametrics views. Institute of Science and Technology Austria."},"day":"01","OA_place":"publisher","file_date_updated":"2021-11-17T13:47:24Z","month":"04","has_accepted_license":"1","year":"2015","ddc":["000"],"language":[{"iso":"eng"}],"date_updated":"2026-04-09T14:25:49Z","alternative_title":["ISTA Thesis"],"_id":"1401","main_file_link":[{"url":"http://users.sussex.ac.uk/~nq28/viktoriia/Thesis_Sharmanska.pdf"}],"date_published":"2015-04-01T00:00:00Z","title":"Learning with attributes for object recognition: Parametric and non-parametrics views","supervisor":[{"first_name":"Christoph","orcid":"0000-0001-8622-7887","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert","full_name":"Lampert, Christoph"}],"corr_author":"1","page":"144","status":"public"},{"intvolume":"        28","status":"public","day":"01","citation":{"ama":"Kwitt R, Huber S, Niethammer M, Lin W, Bauer U. Statistical topological data analysis-A kernel perspective. In: Vol 28. Neural Information Processing Systems Foundation; 2015:3070-3078.","short":"R. Kwitt, S. Huber, M. Niethammer, W. Lin, U. Bauer, in:, Neural Information Processing Systems Foundation, 2015, pp. 3070–3078.","chicago":"Kwitt, Roland, Stefan Huber, Marc Niethammer, Weili Lin, and Ulrich Bauer. “Statistical Topological Data Analysis-A Kernel Perspective,” 28:3070–78. Neural Information Processing Systems Foundation, 2015.","ista":"Kwitt R, Huber S, Niethammer M, Lin W, Bauer U. 2015. Statistical topological data analysis-A kernel perspective. NIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 28, 3070–3078.","apa":"Kwitt, R., Huber, S., Niethammer, M., Lin, W., &#38; Bauer, U. (2015). Statistical topological data analysis-A kernel perspective (Vol. 28, pp. 3070–3078). Presented at the NIPS: Neural Information Processing Systems, Montreal, Canada: Neural Information Processing Systems Foundation.","mla":"Kwitt, Roland, et al. <i>Statistical Topological Data Analysis-A Kernel Perspective</i>. Vol. 28, Neural Information Processing Systems Foundation, 2015, pp. 3070–78.","ieee":"R. Kwitt, S. Huber, M. Niethammer, W. Lin, and U. Bauer, “Statistical topological data analysis-A kernel perspective,” presented at the NIPS: Neural Information Processing Systems, Montreal, Canada, 2015, vol. 28, pp. 3070–3078."},"page":"3070 - 3078","oa":1,"article_processing_charge":"No","type":"conference","acknowledgement":"This work was partially supported by the Austrian Science FUnd, project no. KLI 00012.","department":[{"_id":"HeEd"}],"author":[{"first_name":"Roland","full_name":"Kwitt, Roland","last_name":"Kwitt"},{"first_name":"Stefan","orcid":"0000-0002-8871-5814","id":"4700A070-F248-11E8-B48F-1D18A9856A87","last_name":"Huber","full_name":"Huber, Stefan"},{"first_name":"Marc","full_name":"Niethammer, Marc","last_name":"Niethammer"},{"first_name":"Weili","full_name":"Lin, Weili","last_name":"Lin"},{"full_name":"Bauer, Ulrich","last_name":"Bauer","id":"2ADD483A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9683-0724","first_name":"Ulrich"}],"volume":28,"title":"Statistical topological data analysis-A kernel perspective","date_published":"2015-12-01T00:00:00Z","publication_status":"published","_id":"1424","abstract":[{"text":"We consider the problem of statistical computations with persistence diagrams, a summary representation of topological features in data. These diagrams encode persistent homology, a widely used invariant in topological data analysis. While several avenues towards a statistical treatment of the diagrams have been explored recently, we follow an alternative route that is motivated by the success of methods based on the embedding of probability measures into reproducing kernel Hilbert spaces. In fact, a positive definite kernel on persistence diagrams has recently been proposed, connecting persistent homology to popular kernel-based learning techniques such as support vector machines. However, important properties of that kernel enabling a principled use in the context of probability measure embeddings remain to be explored. Our contribution is to close this gap by proving universality of a variant of the original kernel, and to demonstrate its effective use in twosample hypothesis testing on synthetic as well as real-world data.","lang":"eng"}],"main_file_link":[{"url":"https://papers.nips.cc/paper/5887-statistical-topological-data-analysis-a-kernel-perspective","open_access":"1"}],"alternative_title":["Advances in Neural Information Processing Systems"],"oa_version":"Submitted Version","quality_controlled":"1","language":[{"iso":"eng"}],"publist_id":"5782","date_updated":"2025-06-03T11:41:36Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Montreal, Canada","start_date":"2015-12-07","name":"NIPS: Neural Information Processing Systems","end_date":"2015-12-12"},"year":"2015","date_created":"2018-12-11T11:51:56Z","month":"12","publisher":"Neural Information Processing Systems Foundation"},{"page":"1540 - 1548","status":"public","title":"Lifelong learning with non-i.i.d. tasks","volume":2015,"language":[{"iso":"eng"}],"date_updated":"2025-06-03T11:41:45Z","quality_controlled":"1","alternative_title":["Advances in Neural Information Processing Systems"],"main_file_link":[{"open_access":"1","url":"http://papers.nips.cc/paper/6007-lifelong-learning-with-non-iid-tasks"}],"_id":"1425","date_published":"2015-01-01T00:00:00Z","month":"01","year":"2015","conference":{"end_date":"2015-12-12","name":"NIPS: Neural Information Processing Systems","start_date":"2015-12-07","location":"Montreal, Canada"},"article_processing_charge":"No","type":"conference","oa":1,"citation":{"ista":"Pentina A, Lampert C. 2015. Lifelong learning with non-i.i.d. tasks. NIPS: Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 2015, 1540–1548.","apa":"Pentina, A., &#38; Lampert, C. (2015). Lifelong learning with non-i.i.d. tasks (Vol. 2015, pp. 1540–1548). Presented at the NIPS: Neural Information Processing Systems, Montreal, Canada: Neural Information Processing Systems Foundation.","mla":"Pentina, Anastasia, and Christoph Lampert. <i>Lifelong Learning with Non-i.i.d. Tasks</i>. Vol. 2015, Neural Information Processing Systems Foundation, 2015, pp. 1540–48.","ieee":"A. Pentina and C. Lampert, “Lifelong learning with non-i.i.d. tasks,” presented at the NIPS: Neural Information Processing Systems, Montreal, Canada, 2015, vol. 2015, pp. 1540–1548.","ama":"Pentina A, Lampert C. Lifelong learning with non-i.i.d. tasks. In: Vol 2015. Neural Information Processing Systems Foundation; 2015:1540-1548.","short":"A. Pentina, C. Lampert, in:, Neural Information Processing Systems Foundation, 2015, pp. 1540–1548.","chicago":"Pentina, Anastasia, and Christoph Lampert. “Lifelong Learning with Non-i.i.d. Tasks,” 2015:1540–48. Neural Information Processing Systems Foundation, 2015."},"day":"01","intvolume":"      2015","scopus_import":"1","author":[{"last_name":"Pentina","full_name":"Pentina, Anastasia","first_name":"Anastasia","id":"42E87FC6-F248-11E8-B48F-1D18A9856A87"},{"id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","first_name":"Christoph","orcid":"0000-0001-8622-7887","last_name":"Lampert","full_name":"Lampert, Christoph"}],"project":[{"name":"Lifelong Learning of Visual Scene Understanding","grant_number":"308036","_id":"2532554C-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"department":[{"_id":"ChLa"}],"ec_funded":1,"publist_id":"5781","oa_version":"None","abstract":[{"lang":"eng","text":"In this work we aim at extending the theoretical foundations of lifelong learning. Previous work analyzing this scenario is based on the assumption that learning tasks are sampled i.i.d. from a task environment or limited to strongly constrained data distributions. Instead, we study two scenarios when lifelong learning is possible, even though the observed tasks do not form an i.i.d. sample: first, when they are sampled from the same environment, but possibly with dependencies, and second, when the task environment is allowed to change over time in a consistent way. In the first case we prove a PAC-Bayesian theorem that can be seen as a direct generalization of the analogous previous result for the i.i.d. case. For the second scenario we propose to learn an inductive bias in form of a transfer procedure. We present a generalization bound and show on a toy example how it can be used to identify a beneficial transfer algorithm."}],"publication_status":"published","publisher":"Neural Information Processing Systems Foundation","date_created":"2018-12-11T11:51:57Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"date_published":"2015-07-11T00:00:00Z","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1504.06260"}],"_id":"1430","quality_controlled":"1","language":[{"iso":"eng"}],"date_updated":"2025-09-23T08:50:33Z","conference":{"end_date":"2015-07-15","name":"GECCO: Genetic and evolutionary computation conference","start_date":"2015-07-11","location":"Madrid, Spain"},"year":"2015","month":"07","status":"public","page":"1455 - 1462","arxiv":1,"title":"First steps towards a runtime comparison of natural and artificial evolution","publication_status":"published","abstract":[{"lang":"eng","text":"Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse their runtime on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrence of new mutations is much longer than the time it takes for a new beneficial mutation to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a (1+1)-type process where the probability of accepting a new genotype (improvements or worsenings) depends on the change in fitness. We present an initial runtime analysis of SSWM, quantifying its performance for various parameters and investigating differences to the (1+1) EA. We show that SSWM can have a moderate advantage over the (1+1) EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1) EA by taking advantage of information on the fitness gradient."}],"publication":"Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation","doi":"10.1145/2739480.2754758","oa_version":"Preprint","publist_id":"5768","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2018-12-11T11:51:58Z","publisher":"ACM","day":"11","citation":{"ieee":"T. Paixao, D. Sudholt, J. Heredia, and B. Trubenova, “First steps towards a runtime comparison of natural and artificial evolution,” in <i>Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation</i>, Madrid, Spain, 2015, pp. 1455–1462.","ista":"Paixao T, Sudholt D, Heredia J, Trubenova B. 2015. First steps towards a runtime comparison of natural and artificial evolution. Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. GECCO: Genetic and evolutionary computation conference, 1455–1462.","apa":"Paixao, T., Sudholt, D., Heredia, J., &#38; Trubenova, B. (2015). First steps towards a runtime comparison of natural and artificial evolution. In <i>Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation</i> (pp. 1455–1462). Madrid, Spain: ACM. <a href=\"https://doi.org/10.1145/2739480.2754758\">https://doi.org/10.1145/2739480.2754758</a>","mla":"Paixao, Tiago, et al. “First Steps towards a Runtime Comparison of Natural and Artificial Evolution.” <i>Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation</i>, ACM, 2015, pp. 1455–62, doi:<a href=\"https://doi.org/10.1145/2739480.2754758\">10.1145/2739480.2754758</a>.","chicago":"Paixao, Tiago, Dirk Sudholt, Jorge Heredia, and Barbora Trubenova. “First Steps towards a Runtime Comparison of Natural and Artificial Evolution.” In <i>Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation</i>, 1455–62. ACM, 2015. <a href=\"https://doi.org/10.1145/2739480.2754758\">https://doi.org/10.1145/2739480.2754758</a>.","ama":"Paixao T, Sudholt D, Heredia J, Trubenova B. First steps towards a runtime comparison of natural and artificial evolution. In: <i>Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation</i>. ACM; 2015:1455-1462. doi:<a href=\"https://doi.org/10.1145/2739480.2754758\">10.1145/2739480.2754758</a>","short":"T. Paixao, D. Sudholt, J. Heredia, B. Trubenova, in:, Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, ACM, 2015, pp. 1455–1462."},"oa":1,"type":"conference","article_processing_charge":"No","ec_funded":1,"department":[{"_id":"NiBa"},{"_id":"CaGu"}],"project":[{"grant_number":"618091","_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation","call_identifier":"FP7"}],"author":[{"orcid":"0000-0003-2361-3953","id":"2C5658E6-F248-11E8-B48F-1D18A9856A87","first_name":"Tiago","last_name":"Paixao","full_name":"Paixao, Tiago"},{"first_name":"Dirk","last_name":"Sudholt","full_name":"Sudholt, Dirk"},{"last_name":"Heredia","full_name":"Heredia, Jorge","first_name":"Jorge"},{"last_name":"Trubenova","full_name":"Trubenova, Barbora","id":"42302D54-F248-11E8-B48F-1D18A9856A87","first_name":"Barbora","orcid":"0000-0002-6873-2967"}],"isi":1,"external_id":{"isi":["000358795700182"],"arxiv":["1504.06260"]},"scopus_import":"1"},{"quality_controlled":"1","date_updated":"2025-09-23T09:50:52Z","language":[{"iso":"eng"}],"date_published":"2015-09-04T00:00:00Z","main_file_link":[{"open_access":"1","url":"http://epubs.surrey.ac.uk/808055/"}],"_id":"1474","month":"09","conference":{"location":"Verona, Italy","end_date":"2015-07-17","name":"CSF: Computer Security Foundations","start_date":"2015-07-13"},"year":"2015","page":"46-60","status":"public","title":"Policy privacy in cryptographic access control","oa_version":"Submitted Version","publist_id":"5722","publication_status":"published","abstract":[{"text":"Cryptographic access control offers selective access to encrypted data via a combination of key management and functionality-rich cryptographic schemes, such as attribute-based encryption. Using this approach, publicly available meta-data may inadvertently leak information on the access policy that is enforced by cryptography, which renders cryptographic access control unusable in settings where this information is highly sensitive. We begin to address this problem by presenting rigorous definitions for policy privacy in cryptographic access control. For concreteness we set our results in the model of Role-Based Access Control (RBAC), where we identify and formalize several different flavors of privacy, however, our framework should serve as inspiration for other models of access control. Based on our insights we propose a new system which significantly improves on the privacy properties of state-of-the-art constructions. Our design is based on a novel type of privacy-preserving attribute-based encryption, which we introduce and show how to instantiate. We present our results in the context of a cryptographic RBAC system by Ferrara et al. (CSF'13), which uses cryptography to control read access to files, while write access is still delegated to trusted monitors. We give an extension of the construction that permits cryptographic control over write access. Our construction assumes that key management uses out-of-band channels between the policy enforcer and the users but eliminates completely the need for monitoring read/write access to the data.","lang":"eng"}],"doi":"10.1109/CSF.2015.11","date_created":"2018-12-11T11:52:14Z","publisher":"IEEE","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","citation":{"chicago":"Ferrara, Anna, Georg Fuchsbauer, Bin Liu, and Bogdan Warinschi. “Policy Privacy in Cryptographic Access Control,” 46–60. IEEE, 2015. <a href=\"https://doi.org/10.1109/CSF.2015.11\">https://doi.org/10.1109/CSF.2015.11</a>.","short":"A. Ferrara, G. Fuchsbauer, B. Liu, B. Warinschi, in:, IEEE, 2015, pp. 46–60.","ama":"Ferrara A, Fuchsbauer G, Liu B, Warinschi B. Policy privacy in cryptographic access control. In: IEEE; 2015:46-60. doi:<a href=\"https://doi.org/10.1109/CSF.2015.11\">10.1109/CSF.2015.11</a>","ieee":"A. Ferrara, G. Fuchsbauer, B. Liu, and B. Warinschi, “Policy privacy in cryptographic access control,” presented at the CSF: Computer Security Foundations, Verona, Italy, 2015, pp. 46–60.","apa":"Ferrara, A., Fuchsbauer, G., Liu, B., &#38; Warinschi, B. (2015). Policy privacy in cryptographic access control (pp. 46–60). Presented at the CSF: Computer Security Foundations, Verona, Italy: IEEE. <a href=\"https://doi.org/10.1109/CSF.2015.11\">https://doi.org/10.1109/CSF.2015.11</a>","ista":"Ferrara A, Fuchsbauer G, Liu B, Warinschi B. 2015. Policy privacy in cryptographic access control. CSF: Computer Security Foundations, 46–60.","mla":"Ferrara, Anna, et al. <i>Policy Privacy in Cryptographic Access Control</i>. IEEE, 2015, pp. 46–60, doi:<a href=\"https://doi.org/10.1109/CSF.2015.11\">10.1109/CSF.2015.11</a>."},"oa":1,"type":"conference","article_processing_charge":"No","day":"04","author":[{"full_name":"Ferrara, Anna","last_name":"Ferrara","first_name":"Anna"},{"first_name":"Georg","id":"46B4C3EE-F248-11E8-B48F-1D18A9856A87","last_name":"Fuchsbauer","full_name":"Fuchsbauer, Georg"},{"full_name":"Liu, Bin","last_name":"Liu","first_name":"Bin"},{"first_name":"Bogdan","full_name":"Warinschi, Bogdan","last_name":"Warinschi"}],"external_id":{"isi":["000380428500004"]},"isi":1,"scopus_import":"1","ec_funded":1,"department":[{"_id":"KrPi"}],"project":[{"call_identifier":"FP7","grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425","name":"Provable Security for Physical Cryptography"}]},{"external_id":{"arxiv":["1411.4023"]},"scopus_import":"1","author":[{"last_name":"Ahmed","full_name":"Ahmed, Umair","first_name":"Umair"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Gulwani, Sumit","last_name":"Gulwani","first_name":"Sumit"}],"department":[{"_id":"KrCh"}],"acknowledgement":"A Technical Report of this paper is available at: \r\nhttps://repository.ist.ac.at/id/eprint/146.\r\n","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"_id":"2587B514-B435-11E9-9278-68D0E5697425","name":"Microsoft Research Faculty Fellowship"}],"ec_funded":1,"oa":1,"article_processing_charge":"No","type":"conference","citation":{"apa":"Ahmed, U., Chatterjee, K., &#38; Gulwani, S. (2015). Automatic generation of alternative starting positions for simple traditional board games. In <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i> (Vol. 2, pp. 745–752). Austin, TX, USA: AAAI Press.","ista":"Ahmed U, Chatterjee K, Gulwani S. 2015. Automatic generation of alternative starting positions for simple traditional board games. Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence vol. 2, 745–752.","mla":"Ahmed, Umair, et al. “Automatic Generation of Alternative Starting Positions for Simple Traditional Board Games.” <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i>, vol. 2, AAAI Press, 2015, pp. 745–52.","ieee":"U. Ahmed, K. Chatterjee, and S. Gulwani, “Automatic generation of alternative starting positions for simple traditional board games,” in <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i>, Austin, TX, USA, 2015, vol. 2, pp. 745–752.","short":"U. Ahmed, K. Chatterjee, S. Gulwani, in:, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015, pp. 745–752.","ama":"Ahmed U, Chatterjee K, Gulwani S. Automatic generation of alternative starting positions for simple traditional board games. In: <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i>. Vol 2. AAAI Press; 2015:745-752.","chicago":"Ahmed, Umair, Krishnendu Chatterjee, and Sumit Gulwani. “Automatic Generation of Alternative Starting Positions for Simple Traditional Board Games.” In <i>Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence</i>, 2:745–52. AAAI Press, 2015."},"day":"01","intvolume":"         2","publisher":"AAAI Press","date_created":"2018-12-11T11:52:16Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"5713","oa_version":"None","publication_status":"published","publication":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence","abstract":[{"text":"Simple board games, like Tic-Tac-Toe and CONNECT-4, play an important role not only in the development of mathematical and logical skills, but also in the emotional and social development. In this paper, we address the problem of generating targeted starting positions for such games. This can facilitate new approaches for bringing novice players to mastery, and also leads to discovery of interesting game variants. We present an approach that generates starting states of varying hardness levels for player 1 in a two-player board game, given rules of the board game, the desired number of steps required for player 1 to win, and the expertise levels of the two players. Our approach leverages symbolic methods and iterative simulation to efficiently search the extremely large state space. We present experimental results that include discovery of states of varying hardness levels for several simple grid-based board games. The presence of such states for standard game variants like 4×4 Tic-Tac-Toe opens up new games to be played that have never been played as the default start state is heavily biased. ","lang":"eng"}],"title":"Automatic generation of alternative starting positions for simple traditional board games","volume":2,"page":"745 - 752","arxiv":1,"status":"public","related_material":{"record":[{"id":"5410","relation":"earlier_version","status":"public"}]},"month":"01","conference":{"name":"AAAI: Conference on Artificial Intelligence","start_date":"2015-01-25","end_date":"2015-01-30","location":"Austin, TX, USA"},"year":"2015","date_updated":"2025-05-19T11:10:17Z","language":[{"iso":"eng"}],"quality_controlled":"1","date_published":"2015-01-01T00:00:00Z","_id":"1481","main_file_link":[{"url":"https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/download/9523/9300","open_access":"1"}]},{"oa_version":"Preprint","publication_identifier":{"eisbn":["978-1-4673-6964-0 "]},"date_updated":"2025-06-11T06:37:43Z","language":[{"iso":"eng"}],"publist_id":"5709","_id":"1483","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1412.6821"}],"abstract":[{"lang":"eng","text":"Topological data analysis offers a rich source of valuable information to study vision problems. Yet, so far we lack a theoretically sound connection to popular kernel-based learning techniques, such as kernel SVMs or kernel PCA. In this work, we establish such a connection by designing a multi-scale kernel for persistence diagrams, a stable summary representation of topological features in data. We show that this kernel is positive definite and prove its stability with respect to the 1-Wasserstein distance. Experiments on two benchmark datasets for 3D shape classification/retrieval and texture recognition show considerable performance gains of the proposed method compared to an alternative approach that is based on the recently introduced persistence landscapes."}],"date_published":"2015-10-14T00:00:00Z","publication_status":"published","doi":"10.1109/CVPR.2015.7299106","month":"10","date_created":"2018-12-11T11:52:17Z","publisher":"IEEE","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2015","conference":{"location":"Boston, MA, USA","start_date":"2015-06-07","name":"CVPR: Computer Vision and Pattern Recognition","end_date":"2015-06-12"},"arxiv":1,"citation":{"ieee":"J. Reininghaus, S. Huber, U. Bauer, and R. Kwitt, “A stable multi-scale kernel for topological machine learning,” presented at the CVPR: Computer Vision and Pattern Recognition, Boston, MA, USA, 2015, pp. 4741–4748.","mla":"Reininghaus, Jan, et al. <i>A Stable Multi-Scale Kernel for Topological Machine Learning</i>. IEEE, 2015, pp. 4741–48, doi:<a href=\"https://doi.org/10.1109/CVPR.2015.7299106\">10.1109/CVPR.2015.7299106</a>.","ista":"Reininghaus J, Huber S, Bauer U, Kwitt R. 2015. A stable multi-scale kernel for topological machine learning. CVPR: Computer Vision and Pattern Recognition, 4741–4748.","apa":"Reininghaus, J., Huber, S., Bauer, U., &#38; Kwitt, R. (2015). A stable multi-scale kernel for topological machine learning (pp. 4741–4748). Presented at the CVPR: Computer Vision and Pattern Recognition, Boston, MA, USA: IEEE. <a href=\"https://doi.org/10.1109/CVPR.2015.7299106\">https://doi.org/10.1109/CVPR.2015.7299106</a>","chicago":"Reininghaus, Jan, Stefan Huber, Ulrich Bauer, and Roland Kwitt. “A Stable Multi-Scale Kernel for Topological Machine Learning,” 4741–48. IEEE, 2015. <a href=\"https://doi.org/10.1109/CVPR.2015.7299106\">https://doi.org/10.1109/CVPR.2015.7299106</a>.","ama":"Reininghaus J, Huber S, Bauer U, Kwitt R. A stable multi-scale kernel for topological machine learning. In: IEEE; 2015:4741-4748. doi:<a href=\"https://doi.org/10.1109/CVPR.2015.7299106\">10.1109/CVPR.2015.7299106</a>","short":"J. Reininghaus, S. Huber, U. Bauer, R. Kwitt, in:, IEEE, 2015, pp. 4741–4748."},"page":"4741 - 4748","type":"conference","article_processing_charge":"No","oa":1,"status":"public","day":"14","author":[{"last_name":"Reininghaus","full_name":"Reininghaus, Jan","first_name":"Jan","id":"4505473A-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Huber, Stefan","last_name":"Huber","orcid":"0000-0002-8871-5814","id":"4700A070-F248-11E8-B48F-1D18A9856A87","first_name":"Stefan"},{"full_name":"Bauer, Ulrich","last_name":"Bauer","first_name":"Ulrich","id":"2ADD483A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9683-0724"},{"last_name":"Kwitt","full_name":"Kwitt, Roland","first_name":"Roland"}],"scopus_import":"1","title":"A stable multi-scale kernel for topological machine learning","external_id":{"arxiv":["1412.6821"]},"department":[{"_id":"HeEd"}]},{"citation":{"mla":"Edelsbrunner, Herbert, et al. “Relaxed Disk Packing.” <i>Proceedings of the 27th Canadian Conference on Computational Geometry</i>, vol. 2015–August, Queen’s University, 2015, pp. 128–35.","ista":"Edelsbrunner H, Iglesias Ham M, Kurlin V. 2015. Relaxed disk packing. Proceedings of the 27th Canadian Conference on Computational Geometry. CCCG: Canadian Conference on Computational Geometry vol. 2015–August, 128–135.","apa":"Edelsbrunner, H., Iglesias Ham, M., &#38; Kurlin, V. (2015). Relaxed disk packing. In <i>Proceedings of the 27th Canadian Conference on Computational Geometry</i> (Vol. 2015–August, pp. 128–135). Ontario, Canada: Queen’s University.","ieee":"H. Edelsbrunner, M. Iglesias Ham, and V. Kurlin, “Relaxed disk packing,” in <i>Proceedings of the 27th Canadian Conference on Computational Geometry</i>, Ontario, Canada, 2015, vol. 2015–August, pp. 128–135.","ama":"Edelsbrunner H, Iglesias Ham M, Kurlin V. Relaxed disk packing. In: <i>Proceedings of the 27th Canadian Conference on Computational Geometry</i>. Vol 2015-August. Queen’s University; 2015:128-135.","short":"H. Edelsbrunner, M. Iglesias Ham, V. Kurlin, in:, Proceedings of the 27th Canadian Conference on Computational Geometry, Queen’s University, 2015, pp. 128–135.","chicago":"Edelsbrunner, Herbert, Mabel Iglesias Ham, and Vitaliy Kurlin. “Relaxed Disk Packing.” In <i>Proceedings of the 27th Canadian Conference on Computational Geometry</i>, 2015–August:128–35. Queen’s University, 2015."},"oa":1,"type":"conference","article_processing_charge":"No","day":"01","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"id":"41B58C0C-F248-11E8-B48F-1D18A9856A87","first_name":"Mabel","full_name":"Iglesias Ham, Mabel","last_name":"Iglesias Ham"},{"first_name":"Vitaliy","full_name":"Kurlin, Vitaliy","last_name":"Kurlin"}],"external_id":{"arxiv":["1505.03402"]},"scopus_import":"1","ec_funded":1,"department":[{"_id":"HeEd"}],"project":[{"name":"Topological Complex Systems","grant_number":"318493","_id":"255D761E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"oa_version":"Submitted Version","publist_id":"5684","publication_status":"published","publication":"Proceedings of the 27th Canadian Conference on Computational Geometry","abstract":[{"lang":"eng","text":"Motivated by biological questions, we study configurations of equal-sized disks in the Euclidean plane that neither pack nor cover. Measuring the quality by the probability that a random point lies in exactly one disk, we show that the regular hexagonal grid gives the maximum among lattice configurations. "}],"date_created":"2018-12-11T11:52:21Z","publisher":"Queen's University","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"128-135","arxiv":1,"status":"public","volume":"2015-August","title":"Relaxed disk packing","quality_controlled":"1","language":[{"iso":"eng"}],"date_updated":"2025-06-11T06:38:01Z","date_published":"2015-08-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1505.03402","open_access":"1"}],"_id":"1495","month":"08","conference":{"location":"Ontario, Canada","name":"CCCG: Canadian Conference on Computational Geometry","start_date":"2015-08-10","end_date":"2015-08-12"},"year":"2015"},{"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2018-12-11T11:52:22Z","publisher":"Oxford University Press","publication":"Nucleic Acids Research","file":[{"creator":"dernst","file_id":"5768","date_updated":"2020-07-14T12:44:58Z","checksum":"385b83854fd0eb2e4f386867da2823e2","file_name":"2015_NucleicAcidsRes_Andergassen.pdf","file_size":6863297,"date_created":"2018-12-20T14:18:57Z","relation":"main_file","content_type":"application/pdf","access_level":"open_access"}],"abstract":[{"lang":"eng","text":"Detecting allelic biases from high-throughput sequencing data requires an approach that maximises sensitivity while minimizing false positives. Here, we present Allelome.PRO, an automated user-friendly bioinformatics pipeline, which uses high-throughput sequencing data from reciprocal crosses of two genetically distinct mouse strains to detect allele-specific expression and chromatin modifications. Allelome.PRO extends approaches used in previous studies that exclusively analyzed imprinted expression to give a complete picture of the ‘allelome’ by automatically categorising the allelic expression of all genes in a given cell type into imprinted, strain-biased, biallelic or non-informative. Allelome.PRO offers increased sensitivity to analyze lowly expressed transcripts, together with a robust false discovery rate empirically calculated from variation in the sequencing data. We used RNA-seq data from mouse embryonic fibroblasts from F1 reciprocal crosses to determine a biologically relevant allelic ratio cutoff, and define for the first time an entire allelome. Furthermore, we show that Allelome.PRO detects differential enrichment of H3K4me3 over promoters from ChIP-seq data validating the RNA-seq results. This approach can be easily extended to analyze histone marks of active enhancers, or transcription factor binding sites and therefore provides a powerful tool to identify candidate cis regulatory elements genome wide."}],"publication_status":"published","doi":"10.1093/nar/gkv727","oa_version":"Published Version","publist_id":"5682","issue":"21","department":[{"_id":"GaNo"}],"acknowledgement":"Austrian Science Fund [FWF P25185-B22, FWF F4302- B09, FWFW1207-B09]. Funding for open access charge: Austrian Science Fund.\r\nWe thank Florian Breitwieser for advice during the early stages of this project. High-throughput sequencing was conducted by the Biomedical Sequencing Facility (BSF) at CeMM in Vienna.","author":[{"first_name":"Daniel","full_name":"Andergassen, Daniel","last_name":"Andergassen"},{"id":"4C66542E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9033-9096","first_name":"Christoph","full_name":"Dotter, Christoph","last_name":"Dotter"},{"last_name":"Kulinski","full_name":"Kulinski, Tomasz","first_name":"Tomasz"},{"last_name":"Guenzl","full_name":"Guenzl, Philipp","first_name":"Philipp"},{"full_name":"Bammer, Philipp","last_name":"Bammer","first_name":"Philipp"},{"last_name":"Barlow","full_name":"Barlow, Denise","first_name":"Denise"},{"last_name":"Pauler","full_name":"Pauler, Florian","first_name":"Florian"},{"first_name":"Quanah","last_name":"Hudson","full_name":"Hudson, Quanah"}],"scopus_import":"1","article_number":"e146","isi":1,"external_id":{"isi":["000366410900009"]},"intvolume":"        43","day":"21","file_date_updated":"2020-07-14T12:44:58Z","citation":{"ieee":"D. Andergassen <i>et al.</i>, “Allelome.PRO, a pipeline to define allele-specific genomic features from high-throughput sequencing data,” <i>Nucleic Acids Research</i>, vol. 43, no. 21. Oxford University Press, 2015.","ista":"Andergassen D, Dotter C, Kulinski T, Guenzl P, Bammer P, Barlow D, Pauler F, Hudson Q. 2015. Allelome.PRO, a pipeline to define allele-specific genomic features from high-throughput sequencing data. Nucleic Acids Research. 43(21), e146.","apa":"Andergassen, D., Dotter, C., Kulinski, T., Guenzl, P., Bammer, P., Barlow, D., … Hudson, Q. (2015). Allelome.PRO, a pipeline to define allele-specific genomic features from high-throughput sequencing data. <i>Nucleic Acids Research</i>. Oxford University Press. <a href=\"https://doi.org/10.1093/nar/gkv727\">https://doi.org/10.1093/nar/gkv727</a>","mla":"Andergassen, Daniel, et al. “Allelome.PRO, a Pipeline to Define Allele-Specific Genomic Features from High-Throughput Sequencing Data.” <i>Nucleic Acids Research</i>, vol. 43, no. 21, e146, Oxford University Press, 2015, doi:<a href=\"https://doi.org/10.1093/nar/gkv727\">10.1093/nar/gkv727</a>.","chicago":"Andergassen, Daniel, Christoph Dotter, Tomasz Kulinski, Philipp Guenzl, Philipp Bammer, Denise Barlow, Florian Pauler, and Quanah Hudson. “Allelome.PRO, a Pipeline to Define Allele-Specific Genomic Features from High-Throughput Sequencing Data.” <i>Nucleic Acids Research</i>. Oxford University Press, 2015. <a href=\"https://doi.org/10.1093/nar/gkv727\">https://doi.org/10.1093/nar/gkv727</a>.","ama":"Andergassen D, Dotter C, Kulinski T, et al. Allelome.PRO, a pipeline to define allele-specific genomic features from high-throughput sequencing data. <i>Nucleic Acids Research</i>. 2015;43(21). doi:<a href=\"https://doi.org/10.1093/nar/gkv727\">10.1093/nar/gkv727</a>","short":"D. Andergassen, C. Dotter, T. Kulinski, P. Guenzl, P. Bammer, D. Barlow, F. Pauler, Q. Hudson, Nucleic Acids Research 43 (2015)."},"type":"journal_article","article_processing_charge":"No","oa":1,"ddc":["570"],"year":"2015","month":"07","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"has_accepted_license":"1","_id":"1497","date_published":"2015-07-21T00:00:00Z","quality_controlled":"1","date_updated":"2025-09-23T07:45:31Z","language":[{"iso":"eng"}],"volume":43,"title":"Allelome.PRO, a pipeline to define allele-specific genomic features from high-throughput sequencing data","license":"https://creativecommons.org/licenses/by/4.0/","status":"public"},{"oa":1,"type":"conference","citation":{"ieee":"C. Dragoi, T. A. Henzinger, and D. Zufferey, “The need for language support for fault-tolerant distributed systems,” vol. 32. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 90–102, 2015.","mla":"Dragoi, Cezara, et al. <i>The Need for Language Support for Fault-Tolerant Distributed Systems</i>. Vol. 32, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 90–102, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SNAPL.2015.90\">10.4230/LIPIcs.SNAPL.2015.90</a>.","apa":"Dragoi, C., Henzinger, T. A., &#38; Zufferey, D. (2015). The need for language support for fault-tolerant distributed systems. Presented at the SNAPL: Summit oN Advances in Programming Languages, Asilomar, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SNAPL.2015.90\">https://doi.org/10.4230/LIPIcs.SNAPL.2015.90</a>","ista":"Dragoi C, Henzinger TA, Zufferey D. 2015. The need for language support for fault-tolerant distributed systems. 32, 90–102.","chicago":"Dragoi, Cezara, Thomas A Henzinger, and Damien Zufferey. “The Need for Language Support for Fault-Tolerant Distributed Systems.” Leibniz International Proceedings in Informatics. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href=\"https://doi.org/10.4230/LIPIcs.SNAPL.2015.90\">https://doi.org/10.4230/LIPIcs.SNAPL.2015.90</a>.","ama":"Dragoi C, Henzinger TA, Zufferey D. The need for language support for fault-tolerant distributed systems. 2015;32:90-102. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SNAPL.2015.90\">10.4230/LIPIcs.SNAPL.2015.90</a>","short":"C. Dragoi, T.A. Henzinger, D. Zufferey, 32 (2015) 90–102."},"file_date_updated":"2020-07-14T12:44:58Z","day":"01","intvolume":"        32","scopus_import":1,"author":[{"last_name":"Dragoi","full_name":"Dragoi, Cezara","id":"2B2B5ED0-F248-11E8-B48F-1D18A9856A87","first_name":"Cezara"},{"orcid":"0000−0002−2985−7724","id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","full_name":"Henzinger, Thomas A","last_name":"Henzinger"},{"id":"4397AC76-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3197-8736","first_name":"Damien","last_name":"Zufferey","full_name":"Zufferey, Damien"}],"department":[{"_id":"ToHe"}],"project":[{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","name":"Quantitative Reactive Modeling","call_identifier":"FP7"},{"grant_number":"S11402-N23","_id":"25F5A88A-B435-11E9-9278-68D0E5697425","name":"Moderne Concurrency Paradigms","call_identifier":"FWF"},{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF"}],"ec_funded":1,"publist_id":"5681","oa_version":"Published Version","publication_identifier":{"isbn":["978-3-939897-80-4 "]},"doi":"10.4230/LIPIcs.SNAPL.2015.90","publication_status":"published","file":[{"file_name":"IST-2016-499-v1+1_9.pdf","checksum":"cf5e94baa89a2dc4c5de01abc676eda8","file_id":"5050","creator":"system","date_updated":"2020-07-14T12:44:58Z","date_created":"2018-12-12T10:14:02Z","file_size":489362,"access_level":"open_access","content_type":"application/pdf","relation":"main_file"}],"abstract":[{"text":"Fault-tolerant distributed algorithms play an important role in many critical/high-availability applications. These algorithms are notoriously difficult to implement correctly, due to asynchronous communication and the occurrence of faults, such as the network dropping messages or computers crashing. Nonetheless there is surprisingly little language and verification support to build distributed systems based on fault-tolerant algorithms. In this paper, we present some of the challenges that a designer has to overcome to implement a fault-tolerant distributed system. Then we review different models that have been proposed to reason about distributed algorithms and sketch how such a model can form the basis for a domain-specific programming language. Adopting a high-level programming model can simplify the programmer's life and make the code amenable to automated verification, while still compiling to efficiently executable code. We conclude by summarizing the current status of an ongoing language design and implementation project that is based on this idea.","lang":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2018-12-11T11:52:22Z","series_title":"Leibniz International Proceedings in Informatics","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"90 - 102","corr_author":"1","status":"public","title":"The need for language support for fault-tolerant distributed systems","volume":32,"date_updated":"2025-04-15T06:26:02Z","language":[{"iso":"eng"}],"quality_controlled":"1","pubrep_id":"499","alternative_title":["LIPIcs"],"date_published":"2015-01-01T00:00:00Z","_id":"1498","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"month":"01","conference":{"end_date":"2015-05-06","name":"SNAPL: Summit oN Advances in Programming Languages","start_date":"2015-05-03","location":"Asilomar, CA, United States"},"year":"2015","ddc":["005"]},{"ec_funded":1,"project":[{"name":"Quantitative Reactive Modeling","grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"Z211","_id":"25F42A32-B435-11E9-9278-68D0E5697425","name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF"},{"call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"department":[{"_id":"ToHe"},{"_id":"KrCh"}],"acknowledgement":"The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under grant agreement 601148 (CASSTING), EU FP7 FET project SENSATION, Sino-Danish Basic Research Center IDAE4CPS, the European Research Council (ERC) under grant agreement 267989 (QUAREM), the Austrian Science Fund (FWF) project S11402-N23 (RiSE) and Z211-N23 (Wittgenstein Award), the Czech Science Foundation under grant agreement P202/12/G061, and People Programme (Marie Curie Actions) of the European Union’s Seventh Framework\r\nProgramme (FP7/2007-2013) REA Grant No 291734.","author":[{"full_name":"Kretinsky, Jan","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"},{"last_name":"Larsen","full_name":"Larsen, Kim","first_name":"Kim"},{"first_name":"Simon","full_name":"Laursen, Simon","last_name":"Laursen"},{"first_name":"Jiří","full_name":"Srba, Jiří","last_name":"Srba"}],"scopus_import":1,"intvolume":"        42","day":"01","file_date_updated":"2020-07-14T12:44:58Z","citation":{"chicago":"Kretinsky, Jan, Kim Larsen, Simon Laursen, and Jiří Srba. “Polynomial Time Decidability of Weighted Synchronization under Partial Observability,” 42:142–54. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2015.142\">https://doi.org/10.4230/LIPIcs.CONCUR.2015.142</a>.","ama":"Kretinsky J, Larsen K, Laursen S, Srba J. Polynomial time decidability of weighted synchronization under partial observability. In: Vol 42. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:142-154. doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2015.142\">10.4230/LIPIcs.CONCUR.2015.142</a>","short":"J. Kretinsky, K. Larsen, S. Laursen, J. Srba, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 142–154.","ieee":"J. Kretinsky, K. Larsen, S. Laursen, and J. Srba, “Polynomial time decidability of weighted synchronization under partial observability,” presented at the CONCUR: Concurrency Theory, Madrid, Spain, 2015, vol. 42, pp. 142–154.","apa":"Kretinsky, J., Larsen, K., Laursen, S., &#38; Srba, J. (2015). Polynomial time decidability of weighted synchronization under partial observability (Vol. 42, pp. 142–154). Presented at the CONCUR: Concurrency Theory, Madrid, Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2015.142\">https://doi.org/10.4230/LIPIcs.CONCUR.2015.142</a>","ista":"Kretinsky J, Larsen K, Laursen S, Srba J. 2015. Polynomial time decidability of weighted synchronization under partial observability. CONCUR: Concurrency Theory, LIPIcs, vol. 42, 142–154.","mla":"Kretinsky, Jan, et al. <i>Polynomial Time Decidability of Weighted Synchronization under Partial Observability</i>. Vol. 42, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 142–54, doi:<a href=\"https://doi.org/10.4230/LIPIcs.CONCUR.2015.142\">10.4230/LIPIcs.CONCUR.2015.142</a>."},"type":"conference","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_created":"2018-12-11T11:52:22Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","file":[{"date_updated":"2020-07-14T12:44:58Z","file_id":"4672","creator":"system","file_name":"IST-2016-498-v1+1_32.pdf","checksum":"49eb5021caafaabe5356c65b9c5f8c9c","access_level":"open_access","content_type":"application/pdf","relation":"main_file","date_created":"2018-12-12T10:08:12Z","file_size":623563}],"abstract":[{"lang":"eng","text":"We consider weighted automata with both positive and negative integer weights on edges and\r\nstudy the problem of synchronization using adaptive strategies that may only observe whether\r\nthe current weight-level is negative or nonnegative. We show that the synchronization problem is decidable in polynomial time for deterministic weighted automata."}],"publication_status":"published","doi":"10.4230/LIPIcs.CONCUR.2015.142","oa_version":"Published Version","publist_id":"5680","volume":42,"title":"Polynomial time decidability of weighted synchronization under partial observability","status":"public","page":"142 - 154","year":"2015","ddc":["000","003"],"conference":{"name":"CONCUR: Concurrency Theory","start_date":"2015-09-01","end_date":"2015-09-04","location":"Madrid, Spain"},"month":"01","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"_id":"1499","date_published":"2015-01-01T00:00:00Z","alternative_title":["LIPIcs"],"pubrep_id":"498","quality_controlled":"1","language":[{"iso":"eng"}],"date_updated":"2025-04-15T06:26:02Z"},{"quality_controlled":"1","language":[{"iso":"eng"}],"date_updated":"2026-04-15T10:02:12Z","date_published":"2015-10-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1405.0835","open_access":"1"}],"_id":"1501","month":"10","related_material":{"record":[{"status":"public","id":"1155","relation":"dissertation_contains"}]},"year":"2015","page":"230 - 264","arxiv":1,"corr_author":"1","status":"public","volume":47,"title":"CEGAR for compositional analysis of qualitative properties in Markov decision processes","oa_version":"Preprint","publist_id":"5677","publication_status":"published","abstract":[{"lang":"eng","text":"We consider Markov decision processes (MDPs) which are a standard model for probabilistic systems. We focus on qualitative properties for MDPs that can express that desired behaviors of the system arise almost-surely (with probability 1) or with positive probability. We introduce a new simulation relation to capture the refinement relation of MDPs with respect to qualitative properties, and present discrete graph algorithms with quadratic complexity to compute the simulation relation. We present an automated technique for assume-guarantee style reasoning for compositional analysis of two-player games by giving a counterexample guided abstraction-refinement approach to compute our new simulation relation. We show a tight link between two-player games and MDPs, and as a consequence the results for games are lifted to MDPs with qualitative properties. We have implemented our algorithms and show that the compositional analysis leads to significant improvements. "}],"publication":"Formal Methods in System Design","doi":"10.1007/s10703-015-0235-2","date_created":"2018-12-11T11:52:23Z","publisher":"Springer","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","citation":{"apa":"Chatterjee, K., Chmelik, M., &#38; Daca, P. (2015). CEGAR for compositional analysis of qualitative properties in Markov decision processes. <i>Formal Methods in System Design</i>. Springer. <a href=\"https://doi.org/10.1007/s10703-015-0235-2\">https://doi.org/10.1007/s10703-015-0235-2</a>","ista":"Chatterjee K, Chmelik M, Daca P. 2015. CEGAR for compositional analysis of qualitative properties in Markov decision processes. Formal Methods in System Design. 47(2), 230–264.","mla":"Chatterjee, Krishnendu, et al. “CEGAR for Compositional Analysis of Qualitative Properties in Markov Decision Processes.” <i>Formal Methods in System Design</i>, vol. 47, no. 2, Springer, 2015, pp. 230–64, doi:<a href=\"https://doi.org/10.1007/s10703-015-0235-2\">10.1007/s10703-015-0235-2</a>.","ieee":"K. Chatterjee, M. Chmelik, and P. Daca, “CEGAR for compositional analysis of qualitative properties in Markov decision processes,” <i>Formal Methods in System Design</i>, vol. 47, no. 2. Springer, pp. 230–264, 2015.","short":"K. Chatterjee, M. Chmelik, P. Daca, Formal Methods in System Design 47 (2015) 230–264.","ama":"Chatterjee K, Chmelik M, Daca P. CEGAR for compositional analysis of qualitative properties in Markov decision processes. <i>Formal Methods in System Design</i>. 2015;47(2):230-264. doi:<a href=\"https://doi.org/10.1007/s10703-015-0235-2\">10.1007/s10703-015-0235-2</a>","chicago":"Chatterjee, Krishnendu, Martin Chmelik, and Przemyslaw Daca. “CEGAR for Compositional Analysis of Qualitative Properties in Markov Decision Processes.” <i>Formal Methods in System Design</i>. Springer, 2015. <a href=\"https://doi.org/10.1007/s10703-015-0235-2\">https://doi.org/10.1007/s10703-015-0235-2</a>."},"oa":1,"type":"journal_article","article_processing_charge":"No","intvolume":"        47","day":"01","author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4561-241X","first_name":"Krishnendu"},{"last_name":"Chmelik","full_name":"Chmelik, Martin","first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Daca, Przemyslaw","last_name":"Daca","id":"49351290-F248-11E8-B48F-1D18A9856A87","first_name":"Przemyslaw"}],"isi":1,"external_id":{"arxiv":["1405.0835"],"isi":["000361752300003"]},"scopus_import":"1","ec_funded":1,"acknowledgement":"The research was partly supported by Austrian Science Fund (FWF) Grant No. P23499- N23, FWF NFN Grant No. S11407-N23, FWF Grant S11403-N23 (RiSE), and FWF Grant Z211-N23 (Wittgenstein Award), ERC Start Grant (279307: Graph Games), Microsoft faculty fellows award, the ERC Advanced Grant QUAREM (Quantitative Reactive Modeling).","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"issue":"2","project":[{"call_identifier":"FWF","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23"},{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","call_identifier":"FP7"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"},{"name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","grant_number":"267989","call_identifier":"FP7"}]},{"title":"Complete composition operators for IOCO-testing theory","status":"public","page":"101 - 110","ddc":["000"],"year":"2015","conference":{"location":"Montreal, QC, Canada","end_date":"2015-05-08","start_date":"2015-05-04","name":"CBSE: Component-Based Software Engineering "},"related_material":{"record":[{"status":"public","id":"1155","relation":"dissertation_contains"}]},"month":"05","has_accepted_license":"1","alternative_title":["Proceedings of the 18th International ACM SIGSOFT Symposium on Component-Based Software Engineering "],"_id":"1502","date_published":"2015-05-01T00:00:00Z","language":[{"iso":"eng"}],"date_updated":"2026-04-15T10:02:12Z","pubrep_id":"625","quality_controlled":"1","project":[{"grant_number":"267989","_id":"25EE3708-B435-11E9-9278-68D0E5697425","name":"Quantitative Reactive Modeling","call_identifier":"FP7"},{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"acknowledgement":"This research was funded in part by the European Research Council (ERC) under grant agreement 267989 (QUAREM), by the Austrian Science Fund (FWF) projects S11402-N23(RiSE) and Z211-N23 (Wittgestein Award), by People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant agreement 291734, and by the ARTEMIS JU under grant agreement 295373 (nSafeCer).  Jan Křetínský has been partially supported by the Czech Science Foundation, grant No.  P202/12/G061.  Nikola Beneš has been supported by the\r\nMEYS project No. CZ.1.07/2.3.00/30.0009 Employment of Newly Graduated Doctors of Science for Scientific Excellence.","department":[{"_id":"ToHe"},{"_id":"KrCh"}],"ec_funded":1,"scopus_import":"1","isi":1,"external_id":{"isi":["000380554800013"]},"author":[{"full_name":"Beneš, Nikola","last_name":"Beneš","first_name":"Nikola"},{"id":"49351290-F248-11E8-B48F-1D18A9856A87","first_name":"Przemyslaw","full_name":"Daca, Przemyslaw","last_name":"Daca"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","first_name":"Thomas A","orcid":"0000−0002−2985−7724","last_name":"Henzinger","full_name":"Henzinger, Thomas A"},{"full_name":"Kretinsky, Jan","last_name":"Kretinsky","orcid":"0000-0002-8122-2881","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan"},{"last_name":"Nickovic","full_name":"Nickovic, Dejan","first_name":"Dejan"}],"day":"01","file_date_updated":"2020-07-14T12:44:59Z","article_processing_charge":"No","type":"conference","oa":1,"citation":{"ama":"Beneš N, Daca P, Henzinger TA, Kretinsky J, Nickovic D. Complete composition operators for IOCO-testing theory. In: ACM; 2015:101-110. doi:<a href=\"https://doi.org/10.1145/2737166.2737175\">10.1145/2737166.2737175</a>","short":"N. Beneš, P. Daca, T.A. Henzinger, J. Kretinsky, D. Nickovic, in:, ACM, 2015, pp. 101–110.","chicago":"Beneš, Nikola, Przemyslaw Daca, Thomas A Henzinger, Jan Kretinsky, and Dejan Nickovic. “Complete Composition Operators for IOCO-Testing Theory,” 101–10. ACM, 2015. <a href=\"https://doi.org/10.1145/2737166.2737175\">https://doi.org/10.1145/2737166.2737175</a>.","apa":"Beneš, N., Daca, P., Henzinger, T. A., Kretinsky, J., &#38; Nickovic, D. (2015). Complete composition operators for IOCO-testing theory (pp. 101–110). Presented at the CBSE: Component-Based Software Engineering , Montreal, QC, Canada: ACM. <a href=\"https://doi.org/10.1145/2737166.2737175\">https://doi.org/10.1145/2737166.2737175</a>","ista":"Beneš N, Daca P, Henzinger TA, Kretinsky J, Nickovic D. 2015. Complete composition operators for IOCO-testing theory. CBSE: Component-Based Software Engineering , Proceedings of the 18th International ACM SIGSOFT Symposium on Component-Based Software Engineering , , 101–110.","mla":"Beneš, Nikola, et al. <i>Complete Composition Operators for IOCO-Testing Theory</i>. ACM, 2015, pp. 101–10, doi:<a href=\"https://doi.org/10.1145/2737166.2737175\">10.1145/2737166.2737175</a>.","ieee":"N. Beneš, P. Daca, T. A. Henzinger, J. Kretinsky, and D. Nickovic, “Complete composition operators for IOCO-testing theory,” presented at the CBSE: Component-Based Software Engineering , Montreal, QC, Canada, 2015, pp. 101–110."},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publisher":"ACM","date_created":"2018-12-11T11:52:24Z","doi":"10.1145/2737166.2737175","file":[{"date_created":"2018-12-12T10:17:46Z","file_size":467561,"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_name":"IST-2016-625-v1+1_conf-cbse-BenesDHKN15.pdf","checksum":"c6ce681035c163a158751f240cb7d389","file_id":"5303","creator":"system","date_updated":"2020-07-14T12:44:59Z"}],"abstract":[{"text":"We extend the theory of input-output conformance with operators for merge and quotient. The former is useful when testing against multiple requirements or views. The latter can be used to generate tests for patches of an already tested system. Both operators can combine systems with different action alphabets, which is usually the case when constructing complex systems and specifications from parts, for instance different views as well as newly defined functionality of a~previous version of the system.","lang":"eng"}],"publication_status":"published","publist_id":"5676","publication_identifier":{"isbn":["978-1-4503-3471-6"]},"oa_version":"Submitted Version"},{"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2018-12-11T11:52:25Z","publisher":"Institute of Mathematical Statistics","publication_status":"published","abstract":[{"text":"This paper is aimed at deriving the universality of the largest eigenvalue of a class of high-dimensional real or complex sample covariance matrices of the form W N =Σ 1/2XX∗Σ 1/2 . Here, X = (xij )M,N is an M× N random matrix with independent entries xij , 1 ≤ i M,≤ 1 ≤ j ≤ N such that Exij = 0, E|xij |2 = 1/N . On dimensionality, we assume that M = M(N) and N/M → d ε (0, ∞) as N ∞→. For a class of general deterministic positive-definite M × M matrices Σ , under some additional assumptions on the distribution of xij 's, we show that the limiting behavior of the largest eigenvalue of W N is universal, via pursuing a Green function comparison strategy raised in [Probab. Theory Related Fields 154 (2012) 341-407, Adv. Math. 229 (2012) 1435-1515] by Erd″os, Yau and Yin for Wigner matrices and extended by Pillai and Yin [Ann. Appl. Probab. 24 (2014) 935-1001] to sample covariance matrices in the null case (&amp;Epsi = I ). Consequently, in the standard complex case (Ex2 ij = 0), combing this universality property and the results known for Gaussian matrices obtained by El Karoui in [Ann. Probab. 35 (2007) 663-714] (nonsingular case) and Onatski in [Ann. Appl. Probab. 18 (2008) 470-490] (singular case), we show that after an appropriate normalization the largest eigenvalue of W N converges weakly to the type 2 Tracy-Widom distribution TW2 . Moreover, in the real case, we show that whenΣ is spiked with a fixed number of subcritical spikes, the type 1 Tracy-Widom limit TW1 holds for the normalized largest eigenvalue of W N , which extends a result of Féral and Péché in [J. Math. Phys. 50 (2009) 073302] to the scenario of nondiagonal Σ and more generally distributed X . In summary, we establish the Tracy-Widom type universality for the largest eigenvalue of generally distributed sample covariance matrices under quite light assumptions on &amp;Sigma . Applications of these limiting results to statistical signal detection and structure recognition of separable covariance matrices are also discussed.","lang":"eng"}],"publication":"Annals of Statistics","doi":"10.1214/14-AOS1281","oa_version":"Preprint","publist_id":"5672","department":[{"_id":"LaEr"}],"issue":"1","acknowledgement":"B.Z. was supported  in  part  by  NSFC  Grant  11071213,  ZJNSF  Grant  R6090034  and  SRFDP  Grant 20100101110001. P.G. was supported in part by the Ministry of Education, Singapore, under Grant ARC 14/11. Z.W. was supported  in  part  by  the  Ministry  of  Education,  Singapore,  under  Grant  ARC  14/11,  and  by a Grant R-155-000-131-112 at the National University of Singapore\r\n","author":[{"first_name":"Zhigang","id":"442E6A6C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3036-1475","full_name":"Bao, Zhigang","last_name":"Bao"},{"last_name":"Pan","full_name":"Pan, Guangming","first_name":"Guangming"},{"last_name":"Zhou","full_name":"Zhou, Wang","first_name":"Wang"}],"isi":1,"external_id":{"arxiv":["1304.5690"],"isi":["000349738500014"]},"intvolume":"        43","day":"01","citation":{"ieee":"Z. Bao, G. Pan, and W. Zhou, “Universality for the largest eigenvalue of sample covariance matrices with general population,” <i>Annals of Statistics</i>, vol. 43, no. 1. Institute of Mathematical Statistics, pp. 382–421, 2015.","mla":"Bao, Zhigang, et al. “Universality for the Largest Eigenvalue of Sample Covariance Matrices with General Population.” <i>Annals of Statistics</i>, vol. 43, no. 1, Institute of Mathematical Statistics, 2015, pp. 382–421, doi:<a href=\"https://doi.org/10.1214/14-AOS1281\">10.1214/14-AOS1281</a>.","apa":"Bao, Z., Pan, G., &#38; Zhou, W. (2015). Universality for the largest eigenvalue of sample covariance matrices with general population. <i>Annals of Statistics</i>. Institute of Mathematical Statistics. <a href=\"https://doi.org/10.1214/14-AOS1281\">https://doi.org/10.1214/14-AOS1281</a>","ista":"Bao Z, Pan G, Zhou W. 2015. Universality for the largest eigenvalue of sample covariance matrices with general population. Annals of Statistics. 43(1), 382–421.","chicago":"Bao, Zhigang, Guangming Pan, and Wang Zhou. “Universality for the Largest Eigenvalue of Sample Covariance Matrices with General Population.” <i>Annals of Statistics</i>. Institute of Mathematical Statistics, 2015. <a href=\"https://doi.org/10.1214/14-AOS1281\">https://doi.org/10.1214/14-AOS1281</a>.","short":"Z. Bao, G. Pan, W. Zhou, Annals of Statistics 43 (2015) 382–421.","ama":"Bao Z, Pan G, Zhou W. Universality for the largest eigenvalue of sample covariance matrices with general population. <i>Annals of Statistics</i>. 2015;43(1):382-421. doi:<a href=\"https://doi.org/10.1214/14-AOS1281\">10.1214/14-AOS1281</a>"},"oa":1,"article_processing_charge":"No","type":"journal_article","year":"2015","month":"02","date_published":"2015-02-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1304.5690"}],"_id":"1505","quality_controlled":"1","language":[{"iso":"eng"}],"date_updated":"2025-09-29T11:02:34Z","volume":43,"title":"Universality for the largest eigenvalue of sample covariance matrices with general population","status":"public","page":"382 - 421","arxiv":1},{"quality_controlled":"1","date_updated":"2025-09-23T13:59:56Z","language":[{"iso":"eng"}],"_id":"1506","main_file_link":[{"url":"http://arxiv.org/abs/1208.5823","open_access":"1"}],"date_published":"2015-08-01T00:00:00Z","month":"08","year":"2015","arxiv":1,"page":"1600 - 1628","status":"public","volume":21,"title":"The logarithmic law of random determinant","oa_version":"Preprint","publist_id":"5671","publication":"Bernoulli","abstract":[{"text":"Consider the square random matrix An = (aij)n,n, where {aij:= a(n)ij , i, j = 1, . . . , n} is a collection of independent real random variables with means zero and variances one. Under the additional moment condition supn max1≤i,j ≤n Ea4ij &lt;∞, we prove Girko's logarithmic law of det An in the sense that as n→∞ log | detAn| ? (1/2) log(n-1)! d/→√(1/2) log n N(0, 1).","lang":"eng"}],"publication_status":"published","doi":"10.3150/14-BEJ615","date_created":"2018-12-11T11:52:25Z","publisher":"Bernoulli Society for Mathematical Statistics and Probability","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","citation":{"ieee":"Z. Bao, G. Pan, and W. Zhou, “The logarithmic law of random determinant,” <i>Bernoulli</i>, vol. 21, no. 3. Bernoulli Society for Mathematical Statistics and Probability, pp. 1600–1628, 2015.","apa":"Bao, Z., Pan, G., &#38; Zhou, W. (2015). The logarithmic law of random determinant. <i>Bernoulli</i>. Bernoulli Society for Mathematical Statistics and Probability. <a href=\"https://doi.org/10.3150/14-BEJ615\">https://doi.org/10.3150/14-BEJ615</a>","ista":"Bao Z, Pan G, Zhou W. 2015. The logarithmic law of random determinant. Bernoulli. 21(3), 1600–1628.","mla":"Bao, Zhigang, et al. “The Logarithmic Law of Random Determinant.” <i>Bernoulli</i>, vol. 21, no. 3, Bernoulli Society for Mathematical Statistics and Probability, 2015, pp. 1600–28, doi:<a href=\"https://doi.org/10.3150/14-BEJ615\">10.3150/14-BEJ615</a>.","chicago":"Bao, Zhigang, Guangming Pan, and Wang Zhou. “The Logarithmic Law of Random Determinant.” <i>Bernoulli</i>. Bernoulli Society for Mathematical Statistics and Probability, 2015. <a href=\"https://doi.org/10.3150/14-BEJ615\">https://doi.org/10.3150/14-BEJ615</a>.","short":"Z. Bao, G. Pan, W. Zhou, Bernoulli 21 (2015) 1600–1628.","ama":"Bao Z, Pan G, Zhou W. The logarithmic law of random determinant. <i>Bernoulli</i>. 2015;21(3):1600-1628. doi:<a href=\"https://doi.org/10.3150/14-BEJ615\">10.3150/14-BEJ615</a>"},"type":"journal_article","article_processing_charge":"No","oa":1,"intvolume":"        21","day":"01","author":[{"last_name":"Bao","full_name":"Bao, Zhigang","orcid":"0000-0003-3036-1475","id":"442E6A6C-F248-11E8-B48F-1D18A9856A87","first_name":"Zhigang"},{"first_name":"Guangming","last_name":"Pan","full_name":"Pan, Guangming"},{"first_name":"Wang","last_name":"Zhou","full_name":"Zhou, Wang"}],"external_id":{"isi":["000356993100012"],"arxiv":["1208.5823"]},"isi":1,"department":[{"_id":"LaEr"}],"issue":"3"},{"volume":17,"title":"Gap universality of generalized Wigner and β ensembles","status":"public","arxiv":1,"page":"1927 - 2036","year":"2015","month":"08","_id":"1508","main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1211.3786"}],"date_published":"2015-08-01T00:00:00Z","quality_controlled":"1","language":[{"iso":"eng"}],"date_updated":"2025-09-23T09:08:38Z","department":[{"_id":"LaEr"}],"issue":"8","author":[{"full_name":"Erdös, László","last_name":"Erdös","id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","first_name":"László","orcid":"0000-0001-5366-9603"},{"last_name":"Yau","full_name":"Yau, Horng","first_name":"Horng"}],"scopus_import":"1","isi":1,"external_id":{"isi":["000360822900003"],"arxiv":["1211.3786"]},"intvolume":"        17","day":"01","citation":{"ieee":"L. Erdös and H. Yau, “Gap universality of generalized Wigner and β ensembles,” <i>Journal of the European Mathematical Society</i>, vol. 17, no. 8. European Mathematical Society, pp. 1927–2036, 2015.","mla":"Erdös, László, and Horng Yau. “Gap Universality of Generalized Wigner and β Ensembles.” <i>Journal of the European Mathematical Society</i>, vol. 17, no. 8, European Mathematical Society, 2015, pp. 1927–2036, doi:<a href=\"https://doi.org/10.4171/JEMS/548\">10.4171/JEMS/548</a>.","apa":"Erdös, L., &#38; Yau, H. (2015). Gap universality of generalized Wigner and β ensembles. <i>Journal of the European Mathematical Society</i>. European Mathematical Society. <a href=\"https://doi.org/10.4171/JEMS/548\">https://doi.org/10.4171/JEMS/548</a>","ista":"Erdös L, Yau H. 2015. Gap universality of generalized Wigner and β ensembles. Journal of the European Mathematical Society. 17(8), 1927–2036.","chicago":"Erdös, László, and Horng Yau. “Gap Universality of Generalized Wigner and β Ensembles.” <i>Journal of the European Mathematical Society</i>. European Mathematical Society, 2015. <a href=\"https://doi.org/10.4171/JEMS/548\">https://doi.org/10.4171/JEMS/548</a>.","ama":"Erdös L, Yau H. Gap universality of generalized Wigner and β ensembles. <i>Journal of the European Mathematical Society</i>. 2015;17(8):1927-2036. doi:<a href=\"https://doi.org/10.4171/JEMS/548\">10.4171/JEMS/548</a>","short":"L. Erdös, H. Yau, Journal of the European Mathematical Society 17 (2015) 1927–2036."},"article_processing_charge":"No","type":"journal_article","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_created":"2018-12-11T11:52:26Z","publisher":"European Mathematical Society","publication":"Journal of the European Mathematical Society","abstract":[{"text":"We consider generalized Wigner ensembles and general β-ensembles with analytic potentials for any β ≥ 1. The recent universality results in particular assert that the local averages of consecutive eigenvalue gaps in the bulk of the spectrum are universal in the sense that they coincide with those of the corresponding Gaussian β-ensembles. In this article, we show that local averaging is not necessary for this result, i.e. we prove that the single gap distributions in the bulk are universal. In fact, with an additional step, our result can be extended to any C4(ℝ) potential.","lang":"eng"}],"publication_status":"published","doi":"10.4171/JEMS/548","oa_version":"Preprint","publist_id":"5669"},{"date_published":"2015-10-01T00:00:00Z","_id":"1509","date_updated":"2025-04-15T07:48:03Z","language":[{"iso":"eng"}],"quality_controlled":"1","pubrep_id":"497","year":"2015","ddc":["570"],"tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"has_accepted_license":"1","month":"10","status":"public","corr_author":"1","title":"Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene","volume":4,"doi":"10.12688/f1000research.7143.1","publication_status":"published","file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_size":4414248,"date_created":"2018-12-12T10:16:12Z","date_updated":"2020-07-14T12:44:59Z","creator":"system","file_id":"5198","checksum":"8beae5cbe988e1060265ae7de2ee8306","file_name":"IST-2016-497-v1+1_10.12688_f1000research.7143.1_20151102.pdf"}],"abstract":[{"lang":"eng","text":"The Auxin Binding Protein1 (ABP1) has been identified based on its ability to bind auxin with high affinity and studied for a long time as a prime candidate for the extracellular auxin receptor responsible for mediating in particular the fast non-transcriptional auxin responses. However, the contradiction between the embryo-lethal phenotypes of the originally described Arabidopsis T-DNA insertional knock-out alleles (abp1-1 and abp1-1s) and the wild type-like phenotypes of other recently described loss-of-function alleles (abp1-c1 and abp1-TD1) questions the biological importance of ABP1 and relevance of the previous genetic studies. Here we show that there is no hidden copy of the ABP1 gene in the Arabidopsis genome but the embryo-lethal phenotypes of abp1-1 and abp1-1s alleles are very similar to the knock-out phenotypes of the neighboring gene, BELAYA SMERT (BSM). Furthermore, the allelic complementation test between bsm and abp1 alleles shows that the embryo-lethality in the abp1-1 and abp1-1s alleles is caused by the off-target disruption of the BSM locus by the T-DNA insertions. This clarifies the controversy of different phenotypes among published abp1 knock-out alleles and asks for reflections on the developmental role of ABP1."}],"publication":"F1000 Research ","publist_id":"5668","oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"F1000 Research","date_created":"2018-12-11T11:52:26Z","file_date_updated":"2020-07-14T12:44:59Z","day":"01","intvolume":"         4","oa":1,"type":"journal_article","article_processing_charge":"No","citation":{"chicago":"Michalko, Jaroslav, Marta Lukacisinova, Mark Tobias Bollenbach, and Jiří Friml. “Embryo-Lethal Phenotypes in Early Abp1 Mutants Are Due to Disruption of the Neighboring BSM Gene.” <i>F1000 Research </i>. F1000 Research, 2015. <a href=\"https://doi.org/10.12688/f1000research.7143.1\">https://doi.org/10.12688/f1000research.7143.1</a>.","short":"J. Michalko, M. Lukacisinova, M.T. Bollenbach, J. Friml, F1000 Research  4 (2015).","ama":"Michalko J, Lukacisinova M, Bollenbach MT, Friml J. Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene. <i>F1000 Research </i>. 2015;4. doi:<a href=\"https://doi.org/10.12688/f1000research.7143.1\">10.12688/f1000research.7143.1</a>","ieee":"J. Michalko, M. Lukacisinova, M. T. Bollenbach, and J. Friml, “Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene,” <i>F1000 Research </i>, vol. 4. F1000 Research, 2015.","mla":"Michalko, Jaroslav, et al. “Embryo-Lethal Phenotypes in Early Abp1 Mutants Are Due to Disruption of the Neighboring BSM Gene.” <i>F1000 Research </i>, vol. 4, F1000 Research, 2015, doi:<a href=\"https://doi.org/10.12688/f1000research.7143.1\">10.12688/f1000research.7143.1</a>.","ista":"Michalko J, Lukacisinova M, Bollenbach MT, Friml J. 2015. Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene. F1000 Research . 4.","apa":"Michalko, J., Lukacisinova, M., Bollenbach, M. T., &#38; Friml, J. (2015). Embryo-lethal phenotypes in early abp1 mutants are due to disruption of the neighboring BSM gene. <i>F1000 Research </i>. F1000 Research. <a href=\"https://doi.org/10.12688/f1000research.7143.1\">https://doi.org/10.12688/f1000research.7143.1</a>"},"acknowledgement":"This work was supported by ERC Independent Research grant (ERC-2011-StG-20101109-PSDP to JF). JM internship was supported by the grant “Action Austria – Slovakia”.\r\nData associated with the article are available under the terms of the Creative Commons Zero \"No rights reserved\" data waiver (CC0 1.0 Public domain dedication). \r\n\r\nData availability: \r\nF1000Research: Dataset 1. Dataset 1, 10.5256/f1000research.7143.d104552\r\n\r\nF1000Research: Dataset 2. Dataset 2, 10.5256/f1000research.7143.d104553\r\n\r\nF1000Research: Dataset 3. Dataset 3, 10.5256/f1000research.7143.d104554","department":[{"_id":"JiFr"},{"_id":"ToBo"}],"project":[{"_id":"25716A02-B435-11E9-9278-68D0E5697425","grant_number":"282300","name":"Polarity and subcellular dynamics in plants","call_identifier":"FP7"}],"ec_funded":1,"scopus_import":"1","author":[{"last_name":"Michalko","full_name":"Michalko, Jaroslav","id":"483727CA-F248-11E8-B48F-1D18A9856A87","first_name":"Jaroslav"},{"first_name":"Marta","id":"4342E402-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2519-8004","last_name":"Dravecka","full_name":"Dravecka, Marta"},{"first_name":"Tobias","orcid":"0000-0003-4398-476X","id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87","full_name":"Bollenbach, Tobias","last_name":"Bollenbach"},{"last_name":"Friml","full_name":"Friml, Jirí","id":"4159519E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8302-7596","first_name":"Jirí"}]},{"pubrep_id":"503","quality_controlled":"1","language":[{"iso":"eng"}],"date_updated":"2025-09-18T14:30:52Z","_id":"1510","date_published":"2015-06-11T00:00:00Z","alternative_title":["LIPIcs"],"month":"06","has_accepted_license":"1","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"related_material":{"record":[{"relation":"later_version","id":"1408","status":"public"}]},"year":"2015","ddc":["510"],"conference":{"location":"Eindhoven, Netherlands","end_date":"2015-06-25","start_date":"2015-06-22","name":"SoCG: Symposium on Computational Geometry"},"page":"842 - 856","status":"public","volume":34,"title":"On computability and triviality of well groups","oa_version":"Published Version","publist_id":"5667","file":[{"date_updated":"2020-07-14T12:44:59Z","creator":"system","file_id":"5001","checksum":"49eb5021caafaabe5356c65b9c5f8c9c","file_name":"IST-2016-503-v1+1_32.pdf","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_size":623563,"date_created":"2018-12-12T10:13:19Z"}],"abstract":[{"lang":"eng","text":"The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r &gt; 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K &lt; 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status. "}],"publication_status":"published","doi":"10.4230/LIPIcs.SOCG.2015.842","date_created":"2018-12-11T11:52:26Z","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Franek, Peter, and Marek Krcál. “On Computability and Triviality of Well Groups,” 34:842–56. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">https://doi.org/10.4230/LIPIcs.SOCG.2015.842</a>.","short":"P. Franek, M. Krcál, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 842–856.","ama":"Franek P, Krcál M. On computability and triviality of well groups. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:842-856. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">10.4230/LIPIcs.SOCG.2015.842</a>","ieee":"P. Franek and M. Krcál, “On computability and triviality of well groups,” presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 842–856.","apa":"Franek, P., &#38; Krcál, M. (2015). On computability and triviality of well groups (Vol. 34, pp. 842–856). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">https://doi.org/10.4230/LIPIcs.SOCG.2015.842</a>","ista":"Franek P, Krcál M. 2015. On computability and triviality of well groups. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 842–856.","mla":"Franek, Peter, and Marek Krcál. <i>On Computability and Triviality of Well Groups</i>. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 842–56, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.842\">10.4230/LIPIcs.SOCG.2015.842</a>."},"type":"conference","oa":1,"intvolume":"        34","day":"11","file_date_updated":"2020-07-14T12:44:59Z","author":[{"id":"473294AE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8878-8397","first_name":"Peter","full_name":"Franek, Peter","last_name":"Franek"},{"id":"33E21118-F248-11E8-B48F-1D18A9856A87","first_name":"Marek","last_name":"Krcál","full_name":"Krcál, Marek"}],"scopus_import":1,"ec_funded":1,"project":[{"call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}],"department":[{"_id":"UlWa"},{"_id":"HeEd"}]},{"related_material":{"record":[{"status":"public","relation":"later_version","id":"610"}]},"month":"06","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"has_accepted_license":"1","ddc":["510"],"year":"2015","conference":{"location":"Eindhoven, Netherlands","start_date":"2015-06-22","name":"SoCG: Symposium on Computational Geometry","end_date":"2015-06-25"},"language":[{"iso":"eng"}],"date_updated":"2025-09-11T07:35:35Z","pubrep_id":"502","quality_controlled":"1","alternative_title":["LIPIcs"],"_id":"1511","date_published":"2015-06-11T00:00:00Z","title":"On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result","volume":"34 ","page":"476 - 490","status":"public","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","date_created":"2018-12-11T11:52:27Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"5666","oa_version":"Published Version","doi":"10.4230/LIPIcs.SOCG.2015.476","file":[{"file_id":"4871","creator":"system","date_updated":"2020-07-14T12:44:59Z","file_name":"IST-2016-502-v1+1_42.pdf","checksum":"0945811875351796324189312ca29e9e","date_created":"2018-12-12T10:11:18Z","file_size":636735,"access_level":"open_access","content_type":"application/pdf","relation":"main_file"}],"abstract":[{"text":"The fact that the complete graph K_5 does not embed in the plane has been generalized in two independent directions. On the one hand, the solution of the classical Heawood problem for graphs on surfaces established that the complete graph K_n embeds in a closed surface M if and only if (n-3)(n-4) is at most 6b_1(M), where b_1(M) is the first Z_2-Betti number of M. On the other hand, Van Kampen and Flores proved that the k-skeleton of the n-dimensional simplex (the higher-dimensional analogue of K_{n+1}) embeds in R^{2k} if and only if n is less or equal to 2k+2. Two decades ago, Kuhnel conjectured that the k-skeleton of the n-simplex embeds in a compact, (k-1)-connected 2k-manifold with kth Z_2-Betti number b_k only if the following generalized Heawood inequality holds: binom{n-k-1}{k+1} is at most binom{2k+1}{k+1} b_k. This is a common generalization of the case of graphs on surfaces as well as the Van Kampen--Flores theorem. In the spirit of Kuhnel's conjecture, we prove that if the k-skeleton of the n-simplex embeds in a 2k-manifold with kth Z_2-Betti number b_k, then n is at most 2b_k binom{2k+2}{k} + 2k + 5. This bound is weaker than the generalized Heawood inequality, but does not require the assumption that M is (k-1)-connected. Our proof uses a result of Volovikov about maps that satisfy a certain homological triviality condition.","lang":"eng"}],"publication_status":"published","scopus_import":1,"author":[{"last_name":"Goaoc","full_name":"Goaoc, Xavier","first_name":"Xavier"},{"first_name":"Isaac","id":"32BF9DAA-F248-11E8-B48F-1D18A9856A87","full_name":"Mabillard, Isaac","last_name":"Mabillard"},{"first_name":"Pavel","full_name":"Paták, Pavel","last_name":"Paták"},{"last_name":"Patakova","full_name":"Patakova, Zuzana","orcid":"0000-0002-3975-1683","first_name":"Zuzana","id":"48B57058-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","id":"38AC689C-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1191-6714","last_name":"Tancer","full_name":"Tancer, Martin"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","full_name":"Wagner, Uli"}],"project":[{"grant_number":"291734","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"department":[{"_id":"UlWa"}],"acknowledgement":"The work by Z. P. was partially supported by the Charles University Grant SVV-2014-260103. The\r\nwork by Z. P. and M. T. was partially supported by the project CE-ITI (GACR P202/12/G061) of\r\nthe Czech Science Foundation and by the ERC Advanced Grant No. 267165. Part of the research\r\nwork of M. T. was conducted at IST Austria, supported by an IST Fellowship. The work by U.W.\r\nwas partially supported by the Swiss National Science Foundation (grants SNSF-200020-138230 and\r\nSNSF-PP00P2-138948).","ec_funded":1,"type":"conference","oa":1,"citation":{"ieee":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result,” presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 476–490.","ista":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. 2015. On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 476–490.","apa":"Goaoc, X., Mabillard, I., Paták, P., Patakova, Z., Tancer, M., &#38; Wagner, U. (2015). On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result (Vol. 34, pp. 476–490). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">https://doi.org/10.4230/LIPIcs.SOCG.2015.476</a>","mla":"Goaoc, Xavier, et al. <i>On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result</i>. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 476–90, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">10.4230/LIPIcs.SOCG.2015.476</a>.","chicago":"Goaoc, Xavier, Isaac Mabillard, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “On Generalized Heawood Inequalities for Manifolds: A Van Kampen–Flores-Type Nonembeddability Result,” 34:476–90. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. <a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">https://doi.org/10.4230/LIPIcs.SOCG.2015.476</a>.","ama":"Goaoc X, Mabillard I, Paták P, Patakova Z, Tancer M, Wagner U. On generalized Heawood inequalities for manifolds: A Van Kampen–Flores-type nonembeddability result. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:476-490. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SOCG.2015.476\">10.4230/LIPIcs.SOCG.2015.476</a>","short":"X. Goaoc, I. Mabillard, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 476–490."},"day":"11","file_date_updated":"2020-07-14T12:44:59Z"}]