[{"status":"public","type":"conference","file_date_updated":"2020-07-14T12:47:49Z","year":"2018","publication_status":"published","quality_controlled":"1","doi":"10.5441/002/EDBT.2018.14","publication_identifier":{"issn":["2367-2005"],"isbn":["9783893180783"]},"_id":"7116","oa":1,"has_accepted_license":"1","day":"26","tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode"},"date_created":"2019-11-26T14:19:11Z","scopus_import":1,"publication":"Proceedings of the 21st International Conference on Extending Database Technology","title":"Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study","page":"145-156","file":[{"file_size":1603204,"content_type":"application/pdf","date_updated":"2020-07-14T12:47:49Z","file_name":"2018_OpenProceedings_Grubic.pdf","access_level":"open_access","relation":"main_file","creator":"dernst","file_id":"7118","date_created":"2019-11-26T14:23:04Z","checksum":"ec979b56abc71016d6e6adfdadbb4afe"}],"month":"03","article_processing_charge":"No","date_published":"2018-03-26T00:00:00Z","publisher":"OpenProceedings","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","conference":{"start_date":"2018-03-26","location":"Vienna, Austria","name":"EDBT: Conference on Extending Database Technology","end_date":"2018-03-29"},"ddc":["000"],"abstract":[{"lang":"eng","text":"Training deep learning models has received tremendous research interest recently. In particular, there has been intensive research on reducing the communication cost of training when using multiple computational devices, through reducing the precision of the underlying data representation. Naturally, such methods induce system trade-offs—lowering communication precision could de-crease communication overheads and improve scalability; but, on the other hand, it can also reduce the accuracy of training. In this paper, we study this trade-off space, and ask:Can low-precision communication consistently improve the end-to-end performance of training modern neural networks, with no accuracy loss?From the performance point of view, the answer to this question may appear deceptively easy: compressing communication through low precision should help when the ratio between communication and computation is high. However, this answer is less straightforward when we try to generalize this principle across various neural network architectures (e.g., AlexNet vs. ResNet),number of GPUs (e.g., 2 vs. 8 GPUs), machine configurations(e.g., EC2 instances vs. NVIDIA DGX-1), communication primitives (e.g., MPI vs. NCCL), and even different GPU architectures(e.g., Kepler vs. Pascal). Currently, it is not clear how a realistic realization of all these factors maps to the speed up provided by low-precision communication. In this paper, we conduct an empirical study to answer this question and report the insights."}],"department":[{"_id":"DaAl"}],"date_updated":"2024-10-09T20:59:05Z","corr_author":"1","author":[{"full_name":"Grubic, Demjan","first_name":"Demjan","last_name":"Grubic"},{"first_name":"Leo","last_name":"Tam","full_name":"Tam, Leo"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"full_name":"Zhang, Ce","last_name":"Zhang","first_name":"Ce"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","language":[{"iso":"eng"}],"citation":{"ieee":"D. Grubic, L. Tam, D.-A. Alistarh, and C. Zhang, “Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study,” in <i>Proceedings of the 21st International Conference on Extending Database Technology</i>, Vienna, Austria, 2018, pp. 145–156.","chicago":"Grubic, Demjan, Leo Tam, Dan-Adrian Alistarh, and Ce Zhang. “Synchronous Multi-GPU Training for Deep Learning with Low-Precision Communications: An Empirical Study.” In <i>Proceedings of the 21st International Conference on Extending Database Technology</i>, 145–56. OpenProceedings, 2018. <a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">https://doi.org/10.5441/002/EDBT.2018.14</a>.","ista":"Grubic D, Tam L, Alistarh D-A, Zhang C. 2018. Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study. Proceedings of the 21st International Conference on Extending Database Technology. EDBT: Conference on Extending Database Technology, 145–156.","mla":"Grubic, Demjan, et al. “Synchronous Multi-GPU Training for Deep Learning with Low-Precision Communications: An Empirical Study.” <i>Proceedings of the 21st International Conference on Extending Database Technology</i>, OpenProceedings, 2018, pp. 145–56, doi:<a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">10.5441/002/EDBT.2018.14</a>.","short":"D. Grubic, L. Tam, D.-A. Alistarh, C. Zhang, in:, Proceedings of the 21st International Conference on Extending Database Technology, OpenProceedings, 2018, pp. 145–156.","ama":"Grubic D, Tam L, Alistarh D-A, Zhang C. Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study. In: <i>Proceedings of the 21st International Conference on Extending Database Technology</i>. OpenProceedings; 2018:145-156. doi:<a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">10.5441/002/EDBT.2018.14</a>","apa":"Grubic, D., Tam, L., Alistarh, D.-A., &#38; Zhang, C. (2018). Synchronous multi-GPU training for deep learning with low-precision communications: An empirical study. In <i>Proceedings of the 21st International Conference on Extending Database Technology</i> (pp. 145–156). Vienna, Austria: OpenProceedings. <a href=\"https://doi.org/10.5441/002/EDBT.2018.14\">https://doi.org/10.5441/002/EDBT.2018.14</a>"}},{"date_created":"2019-11-26T15:10:55Z","scopus_import":"1","day":"30","publication":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms","page":"2221-2239","title":"Space-optimal majority in population protocols","article_processing_charge":"No","month":"01","quality_controlled":"1","type":"conference","status":"public","year":"2018","publication_status":"published","doi":"10.1137/1.9781611975031.144","publication_identifier":{"isbn":["9781611975031"]},"_id":"7123","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1704.04947"}],"oa":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian"},{"last_name":"Aspnes","first_name":"James","full_name":"Aspnes, James"},{"last_name":"Gelashvili","first_name":"Rati","full_name":"Gelashvili, Rati"}],"oa_version":"Preprint","language":[{"iso":"eng"}],"citation":{"apa":"Alistarh, D.-A., Aspnes, J., &#38; Gelashvili, R. (2018). Space-optimal majority in population protocols. In <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i> (pp. 2221–2239). New Orleans, LA, United States: ACM. <a href=\"https://doi.org/10.1137/1.9781611975031.144\">https://doi.org/10.1137/1.9781611975031.144</a>","short":"D.-A. Alistarh, J. Aspnes, R. Gelashvili, in:, Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, 2018, pp. 2221–2239.","ama":"Alistarh D-A, Aspnes J, Gelashvili R. Space-optimal majority in population protocols. In: <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. ACM; 2018:2221-2239. doi:<a href=\"https://doi.org/10.1137/1.9781611975031.144\">10.1137/1.9781611975031.144</a>","mla":"Alistarh, Dan-Adrian, et al. “Space-Optimal Majority in Population Protocols.” <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, ACM, 2018, pp. 2221–39, doi:<a href=\"https://doi.org/10.1137/1.9781611975031.144\">10.1137/1.9781611975031.144</a>.","ista":"Alistarh D-A, Aspnes J, Gelashvili R. 2018. Space-optimal majority in population protocols. Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2221–2239.","chicago":"Alistarh, Dan-Adrian, James Aspnes, and Rati Gelashvili. “Space-Optimal Majority in Population Protocols.” In <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, 2221–39. ACM, 2018. <a href=\"https://doi.org/10.1137/1.9781611975031.144\">https://doi.org/10.1137/1.9781611975031.144</a>.","ieee":"D.-A. Alistarh, J. Aspnes, and R. Gelashvili, “Space-optimal majority in population protocols,” in <i>Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, New Orleans, LA, United States, 2018, pp. 2221–2239."},"date_published":"2018-01-30T00:00:00Z","arxiv":1,"conference":{"location":"New Orleans, LA, United States","start_date":"2018-01-07","name":"SODA: Symposium on Discrete Algorithms","end_date":"2018-01-10"},"publisher":"ACM","external_id":{"isi":["000483921200145"],"arxiv":["1704.04947"]},"isi":1,"department":[{"_id":"DaAl"}],"date_updated":"2024-10-21T06:02:41Z","abstract":[{"text":"Population protocols are a popular model of distributed computing, in which n agents with limited local state interact randomly, and cooperate to collectively compute global predicates. Inspired by recent developments in DNA programming, an extensive series of papers, across different communities, has examined the computability and complexity characteristics of this model. Majority, or consensus, is a central task in this model, in which agents need to collectively reach a decision as to which one of two states A or B had a higher initial count. Two metrics are important: the time that a protocol requires to stabilize to an output decision, and the state space size that each agent requires to do so. It is known that majority requires Ω(log log n) states per agent to allow for fast (poly-logarithmic time) stabilization, and that O(log2 n) states are sufficient. Thus, there is an exponential gap between the space upper and lower bounds for this problem. This paper addresses this question.\r\n\r\nOn the negative side, we provide a new lower bound of Ω(log n) states for any protocol which stabilizes in O(n1–c) expected time, for any constant c > 0. This result is conditional on monotonicity and output assumptions, satisfied by all known protocols. Technically, it represents a departure from previous lower bounds, in that it does not rely on the existence of dense configurations. Instead, we introduce a new generalized surgery technique to prove the existence of incorrect executions for any algorithm which would contradict the lower bound. Subsequently, our lower bound also applies to general initial configurations, including ones with a leader. On the positive side, we give a new algorithm for majority which uses O(log n) states, and stabilizes in O(log2 n) expected time. Central to the algorithm is a new leaderless phase clock technique, which allows agents to synchronize in phases of Θ(n log n) consecutive interactions using O(log n) states per agent, exploiting a new connection between population protocols and power-of-two-choices load balancing mechanisms. We also employ our phase clock to build a leader election algorithm with a state space of size O(log n), which stabilizes in O(log2 n) expected time.","lang":"eng"}]},{"quality_controlled":"1","year":"2018","file_date_updated":"2020-07-14T12:47:54Z","publication_status":"published","status":"public","type":"journal_article","_id":"723","doi":"10.1007/s00453-017-0369-2","has_accepted_license":"1","oa":1,"scopus_import":"1","ec_funded":1,"date_created":"2018-12-11T11:48:09Z","tmp":{"short":"CC BY (4.0)","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)"},"day":"01","pubrep_id":"1014","publication":"Algorithmica","intvolume":"        80","project":[{"_id":"25B1EC9E-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"618091","name":"Speed of Adaptation in Population Genetics and Evolutionary Computation"}],"page":"1604 - 1633","title":"How to escape local optima in black box optimisation when non elitism outperforms elitism","article_processing_charge":"No","month":"05","volume":80,"file":[{"access_level":"open_access","checksum":"7d92f5d7be81e387edeec4f06442791c","date_created":"2018-12-12T10:08:14Z","relation":"main_file","creator":"system","file_id":"4674","content_type":"application/pdf","date_updated":"2020-07-14T12:47:54Z","file_size":691245,"file_name":"IST-2018-1014-v1+1_2018_Paixao_Escape.pdf"}],"date_published":"2018-05-01T00:00:00Z","issue":"5","publisher":"Springer","ddc":["576"],"isi":1,"external_id":{"isi":["000428239300010"]},"date_updated":"2025-04-15T08:22:22Z","department":[{"_id":"NiBa"},{"_id":"CaGu"}],"abstract":[{"text":"Escaping local optima is one of the major obstacles to function optimisation. Using the metaphor of a fitness landscape, local optima correspond to hills separated by fitness valleys that have to be overcome. We define a class of fitness valleys of tunable difficulty by considering their length, representing the Hamming path between the two optima and their depth, the drop in fitness. For this function class we present a runtime comparison between stochastic search algorithms using different search strategies. The (1+1) EA is a simple and well-studied evolutionary algorithm that has to jump across the valley to a point of higher fitness because it does not accept worsening moves (elitism). In contrast, the Metropolis algorithm and the Strong Selection Weak Mutation (SSWM) algorithm, a famous process in population genetics, are both able to cross the fitness valley by accepting worsening moves. We show that the runtime of the (1+1) EA depends critically on the length of the valley while the runtimes of the non-elitist algorithms depend crucially on the depth of the valley. Moreover, we show that both SSWM and Metropolis can also efficiently optimise a rugged function consisting of consecutive valleys.","lang":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"first_name":"Pietro","last_name":"Oliveto","full_name":"Oliveto, Pietro"},{"id":"2C5658E6-F248-11E8-B48F-1D18A9856A87","last_name":"Paixao","first_name":"Tiago","orcid":"0000-0003-2361-3953","full_name":"Paixao, Tiago"},{"last_name":"Pérez Heredia","first_name":"Jorge","full_name":"Pérez Heredia, Jorge"},{"full_name":"Sudholt, Dirk","last_name":"Sudholt","first_name":"Dirk"},{"id":"42302D54-F248-11E8-B48F-1D18A9856A87","last_name":"Trubenova","first_name":"Barbora","orcid":"0000-0002-6873-2967","full_name":"Trubenova, Barbora"}],"language":[{"iso":"eng"}],"oa_version":"Published Version","publist_id":"6957","citation":{"mla":"Oliveto, Pietro, et al. “How to Escape Local Optima in Black Box Optimisation When Non Elitism Outperforms Elitism.” <i>Algorithmica</i>, vol. 80, no. 5, Springer, 2018, pp. 1604–33, doi:<a href=\"https://doi.org/10.1007/s00453-017-0369-2\">10.1007/s00453-017-0369-2</a>.","ista":"Oliveto P, Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. 2018. How to escape local optima in black box optimisation when non elitism outperforms elitism. Algorithmica. 80(5), 1604–1633.","ieee":"P. Oliveto, T. Paixao, J. Pérez Heredia, D. Sudholt, and B. Trubenova, “How to escape local optima in black box optimisation when non elitism outperforms elitism,” <i>Algorithmica</i>, vol. 80, no. 5. Springer, pp. 1604–1633, 2018.","chicago":"Oliveto, Pietro, Tiago Paixao, Jorge Pérez Heredia, Dirk Sudholt, and Barbora Trubenova. “How to Escape Local Optima in Black Box Optimisation When Non Elitism Outperforms Elitism.” <i>Algorithmica</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s00453-017-0369-2\">https://doi.org/10.1007/s00453-017-0369-2</a>.","short":"P. Oliveto, T. Paixao, J. Pérez Heredia, D. Sudholt, B. Trubenova, Algorithmica 80 (2018) 1604–1633.","ama":"Oliveto P, Paixao T, Pérez Heredia J, Sudholt D, Trubenova B. How to escape local optima in black box optimisation when non elitism outperforms elitism. <i>Algorithmica</i>. 2018;80(5):1604-1633. doi:<a href=\"https://doi.org/10.1007/s00453-017-0369-2\">10.1007/s00453-017-0369-2</a>","apa":"Oliveto, P., Paixao, T., Pérez Heredia, J., Sudholt, D., &#38; Trubenova, B. (2018). How to escape local optima in black box optimisation when non elitism outperforms elitism. <i>Algorithmica</i>. Springer. <a href=\"https://doi.org/10.1007/s00453-017-0369-2\">https://doi.org/10.1007/s00453-017-0369-2</a>"}},{"tmp":{"short":"CC BY (4.0)","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)"},"pubrep_id":"960","day":"01","scopus_import":"1","date_created":"2018-12-11T11:48:14Z","ec_funded":1,"publication":"Real-Time Systems","title":"Automated competitive analysis of real time scheduling with graph games","page":"166 - 207","intvolume":"        54","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"name":"Microsoft Research Faculty Fellowship","_id":"2587B514-B435-11E9-9278-68D0E5697425"}],"volume":54,"file":[{"access_level":"open_access","date_created":"2018-12-12T10:17:14Z","checksum":"c2590ef160709d8054cf29ee173f1454","creator":"system","file_id":"5267","relation":"main_file","content_type":"application/pdf","date_updated":"2020-07-14T12:47:56Z","file_size":1163507,"file_name":"IST-2018-960-v1+1_2017_Chatterjee_Automated_competetive.pdf"}],"article_processing_charge":"No","month":"01","year":"2018","file_date_updated":"2020-07-14T12:47:56Z","publication_status":"published","type":"journal_article","status":"public","quality_controlled":"1","_id":"738","doi":"10.1007/s11241-017-9293-4","oa":1,"has_accepted_license":"1","corr_author":"1","author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722","first_name":"Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Kößler, Alexander","first_name":"Alexander","last_name":"Kößler"},{"full_name":"Schmid, Ulrich","last_name":"Schmid","first_name":"Ulrich"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","language":[{"iso":"eng"}],"oa_version":"Published Version","citation":{"ista":"Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. 2018. Automated competitive analysis of real time scheduling with graph games. Real-Time Systems. 54(1), 166–207.","mla":"Chatterjee, Krishnendu, et al. “Automated Competitive Analysis of Real Time Scheduling with Graph Games.” <i>Real-Time Systems</i>, vol. 54, no. 1, Springer, 2018, pp. 166–207, doi:<a href=\"https://doi.org/10.1007/s11241-017-9293-4\">10.1007/s11241-017-9293-4</a>.","ieee":"K. Chatterjee, A. Pavlogiannis, A. Kößler, and U. Schmid, “Automated competitive analysis of real time scheduling with graph games,” <i>Real-Time Systems</i>, vol. 54, no. 1. Springer, pp. 166–207, 2018.","chicago":"Chatterjee, Krishnendu, Andreas Pavlogiannis, Alexander Kößler, and Ulrich Schmid. “Automated Competitive Analysis of Real Time Scheduling with Graph Games.” <i>Real-Time Systems</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s11241-017-9293-4\">https://doi.org/10.1007/s11241-017-9293-4</a>.","ama":"Chatterjee K, Pavlogiannis A, Kößler A, Schmid U. Automated competitive analysis of real time scheduling with graph games. <i>Real-Time Systems</i>. 2018;54(1):166-207. doi:<a href=\"https://doi.org/10.1007/s11241-017-9293-4\">10.1007/s11241-017-9293-4</a>","short":"K. Chatterjee, A. Pavlogiannis, A. Kößler, U. Schmid, Real-Time Systems 54 (2018) 166–207.","apa":"Chatterjee, K., Pavlogiannis, A., Kößler, A., &#38; Schmid, U. (2018). Automated competitive analysis of real time scheduling with graph games. <i>Real-Time Systems</i>. Springer. <a href=\"https://doi.org/10.1007/s11241-017-9293-4\">https://doi.org/10.1007/s11241-017-9293-4</a>"},"publist_id":"6929","date_published":"2018-01-01T00:00:00Z","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"2820"}]},"publisher":"Springer","issue":"1","ddc":["000"],"external_id":{"isi":["000419955500006"]},"isi":1,"abstract":[{"lang":"eng","text":"This paper is devoted to automatic competitive analysis of real-time scheduling algorithms for firm-deadline tasksets, where only completed tasks con- tribute some utility to the system. Given such a taskset T , the competitive ratio of an on-line scheduling algorithm A for T is the worst-case utility ratio of A over the utility achieved by a clairvoyant algorithm. We leverage the theory of quantitative graph games to address the competitive analysis and competitive synthesis problems. For the competitive analysis case, given any taskset T and any finite-memory on- line scheduling algorithm A , we show that the competitive ratio of A in T can be computed in polynomial time in the size of the state space of A . Our approach is flexible as it also provides ways to model meaningful constraints on the released task sequences that determine the competitive ratio. We provide an experimental study of many well-known on-line scheduling algorithms, which demonstrates the feasibility of our competitive analysis approach that effectively replaces human ingenuity (required Preliminary versions of this paper have appeared in Chatterjee et al. ( 2013 , 2014 ). B Andreas Pavlogiannis pavlogiannis@ist.ac.at Krishnendu Chatterjee krish.chat@ist.ac.at Alexander Kößler koe@ecs.tuwien.ac.at Ulrich Schmid s@ecs.tuwien.ac.at 1 IST Austria (Institute of Science and Technology Austria), Am Campus 1, 3400 Klosterneuburg, Austria 2 Embedded Computing Systems Group, Vienna University of Technology, Treitlstrasse 3, 1040 Vienna, Austria 123 Real-Time Syst for finding worst-case scenarios) by computing power. For the competitive synthesis case, we are just given a taskset T , and the goal is to automatically synthesize an opti- mal on-line scheduling algorithm A , i.e., one that guarantees the largest competitive ratio possible for T . We show how the competitive synthesis problem can be reduced to a two-player graph game with partial information, and establish that the compu- tational complexity of solving this game is Np -complete. The competitive synthesis problem is hence in Np in the size of the state space of the non-deterministic labeled transition system encoding the taskset. Overall, the proposed framework assists in the selection of suitable scheduling algorithms for a given taskset, which is in fact the most common situation in real-time systems design. "}],"date_updated":"2025-04-15T08:12:27Z","department":[{"_id":"KrCh"}]},{"_id":"7407","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2018/194"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-095-8"]},"doi":"10.4230/LIPICS.ITCS.2019.59","has_accepted_license":"1","oa":1,"quality_controlled":"1","publication_status":"published","year":"2018","file_date_updated":"2020-07-14T12:47:57Z","status":"public","type":"conference","alternative_title":["LIPIcs"],"intvolume":"       124","project":[{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020"}],"page":"59:1-59:25","title":"Proofs of catalytic space","month":"12","article_processing_charge":"No","volume":124,"file":[{"file_name":"2018_LIPIcs_Pietrzak.pdf","file_size":822884,"date_updated":"2020-07-14T12:47:57Z","content_type":"application/pdf","file_id":"7443","creator":"dernst","relation":"main_file","checksum":"5cebb7f7849a3beda898f697d755dd96","date_created":"2020-02-04T08:17:52Z","access_level":"open_access"}],"scopus_import":"1","date_created":"2020-01-30T09:16:05Z","ec_funded":1,"tmp":{"short":"CC BY (4.0)","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)"},"day":"31","publication":"10th Innovations in Theoretical Computer Science Conference","ddc":["000"],"date_updated":"2025-07-03T11:55:28Z","department":[{"_id":"KrPi"}],"abstract":[{"text":"Proofs of space (PoS) [Dziembowski et al., CRYPTO'15] are proof systems where a prover can convince a verifier that he \"wastes\" disk space. PoS were introduced as a more ecological and economical replacement for proofs of work which are currently used to secure blockchains like Bitcoin. In this work we investigate extensions of PoS which allow the prover to embed useful data into the dedicated space, which later can be recovered. Our first contribution is a security proof for the original PoS from CRYPTO'15 in the random oracle model (the original proof only applied to a restricted class of adversaries which can store a subset of the data an honest prover would store). When this PoS is instantiated with recent constructions of maximally depth robust graphs, our proof implies basically optimal security. As a second contribution we show three different extensions of this PoS where useful data can be embedded into the space required by the prover. Our security proof for the PoS extends (non-trivially) to these constructions. We discuss how some of these variants can be used as proofs of catalytic space (PoCS), a notion we put forward in this work, and which basically is a PoS where most of the space required by the prover can be used to backup useful data. Finally we discuss how one of the extensions is a candidate construction for a proof of replication (PoR), a proof system recently suggested in the Filecoin whitepaper. ","lang":"eng"}],"date_published":"2018-12-31T00:00:00Z","conference":{"name":"ITCS: Innovations in Theoretical Computer Science","end_date":"2019-01-12","location":"San Diego, CA, United States","start_date":"2019-01-10"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","language":[{"iso":"eng"}],"oa_version":"Published Version","citation":{"apa":"Pietrzak, K. Z. (2018). Proofs of catalytic space. In <i>10th Innovations in Theoretical Computer Science Conference</i> (Vol. 124, p. 59:1-59:25). San Diego, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.59\">https://doi.org/10.4230/LIPICS.ITCS.2019.59</a>","short":"K.Z. Pietrzak, in:, 10th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25.","ama":"Pietrzak KZ. Proofs of catalytic space. In: <i>10th Innovations in Theoretical Computer Science Conference</i>. Vol 124. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2018:59:1-59:25. doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.59\">10.4230/LIPICS.ITCS.2019.59</a>","ista":"Pietrzak KZ. 2018. Proofs of catalytic space. 10th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 124, 59:1-59:25.","mla":"Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” <i>10th Innovations in Theoretical Computer Science Conference</i>, vol. 124, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, p. 59:1-59:25, doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.59\">10.4230/LIPICS.ITCS.2019.59</a>.","chicago":"Pietrzak, Krzysztof Z. “Proofs of Catalytic Space.” In <i>10th Innovations in Theoretical Computer Science Conference</i>, 124:59:1-59:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2019.59\">https://doi.org/10.4230/LIPICS.ITCS.2019.59</a>.","ieee":"K. Z. Pietrzak, “Proofs of catalytic space,” in <i>10th Innovations in Theoretical Computer Science Conference</i>, San Diego, CA, United States, 2018, vol. 124, p. 59:1-59:25."},"corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}]},{"has_accepted_license":"1","oa":1,"doi":"10.1007/s10711-017-0291-4","_id":"742","quality_controlled":"1","status":"public","type":"journal_article","file_date_updated":"2020-07-14T12:47:58Z","publication_status":"published","year":"2018","article_processing_charge":"Yes (via OA deal)","month":"08","file":[{"file_name":"s10711-017-0291-4.pdf","file_size":412486,"date_updated":"2020-07-14T12:47:58Z","content_type":"application/pdf","relation":"main_file","file_id":"5835","creator":"kschuh","checksum":"d2f70fc132156504aa4c626aa378a7ab","date_created":"2019-01-15T13:44:05Z","access_level":"open_access"}],"volume":195,"project":[{"grant_number":"PP00P2_138948","name":"Embeddings in Higher Dimensions: Algorithms and Combinatorics","_id":"25FA3206-B435-11E9-9278-68D0E5697425"}],"intvolume":"       195","page":"307–317","title":"On expansion and topological overlap","publication":"Geometriae Dedicata","date_created":"2018-12-11T11:48:16Z","scopus_import":"1","day":"01","pubrep_id":"912","tmp":{"short":"CC BY (4.0)","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)"},"department":[{"_id":"UlWa"}],"date_updated":"2025-06-03T11:41:00Z","abstract":[{"lang":"eng","text":"We give a detailed and easily accessible proof of Gromov’s Topological Overlap Theorem. Let X be a finite simplicial complex or, more generally, a finite polyhedral cell complex of dimension d. Informally, the theorem states that if X has sufficiently strong higher-dimensional expansion properties (which generalize edge expansion of graphs and are defined in terms of cellular cochains of X) then X has the following topological overlap property: for every continuous map (Formula presented.) there exists a point (Formula presented.) that is contained in the images of a positive fraction (Formula presented.) of the d-cells of X. More generally, the conclusion holds if (Formula presented.) is replaced by any d-dimensional piecewise-linear manifold M, with a constant (Formula presented.) that depends only on d and on the expansion properties of X, but not on M."}],"external_id":{"isi":["000437122700017"]},"isi":1,"ddc":["514","516"],"issue":"1","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"1378"}]},"publisher":"Springer","date_published":"2018-08-01T00:00:00Z","publist_id":"6925","citation":{"ista":"Dotterrer D, Kaufman T, Wagner U. 2018. On expansion and topological overlap. Geometriae Dedicata. 195(1), 307–317.","mla":"Dotterrer, Dominic, et al. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>, vol. 195, no. 1, Springer, 2018, pp. 307–317, doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>.","ieee":"D. Dotterrer, T. Kaufman, and U. Wagner, “On expansion and topological overlap,” <i>Geometriae Dedicata</i>, vol. 195, no. 1. Springer, pp. 307–317, 2018.","chicago":"Dotterrer, Dominic, Tali Kaufman, and Uli Wagner. “On Expansion and Topological Overlap.” <i>Geometriae Dedicata</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>.","short":"D. Dotterrer, T. Kaufman, U. Wagner, Geometriae Dedicata 195 (2018) 307–317.","ama":"Dotterrer D, Kaufman T, Wagner U. On expansion and topological overlap. <i>Geometriae Dedicata</i>. 2018;195(1):307–317. doi:<a href=\"https://doi.org/10.1007/s10711-017-0291-4\">10.1007/s10711-017-0291-4</a>","apa":"Dotterrer, D., Kaufman, T., &#38; Wagner, U. (2018). On expansion and topological overlap. <i>Geometriae Dedicata</i>. Springer. <a href=\"https://doi.org/10.1007/s10711-017-0291-4\">https://doi.org/10.1007/s10711-017-0291-4</a>"},"oa_version":"Published Version","language":[{"iso":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"full_name":"Dotterrer, Dominic","first_name":"Dominic","last_name":"Dotterrer"},{"first_name":"Tali","last_name":"Kaufman","full_name":"Kaufman, Tali"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"corr_author":"1"},{"project":[{"call_identifier":"H2020","grant_number":"716117","name":"Optimal Transport and Stochastic Dynamics","_id":"256E75B8-B435-11E9-9278-68D0E5697425"}],"oa_version":"Preprint","language":[{"iso":"eng"}],"title":"Convex fair partitions into arbitrary number of pieces","article_processing_charge":"No","month":"09","citation":{"apa":"Akopyan, A., Avvakumov, S., &#38; Karasev, R. (2018). Convex fair partitions into arbitrary number of pieces. arXiv. <a href=\"https://doi.org/10.48550/arXiv.1804.03057\">https://doi.org/10.48550/arXiv.1804.03057</a>","ama":"Akopyan A, Avvakumov S, Karasev R. Convex fair partitions into arbitrary number of pieces. 2018. doi:<a href=\"https://doi.org/10.48550/arXiv.1804.03057\">10.48550/arXiv.1804.03057</a>","short":"A. Akopyan, S. Avvakumov, R. Karasev, (2018).","ista":"Akopyan A, Avvakumov S, Karasev R. 2018. Convex fair partitions into arbitrary number of pieces. 1804.03057.","mla":"Akopyan, Arseniy, et al. <i>Convex Fair Partitions into Arbitrary Number of Pieces</i>. 1804.03057, arXiv, 2018, doi:<a href=\"https://doi.org/10.48550/arXiv.1804.03057\">10.48550/arXiv.1804.03057</a>.","chicago":"Akopyan, Arseniy, Sergey Avvakumov, and Roman Karasev. “Convex Fair Partitions into Arbitrary Number of Pieces.” arXiv, 2018. <a href=\"https://doi.org/10.48550/arXiv.1804.03057\">https://doi.org/10.48550/arXiv.1804.03057</a>.","ieee":"A. Akopyan, S. Avvakumov, and R. Karasev, “Convex fair partitions into arbitrary number of pieces.” arXiv, 2018."},"date_created":"2018-12-11T11:44:30Z","ec_funded":1,"corr_author":"1","day":"13","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Akopyan","first_name":"Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2548-617X","full_name":"Akopyan, Arseniy"},{"orcid":"0000-0002-7840-5062","full_name":"Avvakumov, Sergey","first_name":"Sergey","last_name":"Avvakumov","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Karasev","first_name":"Roman","full_name":"Karasev, Roman"}],"doi":"10.48550/arXiv.1804.03057","main_file_link":[{"url":"https://arxiv.org/abs/1804.03057","open_access":"1"}],"_id":"75","external_id":{"arxiv":["1804.03057"]},"article_number":"1804.03057","department":[{"_id":"HeEd"},{"_id":"JaMa"}],"date_updated":"2026-04-08T07:25:54Z","oa":1,"abstract":[{"text":"We prove that any convex body in the plane can be partitioned into m convex parts of equal areas and perimeters for any integer m≥2; this result was previously known for prime powers m=pk. We also give a higher-dimensional generalization.","lang":"eng"}],"date_published":"2018-09-13T00:00:00Z","status":"public","type":"preprint","arxiv":1,"year":"2018","publication_status":"published","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"8156"}]},"publisher":"arXiv"},{"quality_controlled":"1","file_date_updated":"2021-08-16T07:37:28Z","year":"2018","publication_status":"published","type":"journal_article","status":"public","has_accepted_license":"1","article_type":"letter_note","oa":1,"_id":"9915","doi":"10.1002/evl3.85","publication_identifier":{"eissn":["2056-3744"],"issn":[" 2056-3744"]},"publication":"Evolution Letters","scopus_import":"1","date_created":"2021-08-16T07:30:00Z","acknowledgement":"The authors express a special thanks to Dr Richard Willan at the Museum and Art Gallery of the Northern Territory for guidance and support in the field, and to Carole Smadja for reading and commenting on the manuscript. The authors thank the Government of Western Australia Department of Parks and Wildlife (license no. 009254) and Fishery Research Division (exemption no. 2262) for assistance with permits. Khalid Belkhir modified the coalescent sampler msnsam for the specific needs of this project and Martin Hirsch helped to set up the ABC pipeline and to modify the summary statistic calculator mscalc. The authors are grateful to the Crafoord Foundation for supporting this project. R.K.B., A.M.W., and L.D. were supported by grants from the Natural Environment Research Council, R.K.B. and A.M.W. were also supported by the European Research Council and R.K.B. and L.D. by the Leverhulme Trust. M.M.R. was supported by Consejo Nacional de Ciencia y Tecnología and Secretaría de Educación Pública, Mexico. G.B. was supported by the Centre for Animal Movement Research (CAnMove) financed by a Linnaeus grant (No. 349-2007-8690) from the Swedish Research Council and Lund University.","tmp":{"short":"CC BY (4.0)","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)"},"pmid":1,"day":"13","month":"12","article_processing_charge":"Yes","volume":2,"file":[{"file_name":"2018_EvolutionLetters_Hollander.pdf","file_size":584606,"date_updated":"2021-08-16T07:37:28Z","content_type":"application/pdf","relation":"main_file","file_id":"9916","creator":"asandaue","date_created":"2021-08-16T07:37:28Z","checksum":"997a78ac41c809975ca69cbdea441f88","access_level":"open_access","success":1}],"intvolume":"         2","title":"Are assortative mating and genital divergence driven by reinforcement?","page":"557-566","issue":"6","related_material":{"record":[{"id":"9929","relation":"research_data","status":"public"}]},"publisher":"Wiley","date_published":"2018-12-13T00:00:00Z","date_updated":"2024-10-21T06:02:42Z","department":[{"_id":"BeVi"}],"abstract":[{"lang":"eng","text":"The evolution of assortative mating is a key part of the speciation process. Stronger assortment, or greater divergence in mating traits, between species pairs with overlapping ranges is commonly observed, but possible causes of this pattern of reproductive character displacement are difficult to distinguish. We use a multidisciplinary approach to provide a rare example where it is possible to distinguish among hypotheses concerning the evolution of reproductive character displacement. We build on an earlier comparative analysis that illustrated a strong pattern of greater divergence in penis form between pairs of sister species with overlapping ranges than between allopatric sister-species pairs, in a large clade of marine gastropods (Littorinidae). We investigate both assortative mating and divergence in male genitalia in one of the sister-species pairs, discriminating among three contrasting processes each of which can generate a pattern of reproductive character displacement: reinforcement, reproductive interference and the Templeton effect. We demonstrate reproductive character displacement in assortative mating, but not in genital form between this pair of sister species and use demographic models to distinguish among the different processes. Our results support a model with no gene flow since secondary contact and thus favor reproductive interference as the cause of reproductive character displacement for mate choice, rather than reinforcement. High gene flow within species argues against the Templeton effect. Secondary contact appears to have had little impact on genital divergence."}],"ddc":["570"],"external_id":{"pmid":["30564439"],"isi":["000452990000002"]},"isi":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"full_name":"Hollander, Johan","last_name":"Hollander","first_name":"Johan"},{"full_name":"Montaño-Rendón, Mauricio","last_name":"Montaño-Rendón","first_name":"Mauricio"},{"last_name":"Bianco","first_name":"Giuseppe","full_name":"Bianco, Giuseppe"},{"first_name":"Xi","last_name":"Yang","full_name":"Yang, Xi"},{"last_name":"Westram","first_name":"Anja M","id":"3C147470-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1050-4969","full_name":"Westram, Anja M"},{"full_name":"Duvaux, Ludovic","last_name":"Duvaux","first_name":"Ludovic"},{"full_name":"Reid, David G.","first_name":"David G.","last_name":"Reid"},{"first_name":"Roger K.","last_name":"Butlin","full_name":"Butlin, Roger K."}],"citation":{"apa":"Hollander, J., Montaño-Rendón, M., Bianco, G., Yang, X., Westram, A. M., Duvaux, L., … Butlin, R. K. (2018). Are assortative mating and genital divergence driven by reinforcement? <i>Evolution Letters</i>. Wiley. <a href=\"https://doi.org/10.1002/evl3.85\">https://doi.org/10.1002/evl3.85</a>","short":"J. Hollander, M. Montaño-Rendón, G. Bianco, X. Yang, A.M. Westram, L. Duvaux, D.G. Reid, R.K. Butlin, Evolution Letters 2 (2018) 557–566.","ama":"Hollander J, Montaño-Rendón M, Bianco G, et al. Are assortative mating and genital divergence driven by reinforcement? <i>Evolution Letters</i>. 2018;2(6):557-566. doi:<a href=\"https://doi.org/10.1002/evl3.85\">10.1002/evl3.85</a>","chicago":"Hollander, Johan, Mauricio Montaño-Rendón, Giuseppe Bianco, Xi Yang, Anja M Westram, Ludovic Duvaux, David G. Reid, and Roger K. Butlin. “Are Assortative Mating and Genital Divergence Driven by Reinforcement?” <i>Evolution Letters</i>. Wiley, 2018. <a href=\"https://doi.org/10.1002/evl3.85\">https://doi.org/10.1002/evl3.85</a>.","ieee":"J. Hollander <i>et al.</i>, “Are assortative mating and genital divergence driven by reinforcement?,” <i>Evolution Letters</i>, vol. 2, no. 6. Wiley, pp. 557–566, 2018.","ista":"Hollander J, Montaño-Rendón M, Bianco G, Yang X, Westram AM, Duvaux L, Reid DG, Butlin RK. 2018. Are assortative mating and genital divergence driven by reinforcement? Evolution Letters. 2(6), 557–566.","mla":"Hollander, Johan, et al. “Are Assortative Mating and Genital Divergence Driven by Reinforcement?” <i>Evolution Letters</i>, vol. 2, no. 6, Wiley, 2018, pp. 557–66, doi:<a href=\"https://doi.org/10.1002/evl3.85\">10.1002/evl3.85</a>."},"language":[{"iso":"eng"}],"oa_version":"Published Version"},{"date_published":"2018-08-20T00:00:00Z","issue":"4","related_material":{"record":[{"id":"9930","relation":"research_data","status":"public"}]},"publisher":"Wiley","ddc":["570"],"external_id":{"pmid":["30283683"],"isi":["000446774400004"]},"isi":1,"date_updated":"2024-10-21T06:02:42Z","department":[{"_id":"BeVi"}],"abstract":[{"text":"Adaptive divergence and speciation may happen despite opposition by gene flow. Identifying the genomic basis underlying divergence with gene flow is a major task in evolutionary genomics. Most approaches (e.g., outlier scans) focus on genomic regions of high differentiation. However, not all genomic architectures potentially underlying divergence are expected to show extreme differentiation. Here, we develop an approach that combines hybrid zone analysis (i.e., focuses on spatial patterns of allele frequency change) with system-specific simulations to identify loci inconsistent with neutral evolution. We apply this to a genome-wide SNP set from an ideally suited study organism, the intertidal snail Littorina saxatilis, which shows primary divergence between ecotypes associated with different shore habitats. We detect many SNPs with clinal patterns, most of which are consistent with neutrality. Among non-neutral SNPs, most are located within three large putative inversions differentiating ecotypes. Many non-neutral SNPs show relatively low levels of differentiation. We discuss potential reasons for this pattern, including loose linkage to selected variants, polygenic adaptation and a component of balancing selection within populations (which may be expected for inversions). Our work is in line with theory predicting a role for inversions in divergence, and emphasizes that genomic regions contributing to divergence may not always be accessible with methods purely based on allele frequency differences. These conclusions call for approaches that take spatial patterns of allele frequency change into account in other systems.","lang":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"full_name":"Westram, Anja M","orcid":"0000-0003-1050-4969","last_name":"Westram","first_name":"Anja M","id":"3C147470-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Rafajlović, Marina","first_name":"Marina","last_name":"Rafajlović"},{"last_name":"Chaube","first_name":"Pragya","full_name":"Chaube, Pragya"},{"full_name":"Faria, Rui","first_name":"Rui","last_name":"Faria"},{"full_name":"Larsson, Tomas","first_name":"Tomas","last_name":"Larsson"},{"last_name":"Panova","first_name":"Marina","full_name":"Panova, Marina"},{"full_name":"Ravinet, Mark","last_name":"Ravinet","first_name":"Mark"},{"full_name":"Blomberg, Anders","first_name":"Anders","last_name":"Blomberg"},{"first_name":"Bernhard","last_name":"Mehlig","full_name":"Mehlig, Bernhard"},{"last_name":"Johannesson","first_name":"Kerstin","full_name":"Johannesson, Kerstin"},{"full_name":"Butlin, Roger","last_name":"Butlin","first_name":"Roger"}],"language":[{"iso":"eng"}],"oa_version":"Published Version","citation":{"short":"A.M. Westram, M. Rafajlović, P. Chaube, R. Faria, T. Larsson, M. Panova, M. Ravinet, A. Blomberg, B. Mehlig, K. Johannesson, R. Butlin, Evolution Letters 2 (2018) 297–309.","ama":"Westram AM, Rafajlović M, Chaube P, et al. Clines on the seashore: The genomic architecture underlying rapid divergence in the face of gene flow. <i>Evolution Letters</i>. 2018;2(4):297-309. doi:<a href=\"https://doi.org/10.1002/evl3.74\">10.1002/evl3.74</a>","apa":"Westram, A. M., Rafajlović, M., Chaube, P., Faria, R., Larsson, T., Panova, M., … Butlin, R. (2018). Clines on the seashore: The genomic architecture underlying rapid divergence in the face of gene flow. <i>Evolution Letters</i>. Wiley. <a href=\"https://doi.org/10.1002/evl3.74\">https://doi.org/10.1002/evl3.74</a>","mla":"Westram, Anja M., et al. “Clines on the Seashore: The Genomic Architecture Underlying Rapid Divergence in the Face of Gene Flow.” <i>Evolution Letters</i>, vol. 2, no. 4, Wiley, 2018, pp. 297–309, doi:<a href=\"https://doi.org/10.1002/evl3.74\">10.1002/evl3.74</a>.","ista":"Westram AM, Rafajlović M, Chaube P, Faria R, Larsson T, Panova M, Ravinet M, Blomberg A, Mehlig B, Johannesson K, Butlin R. 2018. Clines on the seashore: The genomic architecture underlying rapid divergence in the face of gene flow. Evolution Letters. 2(4), 297–309.","ieee":"A. M. Westram <i>et al.</i>, “Clines on the seashore: The genomic architecture underlying rapid divergence in the face of gene flow,” <i>Evolution Letters</i>, vol. 2, no. 4. Wiley, pp. 297–309, 2018.","chicago":"Westram, Anja M, Marina Rafajlović, Pragya Chaube, Rui Faria, Tomas Larsson, Marina Panova, Mark Ravinet, et al. “Clines on the Seashore: The Genomic Architecture Underlying Rapid Divergence in the Face of Gene Flow.” <i>Evolution Letters</i>. Wiley, 2018. <a href=\"https://doi.org/10.1002/evl3.74\">https://doi.org/10.1002/evl3.74</a>."},"quality_controlled":"1","year":"2018","file_date_updated":"2021-08-16T07:48:03Z","publication_status":"published","type":"journal_article","status":"public","_id":"9917","publication_identifier":{"eissn":["2056-3744"],"issn":["2056-3744"]},"doi":"10.1002/evl3.74","has_accepted_license":"1","article_type":"letter_note","oa":1,"scopus_import":"1","acknowledgement":"We are very grateful to people who helped with fieldwork, snail processing, and DNA extractions, particularly Laura Brettell, Mårten Duvetorp, Juan Galindo, Anne-Lise Liabot and Irena Senčić. We would also like to thank Magnus Alm Rosenblad and Mats Töpel for their contribution to assembling the Littorina saxatilis genome, Carl André, Pasi Rastas, and Romain Villoutreix for discussion, and two anonymous reviewers for their helpful comments on the manuscript. We are grateful to RapidGenomics for library preparation and sequencing. We thank the Natural Environment Research Council, the European Research Council and the Swedish Research Councils VR and Formas (Linnaeus grant to the Centre for Marine Evolutionary Biology and Tage Erlander Guest Professorship) for funding. P.C. was funded by the University of Sheffield Vice-chancellor's India scholarship. R.F. is funded by the European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement no. 706376. M. Raf. was supported by the Adlerbert Research Foundation.","date_created":"2021-08-16T07:45:38Z","tmp":{"short":"CC BY (4.0)","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)"},"pmid":1,"day":"20","publication":"Evolution Letters","intvolume":"         2","page":"297-309","title":"Clines on the seashore: The genomic architecture underlying rapid divergence in the face of gene flow","article_processing_charge":"Yes","month":"08","volume":2,"file":[{"content_type":"application/pdf","date_updated":"2021-08-16T07:48:03Z","file_size":764299,"file_name":"2018_EvolutionLetters_Westram.pdf","success":1,"access_level":"open_access","date_created":"2021-08-16T07:48:03Z","checksum":"8524e72507d521416be3f8ccfcd5e3f5","file_id":"9918","creator":"asandaue","relation":"main_file"}]},{"doi":"10.5061/dryad.51sd2p5","_id":"9929","main_file_link":[{"open_access":"1","url":"https://doi.org/10.5061/dryad.51sd2p5"}],"oa":1,"abstract":[{"text":"The evolution of assortative mating is a key part of the speciation process. Stronger assortment, or greater divergence in mating traits, between species pairs with overlapping ranges is commonly observed, but possible causes of this pattern of reproductive character displacement are difficult to distinguish. We use a multidisciplinary approach to provide a rare example where it is possible to distinguish among hypotheses concerning the evolution of reproductive character displacement. We build on an earlier comparative analysis that illustrated a strong pattern of greater divergence in penis form between pairs of sister species with overlapping ranges than between allopatric sister-species pairs, in a large clade of marine gastropods (Littorinidae). We investigate both assortative mating and divergence in male genitalia in one of the sister-species pairs, discriminating among three contrasting processes each of which can generate a pattern of reproductive character displacement: reinforcement, reproductive interference and the Templeton effect. We demonstrate reproductive character displacement in assortative mating, but not in genital form between this pair of sister species and use demographic models to distinguish among the different processes. Our results support a model with no gene flow since secondary contact and thus favour reproductive interference as the cause of reproductive character displacement for mate choice, rather than reinforcement. High gene flow within species argues against the Templeton effect. Secondary contact appears to have had little impact on genital divergence.","lang":"eng"}],"department":[{"_id":"BeVi"}],"date_updated":"2024-10-21T06:02:42Z","type":"research_data_reference","status":"public","year":"2018","date_published":"2018-10-17T00:00:00Z","related_material":{"record":[{"id":"9915","status":"public","relation":"used_in_publication"}]},"publisher":"Dryad","oa_version":"Published Version","title":"Data from: Are assortative mating and genital divergence driven by reinforcement?","citation":{"ista":"Hollander J, Montaño-Rendón M, Bianco G, Yang X, Westram AM, Duvaux L, Reid DG, Butlin RK. 2018. Data from: Are assortative mating and genital divergence driven by reinforcement?, Dryad, <a href=\"https://doi.org/10.5061/dryad.51sd2p5\">10.5061/dryad.51sd2p5</a>.","mla":"Hollander, Johan, et al. <i>Data from: Are Assortative Mating and Genital Divergence Driven by Reinforcement?</i> Dryad, 2018, doi:<a href=\"https://doi.org/10.5061/dryad.51sd2p5\">10.5061/dryad.51sd2p5</a>.","chicago":"Hollander, Johan, Mauricio Montaño-Rendón, Giuseppe Bianco, Xi Yang, Anja M Westram, Ludovic Duvaux, David G. Reid, and Roger K. Butlin. “Data from: Are Assortative Mating and Genital Divergence Driven by Reinforcement?” Dryad, 2018. <a href=\"https://doi.org/10.5061/dryad.51sd2p5\">https://doi.org/10.5061/dryad.51sd2p5</a>.","ieee":"J. Hollander <i>et al.</i>, “Data from: Are assortative mating and genital divergence driven by reinforcement?” Dryad, 2018.","apa":"Hollander, J., Montaño-Rendón, M., Bianco, G., Yang, X., Westram, A. M., Duvaux, L., … Butlin, R. K. (2018). Data from: Are assortative mating and genital divergence driven by reinforcement? Dryad. <a href=\"https://doi.org/10.5061/dryad.51sd2p5\">https://doi.org/10.5061/dryad.51sd2p5</a>","short":"J. Hollander, M. Montaño-Rendón, G. Bianco, X. Yang, A.M. Westram, L. Duvaux, D.G. Reid, R.K. Butlin, (2018).","ama":"Hollander J, Montaño-Rendón M, Bianco G, et al. Data from: Are assortative mating and genital divergence driven by reinforcement? 2018. doi:<a href=\"https://doi.org/10.5061/dryad.51sd2p5\">10.5061/dryad.51sd2p5</a>"},"article_processing_charge":"No","month":"10","day":"17","date_created":"2021-08-17T08:51:06Z","author":[{"full_name":"Hollander, Johan","first_name":"Johan","last_name":"Hollander"},{"full_name":"Montaño-Rendón, Mauricio","last_name":"Montaño-Rendón","first_name":"Mauricio"},{"last_name":"Bianco","first_name":"Giuseppe","full_name":"Bianco, Giuseppe"},{"full_name":"Yang, Xi","last_name":"Yang","first_name":"Xi"},{"id":"3C147470-F248-11E8-B48F-1D18A9856A87","first_name":"Anja M","last_name":"Westram","full_name":"Westram, Anja M","orcid":"0000-0003-1050-4969"},{"full_name":"Duvaux, Ludovic","first_name":"Ludovic","last_name":"Duvaux"},{"full_name":"Reid, David G.","last_name":"Reid","first_name":"David G."},{"full_name":"Butlin, Roger K.","last_name":"Butlin","first_name":"Roger K."}],"user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf"},{"date_published":"2018-07-23T00:00:00Z","year":"2018","status":"public","type":"research_data_reference","related_material":{"record":[{"relation":"used_in_publication","status":"public","id":"9917"}]},"publisher":"Dryad","_id":"9930","main_file_link":[{"url":"https://doi.org/10.5061/dryad.bp25b65","open_access":"1"}],"doi":"10.5061/dryad.bp25b65","date_updated":"2024-10-21T06:02:42Z","department":[{"_id":"BeVi"}],"abstract":[{"lang":"eng","text":"Adaptive divergence and speciation may happen despite opposition by gene flow. Identifying the genomic basis underlying divergence with gene flow is a major task in evolutionary genomics. Most approaches (e.g. outlier scans) focus on genomic regions of high differentiation. However, not all genomic architectures potentially underlying divergence are expected to show extreme differentiation. Here, we develop an approach that combines hybrid zone analysis (i.e. focuses on spatial patterns of allele frequency change) with system-specific simulations to identify loci inconsistent with neutral evolution. We apply this to a genome-wide SNP set from an ideally-suited study organism, the intertidal snail Littorina saxatilis, which shows primary divergence between ecotypes associated with different shore habitats. We detect many SNPs with clinal patterns, most of which are consistent with neutrality. Among non-neutral SNPs, most are located within three large putative inversions differentiating ecotypes. Many non-neutral SNPs show relatively low levels of differentiation. We discuss potential reasons for this pattern, including loose linkage to selected variants, polygenic adaptation and a component of balancing selection within populations (which may be expected for inversions). Our work is in line with theory predicting a role for inversions in divergence, and emphasises that genomic regions contributing to divergence may not always be accessible with methods purely based on allele frequency differences. These conclusions call for approaches that take spatial patterns of allele frequency change into account in other systems."}],"oa":1,"date_created":"2021-08-17T08:58:47Z","day":"23","user_id":"6785fbc1-c503-11eb-8a32-93094b40e1cf","author":[{"full_name":"Westram, Anja M","orcid":"0000-0003-1050-4969","first_name":"Anja M","last_name":"Westram","id":"3C147470-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Rafajlović, Marina","first_name":"Marina","last_name":"Rafajlović"},{"full_name":"Chaube, Pragya","last_name":"Chaube","first_name":"Pragya"},{"full_name":"Faria, Rui","last_name":"Faria","first_name":"Rui"},{"last_name":"Larsson","first_name":"Tomas","full_name":"Larsson, Tomas"},{"full_name":"Panova, Marina","last_name":"Panova","first_name":"Marina"},{"first_name":"Mark","last_name":"Ravinet","full_name":"Ravinet, Mark"},{"first_name":"Anders","last_name":"Blomberg","full_name":"Blomberg, Anders"},{"full_name":"Mehlig, Bernhard","first_name":"Bernhard","last_name":"Mehlig"},{"last_name":"Johannesson","first_name":"Kerstin","full_name":"Johannesson, Kerstin"},{"full_name":"Butlin, Roger","last_name":"Butlin","first_name":"Roger"}],"title":"Data from: Clines on the seashore: the genomic architecture underlying rapid divergence in the face of gene flow","oa_version":"Published Version","article_processing_charge":"No","month":"07","citation":{"apa":"Westram, A. M., Rafajlović, M., Chaube, P., Faria, R., Larsson, T., Panova, M., … Butlin, R. (2018). Data from: Clines on the seashore: the genomic architecture underlying rapid divergence in the face of gene flow. Dryad. <a href=\"https://doi.org/10.5061/dryad.bp25b65\">https://doi.org/10.5061/dryad.bp25b65</a>","ama":"Westram AM, Rafajlović M, Chaube P, et al. Data from: Clines on the seashore: the genomic architecture underlying rapid divergence in the face of gene flow. 2018. doi:<a href=\"https://doi.org/10.5061/dryad.bp25b65\">10.5061/dryad.bp25b65</a>","short":"A.M. Westram, M. Rafajlović, P. Chaube, R. Faria, T. Larsson, M. Panova, M. Ravinet, A. Blomberg, B. Mehlig, K. Johannesson, R. Butlin, (2018).","chicago":"Westram, Anja M, Marina Rafajlović, Pragya Chaube, Rui Faria, Tomas Larsson, Marina Panova, Mark Ravinet, et al. “Data from: Clines on the Seashore: The Genomic Architecture Underlying Rapid Divergence in the Face of Gene Flow.” Dryad, 2018. <a href=\"https://doi.org/10.5061/dryad.bp25b65\">https://doi.org/10.5061/dryad.bp25b65</a>.","ieee":"A. M. Westram <i>et al.</i>, “Data from: Clines on the seashore: the genomic architecture underlying rapid divergence in the face of gene flow.” Dryad, 2018.","ista":"Westram AM, Rafajlović M, Chaube P, Faria R, Larsson T, Panova M, Ravinet M, Blomberg A, Mehlig B, Johannesson K, Butlin R. 2018. Data from: Clines on the seashore: the genomic architecture underlying rapid divergence in the face of gene flow, Dryad, <a href=\"https://doi.org/10.5061/dryad.bp25b65\">10.5061/dryad.bp25b65</a>.","mla":"Westram, Anja M., et al. <i>Data from: Clines on the Seashore: The Genomic Architecture Underlying Rapid Divergence in the Face of Gene Flow</i>. Dryad, 2018, doi:<a href=\"https://doi.org/10.5061/dryad.bp25b65\">10.5061/dryad.bp25b65</a>."}},{"oa":1,"doi":"10.1137/1.9781611975031.20","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1709.09209"}],"_id":"309","quality_controlled":"1","status":"public","type":"conference","publication_status":"published","year":"2018","month":"01","article_processing_charge":"No","project":[{"call_identifier":"FWF","grant_number":"M02281","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"page":"274 - 292","title":"Recognizing weak embeddings of graphs","acknowledgement":"∗Research supported in part by the NSF awards CCF-1422311 and CCF-1423615, and the Science Without Borders program. The second author gratefully acknowledges support from Austrian Science Fund (FWF): M2281-N35.","date_created":"2018-12-11T11:45:45Z","scopus_import":"1","day":"01","department":[{"_id":"UlWa"}],"date_updated":"2025-04-14T13:52:37Z","abstract":[{"text":"We present an efficient algorithm for a problem in the interface between clustering and graph embeddings. An embedding ' : G ! M of a graph G into a 2manifold M maps the vertices in V (G) to distinct points and the edges in E(G) to interior-disjoint Jordan arcs between the corresponding vertices. In applications in clustering, cartography, and visualization, nearby vertices and edges are often bundled to a common node or arc, due to data compression or low resolution. This raises the computational problem of deciding whether a given map ' : G ! M comes from an embedding. A map ' : G ! M is a weak embedding if it can be perturbed into an embedding ψ: G ! M with k' \"k < \" for every &quot; &gt; 0. A polynomial-time algorithm for recognizing weak embeddings was recently found by Fulek and Kyncl [14], which reduces to solving a system of linear equations over Z2. It runs in O(n2!) O(n4:75) time, where 2:373 is the matrix multiplication exponent and n is the number of vertices and edges of G. We improve the running time to O(n log n). Our algorithm is also conceptually simpler than [14]: We perform a sequence of local operations that gradually &quot;untangles&quot; the image '(G) into an embedding (G), or reports that ' is not a weak embedding. It generalizes a recent technique developed for the case that G is a cycle and the embedding is a simple polygon [1], and combines local constraints on the orientation of subgraphs directly, thereby eliminating the need for solving large systems of linear equations.","lang":"eng"}],"external_id":{"isi":["000483921200021"],"arxiv":["1709.09209"]},"isi":1,"conference":{"location":"New Orleans, LA, USA","start_date":"2018-01-07","name":"SODA: Symposium on Discrete Algorithms","end_date":"2018-01-10"},"related_material":{"record":[{"id":"6982","relation":"later_version","status":"public"}]},"publisher":"ACM","date_published":"2018-01-01T00:00:00Z","arxiv":1,"publist_id":"7556","citation":{"short":"H. Akitaya, R. Fulek, C. Tóth, in:, ACM, 2018, pp. 274–292.","ama":"Akitaya H, Fulek R, Tóth C. Recognizing weak embeddings of graphs. In: ACM; 2018:274-292. doi:<a href=\"https://doi.org/10.1137/1.9781611975031.20\">10.1137/1.9781611975031.20</a>","apa":"Akitaya, H., Fulek, R., &#38; Tóth, C. (2018). Recognizing weak embeddings of graphs (pp. 274–292). Presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA: ACM. <a href=\"https://doi.org/10.1137/1.9781611975031.20\">https://doi.org/10.1137/1.9781611975031.20</a>","ieee":"H. Akitaya, R. Fulek, and C. Tóth, “Recognizing weak embeddings of graphs,” presented at the SODA: Symposium on Discrete Algorithms, New Orleans, LA, USA, 2018, pp. 274–292.","chicago":"Akitaya, Hugo, Radoslav Fulek, and Csaba Tóth. “Recognizing Weak Embeddings of Graphs,” 274–92. ACM, 2018. <a href=\"https://doi.org/10.1137/1.9781611975031.20\">https://doi.org/10.1137/1.9781611975031.20</a>.","ista":"Akitaya H, Fulek R, Tóth C. 2018. Recognizing weak embeddings of graphs. SODA: Symposium on Discrete Algorithms, 274–292.","mla":"Akitaya, Hugo, et al. <i>Recognizing Weak Embeddings of Graphs</i>. ACM, 2018, pp. 274–92, doi:<a href=\"https://doi.org/10.1137/1.9781611975031.20\">10.1137/1.9781611975031.20</a>."},"oa_version":"Preprint","language":[{"iso":"eng"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"last_name":"Akitaya","first_name":"Hugo","full_name":"Akitaya, Hugo"},{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","last_name":"Fulek","first_name":"Radoslav","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Tóth, Csaba","first_name":"Csaba","last_name":"Tóth"}]},{"external_id":{"isi":["000447486100004"]},"isi":1,"department":[{"_id":"GaTk"}],"date_updated":"2025-05-05T13:48:04Z","abstract":[{"lang":"eng","text":"Correlations in sensory neural networks have both extrinsic and intrinsic origins. Extrinsic or stimulus correlations arise from shared inputs to the network and, thus, depend strongly on the stimulus ensemble. Intrinsic or noise correlations reflect biophysical mechanisms of interactions between neurons, which are expected to be robust to changes in the stimulus ensemble. Despite the importance of this distinction for understanding how sensory networks encode information collectively, no method exists to reliably separate intrinsic interactions from extrinsic correlations in neural activity data, limiting our ability to build predictive models of the network response. In this paper we introduce a general strategy to infer population models of interacting neurons that collectively encode stimulus information. The key to disentangling intrinsic from extrinsic correlations is to infer the couplings between neurons separately from the encoding model and to combine the two using corrections calculated in a mean-field approximation. We demonstrate the effectiveness of this approach in retinal recordings. The same coupling network is inferred from responses to radically different stimulus ensembles, showing that these couplings indeed reflect stimulus-independent interactions between neurons. The inferred model predicts accurately the collective response of retinal ganglion cell populations as a function of the stimulus."}],"date_published":"2018-10-17T00:00:00Z","issue":"4","publisher":"American Physical Society","oa_version":"Preprint","language":[{"iso":"eng"}],"publist_id":"8024","citation":{"ista":"Ferrari U, Deny S, Chalk MJ, Tkačik G, Marre O, Mora T. 2018. Separating intrinsic interactions from extrinsic correlations in a network of sensory neurons. Physical Review E. 98(4), 042410.","mla":"Ferrari, Ulisse, et al. “Separating Intrinsic Interactions from Extrinsic Correlations in a Network of Sensory Neurons.” <i>Physical Review E</i>, vol. 98, no. 4, 042410, American Physical Society, 2018, doi:<a href=\"https://doi.org/10.1103/PhysRevE.98.042410\">10.1103/PhysRevE.98.042410</a>.","ieee":"U. Ferrari, S. Deny, M. J. Chalk, G. Tkačik, O. Marre, and T. Mora, “Separating intrinsic interactions from extrinsic correlations in a network of sensory neurons,” <i>Physical Review E</i>, vol. 98, no. 4. American Physical Society, 2018.","chicago":"Ferrari, Ulisse, Stephane Deny, Matthew J Chalk, Gašper Tkačik, Olivier Marre, and Thierry Mora. “Separating Intrinsic Interactions from Extrinsic Correlations in a Network of Sensory Neurons.” <i>Physical Review E</i>. American Physical Society, 2018. <a href=\"https://doi.org/10.1103/PhysRevE.98.042410\">https://doi.org/10.1103/PhysRevE.98.042410</a>.","ama":"Ferrari U, Deny S, Chalk MJ, Tkačik G, Marre O, Mora T. Separating intrinsic interactions from extrinsic correlations in a network of sensory neurons. <i>Physical Review E</i>. 2018;98(4). doi:<a href=\"https://doi.org/10.1103/PhysRevE.98.042410\">10.1103/PhysRevE.98.042410</a>","short":"U. Ferrari, S. Deny, M.J. Chalk, G. Tkačik, O. Marre, T. Mora, Physical Review E 98 (2018).","apa":"Ferrari, U., Deny, S., Chalk, M. J., Tkačik, G., Marre, O., &#38; Mora, T. (2018). Separating intrinsic interactions from extrinsic correlations in a network of sensory neurons. <i>Physical Review E</i>. American Physical Society. <a href=\"https://doi.org/10.1103/PhysRevE.98.042410\">https://doi.org/10.1103/PhysRevE.98.042410</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Ferrari, Ulisse","last_name":"Ferrari","first_name":"Ulisse"},{"first_name":"Stephane","last_name":"Deny","full_name":"Deny, Stephane"},{"last_name":"Chalk","first_name":"Matthew J","full_name":"Chalk, Matthew J"},{"full_name":"Tkacik, Gasper","orcid":"0000-0002-6699-1455","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87","last_name":"Tkacik","first_name":"Gasper"},{"last_name":"Marre","first_name":"Olivier","full_name":"Marre, Olivier"},{"full_name":"Mora, Thierry","first_name":"Thierry","last_name":"Mora"}],"doi":"10.1103/PhysRevE.98.042410","publication_identifier":{"issn":["2470-0045"]},"main_file_link":[{"open_access":"1","url":"https://www.biorxiv.org/content/10.1101/243816v2.full"}],"_id":"31","article_number":"042410","oa":1,"article_type":"original","quality_controlled":"1","status":"public","type":"journal_article","publication_status":"published","year":"2018","project":[{"_id":"26436750-B435-11E9-9278-68D0E5697425","grant_number":"785907","name":"Human Brain Project Specific Grant Agreement 2","call_identifier":"H2020"}],"intvolume":"        98","title":"Separating intrinsic interactions from extrinsic correlations in a network of sensory neurons","month":"10","article_processing_charge":"No","volume":98,"acknowledgement":"This work was supported by ANR Trajectory, the French State program Investissements d’Avenir managed by the Agence Nationale de la Recherche (LIFESENSES; ANR-10-LABX-65), EC Grant No. H2020-785907 from the Human Brain Project, NIH Grant No. U01NS090501, and an AVIESAN-UNADEV grant to O.M. M.C. was supported by the Agence Nationale de la Recherche Jeune Chercheur/Jeune Chercheuse grant (ANR-17-CE37-0013).","date_created":"2018-12-11T11:44:15Z","ec_funded":1,"scopus_import":"1","day":"17","publication":"Physical Review E"},{"title":"Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter","page":"2341 - 2356","project":[{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"}],"month":"01","article_processing_charge":"No","day":"01","ec_funded":1,"date_created":"2018-12-11T11:45:45Z","scopus_import":"1","doi":"10.1137/1.9781611975031.151","_id":"310","main_file_link":[{"url":"https://arxiv.org/abs/1711.09148","open_access":"1"}],"oa":1,"type":"conference","status":"public","year":"2018","publication_status":"published","quality_controlled":"1","oa_version":"Preprint","language":[{"iso":"eng"}],"citation":{"mla":"Chatterjee, Krishnendu, et al. <i>Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter</i>. ACM, 2018, pp. 2341–56, doi:<a href=\"https://doi.org/10.1137/1.9781611975031.151\">10.1137/1.9781611975031.151</a>.","ista":"Chatterjee K, Dvorák W, Henzinger M, Loitzenbauer V. 2018. Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter. SODA: Symposium on Discrete Algorithms, 2341–2356.","chicago":"Chatterjee, Krishnendu, Wolfgang Dvorák, Monika Henzinger, and Veronika Loitzenbauer. “Lower Bounds for Symbolic Computation on Graphs: Strongly Connected Components, Liveness, Safety, and Diameter,” 2341–56. ACM, 2018. <a href=\"https://doi.org/10.1137/1.9781611975031.151\">https://doi.org/10.1137/1.9781611975031.151</a>.","ieee":"K. Chatterjee, W. Dvorák, M. Henzinger, and V. Loitzenbauer, “Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter,” presented at the SODA: Symposium on Discrete Algorithms, New Orleans, Louisiana, United States, 2018, pp. 2341–2356.","apa":"Chatterjee, K., Dvorák, W., Henzinger, M., &#38; Loitzenbauer, V. (2018). Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter (pp. 2341–2356). Presented at the SODA: Symposium on Discrete Algorithms, New Orleans, Louisiana, United States: ACM. <a href=\"https://doi.org/10.1137/1.9781611975031.151\">https://doi.org/10.1137/1.9781611975031.151</a>","short":"K. Chatterjee, W. Dvorák, M. Henzinger, V. Loitzenbauer, in:, ACM, 2018, pp. 2341–2356.","ama":"Chatterjee K, Dvorák W, Henzinger M, Loitzenbauer V. Lower bounds for symbolic computation on graphs: Strongly connected components, liveness, safety, and diameter. In: ACM; 2018:2341-2356. doi:<a href=\"https://doi.org/10.1137/1.9781611975031.151\">10.1137/1.9781611975031.151</a>"},"publist_id":"7555","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu"},{"full_name":"Dvorák, Wolfgang","first_name":"Wolfgang","last_name":"Dvorák"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"Loitzenbauer","first_name":"Veronika","full_name":"Loitzenbauer, Veronika"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1711.09148"],"isi":["000483921200152"]},"isi":1,"abstract":[{"lang":"eng","text":"A model of computation that is widely used in the formal analysis of reactive systems is symbolic algorithms. In this model the access to the input graph is restricted to consist of symbolic operations, which are expensive in comparison to the standard RAM operations. We give lower bounds on the number of symbolic operations for basic graph problems such as the computation of the strongly connected components and of the approximate diameter as well as for fundamental problems in model checking such as safety, liveness, and coliveness. Our lower bounds are linear in the number of vertices of the graph, even for constant-diameter graphs. For none of these problems lower bounds on the number of symbolic operations were known before. The lower bounds show an interesting separation of these problems from the reachability problem, which can be solved with O(D) symbolic operations, where D is the diameter of the graph. Additionally we present an approximation algorithm for the graph diameter which requires Õ(n/D) symbolic steps to achieve a (1 +ϵ)-approximation for any constant &gt; 0. This compares to O(n/D) symbolic steps for the (naive) exact algorithm and O(D) symbolic steps for a 2-approximation. Finally we also give a refined analysis of the strongly connected components algorithms of [15], showing that it uses an optimal number of symbolic steps that is proportional to the sum of the diameters of the strongly connected components."}],"department":[{"_id":"KrCh"}],"date_updated":"2025-04-14T13:51:04Z","arxiv":1,"date_published":"2018-01-01T00:00:00Z","publisher":"ACM","conference":{"name":"SODA: Symposium on Discrete Algorithms","end_date":"2018-01-10","start_date":"2018-01-07","location":"New Orleans, Louisiana, United States"}},{"issue":"4","publisher":"Cell Press","date_published":"2018-04-25T00:00:00Z","department":[{"_id":"AnKi"}],"date_updated":"2026-06-18T18:38:14Z","abstract":[{"text":"The interface of physics and biology pro-vides a fruitful environment for generatingnew concepts and exciting ways forwardto understanding living matter. Examplesof successful studies include the estab-lishment and readout of morphogen gra-dients during development, signal pro-cessing in protein and genetic networks,the role of fluctuations in determining thefates of cells and tissues, and collectiveeffects in proteins and in tissues. It is nothard to envision that significant further ad-vances will translate to societal benefitsby initiating the development of new de-vices and strategies for curing disease.However, research at the interface posesvarious challenges, in particular for youngscientists, and current institutions arerarely designed to facilitate such scientificprograms. In this Letter, we propose aninternational initiative that addressesthese challenges through the establish-ment of a worldwide network of platformsfor cross-disciplinary training and incuba-tors for starting new collaborations.","lang":"eng"}],"external_id":{"pmid":["29698645"],"isi":["000432192100003"]},"isi":1,"ddc":["570"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Guntram","last_name":"Bauer","full_name":"Bauer, Guntram"},{"full_name":"Fakhri, Nikta","first_name":"Nikta","last_name":"Fakhri"},{"full_name":"Kicheva, Anna","orcid":"0000-0003-4509-4998","id":"3959A2A0-F248-11E8-B48F-1D18A9856A87","first_name":"Anna","last_name":"Kicheva"},{"full_name":"Kondev, Jané","last_name":"Kondev","first_name":"Jané"},{"full_name":"Kruse, Karsten","first_name":"Karsten","last_name":"Kruse"},{"first_name":"Hiroyuki","last_name":"Noji","full_name":"Noji, Hiroyuki"},{"full_name":"Riveline, Daniel","last_name":"Riveline","first_name":"Daniel"},{"full_name":"Saunders, Timothy","first_name":"Timothy","last_name":"Saunders"},{"last_name":"Thatta","first_name":"Mukund","full_name":"Thatta, Mukund"},{"full_name":"Wieschaus, Eric","first_name":"Eric","last_name":"Wieschaus"}],"publist_id":"7551","citation":{"chicago":"Bauer, Guntram, Nikta Fakhri, Anna Kicheva, Jané Kondev, Karsten Kruse, Hiroyuki Noji, Daniel Riveline, Timothy Saunders, Mukund Thatta, and Eric Wieschaus. “The Science of Living Matter for Tomorrow.” <i>Cell Systems</i>. Cell Press, 2018. <a href=\"https://doi.org/10.1016/j.cels.2018.04.003\">https://doi.org/10.1016/j.cels.2018.04.003</a>.","ieee":"G. Bauer <i>et al.</i>, “The science of living matter for tomorrow,” <i>Cell Systems</i>, vol. 6, no. 4. Cell Press, pp. 400–402, 2018.","mla":"Bauer, Guntram, et al. “The Science of Living Matter for Tomorrow.” <i>Cell Systems</i>, vol. 6, no. 4, Cell Press, 2018, pp. 400–02, doi:<a href=\"https://doi.org/10.1016/j.cels.2018.04.003\">10.1016/j.cels.2018.04.003</a>.","ista":"Bauer G, Fakhri N, Kicheva A, Kondev J, Kruse K, Noji H, Riveline D, Saunders T, Thatta M, Wieschaus E. 2018. The science of living matter for tomorrow. Cell Systems. 6(4), 400–402.","apa":"Bauer, G., Fakhri, N., Kicheva, A., Kondev, J., Kruse, K., Noji, H., … Wieschaus, E. (2018). The science of living matter for tomorrow. <i>Cell Systems</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.cels.2018.04.003\">https://doi.org/10.1016/j.cels.2018.04.003</a>","ama":"Bauer G, Fakhri N, Kicheva A, et al. The science of living matter for tomorrow. <i>Cell Systems</i>. 2018;6(4):400-402. doi:<a href=\"https://doi.org/10.1016/j.cels.2018.04.003\">10.1016/j.cels.2018.04.003</a>","short":"G. Bauer, N. Fakhri, A. Kicheva, J. Kondev, K. Kruse, H. Noji, D. Riveline, T. Saunders, M. Thatta, E. Wieschaus, Cell Systems 6 (2018) 400–402."},"oa_version":"Published Version","language":[{"iso":"eng"}],"quality_controlled":"1","status":"public","type":"journal_article","publication_status":"published","year":"2018","oa":1,"article_type":"letter_note","doi":"10.1016/j.cels.2018.04.003","publication_identifier":{"eissn":["2405-4712"]},"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1016/j.cels.2018.04.003"}],"_id":"314","publication":"Cell Systems","date_created":"2018-12-11T11:45:46Z","scopus_import":"1","day":"25","pmid":1,"article_processing_charge":"No","month":"04","volume":6,"intvolume":"         6","title":"The science of living matter for tomorrow","page":"400 - 402"},{"title":"Is the sky the limit? On the expansion threshold of a species’ range","intvolume":"        16","file":[{"access_level":"open_access","checksum":"908c52751bba30c55ed36789e5e4c84d","date_created":"2019-01-22T08:30:03Z","relation":"main_file","creator":"dernst","file_id":"5870","content_type":"application/pdf","date_updated":"2020-07-14T12:46:01Z","file_size":6968201,"file_name":"2017_PLOS_Polechova.pdf"}],"volume":16,"month":"06","article_processing_charge":"No","day":"15","tmp":{"short":"CC BY (4.0)","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)"},"date_created":"2018-12-11T11:45:46Z","scopus_import":"1","publication":"PLoS Biology","article_number":"e2005372","publication_identifier":{"issn":["1544-9173"]},"doi":"10.1371/journal.pbio.2005372","_id":"315","oa":1,"has_accepted_license":"1","type":"journal_article","status":"public","file_date_updated":"2020-07-14T12:46:01Z","publication_status":"published","year":"2018","quality_controlled":"1","oa_version":"Published Version","language":[{"iso":"eng"}],"citation":{"chicago":"Polechova, Jitka. “Is the Sky the Limit? On the Expansion Threshold of a Species’ Range.” <i>PLoS Biology</i>. Public Library of Science, 2018. <a href=\"https://doi.org/10.1371/journal.pbio.2005372\">https://doi.org/10.1371/journal.pbio.2005372</a>.","ieee":"J. Polechova, “Is the sky the limit? On the expansion threshold of a species’ range,” <i>PLoS Biology</i>, vol. 16, no. 6. Public Library of Science, 2018.","ista":"Polechova J. 2018. Is the sky the limit? On the expansion threshold of a species’ range. PLoS Biology. 16(6), e2005372.","mla":"Polechova, Jitka. “Is the Sky the Limit? On the Expansion Threshold of a Species’ Range.” <i>PLoS Biology</i>, vol. 16, no. 6, e2005372, Public Library of Science, 2018, doi:<a href=\"https://doi.org/10.1371/journal.pbio.2005372\">10.1371/journal.pbio.2005372</a>.","apa":"Polechova, J. (2018). Is the sky the limit? On the expansion threshold of a species’ range. <i>PLoS Biology</i>. Public Library of Science. <a href=\"https://doi.org/10.1371/journal.pbio.2005372\">https://doi.org/10.1371/journal.pbio.2005372</a>","short":"J. Polechova, PLoS Biology 16 (2018).","ama":"Polechova J. Is the sky the limit? On the expansion threshold of a species’ range. <i>PLoS Biology</i>. 2018;16(6). doi:<a href=\"https://doi.org/10.1371/journal.pbio.2005372\">10.1371/journal.pbio.2005372</a>"},"publist_id":"7550","author":[{"last_name":"Polechova","first_name":"Jitka","id":"3BBFB084-F248-11E8-B48F-1D18A9856A87","full_name":"Polechova, Jitka","orcid":"0000-0003-0951-3112"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["576"],"abstract":[{"lang":"eng","text":"More than 100 years after Grigg’s influential analysis of species’ borders, the causes of limits to species’ ranges still represent a puzzle that has never been understood with clarity. The topic has become especially important recently as many scientists have become interested in the potential for species’ ranges to shift in response to climate change—and yet nearly all of those studies fail to recognise or incorporate evolutionary genetics in a way that relates to theoretical developments. I show that range margins can be understood based on just two measurable parameters: (i) the fitness cost of dispersal—a measure of environmental heterogeneity—and (ii) the strength of genetic drift, which reduces genetic diversity. Together, these two parameters define an ‘expansion threshold’: adaptation fails when genetic drift reduces genetic diversity below that required for adaptation to a heterogeneous environment. When the key parameters drop below this expansion threshold locally, a sharp range margin forms. When they drop below this threshold throughout the species’ range, adaptation collapses everywhere, resulting in either extinction or formation of a fragmented metapopulation. Because the effects of dispersal differ fundamentally with dimension, the second parameter—the strength of genetic drift—is qualitatively different compared to a linear habitat. In two-dimensional habitats, genetic drift becomes effectively independent of selection. It decreases with ‘neighbourhood size’—the number of individuals accessible by dispersal within one generation. Moreover, in contrast to earlier predictions, which neglected evolution of genetic variance and/or stochasticity in two dimensions, dispersal into small marginal populations aids adaptation. This is because the reduction of both genetic and demographic stochasticity has a stronger effect than the cost of dispersal through increased maladaptation. The expansion threshold thus provides a novel, theoretically justified, and testable prediction for formation of the range margin and collapse of the species’ range."}],"department":[{"_id":"NiBa"}],"date_updated":"2025-07-10T11:52:27Z","date_published":"2018-06-15T00:00:00Z","related_material":{"record":[{"id":"9839","relation":"research_data","status":"public"}]},"publisher":"Public Library of Science","issue":"6"},{"volume":209,"article_processing_charge":"No","month":"07","title":"Evolutionary pathways for the generation of new self-incompatibility haplotypes in a non-self recognition system","page":"861-883","project":[{"_id":"25B36484-B435-11E9-9278-68D0E5697425","grant_number":"329960","name":"Mating system and the evolutionary dynamics of hybrid zones","call_identifier":"FP7"},{"call_identifier":"FP7","name":"Limits to selection in biology and in evolutionary computation","grant_number":"250152","_id":"25B07788-B435-11E9-9278-68D0E5697425"},{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"International IST Postdoc Fellowship Programme","grant_number":"291734"}],"intvolume":"       209","publication":"Genetics","day":"01","date_created":"2018-12-11T11:45:47Z","ec_funded":1,"scopus_import":"1","oa":1,"article_type":"original","doi":"10.1534/genetics.118.300748","main_file_link":[{"open_access":"1","url":"https://www.biorxiv.org/node/80098.abstract"}],"_id":"316","status":"public","type":"journal_article","publication_status":"published","year":"2018","quality_controlled":"1","citation":{"ama":"Bodova K, Priklopil T, Field D, Barton NH, Pickup M. Evolutionary pathways for the generation of new self-incompatibility haplotypes in a non-self recognition system. <i>Genetics</i>. 2018;209(3):861-883. doi:<a href=\"https://doi.org/10.1534/genetics.118.300748\">10.1534/genetics.118.300748</a>","short":"K. Bodova, T. Priklopil, D. Field, N.H. Barton, M. Pickup, Genetics 209 (2018) 861–883.","apa":"Bodova, K., Priklopil, T., Field, D., Barton, N. H., &#38; Pickup, M. (2018). Evolutionary pathways for the generation of new self-incompatibility haplotypes in a non-self recognition system. <i>Genetics</i>. Genetics Society of America. <a href=\"https://doi.org/10.1534/genetics.118.300748\">https://doi.org/10.1534/genetics.118.300748</a>","mla":"Bodova, Katarina, et al. “Evolutionary Pathways for the Generation of New Self-Incompatibility Haplotypes in a Non-Self Recognition System.” <i>Genetics</i>, vol. 209, no. 3, Genetics Society of America, 2018, pp. 861–83, doi:<a href=\"https://doi.org/10.1534/genetics.118.300748\">10.1534/genetics.118.300748</a>.","ista":"Bodova K, Priklopil T, Field D, Barton NH, Pickup M. 2018. Evolutionary pathways for the generation of new self-incompatibility haplotypes in a non-self recognition system. Genetics. 209(3), 861–883.","ieee":"K. Bodova, T. Priklopil, D. Field, N. H. Barton, and M. Pickup, “Evolutionary pathways for the generation of new self-incompatibility haplotypes in a non-self recognition system,” <i>Genetics</i>, vol. 209, no. 3. Genetics Society of America, pp. 861–883, 2018.","chicago":"Bodova, Katarina, Tadeas Priklopil, David Field, Nicholas H Barton, and Melinda Pickup. “Evolutionary Pathways for the Generation of New Self-Incompatibility Haplotypes in a Non-Self Recognition System.” <i>Genetics</i>. Genetics Society of America, 2018. <a href=\"https://doi.org/10.1534/genetics.118.300748\">https://doi.org/10.1534/genetics.118.300748</a>."},"oa_version":"Preprint","language":[{"iso":"eng"}],"author":[{"orcid":"0000-0002-7214-0171","full_name":"Bodova, Katarina","first_name":"Katarina","last_name":"Bodova","id":"2BA24EA0-F248-11E8-B48F-1D18A9856A87"},{"id":"3C869AA0-F248-11E8-B48F-1D18A9856A87","last_name":"Priklopil","first_name":"Tadeas","full_name":"Priklopil, Tadeas"},{"id":"419049E2-F248-11E8-B48F-1D18A9856A87","last_name":"Field","first_name":"David","full_name":"Field, David","orcid":"0000-0002-4014-8478"},{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","first_name":"Nicholas H","last_name":"Barton","full_name":"Barton, Nicholas H","orcid":"0000-0002-8548-5240"},{"full_name":"Pickup, Melinda","orcid":"0000-0001-6118-0541","last_name":"Pickup","first_name":"Melinda","id":"2C78037E-F248-11E8-B48F-1D18A9856A87"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","abstract":[{"text":"Self-incompatibility (SI) is a genetically based recognition system that functions to prevent self-fertilization and mating among related plants. An enduring puzzle in SI is how the high diversity observed in nature arises and is maintained. Based on the underlying recognition mechanism, SI can be classified into two main groups: self- and non-self recognition. Most work has focused on diversification within self-recognition systems despite expected differences between the two groups in the evolutionary pathways and outcomes of diversification. Here, we use a deterministic population genetic model and stochastic simulations to investigate how novel S-haplotypes evolve in a gametophytic non-self recognition (SRNase/S Locus F-box (SLF)) SI system. For this model the pathways for diversification involve either the maintenance or breakdown of SI and can vary in the order of mutations of the female (SRNase) and male (SLF) components. We show analytically that diversification can occur with high inbreeding depression and self-pollination, but this varies with evolutionary pathway and level of completeness (which determines the number of potential mating partners in the population), and in general is more likely for lower haplotype number. The conditions for diversification are broader in stochastic simulations of finite population size. However, the number of haplotypes observed under high inbreeding and moderate to high self-pollination is less than that commonly observed in nature. Diversification was observed through pathways that maintain SI as well as through self-compatible intermediates. Yet the lifespan of diversified haplotypes was sensitive to their level of completeness. By examining diversification in a non-self recognition SI system, this model extends our understanding of the evolution and maintenance of haplotype diversity observed in a self recognition system common in flowering plants.","lang":"eng"}],"department":[{"_id":"NiBa"},{"_id":"GaTk"}],"date_updated":"2025-04-15T06:50:00Z","external_id":{"isi":["000437171700017"]},"isi":1,"related_material":{"record":[{"status":"public","relation":"research_data","id":"9813"}],"link":[{"description":"News on IST Homepage","url":"https://ist.ac.at/en/news/recognizing-others-but-not-yourself-new-insights-into-the-evolution-of-plant-mating/","relation":"press_release"}]},"publisher":"Genetics Society of America","issue":"3","date_published":"2018-07-01T00:00:00Z"},{"intvolume":"         8","title":"Palladium gates for reproducible quantum dots in silicon","month":"04","article_processing_charge":"No","volume":8,"file":[{"access_level":"open_access","date_created":"2018-12-12T10:17:04Z","checksum":"20af238ca4ba6491b77270be8d826bf5","creator":"system","file_id":"5256","relation":"main_file","content_type":"application/pdf","date_updated":"2020-07-14T12:46:02Z","file_size":1850530,"file_name":"IST-2018-1016-v1+1_2018_Brauns_Palladium_gates.pdf"}],"scopus_import":"1","date_created":"2018-12-11T11:45:47Z","tmp":{"short":"CC BY (4.0)","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)"},"day":"09","pubrep_id":"1016","publication":"Scientific Reports","_id":"317","doi":"10.1038/s41598-018-24004-y","article_number":"5690","has_accepted_license":"1","oa":1,"quality_controlled":"1","file_date_updated":"2020-07-14T12:46:02Z","publication_status":"published","year":"2018","type":"journal_article","status":"public","language":[{"iso":"eng"}],"oa_version":"Published Version","publist_id":"7548","citation":{"ieee":"M. Brauns, S. Amitonov, P. Spruijtenburg, and F. Zwanenburg, “Palladium gates for reproducible quantum dots in silicon,” <i>Scientific Reports</i>, vol. 8, no. 1. Nature Publishing Group, 2018.","chicago":"Brauns, Matthias, Sergey Amitonov, Paul Spruijtenburg, and Floris Zwanenburg. “Palladium Gates for Reproducible Quantum Dots in Silicon.” <i>Scientific Reports</i>. Nature Publishing Group, 2018. <a href=\"https://doi.org/10.1038/s41598-018-24004-y\">https://doi.org/10.1038/s41598-018-24004-y</a>.","ista":"Brauns M, Amitonov S, Spruijtenburg P, Zwanenburg F. 2018. Palladium gates for reproducible quantum dots in silicon. Scientific Reports. 8(1), 5690.","mla":"Brauns, Matthias, et al. “Palladium Gates for Reproducible Quantum Dots in Silicon.” <i>Scientific Reports</i>, vol. 8, no. 1, 5690, Nature Publishing Group, 2018, doi:<a href=\"https://doi.org/10.1038/s41598-018-24004-y\">10.1038/s41598-018-24004-y</a>.","short":"M. Brauns, S. Amitonov, P. Spruijtenburg, F. Zwanenburg, Scientific Reports 8 (2018).","ama":"Brauns M, Amitonov S, Spruijtenburg P, Zwanenburg F. Palladium gates for reproducible quantum dots in silicon. <i>Scientific Reports</i>. 2018;8(1). doi:<a href=\"https://doi.org/10.1038/s41598-018-24004-y\">10.1038/s41598-018-24004-y</a>","apa":"Brauns, M., Amitonov, S., Spruijtenburg, P., &#38; Zwanenburg, F. (2018). Palladium gates for reproducible quantum dots in silicon. <i>Scientific Reports</i>. Nature Publishing Group. <a href=\"https://doi.org/10.1038/s41598-018-24004-y\">https://doi.org/10.1038/s41598-018-24004-y</a>"},"corr_author":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"full_name":"Brauns, Matthias","first_name":"Matthias","last_name":"Brauns","id":"33F94E3C-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Amitonov","first_name":"Sergey","full_name":"Amitonov, Sergey"},{"first_name":"Paul","last_name":"Spruijtenburg","full_name":"Spruijtenburg, Paul"},{"full_name":"Zwanenburg, Floris","last_name":"Zwanenburg","first_name":"Floris"}],"ddc":["539"],"external_id":{"isi":["000429404300013"]},"isi":1,"date_updated":"2024-10-09T20:58:34Z","department":[{"_id":"GeKa"}],"abstract":[{"lang":"eng","text":"We replace the established aluminium gates for the formation of quantum dots in silicon with gates made from palladium. We study the morphology of both aluminium and palladium gates with transmission electron microscopy. The native aluminium oxide is found to be formed all around the aluminium gates, which could lead to the formation of unintentional dots. Therefore, we report on a novel fabrication route that replaces aluminium and its native oxide by palladium with atomic-layer-deposition-grown aluminium oxide. Using this approach, we show the formation of low-disorder gate-defined quantum dots, which are reproducibly fabricated. Furthermore, palladium enables us to further shrink the gate design, allowing us to perform electron transport measurements in the few-electron regime in devices comprising only two gate layers, a major technological advancement. It remains to be seen, whether the introduction of palladium gates can improve the excellent results on electron and nuclear spin qubits defined with an aluminium gate stack."}],"date_published":"2018-04-09T00:00:00Z","issue":"1","publisher":"Nature Publishing Group"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Casano, Alessandra M","orcid":"0000-0002-6009-6804","last_name":"Casano","first_name":"Alessandra M","id":"3DBA3F4E-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Sixt, Michael K","orcid":"0000-0002-6620-9179","id":"41E9FBEA-F248-11E8-B48F-1D18A9856A87","first_name":"Michael K","last_name":"Sixt"}],"corr_author":"1","publist_id":"7547","citation":{"ama":"Casano AM, Sixt MK. A fat lot of good for wound healing. <i>Developmental Cell</i>. 2018;44(4):405-406. doi:<a href=\"https://doi.org/10.1016/j.devcel.2018.02.009\">10.1016/j.devcel.2018.02.009</a>","short":"A.M. Casano, M.K. Sixt, Developmental Cell 44 (2018) 405–406.","apa":"Casano, A. M., &#38; Sixt, M. K. (2018). A fat lot of good for wound healing. <i>Developmental Cell</i>. Cell Press. <a href=\"https://doi.org/10.1016/j.devcel.2018.02.009\">https://doi.org/10.1016/j.devcel.2018.02.009</a>","ista":"Casano AM, Sixt MK. 2018. A fat lot of good for wound healing. Developmental Cell. 44(4), 405–406.","mla":"Casano, Alessandra M., and Michael K. Sixt. “A Fat Lot of Good for Wound Healing.” <i>Developmental Cell</i>, vol. 44, no. 4, Cell Press, 2018, pp. 405–06, doi:<a href=\"https://doi.org/10.1016/j.devcel.2018.02.009\">10.1016/j.devcel.2018.02.009</a>.","ieee":"A. M. Casano and M. K. Sixt, “A fat lot of good for wound healing,” <i>Developmental Cell</i>, vol. 44, no. 4. Cell Press, pp. 405–406, 2018.","chicago":"Casano, Alessandra M, and Michael K Sixt. “A Fat Lot of Good for Wound Healing.” <i>Developmental Cell</i>. Cell Press, 2018. <a href=\"https://doi.org/10.1016/j.devcel.2018.02.009\">https://doi.org/10.1016/j.devcel.2018.02.009</a>."},"oa_version":"Published Version","language":[{"iso":"eng"}],"issue":"4","publisher":"Cell Press","date_published":"2018-02-26T00:00:00Z","department":[{"_id":"MiSi"}],"date_updated":"2026-06-18T18:39:56Z","abstract":[{"text":"The insect’s fat body combines metabolic and immunological functions. In this issue of Developmental Cell, Franz et al. (2018) show that in Drosophila, cells of the fat body are not static, but can actively “swim” toward sites of epithelial injury, where they physically clog the wound and locally secrete antimicrobial peptides.","lang":"eng"}],"isi":1,"external_id":{"isi":["000426150700002"],"pmid":["29486189"]},"ddc":["570"],"publication":"Developmental Cell","acknowledgement":"Short Survey","date_created":"2018-12-11T11:45:47Z","scopus_import":"1","day":"26","pmid":1,"article_processing_charge":"No","month":"02","volume":44,"intvolume":"        44","title":"A fat lot of good for wound healing","page":"405 - 406","quality_controlled":"1","type":"journal_article","status":"public","year":"2018","publication_status":"published","oa":1,"doi":"10.1016/j.devcel.2018.02.009","_id":"318","main_file_link":[{"url":"https://www.ncbi.nlm.nih.gov/pubmed/29486189","open_access":"1"}]},{"oa_version":"Published Version","language":[{"iso":"eng"}],"publist_id":"8023","citation":{"ieee":"T. Chen <i>et al.</i>, “In Vivo regulation of Oligodendrocyte processor cell proliferation and differentiation by the AMPA-receptor Subunit GluA2,” <i>Cell Reports</i>, vol. 25, no. 4. Elsevier, p. 852–861.e7, 2018.","chicago":"Chen, Ting, Bartosz Kula, Balint Nagy, Ruxandra Barzan, Andrea Gall, Ingrid Ehrlich, and Maria Kukley. “In Vivo Regulation of Oligodendrocyte Processor Cell Proliferation and Differentiation by the AMPA-Receptor Subunit GluA2.” <i>Cell Reports</i>. Elsevier, 2018. <a href=\"https://doi.org/10.1016/j.celrep.2018.09.066\">https://doi.org/10.1016/j.celrep.2018.09.066</a>.","ista":"Chen T, Kula B, Nagy B, Barzan R, Gall A, Ehrlich I, Kukley M. 2018. In Vivo regulation of Oligodendrocyte processor cell proliferation and differentiation by the AMPA-receptor Subunit GluA2. Cell Reports. 25(4), 852–861.e7.","mla":"Chen, Ting, et al. “In Vivo Regulation of Oligodendrocyte Processor Cell Proliferation and Differentiation by the AMPA-Receptor Subunit GluA2.” <i>Cell Reports</i>, vol. 25, no. 4, Elsevier, 2018, p. 852–861.e7, doi:<a href=\"https://doi.org/10.1016/j.celrep.2018.09.066\">10.1016/j.celrep.2018.09.066</a>.","short":"T. Chen, B. Kula, B. Nagy, R. Barzan, A. Gall, I. Ehrlich, M. Kukley, Cell Reports 25 (2018) 852–861.e7.","ama":"Chen T, Kula B, Nagy B, et al. In Vivo regulation of Oligodendrocyte processor cell proliferation and differentiation by the AMPA-receptor Subunit GluA2. <i>Cell Reports</i>. 2018;25(4):852-861.e7. doi:<a href=\"https://doi.org/10.1016/j.celrep.2018.09.066\">10.1016/j.celrep.2018.09.066</a>","apa":"Chen, T., Kula, B., Nagy, B., Barzan, R., Gall, A., Ehrlich, I., &#38; Kukley, M. (2018). In Vivo regulation of Oligodendrocyte processor cell proliferation and differentiation by the AMPA-receptor Subunit GluA2. <i>Cell Reports</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.celrep.2018.09.066\">https://doi.org/10.1016/j.celrep.2018.09.066</a>"},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"first_name":"Ting","last_name":"Chen","full_name":"Chen, Ting"},{"full_name":"Kula, Bartosz","first_name":"Bartosz","last_name":"Kula"},{"full_name":"Nagy, Balint","orcid":"0000-0002-4002-4686","first_name":"Balint","last_name":"Nagy","id":"30F830CE-02D1-11E9-9BAA-DAF4881429F2"},{"last_name":"Barzan","first_name":"Ruxandra","full_name":"Barzan, Ruxandra"},{"full_name":"Gall, Andrea","last_name":"Gall","first_name":"Andrea"},{"last_name":"Ehrlich","first_name":"Ingrid","full_name":"Ehrlich, Ingrid"},{"full_name":"Kukley, Maria","first_name":"Maria","last_name":"Kukley"}],"isi":1,"external_id":{"isi":["000448219500005"]},"ddc":["570"],"department":[{"_id":"SaSi"}],"date_updated":"2023-09-11T14:13:32Z","abstract":[{"text":"The functional role of AMPA receptor (AMPAR)-mediated synaptic signaling between neurons and oligodendrocyte precursor cells (OPCs) remains enigmatic. We modified the properties of AMPARs at axon-OPC synapses in the mouse corpus callosum in vivo during the peak of myelination by targeting the GluA2 subunit. Expression of the unedited (Ca2+ permeable) or the pore-dead GluA2 subunit of AMPARs triggered proliferation of OPCs and reduced their differentiation into oligodendrocytes. Expression of the cytoplasmic C-terminal (GluA2(813-862)) of the GluA2 subunit (C-tail), a modification designed to affect the interaction between GluA2 and AMPAR-binding proteins and to perturb trafficking of GluA2-containing AMPARs, decreased the differentiation of OPCs without affecting their proliferation. These findings suggest that ionotropic and non-ionotropic properties of AMPARs in OPCs, as well as specific aspects of AMPAR-mediated signaling at axon-OPC synapses in the mouse corpus callosum, are important for balancing the response of OPCs to proliferation and differentiation cues. In the brain, oligodendrocyte precursor cells (OPCs) receive glutamatergic AMPA-receptor-mediated synaptic input from neurons. Chen et al. show that modifying AMPA-receptor properties at axon-OPC synapses alters proliferation and differentiation of OPCs. This expands the traditional view of synaptic transmission by suggesting neurons also use synapses to modulate behavior of glia.","lang":"eng"}],"date_published":"2018-10-23T00:00:00Z","issue":"4","publisher":"Elsevier","intvolume":"        25","title":"In Vivo regulation of Oligodendrocyte processor cell proliferation and differentiation by the AMPA-receptor Subunit GluA2","page":"852 - 861.e7","month":"10","article_processing_charge":"No","file":[{"content_type":"application/pdf","date_updated":"2020-07-14T12:46:03Z","file_size":4461997,"file_name":"2018_CellReports_Chen.pdf","access_level":"open_access","checksum":"d9f74277fd57176e04732707d575cf08","date_created":"2018-12-17T12:42:57Z","relation":"main_file","file_id":"5703","creator":"dernst"}],"volume":25,"acknowledgement":"This work was supported by Deutsche Forschungsgemeinschaft (DFG) grant KU2569/1-1 (to M.K.); DFG project EXC307Centre for Integrative Neuroscience (CIN), including grant Pool Project 2011-12 (jointly to M.K. and I.E.); and the Charitable Hertie Foundation (to I.E.). CIN is an Excellence Cluster funded by the DFG within the framework of the Excellence Initiative for 2008–2018. M.K. is supported by the Tistou & Charlotte Kerstan Foundation.","date_created":"2018-12-11T11:44:16Z","scopus_import":"1","day":"23","tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode"},"publication":"Cell Reports","doi":"10.1016/j.celrep.2018.09.066","_id":"32","has_accepted_license":"1","oa":1,"quality_controlled":"1","status":"public","type":"journal_article","year":"2018","publication_status":"published","file_date_updated":"2020-07-14T12:46:03Z"}]