[{"status":"public","conference":{"name":"CAV: Computer Aided Verification","start_date":"2015-07-18","location":"San Francisco, CA, United States","end_date":"2015-07-24"},"type":"conference","_id":"1603","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"date_updated":"2024-02-21T13:52:07Z","intvolume":" 9206","month":"07","main_file_link":[{"url":"http://arxiv.org/abs/1502.02834","open_access":"1"}],"scopus_import":1,"alternative_title":["LNCS"],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"For deterministic systems, a counterexample to a property can simply be an error trace, whereas counterexamples in probabilistic systems are necessarily more complex. For instance, a set of erroneous traces with a sufficient cumulative probability mass can be used. Since these are too large objects to understand and manipulate, compact representations such as subchains have been considered. In the case of probabilistic systems with non-determinism, the situation is even more complex. While a subchain for a given strategy (or scheduler, resolving non-determinism) is a straightforward choice, we take a different approach. Instead, we focus on the strategy itself, and extract the most important decisions it makes, and present its succinct representation.\r\nThe key tools we employ to achieve this are (1) introducing a concept of importance of a state w.r.t. the strategy, and (2) learning using decision trees. There are three main consequent advantages of our approach. Firstly, it exploits the quantitative information on states, stressing the more important decisions. Secondly, it leads to a greater variability and degree of freedom in representing the strategies. Thirdly, the representation uses a self-explanatory data structure. In summary, our approach produces more succinct and more explainable strategies, as opposed to e.g. binary decision diagrams. Finally, our experimental results show that we can extract several rules describing the strategy even for very large systems that do not fit in memory, and based on the rules explain the erroneous behaviour."}],"ec_funded":1,"related_material":{"record":[{"relation":"research_paper","id":"5549","status":"public"}]},"volume":9206,"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"eisbn":["978-3-319-21690-4"]},"project":[{"call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","name":"The Wittgenstein Prize"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Reactive Modeling","grant_number":"267989"},{"grant_number":"291734","name":"International IST Postdoc Fellowship Programme","_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"title":"Counterexample explanation by learning small strategies in Markov decision processes","author":[{"full_name":"Brázdil, Tomáš","last_name":"Brázdil","first_name":"Tomáš"},{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Martin","id":"3624234E-F248-11E8-B48F-1D18A9856A87","last_name":"Chmelik","full_name":"Chmelik, Martin"},{"id":"42BABFB4-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas","last_name":"Fellner","full_name":"Fellner, Andreas"},{"id":"44CEF464-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","orcid":"0000-0002-8122-2881","full_name":"Kretinsky, Jan","last_name":"Kretinsky"}],"publist_id":"5564","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Brázdil T, Chatterjee K, Chmelik M, Fellner A, Kretinsky J. 2015. Counterexample explanation by learning small strategies in Markov decision processes. CAV: Computer Aided Verification, LNCS, vol. 9206, 158–177.","chicago":"Brázdil, Tomáš, Krishnendu Chatterjee, Martin Chmelik, Andreas Fellner, and Jan Kretinsky. “Counterexample Explanation by Learning Small Strategies in Markov Decision Processes,” 9206:158–77. Springer, 2015. https://doi.org/10.1007/978-3-319-21690-4_10.","short":"T. Brázdil, K. Chatterjee, M. Chmelik, A. Fellner, J. Kretinsky, in:, Springer, 2015, pp. 158–177.","ieee":"T. Brázdil, K. Chatterjee, M. Chmelik, A. Fellner, and J. Kretinsky, “Counterexample explanation by learning small strategies in Markov decision processes,” presented at the CAV: Computer Aided Verification, San Francisco, CA, United States, 2015, vol. 9206, pp. 158–177.","apa":"Brázdil, T., Chatterjee, K., Chmelik, M., Fellner, A., & Kretinsky, J. (2015). Counterexample explanation by learning small strategies in Markov decision processes (Vol. 9206, pp. 158–177). Presented at the CAV: Computer Aided Verification, San Francisco, CA, United States: Springer. https://doi.org/10.1007/978-3-319-21690-4_10","ama":"Brázdil T, Chatterjee K, Chmelik M, Fellner A, Kretinsky J. Counterexample explanation by learning small strategies in Markov decision processes. In: Vol 9206. Springer; 2015:158-177. doi:10.1007/978-3-319-21690-4_10","mla":"Brázdil, Tomáš, et al. Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. Vol. 9206, Springer, 2015, pp. 158–77, doi:10.1007/978-3-319-21690-4_10."},"oa":1,"quality_controlled":"1","publisher":"Springer","acknowledgement":"This research was funded in part by Austrian Science Fund (FWF) Grant No P 23499-N23, FWF NFN Grant No S11407-N23 (RiSE) and Z211-N23 (Wittgenstein Award), European Research Council (ERC) Grant No 279307 (Graph Games), ERC Grant No 267989 (QUAREM), the Czech Science Foundation Grant No P202/12/G061, and People Programme (Marie Curie Actions) of the European Union’s Seventh Framework Programme (FP7/2007–2013) REA Grant No 291734.","date_created":"2018-12-11T11:52:58Z","date_published":"2015-07-16T00:00:00Z","doi":"10.1007/978-3-319-21690-4_10","page":"158 - 177","day":"16","year":"2015"},{"month":"08","oa_version":"Published Version","abstract":[{"text":"This repository contains the experimental part of the CAV 2015 publication Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.\r\nWe extended the probabilistic model checker PRISM to represent strategies of Markov Decision Processes as Decision Trees.\r\nThe archive contains a java executable version of the extended tool (prism_dectree.jar) together with a few examples of the PRISM benchmark library.\r\nTo execute the program, please have a look at the README.txt, which provides instructions and further information on the archive.\r\nThe archive contains scripts that (if run often enough) reproduces the data presented in the publication.","lang":"eng"}],"contributor":[{"first_name":"Jan","id":"44CEF464-F248-11E8-B48F-1D18A9856A87","last_name":"Kretinsky"}],"license":"https://creativecommons.org/publicdomain/zero/1.0/","ec_funded":1,"related_material":{"record":[{"status":"public","id":"1603","relation":"popular_science"}]},"file":[{"file_name":"IST-2015-28-v1+2_Fellner_DataRep.zip","date_created":"2018-12-12T13:02:31Z","file_size":49557109,"date_updated":"2020-07-14T12:47:00Z","creator":"system","file_id":"5597","checksum":"b8bcb43c0893023cda66c1b69c16ac62","content_type":"application/zip","relation":"main_file","access_level":"open_access"}],"datarep_id":"28","keyword":["Markov Decision Process","Decision Tree","Probabilistic Verification","Counterexample Explanation"],"status":"public","tmp":{"image":"/images/cc_0.png","legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","name":"Creative Commons Public Domain Dedication (CC0 1.0)","short":"CC0 (1.0)"},"type":"research_data","_id":"5549","file_date_updated":"2020-07-14T12:47:00Z","department":[{"_id":"KrCh"},{"_id":"ToHe"}],"ddc":["004"],"date_updated":"2024-02-21T13:52:07Z","oa":1,"publisher":"Institute of Science and Technology Austria","date_created":"2018-12-12T12:31:29Z","date_published":"2015-08-13T00:00:00Z","doi":"10.15479/AT:ISTA:28","day":"13","year":"2015","has_accepted_license":"1","project":[{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"title":"Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes","article_processing_charge":"No","author":[{"full_name":"Fellner, Andreas","last_name":"Fellner","id":"42BABFB4-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"}],"publist_id":"5564","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"mla":"Fellner, Andreas. Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. Institute of Science and Technology Austria, 2015, doi:10.15479/AT:ISTA:28.","short":"A. Fellner, (2015).","ieee":"A. Fellner, “Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015.","apa":"Fellner, A. (2015). Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:28","ama":"Fellner A. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes. 2015. doi:10.15479/AT:ISTA:28","chicago":"Fellner, Andreas. “Experimental Part of CAV 2015 Publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes.” Institute of Science and Technology Austria, 2015. https://doi.org/10.15479/AT:ISTA:28.","ista":"Fellner A. 2015. Experimental part of CAV 2015 publication: Counterexample Explanation by Learning Small Strategies in Markov Decision Processes, Institute of Science and Technology Austria, 10.15479/AT:ISTA:28."}},{"page":"507 - 521","date_created":"2018-12-11T11:52:27Z","doi":"10.4230/LIPIcs.SOCG.2015.507","date_published":"2015-01-01T00:00:00Z","year":"2015","has_accepted_license":"1","day":"01","oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","acknowledgement":"PP, ZP and MT were partially supported by the Charles University Grant GAUK 421511. ZP was\r\npartially supported by the Charles University Grant SVV-2014-260103. ZP and MT were partially\r\nsupported by the ERC Advanced Grant No. 267165 and by the project CE-ITI (GACR P202/12/G061)\r\nof the Czech Science Foundation. UW was partially supported by the Swiss National Science Foundation\r\n(grants SNSF-200020-138230 and SNSF-PP00P2-138948). Part of this work was done when XG was affiliated with INRIA Nancy Grand-Est and when MT was affiliated with Institutionen för matematik, Kungliga Tekniska Högskolan, then IST Austria.","article_processing_charge":"No","publist_id":"5665","author":[{"full_name":"Goaoc, Xavier","last_name":"Goaoc","first_name":"Xavier"},{"first_name":"Pavel","last_name":"Paták","full_name":"Paták, Pavel"},{"first_name":"Zuzana","last_name":"Patakova","orcid":"0000-0002-3975-1683","full_name":"Patakova, Zuzana"},{"last_name":"Tancer","orcid":"0000-0002-1191-6714","full_name":"Tancer, Martin","first_name":"Martin"},{"last_name":"Wagner","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli"}],"title":"Bounding Helly numbers via Betti numbers","citation":{"ista":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. 2015. Bounding Helly numbers via Betti numbers. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 34, 507–521.","chicago":"Goaoc, Xavier, Pavel Paták, Zuzana Patakova, Martin Tancer, and Uli Wagner. “Bounding Helly Numbers via Betti Numbers,” 34:507–21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. https://doi.org/10.4230/LIPIcs.SOCG.2015.507.","ama":"Goaoc X, Paták P, Patakova Z, Tancer M, Wagner U. Bounding Helly numbers via Betti numbers. In: Vol 34. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2015:507-521. doi:10.4230/LIPIcs.SOCG.2015.507","apa":"Goaoc, X., Paták, P., Patakova, Z., Tancer, M., & Wagner, U. (2015). Bounding Helly numbers via Betti numbers (Vol. 34, pp. 507–521). Presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SOCG.2015.507","ieee":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, and U. Wagner, “Bounding Helly numbers via Betti numbers,” presented at the SoCG: Symposium on Computational Geometry, Eindhoven, Netherlands, 2015, vol. 34, pp. 507–521.","short":"X. Goaoc, P. Paták, Z. Patakova, M. Tancer, U. Wagner, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 507–521.","mla":"Goaoc, Xavier, et al. Bounding Helly Numbers via Betti Numbers. Vol. 34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015, pp. 507–21, doi:10.4230/LIPIcs.SOCG.2015.507."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","license":"https://creativecommons.org/licenses/by/4.0/","related_material":{"record":[{"status":"public","id":"424","relation":"later_version"}]},"volume":34,"publication_status":"published","language":[{"iso":"eng"}],"file":[{"checksum":"e6881df44d87fe0c2529c9f7b2724614","file_id":"4794","access_level":"open_access","relation":"main_file","content_type":"application/pdf","date_created":"2018-12-12T10:10:09Z","file_name":"IST-2016-501-v1+1_46.pdf","creator":"system","date_updated":"2020-07-14T12:45:00Z","file_size":633712}],"alternative_title":["LIPIcs"],"scopus_import":"1","intvolume":" 34","month":"01","abstract":[{"lang":"eng","text":"We show that very weak topological assumptions are enough to ensure the existence of a Helly-type theorem. More precisely, we show that for any non-negative integers b and d there exists an integer h(b,d) such that the following holds. If F is a finite family of subsets of R^d such that the ith reduced Betti number (with Z_2 coefficients in singular homology) of the intersection of any proper subfamily G of F is at most b for every non-negative integer i less or equal to (d-1)/2, then F has Helly number at most h(b,d). These topological conditions are sharp: not controlling any of these first Betti numbers allow for families with unbounded Helly number. Our proofs combine homological non-embeddability results with a Ramsey-based approach to build, given an arbitrary simplicial complex K, some well-behaved chain map from C_*(K) to C_*(R^d). Both techniques are of independent interest."}],"oa_version":"Submitted Version","file_date_updated":"2020-07-14T12:45:00Z","department":[{"_id":"UlWa"}],"date_updated":"2024-02-28T12:59:37Z","ddc":["510"],"conference":{"start_date":"2015-06-22","location":"Eindhoven, Netherlands","end_date":"2015-06-25","name":"SoCG: Symposium on Computational Geometry"},"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"conference","pubrep_id":"501","status":"public","_id":"1512"},{"day":"20","publication":"Journal fur die Reine und Angewandte Mathematik","year":"2015","date_published":"2015-02-20T00:00:00Z","doi":"10.1515/crelle-2014-0122","date_created":"2018-12-11T11:45:32Z","page":"203 - 234","acknowledgement":"While working on this paper the authors were supported by the Leverhulme Trust and ERC grant 306457.","publisher":"Walter de Gruyter","quality_controlled":"1","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Browning, Timothy D, and Sean Prendiville. “Improvements in Birch’s Theorem on Forms in Many Variables.” Journal Fur Die Reine Und Angewandte Mathematik. Walter de Gruyter, n.d. https://doi.org/10.1515/crelle-2014-0122.","ista":"Browning TD, Prendiville S. Improvements in Birch’s theorem on forms in many variables. Journal fur die Reine und Angewandte Mathematik. 2017(731), 203–234.","mla":"Browning, Timothy D., and Sean Prendiville. “Improvements in Birch’s Theorem on Forms in Many Variables.” Journal Fur Die Reine Und Angewandte Mathematik, vol. 2017, no. 731, Walter de Gruyter, pp. 203–34, doi:10.1515/crelle-2014-0122.","apa":"Browning, T. D., & Prendiville, S. (n.d.). Improvements in Birch’s theorem on forms in many variables. Journal Fur Die Reine Und Angewandte Mathematik. Walter de Gruyter. https://doi.org/10.1515/crelle-2014-0122","ama":"Browning TD, Prendiville S. Improvements in Birch’s theorem on forms in many variables. Journal fur die Reine und Angewandte Mathematik. 2017(731):203-234. doi:10.1515/crelle-2014-0122","short":"T.D. Browning, S. Prendiville, Journal Fur Die Reine Und Angewandte Mathematik 2017 (n.d.) 203–234.","ieee":"T. D. Browning and S. Prendiville, “Improvements in Birch’s theorem on forms in many variables,” Journal fur die Reine und Angewandte Mathematik, vol. 2017, no. 731. Walter de Gruyter, pp. 203–234."},"title":"Improvements in Birch's theorem on forms in many variables","author":[{"first_name":"Timothy D","id":"35827D50-F248-11E8-B48F-1D18A9856A87","last_name":"Browning","orcid":"0000-0002-8314-0177","full_name":"Browning, Timothy D"},{"last_name":"Prendiville","full_name":"Prendiville, Sean","first_name":"Sean"}],"publist_id":"7631","external_id":{"arxiv":["1402.4489"]},"article_processing_charge":"No","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0075-4102"]},"publication_status":"submitted","volume":2017,"related_material":{"record":[{"relation":"later_version","id":"256","status":"public"}]},"issue":"731","oa_version":"Preprint","abstract":[{"lang":"eng","text":"We show that a non-singular integral form of degree d is soluble non-trivially over the integers if and only if it is soluble non-trivially over the reals and the p-adic numbers, provided that the form has at least (d-\\sqrt{d}/2)2^d variables. This improves on a longstanding result of Birch."}],"month":"02","intvolume":" 2017","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1402.4489"}],"extern":"1","date_updated":"2024-03-05T12:09:22Z","_id":"271","status":"public","type":"journal_article","article_type":"original"},{"quality_controlled":"1","publisher":"Springer","oa":1,"page":"585 - 605","date_published":"2015-08-01T00:00:00Z","doi":"10.1007/978-3-662-48000-7_29","date_created":"2018-12-11T11:53:24Z","year":"2015","day":"01","publication":"35th Annual Cryptology Conference","project":[{"call_identifier":"FP7","_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","name":"Discrete Optimization in Computer Vision: Theory and Practice"},{"name":"Provable Security for Physical Cryptography","grant_number":"259668","_id":"258C570E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"author":[{"first_name":"Stefan","last_name":"Dziembowski","full_name":"Dziembowski, Stefan"},{"first_name":"Sebastian","full_name":"Faust, Sebastian","last_name":"Faust"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"publist_id":"5474","article_processing_charge":"No","title":"Proofs of space","citation":{"chicago":"Dziembowski, Stefan, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Z Pietrzak. “Proofs of Space.” In 35th Annual Cryptology Conference, 9216:585–605. Springer, 2015. https://doi.org/10.1007/978-3-662-48000-7_29.","ista":"Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. 2015. Proofs of space. 35th Annual Cryptology Conference. CRYPTO: International Cryptology Conference, LNCS, vol. 9216, 585–605.","mla":"Dziembowski, Stefan, et al. “Proofs of Space.” 35th Annual Cryptology Conference, vol. 9216, Springer, 2015, pp. 585–605, doi:10.1007/978-3-662-48000-7_29.","apa":"Dziembowski, S., Faust, S., Kolmogorov, V., & Pietrzak, K. Z. (2015). Proofs of space. In 35th Annual Cryptology Conference (Vol. 9216, pp. 585–605). Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-662-48000-7_29","ama":"Dziembowski S, Faust S, Kolmogorov V, Pietrzak KZ. Proofs of space. In: 35th Annual Cryptology Conference. Vol 9216. Springer; 2015:585-605. doi:10.1007/978-3-662-48000-7_29","short":"S. Dziembowski, S. Faust, V. Kolmogorov, K.Z. Pietrzak, in:, 35th Annual Cryptology Conference, Springer, 2015, pp. 585–605.","ieee":"S. Dziembowski, S. Faust, V. Kolmogorov, and K. Z. Pietrzak, “Proofs of space,” in 35th Annual Cryptology Conference, Santa Barbara, CA, United States, 2015, vol. 9216, pp. 585–605."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","alternative_title":["LNCS"],"main_file_link":[{"url":"https://eprint.iacr.org/2013/796.pdf","open_access":"1"}],"month":"08","intvolume":" 9216","abstract":[{"text":"Proofs of work (PoW) have been suggested by Dwork and Naor (Crypto’92) as protection to a shared resource. The basic idea is to ask the service requestor to dedicate some non-trivial amount of computational work to every request. The original applications included prevention of spam and protection against denial of service attacks. More recently, PoWs have been used to prevent double spending in the Bitcoin digital currency system. In this work, we put forward an alternative concept for PoWs - so-called proofs of space (PoS), where a service requestor must dedicate a significant amount of disk space as opposed to computation. We construct secure PoS schemes in the random oracle model (with one additional mild assumption required for the proof to go through), using graphs with high “pebbling complexity” and Merkle hash-trees. We discuss some applications, including follow-up work where a decentralized digital currency scheme called Spacecoin is constructed that uses PoS (instead of wasteful PoW like in Bitcoin) to prevent double spending. The main technical contribution of this work is the construction of (directed, loop-free) graphs on N vertices with in-degree O(log logN) such that even if one places Θ(N) pebbles on the nodes of the graph, there’s a constant fraction of nodes that needs Θ(N) steps to be pebbled (where in every step one can put a pebble on a node if all its parents have a pebble).","lang":"eng"}],"oa_version":"Preprint","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"2274"}]},"volume":9216,"ec_funded":1,"publication_identifier":{"isbn":["9783662479995"],"issn":["0302-9743"]},"publication_status":"published","language":[{"iso":"eng"}],"type":"conference","conference":{"name":"CRYPTO: International Cryptology Conference","start_date":"2015-08-16","location":"Santa Barbara, CA, United States","end_date":"2015-08-20"},"status":"public","pubrep_id":"671","_id":"1675","department":[{"_id":"VlKo"},{"_id":"KrPi"}],"date_updated":"2024-03-20T08:31:49Z"},{"article_processing_charge":"No","author":[{"full_name":"Michael, Alicia Kathleen","last_name":"Michael","id":"6437c950-2a03-11ee-914d-d6476dd7b75c","first_name":"Alicia Kathleen"},{"full_name":"Harvey, Stacy L.","last_name":"Harvey","first_name":"Stacy L."},{"last_name":"Sammons","full_name":"Sammons, Patrick J.","first_name":"Patrick J."},{"last_name":"Anderson","full_name":"Anderson, Amanda P.","first_name":"Amanda P."},{"first_name":"Hema M.","full_name":"Kopalle, Hema M.","last_name":"Kopalle"},{"full_name":"Banham, Alison H.","last_name":"Banham","first_name":"Alison H."},{"full_name":"Partch, Carrie L.","last_name":"Partch","first_name":"Carrie L."}],"title":"Cancer/Testis antigen PASD1 silences the circadian clock","citation":{"chicago":"Michael, Alicia K., Stacy L. Harvey, Patrick J. Sammons, Amanda P. Anderson, Hema M. Kopalle, Alison H. Banham, and Carrie L. Partch. “Cancer/Testis Antigen PASD1 Silences the Circadian Clock.” Molecular Cell. Elsevier, 2015. https://doi.org/10.1016/j.molcel.2015.03.031.","ista":"Michael AK, Harvey SL, Sammons PJ, Anderson AP, Kopalle HM, Banham AH, Partch CL. 2015. Cancer/Testis antigen PASD1 silences the circadian clock. Molecular Cell. 58(5), 743–754.","mla":"Michael, Alicia K., et al. “Cancer/Testis Antigen PASD1 Silences the Circadian Clock.” Molecular Cell, vol. 58, no. 5, Elsevier, 2015, pp. 743–54, doi:10.1016/j.molcel.2015.03.031.","ieee":"A. K. Michael et al., “Cancer/Testis antigen PASD1 silences the circadian clock,” Molecular Cell, vol. 58, no. 5. Elsevier, pp. 743–754, 2015.","short":"A.K. Michael, S.L. Harvey, P.J. Sammons, A.P. Anderson, H.M. Kopalle, A.H. Banham, C.L. Partch, Molecular Cell 58 (2015) 743–754.","apa":"Michael, A. K., Harvey, S. L., Sammons, P. J., Anderson, A. P., Kopalle, H. M., Banham, A. H., & Partch, C. L. (2015). Cancer/Testis antigen PASD1 silences the circadian clock. Molecular Cell. Elsevier. https://doi.org/10.1016/j.molcel.2015.03.031","ama":"Michael AK, Harvey SL, Sammons PJ, et al. Cancer/Testis antigen PASD1 silences the circadian clock. Molecular Cell. 2015;58(5):743-754. doi:10.1016/j.molcel.2015.03.031"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"743-754","date_created":"2024-03-21T07:58:08Z","doi":"10.1016/j.molcel.2015.03.031","date_published":"2015-06-04T00:00:00Z","year":"2015","publication":"Molecular Cell","day":"04","oa":1,"publisher":"Elsevier","quality_controlled":"1","date_updated":"2024-03-25T11:52:26Z","extern":"1","type":"journal_article","article_type":"original","keyword":["Cell Biology","Molecular Biology"],"status":"public","_id":"15160","issue":"5","volume":58,"publication_status":"published","publication_identifier":{"issn":["1097-2765"]},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1016/j.molcel.2015.03.031"}],"scopus_import":"1","intvolume":" 58","month":"06","abstract":[{"text":"The circadian clock orchestrates global changes in transcriptional regulation on a daily basis via the bHLH-PAS transcription factor CLOCK:BMAL1. Pathways driven by other bHLH-PAS transcription factors have a homologous repressor that modulates activity on a tissue-specific basis, but none have been identified for CLOCK:BMAL1. We show here that the cancer/testis antigen PASD1 fulfills this role to suppress circadian rhythms. PASD1 is evolutionarily related to CLOCK and interacts with the CLOCK:BMAL1 complex to repress transcriptional activation. Expression of PASD1 is restricted to germline tissues in healthy individuals but can be induced in cells of somatic origin upon oncogenic transformation. Reducing PASD1 in human cancer cells significantly increases the amplitude of transcriptional oscillations to generate more robust circadian rhythms. Our results describe a function for a germline-specific protein in regulation of the circadian clock and provide a molecular link from oncogenic transformation to suppression of circadian rhythms.","lang":"eng"}],"oa_version":"Published Version"},{"status":"public","keyword":["Molecular Biology","Biochemistry"],"type":"journal_article","article_type":"original","_id":"15159","extern":"1","date_updated":"2024-03-25T11:53:58Z","month":"09","intvolume":" 40","scopus_import":"1","oa_version":"None","abstract":[{"text":"It is widely recognized that BMAL1 is an essential subunit of the primary transcription factor that drives rhythmic circadian transcription in the nucleus. In a surprising turn, Lipton et al. now show that BMAL1 rhythmically interacts with translational machinery in the cytosol to stimulate protein synthesis in response to mTOR signaling.","lang":"eng"}],"issue":"9","volume":40,"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0968-0004"]},"publication_status":"published","title":"Cytosolic BMAL1 moonlights as a translation factor","author":[{"first_name":"Alicia Kathleen","id":"6437c950-2a03-11ee-914d-d6476dd7b75c","full_name":"Michael, Alicia Kathleen","last_name":"Michael"},{"first_name":"Hande","last_name":"Asimgil","full_name":"Asimgil, Hande"},{"last_name":"Partch","full_name":"Partch, Carrie L.","first_name":"Carrie L."}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Michael, A. K., Asimgil, H., & Partch, C. L. (2015). Cytosolic BMAL1 moonlights as a translation factor. Trends in Biochemical Sciences. Elsevier. https://doi.org/10.1016/j.tibs.2015.07.006","ama":"Michael AK, Asimgil H, Partch CL. Cytosolic BMAL1 moonlights as a translation factor. Trends in Biochemical Sciences. 2015;40(9):489-490. doi:10.1016/j.tibs.2015.07.006","short":"A.K. Michael, H. Asimgil, C.L. Partch, Trends in Biochemical Sciences 40 (2015) 489–490.","ieee":"A. K. Michael, H. Asimgil, and C. L. Partch, “Cytosolic BMAL1 moonlights as a translation factor,” Trends in Biochemical Sciences, vol. 40, no. 9. Elsevier, pp. 489–490, 2015.","mla":"Michael, Alicia K., et al. “Cytosolic BMAL1 Moonlights as a Translation Factor.” Trends in Biochemical Sciences, vol. 40, no. 9, Elsevier, 2015, pp. 489–90, doi:10.1016/j.tibs.2015.07.006.","ista":"Michael AK, Asimgil H, Partch CL. 2015. Cytosolic BMAL1 moonlights as a translation factor. Trends in Biochemical Sciences. 40(9), 489–490.","chicago":"Michael, Alicia K., Hande Asimgil, and Carrie L. Partch. “Cytosolic BMAL1 Moonlights as a Translation Factor.” Trends in Biochemical Sciences. Elsevier, 2015. https://doi.org/10.1016/j.tibs.2015.07.006."},"publisher":"Elsevier","quality_controlled":"1","doi":"10.1016/j.tibs.2015.07.006","date_published":"2015-09-01T00:00:00Z","date_created":"2024-03-21T07:57:44Z","page":"489-490","day":"01","publication":"Trends in Biochemical Sciences","year":"2015"},{"scopus_import":1,"month":"11","intvolume":" 13","abstract":[{"text":"The emergence of drug resistant pathogens is a serious public health problem. It is a long-standing goal to predict rates of resistance evolution and design optimal treatment strategies accordingly. To this end, it is crucial to reveal the underlying causes of drug-specific differences in the evolutionary dynamics leading to resistance. However, it remains largely unknown why the rates of resistance evolution via spontaneous mutations and the diversity of mutational paths vary substantially between drugs. Here we comprehensively quantify the distribution of fitness effects (DFE) of mutations, a key determinant of evolutionary dynamics, in the presence of eight antibiotics representing the main modes of action. Using precise high-throughput fitness measurements for genome-wide Escherichia coli gene deletion strains, we find that the width of the DFE varies dramatically between antibiotics and, contrary to conventional wisdom, for some drugs the DFE width is lower than in the absence of stress. We show that this previously underappreciated divergence in DFE width among antibiotics is largely caused by their distinct drug-specific dose-response characteristics. Unlike the DFE, the magnitude of the changes in tolerated drug concentration resulting from genome-wide mutations is similar for most drugs but exceptionally small for the antibiotic nitrofurantoin, i.e., mutations generally have considerably smaller resistance effects for nitrofurantoin than for other drugs. A population genetics model predicts that resistance evolution for drugs with this property is severely limited and confined to reproducible mutational paths. We tested this prediction in laboratory evolution experiments using the “morbidostat”, a device for evolving bacteria in well-controlled drug environments. Nitrofurantoin resistance indeed evolved extremely slowly via reproducible mutations—an almost paradoxical behavior since this drug causes DNA damage and increases the mutation rate. Overall, we identified novel quantitative characteristics of the evolutionary landscape that provide the conceptual foundation for predicting the dynamics of drug resistance evolution.","lang":"eng"}],"oa_version":"Published Version","issue":"11","volume":13,"related_material":{"record":[{"relation":"research_data","id":"9711","status":"public"},{"id":"9765","status":"public","relation":"research_data"},{"status":"public","id":"6263","relation":"dissertation_contains"}]},"ec_funded":1,"publication_status":"published","file":[{"checksum":"0e82e3279f50b15c6c170c042627802b","file_id":"4723","content_type":"application/pdf","access_level":"open_access","relation":"main_file","date_created":"2018-12-12T10:09:00Z","file_name":"IST-2016-468-v1+1_journal.pbio.1002299.pdf","date_updated":"2020-07-14T12:45:07Z","file_size":1387760,"creator":"system"}],"language":[{"iso":"eng"}],"type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","pubrep_id":"468","_id":"1619","department":[{"_id":"ToBo"}],"file_date_updated":"2020-07-14T12:45:07Z","date_updated":"2024-03-27T23:30:28Z","ddc":["570"],"quality_controlled":"1","publisher":"Public Library of Science","oa":1,"doi":"10.1371/journal.pbio.1002299","date_published":"2015-11-18T00:00:00Z","date_created":"2018-12-11T11:53:04Z","has_accepted_license":"1","year":"2015","day":"18","publication":"PLoS Biology","project":[{"name":"Revealing the fundamental limits of cell growth","grant_number":"RGP0042/2013","_id":"25EB3A80-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"25E9AF9E-B435-11E9-9278-68D0E5697425","name":"Revealing the mechanisms underlying drug interactions","grant_number":"P27201-B22"},{"name":"Optimality principles in responses to antibiotics","grant_number":"303507","call_identifier":"FP7","_id":"25E83C2C-B435-11E9-9278-68D0E5697425"}],"article_number":"e1002299","publist_id":"5547","author":[{"last_name":"Chevereau","full_name":"Chevereau, Guillaume","id":"424D78A0-F248-11E8-B48F-1D18A9856A87","first_name":"Guillaume"},{"id":"4342E402-F248-11E8-B48F-1D18A9856A87","first_name":"Marta","last_name":"Dravecka","orcid":"0000-0002-2519-8004","full_name":"Dravecka, Marta"},{"full_name":"Batur, Tugce","last_name":"Batur","first_name":"Tugce"},{"first_name":"Aysegul","full_name":"Guvenek, Aysegul","last_name":"Guvenek"},{"first_name":"Dilay","full_name":"Ayhan, Dilay","last_name":"Ayhan"},{"first_name":"Erdal","last_name":"Toprak","full_name":"Toprak, Erdal"},{"last_name":"Bollenbach","orcid":"0000-0003-4398-476X","full_name":"Bollenbach, Mark Tobias","id":"3E6DB97A-F248-11E8-B48F-1D18A9856A87","first_name":"Mark Tobias"}],"title":"Quantifying the determinants of evolutionary dynamics leading to drug resistance","citation":{"chicago":"Chevereau, Guillaume, Marta Lukacisinova, Tugce Batur, Aysegul Guvenek, Dilay Ayhan, Erdal Toprak, and Mark Tobias Bollenbach. “Quantifying the Determinants of Evolutionary Dynamics Leading to Drug Resistance.” PLoS Biology. Public Library of Science, 2015. https://doi.org/10.1371/journal.pbio.1002299.","ista":"Chevereau G, Lukacisinova M, Batur T, Guvenek A, Ayhan D, Toprak E, Bollenbach MT. 2015. Quantifying the determinants of evolutionary dynamics leading to drug resistance. PLoS Biology. 13(11), e1002299.","mla":"Chevereau, Guillaume, et al. “Quantifying the Determinants of Evolutionary Dynamics Leading to Drug Resistance.” PLoS Biology, vol. 13, no. 11, e1002299, Public Library of Science, 2015, doi:10.1371/journal.pbio.1002299.","ieee":"G. Chevereau et al., “Quantifying the determinants of evolutionary dynamics leading to drug resistance,” PLoS Biology, vol. 13, no. 11. Public Library of Science, 2015.","short":"G. Chevereau, M. Lukacisinova, T. Batur, A. Guvenek, D. Ayhan, E. Toprak, M.T. Bollenbach, PLoS Biology 13 (2015).","ama":"Chevereau G, Lukacisinova M, Batur T, et al. Quantifying the determinants of evolutionary dynamics leading to drug resistance. PLoS Biology. 2015;13(11). doi:10.1371/journal.pbio.1002299","apa":"Chevereau, G., Lukacisinova, M., Batur, T., Guvenek, A., Ayhan, D., Toprak, E., & Bollenbach, M. T. (2015). Quantifying the determinants of evolutionary dynamics leading to drug resistance. PLoS Biology. Public Library of Science. https://doi.org/10.1371/journal.pbio.1002299"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"volume":111,"issue":"50","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0027-8424"],"eissn":["1091-6490"]},"publication_status":"published","month":"12","intvolume":" 111","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://www.pnas.org/content/111/50/17869"}],"oa_version":"Published Version","pmid":1,"abstract":[{"text":"Protein oligomers have been implicated as toxic agents in a wide range of amyloid-related diseases. However, it has remained unsolved whether the oligomers are a necessary step in the formation of amyloid fibrils or just a dangerous byproduct. Analogously, it has not been resolved if the amyloid nucleation process is a classical one-step nucleation process or a two-step process involving prenucleation clusters. We use coarse-grained computer simulations to study the effect of nonspecific attractions between peptides on the primary nucleation process underlying amyloid fibrillization. We find that, for peptides that do not attract, the classical one-step nucleation mechanism is possible but only at nonphysiologically high peptide concentrations. At low peptide concentrations, which mimic the physiologically relevant regime, attractive interpeptide interactions are essential for fibril formation. Nucleation then inevitably takes place through a two-step mechanism involving prefibrillar oligomers. We show that oligomers not only help peptides meet each other but also, create an environment that facilitates the conversion of monomers into the β-sheet–rich form characteristic of fibrils. Nucleation typically does not proceed through the most prevalent oligomers but through an oligomer size that is only observed in rare fluctuations, which is why such aggregates might be hard to capture experimentally. Finally, we find that the nucleation of amyloid fibrils cannot be described by classical nucleation theory: in the two-step mechanism, the critical nucleus size increases with increases in both concentration and interpeptide interactions, which is in direct contrast with predictions from classical nucleation theory.","lang":"eng"}],"extern":"1","date_updated":"2021-11-29T13:29:05Z","status":"public","keyword":["multidisciplinary"],"type":"journal_article","article_type":"original","_id":"10382","date_published":"2014-12-01T00:00:00Z","doi":"10.1073/pnas.1410159111","date_created":"2021-11-29T13:09:53Z","page":"17869-17874","day":"01","publication":"Proceedings of the National Academy of Sciences","year":"2014","publisher":"National Academy of Sciences","quality_controlled":"1","oa":1,"acknowledgement":"We thank Michele Vendruscolo, Iskra Staneva, and William M. Jacobs, for helpful discussions. A.Š. acknowledges support from the Human Frontier Science Program and Emmanuel College. Y.C.C. and D.F. are supported by Engineering and Physical Sciences Research Council Programme Grant EP/I001352/1. T.P.J.K. acknowledges the Frances and Augustus Newman Foundation, the European Research Council, and the Biotechnology and Biological Sciences Research Council. D.F. acknowledges European Research Council Advanced Grant 227758.","title":"Crucial role of nonspecific interactions in amyloid nucleation","author":[{"orcid":"0000-0002-7854-2139","full_name":"Šarić, Anđela","last_name":"Šarić","first_name":"Anđela","id":"bf63d406-f056-11eb-b41d-f263a6566d8b"},{"first_name":"Yassmine C.","last_name":"Chebaro","full_name":"Chebaro, Yassmine C."},{"first_name":"Tuomas P. J.","full_name":"Knowles, Tuomas P. J.","last_name":"Knowles"},{"last_name":"Frenkel","full_name":"Frenkel, Daan","first_name":"Daan"}],"external_id":{"arxiv":["1412.0897"],"pmid":["25453085"]},"article_processing_charge":"No","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","citation":{"ista":"Šarić A, Chebaro YC, Knowles TPJ, Frenkel D. 2014. Crucial role of nonspecific interactions in amyloid nucleation. Proceedings of the National Academy of Sciences. 111(50), 17869–17874.","chicago":"Šarić, Anđela, Yassmine C. Chebaro, Tuomas P. J. Knowles, and Daan Frenkel. “Crucial Role of Nonspecific Interactions in Amyloid Nucleation.” Proceedings of the National Academy of Sciences. National Academy of Sciences, 2014. https://doi.org/10.1073/pnas.1410159111.","ama":"Šarić A, Chebaro YC, Knowles TPJ, Frenkel D. Crucial role of nonspecific interactions in amyloid nucleation. Proceedings of the National Academy of Sciences. 2014;111(50):17869-17874. doi:10.1073/pnas.1410159111","apa":"Šarić, A., Chebaro, Y. C., Knowles, T. P. J., & Frenkel, D. (2014). Crucial role of nonspecific interactions in amyloid nucleation. Proceedings of the National Academy of Sciences. National Academy of Sciences. https://doi.org/10.1073/pnas.1410159111","ieee":"A. Šarić, Y. C. Chebaro, T. P. J. Knowles, and D. Frenkel, “Crucial role of nonspecific interactions in amyloid nucleation,” Proceedings of the National Academy of Sciences, vol. 111, no. 50. National Academy of Sciences, pp. 17869–17874, 2014.","short":"A. Šarić, Y.C. Chebaro, T.P.J. Knowles, D. Frenkel, Proceedings of the National Academy of Sciences 111 (2014) 17869–17874.","mla":"Šarić, Anđela, et al. “Crucial Role of Nonspecific Interactions in Amyloid Nucleation.” Proceedings of the National Academy of Sciences, vol. 111, no. 50, National Academy of Sciences, 2014, pp. 17869–74, doi:10.1073/pnas.1410159111."}},{"date_updated":"2021-11-29T13:29:01Z","extern":"1","article_type":"original","type":"journal_article","status":"public","_id":"10383","issue":"5","volume":89,"publication_identifier":{"eissn":["1550-2376"],"issn":["1539-3755"]},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1310.0826","open_access":"1"}],"month":"05","intvolume":" 89","abstract":[{"lang":"eng","text":"We use numerical simulations to compute the equation of state of a suspension of spherical self-propelled nanoparticles in two and three dimensions. We study in detail the effect of excluded volume interactions and confinement as a function of the system's temperature, concentration, and strength of the propulsion. We find a striking nonmonotonic dependence of the pressure on the temperature and provide simple scaling arguments to predict and explain the occurrence of such anomalous behavior. We explicitly show how our results have important implications for the effective forces on passive components suspended in a bath of active particles."}],"pmid":1,"oa_version":"Preprint","author":[{"first_name":"S. A.","full_name":"Mallory, S. A.","last_name":"Mallory"},{"first_name":"Anđela","id":"bf63d406-f056-11eb-b41d-f263a6566d8b","full_name":"Šarić, Anđela","orcid":"0000-0002-7854-2139","last_name":"Šarić"},{"last_name":"Valeriani","full_name":"Valeriani, C.","first_name":"C."},{"first_name":"A.","last_name":"Cacciuto","full_name":"Cacciuto, A."}],"external_id":{"pmid":["25353796"],"arxiv":["1310.0826"]},"article_processing_charge":"No","title":"Anomalous thermomechanical properties of a self-propelled colloidal fluid","citation":{"chicago":"Mallory, S. A., Anđela Šarić, C. Valeriani, and A. Cacciuto. “Anomalous Thermomechanical Properties of a Self-Propelled Colloidal Fluid.” Physical Review E. American Physical Society, 2014. https://doi.org/10.1103/physreve.89.052303.","ista":"Mallory SA, Šarić A, Valeriani C, Cacciuto A. 2014. Anomalous thermomechanical properties of a self-propelled colloidal fluid. Physical Review E. 89(5), 052303.","mla":"Mallory, S. A., et al. “Anomalous Thermomechanical Properties of a Self-Propelled Colloidal Fluid.” Physical Review E, vol. 89, no. 5, 052303, American Physical Society, 2014, doi:10.1103/physreve.89.052303.","ama":"Mallory SA, Šarić A, Valeriani C, Cacciuto A. Anomalous thermomechanical properties of a self-propelled colloidal fluid. Physical Review E. 2014;89(5). doi:10.1103/physreve.89.052303","apa":"Mallory, S. A., Šarić, A., Valeriani, C., & Cacciuto, A. (2014). Anomalous thermomechanical properties of a self-propelled colloidal fluid. Physical Review E. American Physical Society. https://doi.org/10.1103/physreve.89.052303","short":"S.A. Mallory, A. Šarić, C. Valeriani, A. Cacciuto, Physical Review E 89 (2014).","ieee":"S. A. Mallory, A. Šarić, C. Valeriani, and A. Cacciuto, “Anomalous thermomechanical properties of a self-propelled colloidal fluid,” Physical Review E, vol. 89, no. 5. American Physical Society, 2014."},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","article_number":"052303","doi":"10.1103/physreve.89.052303","date_published":"2014-05-06T00:00:00Z","date_created":"2021-11-29T13:10:33Z","year":"2014","day":"06","publication":"Physical Review E","publisher":"American Physical Society","quality_controlled":"1","oa":1}]