[{"date_published":"2019-07-25T00:00:00Z","related_material":{"record":[{"relation":"dissertation_contains","id":"8156","status":"public"}],"link":[{"relation":"later_version","url":"https://doi.org/10.1112/mtk.12059"}]},"doi":"10.48550/arXiv.1907.11183","date_created":"2020-07-30T10:45:51Z","year":"2019","publication_status":"submitted","day":"25","publication":"arXiv","language":[{"iso":"eng"}],"main_file_link":[{"url":"https://arxiv.org/abs/1907.11183","open_access":"1"}],"oa":1,"month":"07","abstract":[{"text":"In this paper we study envy-free division problems. The classical approach to some of such problems, used by David Gale, reduces to considering continuous maps of a simplex to itself and finding sufficient conditions when this map hits the center of the simplex. The mere continuity is not sufficient for such a conclusion, the usual assumption (for example, in the Knaster--Kuratowski--Mazurkiewicz and the Gale theorem) is a certain boundary condition.\r\n We follow Erel Segal-Halevi, Fr\\'ed\\'eric Meunier, and Shira Zerbib, and replace the boundary condition by another assumption, which has the economic meaning of possibility for a player to prefer an empty part in the segment\r\npartition problem. We solve the problem positively when $n$, the number of players that divide the segment, is a prime power, and we provide counterexamples for every $n$ which is not a prime power. We also provide counterexamples relevant to a wider class of fair or envy-free partition problems when $n$ is odd and not a prime power.","lang":"eng"}],"oa_version":"Preprint","author":[{"full_name":"Avvakumov, Sergey","last_name":"Avvakumov","first_name":"Sergey","id":"3827DAC8-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Roman","full_name":"Karasev, Roman","last_name":"Karasev"}],"external_id":{"arxiv":["1907.11183"]},"article_processing_charge":"No","department":[{"_id":"UlWa"}],"title":"Envy-free division using mapping degree","date_updated":"2023-09-07T13:12:17Z","citation":{"short":"S. Avvakumov, R. Karasev, ArXiv (n.d.).","ieee":"S. Avvakumov and R. Karasev, “Envy-free division using mapping degree,” arXiv. .","apa":"Avvakumov, S., & Karasev, R. (n.d.). Envy-free division using mapping degree. arXiv. https://doi.org/10.48550/arXiv.1907.11183","ama":"Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv. doi:10.48550/arXiv.1907.11183","mla":"Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.” ArXiv, 1907.11183, doi:10.48550/arXiv.1907.11183.","ista":"Avvakumov S, Karasev R. Envy-free division using mapping degree. arXiv, 1907.11183.","chicago":"Avvakumov, Sergey, and Roman Karasev. “Envy-Free Division Using Mapping Degree.” ArXiv, n.d. https://doi.org/10.48550/arXiv.1907.11183."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","type":"preprint","status":"public","project":[{"grant_number":"P31312","name":"Algorithms for Embeddings and Homotopy Theory","call_identifier":"FWF","_id":"26611F5C-B435-11E9-9278-68D0E5697425"}],"_id":"8185","article_number":"1907.11183"},{"_id":"7524","status":"public","project":[{"grant_number":"694227","name":"Analysis of quantum many-body systems","_id":"25C6DC12-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"type":"preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2023-09-07T13:12:41Z","citation":{"chicago":"Deuchert, Andreas, Simon Mayer, and Robert Seiringer. “The Free Energy of the Two-Dimensional Dilute Bose Gas. I. Lower Bound.” ArXiv:1910.03372. ArXiv, n.d.","ista":"Deuchert A, Mayer S, Seiringer R. The free energy of the two-dimensional dilute Bose gas. I. Lower bound. arXiv:1910.03372, .","mla":"Deuchert, Andreas, et al. “The Free Energy of the Two-Dimensional Dilute Bose Gas. I. Lower Bound.” ArXiv:1910.03372, ArXiv.","apa":"Deuchert, A., Mayer, S., & Seiringer, R. (n.d.). The free energy of the two-dimensional dilute Bose gas. I. Lower bound. arXiv:1910.03372. ArXiv.","ama":"Deuchert A, Mayer S, Seiringer R. The free energy of the two-dimensional dilute Bose gas. I. Lower bound. arXiv:191003372.","ieee":"A. Deuchert, S. Mayer, and R. Seiringer, “The free energy of the two-dimensional dilute Bose gas. I. Lower bound,” arXiv:1910.03372. ArXiv.","short":"A. Deuchert, S. Mayer, R. Seiringer, ArXiv:1910.03372 (n.d.)."},"title":"The free energy of the two-dimensional dilute Bose gas. I. Lower bound","department":[{"_id":"RoSe"}],"article_processing_charge":"No","author":[{"last_name":"Deuchert","full_name":"Deuchert, Andreas","orcid":"0000-0003-3146-6746","first_name":"Andreas","id":"4DA65CD0-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Mayer","full_name":"Mayer, Simon","first_name":"Simon","id":"30C4630A-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Robert","id":"4AFD0470-F248-11E8-B48F-1D18A9856A87","full_name":"Seiringer, Robert","orcid":"0000-0002-6781-0521","last_name":"Seiringer"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"We prove a lower bound for the free energy (per unit volume) of the two-dimensional Bose gas in the thermodynamic limit. We show that the free energy at density $\\rho$ and inverse temperature $\\beta$ differs from the one of the non-interacting system by the correction term $4 \\pi \\rho^2 |\\ln a^2 \\rho|^{-1} (2 - [1 - \\beta_{\\mathrm{c}}/\\beta]_+^2)$. Here $a$ is the scattering length of the interaction potential, $[\\cdot]_+ = \\max\\{ 0, \\cdot \\}$ and $\\beta_{\\mathrm{c}}$ is the inverse Berezinskii--Kosterlitz--Thouless critical temperature for superfluidity. The result is valid in the dilute limit\r\n$a^2\\rho \\ll 1$ and if $\\beta \\rho \\gtrsim 1$."}],"month":"10","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1910.03372"}],"oa":1,"publisher":"ArXiv","scopus_import":1,"publication":"arXiv:1910.03372","language":[{"iso":"eng"}],"day":"08","year":"2019","publication_status":"draft","date_created":"2020-02-26T08:46:40Z","ec_funded":1,"date_published":"2019-10-08T00:00:00Z","related_material":{"record":[{"relation":"later_version","id":"7790","status":"public"},{"relation":"dissertation_contains","status":"public","id":"7514"}]},"page":"61"},{"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"ista":"Edelsbrunner H, Ölsböck K. 2019. Holes and dependences in an ordered complex. Computer Aided Geometric Design. 73, 1–15.","chicago":"Edelsbrunner, Herbert, and Katharina Ölsböck. “Holes and Dependences in an Ordered Complex.” Computer Aided Geometric Design. Elsevier, 2019. https://doi.org/10.1016/j.cagd.2019.06.003.","ieee":"H. Edelsbrunner and K. Ölsböck, “Holes and dependences in an ordered complex,” Computer Aided Geometric Design, vol. 73. Elsevier, pp. 1–15, 2019.","short":"H. Edelsbrunner, K. Ölsböck, Computer Aided Geometric Design 73 (2019) 1–15.","ama":"Edelsbrunner H, Ölsböck K. Holes and dependences in an ordered complex. Computer Aided Geometric Design. 2019;73:1-15. doi:10.1016/j.cagd.2019.06.003","apa":"Edelsbrunner, H., & Ölsböck, K. (2019). Holes and dependences in an ordered complex. Computer Aided Geometric Design. Elsevier. https://doi.org/10.1016/j.cagd.2019.06.003","mla":"Edelsbrunner, Herbert, and Katharina Ölsböck. “Holes and Dependences in an Ordered Complex.” Computer Aided Geometric Design, vol. 73, Elsevier, 2019, pp. 1–15, doi:10.1016/j.cagd.2019.06.003."},"title":"Holes and dependences in an ordered complex","author":[{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert"},{"first_name":"Katharina","id":"4D4AA390-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4672-8297","full_name":"Ölsböck, Katharina","last_name":"Ölsböck"}],"article_processing_charge":"No","external_id":{"isi":["000485207800001"]},"project":[{"grant_number":"788183","name":"Alpha Shape Theory Extended","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"call_identifier":"FWF","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35","name":"Persistence and stability of geometric complexes"}],"day":"01","publication":"Computer Aided Geometric Design","has_accepted_license":"1","isi":1,"year":"2019","date_published":"2019-08-01T00:00:00Z","doi":"10.1016/j.cagd.2019.06.003","date_created":"2019-07-07T21:59:20Z","page":"1-15","publisher":"Elsevier","quality_controlled":"1","oa":1,"ddc":["000"],"date_updated":"2023-09-07T13:15:29Z","file_date_updated":"2020-07-14T12:47:34Z","department":[{"_id":"HeEd"}],"_id":"6608","status":"public","type":"journal_article","tmp":{"short":"CC BY-NC-ND (4.0)","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","image":"/images/cc_by_nc_nd.png"},"file":[{"creator":"kschuh","date_updated":"2020-07-14T12:47:34Z","file_size":2665013,"date_created":"2019-07-08T15:24:26Z","file_name":"Elsevier_2019_Edelsbrunner.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"6624","checksum":"7c99be505dc7533257d42eb1830cef04"}],"language":[{"iso":"eng"}],"publication_status":"published","related_material":{"record":[{"status":"public","id":"7460","relation":"dissertation_contains"}]},"volume":73,"ec_funded":1,"oa_version":"Published Version","abstract":[{"text":"We use the canonical bases produced by the tri-partition algorithm in (Edelsbrunner and Ölsböck, 2018) to open and close holes in a polyhedral complex, K. In a concrete application, we consider the Delaunay mosaic of a finite set, we let K be an Alpha complex, and we use the persistence diagram of the distance function to guide the hole opening and closing operations. The dependences between the holes define a partial order on the cells in K that characterizes what can and what cannot be constructed using the operations. The relations in this partial order reveal structural information about the underlying filtration of complexes beyond what is expressed by the persistence diagram.","lang":"eng"}],"month":"08","intvolume":" 73","scopus_import":"1"},{"related_material":{"record":[{"id":"7896","status":"public","relation":"dissertation_contains"}]},"ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781450367059"]},"publication_status":"published","month":"06","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/549"}],"oa_version":"Preprint","abstract":[{"lang":"eng","text":"The Fiat-Shamir heuristic transforms a public-coin interactive proof into a non-interactive argument, by replacing the verifier with a cryptographic hash function that is applied to the protocol’s transcript. Constructing hash functions for which this transformation is sound is a central and long-standing open question in cryptography.\r\n\r\nWe show that solving the END−OF−METERED−LINE problem is no easier than breaking the soundness of the Fiat-Shamir transformation when applied to the sumcheck protocol. In particular, if the transformed protocol is sound, then any hard problem in #P gives rise to a hard distribution in the class CLS, which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized games for which it is hard to find a Nash equilibrium, by reducing the inversion of appropriately chosen one-way functions to #SAT.\r\n\r\nOur main technical contribution is a stateful incrementally verifiable procedure that, given a SAT instance over n variables, counts the number of satisfying assignments. This is accomplished via an exponential sequence of small steps, each computable in time poly(n). Incremental verifiability means that each intermediate state includes a sumcheck-based proof of its correctness, and the proof can be updated and verified in time poly(n)."}],"department":[{"_id":"KrPi"}],"date_updated":"2023-09-07T13:15:55Z","status":"public","type":"conference","conference":{"end_date":"2019-06-26","location":"Phoenix, AZ, United States","start_date":"2019-06-23","name":"STOC: Symposium on Theory of Computing"},"_id":"6677","date_published":"2019-06-01T00:00:00Z","doi":"10.1145/3313276.3316400","date_created":"2019-07-24T09:20:53Z","page":"1103-1114","day":"01","publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019","isi":1,"year":"2019","quality_controlled":"1","publisher":"ACM Press","oa":1,"title":"Finding a Nash equilibrium is no easier than breaking Fiat-Shamir","author":[{"last_name":"Choudhuri","full_name":"Choudhuri, Arka Rai","first_name":"Arka Rai"},{"first_name":"Pavel","last_name":"Hubáček","full_name":"Hubáček, Pavel"},{"first_name":"Chethan","id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","last_name":"Kamath Hosdurg","full_name":"Kamath Hosdurg, Chethan"},{"full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Rosen","full_name":"Rosen, Alon","first_name":"Alon"},{"full_name":"Rothblum, Guy N.","last_name":"Rothblum","first_name":"Guy N."}],"external_id":{"isi":["000523199100100"]},"article_processing_charge":"No","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"ieee":"A. R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K. Z. Pietrzak, A. Rosen, and G. N. Rothblum, “Finding a Nash equilibrium is no easier than breaking Fiat-Shamir,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, Phoenix, AZ, United States, 2019, pp. 1103–1114.","short":"A.R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K.Z. Pietrzak, A. Rosen, G.N. Rothblum, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, ACM Press, 2019, pp. 1103–1114.","ama":"Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019. ACM Press; 2019:1103-1114. doi:10.1145/3313276.3316400","apa":"Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen, A., & Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019 (pp. 1103–1114). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3313276.3316400","mla":"Choudhuri, Arka Rai, et al. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, ACM Press, 2019, pp. 1103–14, doi:10.1145/3313276.3316400.","ista":"Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum GN. 2019. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019. STOC: Symposium on Theory of Computing, 1103–1114.","chicago":"Choudhuri, Arka Rai, Pavel Hubáček, Chethan Kamath Hosdurg, Krzysztof Z Pietrzak, Alon Rosen, and Guy N. Rothblum. “Finding a Nash Equilibrium Is No Easier than Breaking Fiat-Shamir.” In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019, 1103–14. ACM Press, 2019. https://doi.org/10.1145/3313276.3316400."},"project":[{"grant_number":"682815","name":"Teaching Old Crypto New Tricks","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"}]},{"project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","author":[{"first_name":"Anna","last_name":"Lubiw","full_name":"Lubiw, Anna"},{"first_name":"Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová","full_name":"Masárová, Zuzana","orcid":"0000-0002-6660-1322"},{"last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"article_processing_charge":"Yes (via OA deal)","external_id":{"isi":["000466130000009"],"arxiv":["1710.02741"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry. Springer Nature, 2019. https://doi.org/10.1007/s00454-018-0035-8.","ista":"Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. 61(4), 880–898.","mla":"Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry, vol. 61, no. 4, Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.","short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61 (2019) 880–898.","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge-labelled triangulations,” Discrete & Computational Geometry, vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.","ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. 2019;61(4):880-898. doi:10.1007/s00454-018-0035-8","apa":"Lubiw, A., Masárová, Z., & Wagner, U. (2019). A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-018-0035-8"},"publisher":"Springer Nature","quality_controlled":"1","oa":1,"date_published":"2019-06-01T00:00:00Z","doi":"10.1007/s00454-018-0035-8","date_created":"2019-02-14T11:54:08Z","page":"880-898","day":"01","publication":"Discrete & Computational Geometry","isi":1,"has_accepted_license":"1","year":"2019","status":"public","type":"journal_article","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"_id":"5986","department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:47:14Z","ddc":["000"],"date_updated":"2023-09-07T13:17:36Z","month":"06","intvolume":" 61","scopus_import":"1","oa_version":"Published Version","abstract":[{"text":"Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.","lang":"eng"}],"issue":"4","related_material":{"record":[{"relation":"earlier_version","id":"683","status":"public"},{"relation":"dissertation_contains","id":"7944","status":"public"}]},"volume":61,"file":[{"file_name":"2018_DiscreteGeometry_Lubiw.pdf","date_created":"2019-02-14T11:57:22Z","file_size":556276,"date_updated":"2020-07-14T12:47:14Z","creator":"dernst","file_id":"5988","checksum":"e1bff88f1d77001b53b78c485ce048d7","content_type":"application/pdf","relation":"main_file","access_level":"open_access"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publication_status":"published"},{"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"type":"journal_article","status":"public","_id":"5886","file_date_updated":"2020-07-14T12:47:13Z","department":[{"_id":"MiLe"}],"date_updated":"2023-09-07T13:16:42Z","ddc":["530"],"scopus_import":"1","month":"01","abstract":[{"text":"Problems involving quantum impurities, in which one or a few particles are interacting with a macroscopic environment, represent a pervasive paradigm, spanning across atomic, molecular, and condensed-matter physics. In this paper we introduce new variational approaches to quantum impurities and apply them to the Fröhlich polaron–a quasiparticle formed out of an electron (or other point-like impurity) in a polar medium, and to the angulon–a quasiparticle formed out of a rotating molecule in a bosonic bath. We benchmark these approaches against established theories, evaluating their accuracy as a function of the impurity-bath coupling.","lang":"eng"}],"oa_version":"Published Version","ec_funded":1,"related_material":{"record":[{"relation":"dissertation_contains","id":"8958","status":"public"}]},"publication_status":"published","publication_identifier":{"issn":["00268976"]},"language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","relation":"main_file","access_level":"open_access","checksum":"178964744b636a6f036372f4f090a657","file_id":"5896","file_size":1309966,"date_updated":"2020-07-14T12:47:13Z","creator":"dernst","file_name":"2019_MolecularPhysics_Li.pdf","date_created":"2019-01-29T08:32:57Z"}],"project":[{"grant_number":"P29902","name":"Quantum rotations in the presence of a many-body environment","_id":"26031614-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"article_processing_charge":"No","external_id":{"isi":["000474641400008"]},"author":[{"last_name":"Li","full_name":"Li, Xiang","first_name":"Xiang","id":"4B7E523C-F248-11E8-B48F-1D18A9856A87"},{"id":"4CA96FD4-F248-11E8-B48F-1D18A9856A87","first_name":"Giacomo","last_name":"Bighin","full_name":"Bighin, Giacomo","orcid":"0000-0001-8823-9777"},{"last_name":"Yakaboylu","full_name":"Yakaboylu, Enderalp","orcid":"0000-0001-5973-0874","id":"38CB71F6-F248-11E8-B48F-1D18A9856A87","first_name":"Enderalp"},{"first_name":"Mikhail","id":"37CB05FA-F248-11E8-B48F-1D18A9856A87","last_name":"Lemeshko","orcid":"0000-0002-6990-7802","full_name":"Lemeshko, Mikhail"}],"title":"Variational approaches to quantum impurities: from the Fröhlich polaron to the angulon","citation":{"ama":"Li X, Bighin G, Yakaboylu E, Lemeshko M. Variational approaches to quantum impurities: from the Fröhlich polaron to the angulon. Molecular Physics. 2019. doi:10.1080/00268976.2019.1567852","apa":"Li, X., Bighin, G., Yakaboylu, E., & Lemeshko, M. (2019). Variational approaches to quantum impurities: from the Fröhlich polaron to the angulon. Molecular Physics. Taylor and Francis. https://doi.org/10.1080/00268976.2019.1567852","ieee":"X. Li, G. Bighin, E. Yakaboylu, and M. Lemeshko, “Variational approaches to quantum impurities: from the Fröhlich polaron to the angulon,” Molecular Physics. Taylor and Francis, 2019.","short":"X. Li, G. Bighin, E. Yakaboylu, M. Lemeshko, Molecular Physics (2019).","mla":"Li, Xiang, et al. “Variational Approaches to Quantum Impurities: From the Fröhlich Polaron to the Angulon.” Molecular Physics, Taylor and Francis, 2019, doi:10.1080/00268976.2019.1567852.","ista":"Li X, Bighin G, Yakaboylu E, Lemeshko M. 2019. Variational approaches to quantum impurities: from the Fröhlich polaron to the angulon. Molecular Physics.","chicago":"Li, Xiang, Giacomo Bighin, Enderalp Yakaboylu, and Mikhail Lemeshko. “Variational Approaches to Quantum Impurities: From the Fröhlich Polaron to the Angulon.” Molecular Physics. Taylor and Francis, 2019. https://doi.org/10.1080/00268976.2019.1567852."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","oa":1,"publisher":"Taylor and Francis","quality_controlled":"1","date_created":"2019-01-27T22:59:10Z","date_published":"2019-01-18T00:00:00Z","doi":"10.1080/00268976.2019.1567852","year":"2019","has_accepted_license":"1","isi":1,"publication":"Molecular Physics","day":"18"},{"quality_controlled":"1","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"day":"01","publication":"35th International Symposium on Computational Geometry","has_accepted_license":"1","year":"2019","date_published":"2019-06-01T00:00:00Z","doi":"10.4230/LIPIcs.SoCG.2019.44","date_created":"2019-06-11T20:09:57Z","page":"44:1-44:20","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ista":"Huszár K, Spreer J. 2019. 3-manifold triangulations with small treewidth. 35th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 129, 44:1-44:20.","chicago":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” In 35th International Symposium on Computational Geometry, 129:44:1-44:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.44.","ieee":"K. Huszár and J. Spreer, “3-manifold triangulations with small treewidth,” in 35th International Symposium on Computational Geometry, Portland, Oregon, United States, 2019, vol. 129, p. 44:1-44:20.","short":"K. Huszár, J. Spreer, in:, 35th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20.","apa":"Huszár, K., & Spreer, J. (2019). 3-manifold triangulations with small treewidth. In 35th International Symposium on Computational Geometry (Vol. 129, p. 44:1-44:20). Portland, Oregon, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2019.44","ama":"Huszár K, Spreer J. 3-manifold triangulations with small treewidth. In: 35th International Symposium on Computational Geometry. Vol 129. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:44:1-44:20. doi:10.4230/LIPIcs.SoCG.2019.44","mla":"Huszár, Kristóf, and Jonathan Spreer. “3-Manifold Triangulations with Small Treewidth.” 35th International Symposium on Computational Geometry, vol. 129, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 44:1-44:20, doi:10.4230/LIPIcs.SoCG.2019.44."},"title":"3-manifold triangulations with small treewidth","author":[{"id":"33C26278-F248-11E8-B48F-1D18A9856A87","first_name":"Kristóf","full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","last_name":"Huszár"},{"full_name":"Spreer, Jonathan","last_name":"Spreer","first_name":"Jonathan"}],"article_processing_charge":"No","external_id":{"arxiv":["1812.05528"]},"oa_version":"Published Version","abstract":[{"text":"Motivated by fixed-parameter tractable (FPT) problems in computational topology, we consider the treewidth tw(M) of a compact, connected 3-manifold M, defined to be the minimum treewidth of the face pairing graph of any triangulation T of M. In this setting the relationship between the topology of a 3-manifold and its treewidth is of particular interest. First, as a corollary of work of Jaco and Rubinstein, we prove that for any closed, orientable 3-manifold M the treewidth tw(M) is at most 4g(M)-2, where g(M) denotes Heegaard genus of M. In combination with our earlier work with Wagner, this yields that for non-Haken manifolds the Heegaard genus and the treewidth are within a constant factor. Second, we characterize all 3-manifolds of treewidth one: These are precisely the lens spaces and a single other Seifert fibered space. Furthermore, we show that all remaining orientable Seifert fibered spaces over the 2-sphere or a non-orientable surface have treewidth two. In particular, for every spherical 3-manifold we exhibit a triangulation of treewidth at most two. Our results further validate the parameter of treewidth (and other related parameters such as cutwidth or congestion) to be useful for topological computing, and also shed more light on the scope of existing FPT-algorithms in the field.","lang":"eng"}],"month":"06","intvolume":" 129","alternative_title":["LIPIcs"],"scopus_import":"1","file":[{"creator":"kschuh","date_updated":"2020-07-14T12:47:33Z","file_size":905885,"date_created":"2019-06-12T06:45:33Z","file_name":"2019_LIPIcs-Huszar.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"29d18c435368468aa85823dabb157e43","file_id":"6557"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1868-8969"],"isbn":["978-3-95977-104-7"]},"publication_status":"published","related_material":{"record":[{"status":"public","id":"8032","relation":"part_of_dissertation"}]},"volume":129,"_id":"6556","status":"public","keyword":["computational 3-manifold topology","fixed-parameter tractability","layered triangulations","structural graph theory","treewidth","cutwidth","Heegaard genus"],"type":"conference","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"conference":{"start_date":"2019-06-18","location":"Portland, Oregon, United States","end_date":"2019-06-21","name":"SoCG: Symposium on Computational Geometry"},"ddc":["516"],"date_updated":"2023-09-07T13:18:26Z","file_date_updated":"2020-07-14T12:47:33Z","department":[{"_id":"UlWa"}]},{"title":"On the treewidth of triangulated 3-manifolds","author":[{"last_name":"Huszár","full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","id":"33C26278-F248-11E8-B48F-1D18A9856A87","first_name":"Kristóf"},{"first_name":"Jonathan","full_name":"Spreer, Jonathan","last_name":"Spreer"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"}],"article_processing_charge":"No","external_id":{"arxiv":["1712.00434"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 2019;10(2):70–98. doi:10.20382/JOGC.V10I2A5","apa":"Huszár, K., Spreer, J., & Wagner, U. (2019). On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. Computational Geometry Laborartoy. https://doi.org/10.20382/JOGC.V10I2A5","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” Journal of Computational Geometry, vol. 10, no. 2. Computational Geometry Laborartoy, pp. 70–98, 2019.","short":"K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019) 70–98.","mla":"Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” Journal of Computational Geometry, vol. 10, no. 2, Computational Geometry Laborartoy, 2019, pp. 70–98, doi:10.20382/JOGC.V10I2A5.","ista":"Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds.” Journal of Computational Geometry. Computational Geometry Laborartoy, 2019. https://doi.org/10.20382/JOGC.V10I2A5."},"doi":"10.20382/JOGC.V10I2A5","date_published":"2019-11-01T00:00:00Z","date_created":"2019-11-23T12:14:09Z","page":"70–98","day":"01","publication":"Journal of Computational Geometry","has_accepted_license":"1","year":"2019","quality_controlled":"1","publisher":"Computational Geometry Laborartoy","oa":1,"department":[{"_id":"UlWa"}],"file_date_updated":"2020-07-14T12:47:49Z","ddc":["514"],"date_updated":"2023-09-07T13:18:26Z","status":"public","type":"journal_article","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"_id":"7093","volume":10,"issue":"2","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"285"},{"relation":"part_of_dissertation","status":"public","id":"8032"}]},"file":[{"date_updated":"2020-07-14T12:47:49Z","file_size":857590,"creator":"khuszar","date_created":"2019-11-23T12:35:16Z","file_name":"479-1917-1-PB.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"7094","checksum":"c872d590d38d538404782bca20c4c3f5"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["1920-180X"]},"publication_status":"published","month":"11","intvolume":" 10","oa_version":"Published Version","abstract":[{"text":"In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how \"simple\" or \"thin\" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth.\r\nIn view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs).\r\nWe derive these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann, Schultens and Saito by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 18(k+1) (resp. 4(3k+1)).","lang":"eng"}]},{"publisher":"Springer Nature","quality_controlled":"1","oa":1,"doi":"10.1038/s41467-019-13702-4","date_published":"2019-12-17T00:00:00Z","date_created":"2019-12-20T12:22:57Z","day":"17","publication":"Nature Communications","isi":1,"has_accepted_license":"1","year":"2019","project":[{"call_identifier":"H2020","_id":"2595697A-B435-11E9-9278-68D0E5697425","grant_number":"679239","name":"Self-Organization of the Bacterial Cell"},{"name":"Reconstitution of Bacterial Cell Division Using Purified Components","_id":"260D98C8-B435-11E9-9278-68D0E5697425"}],"article_number":"5744","title":"Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA","author":[{"last_name":"Dos Santos Caldas","orcid":"0000-0001-6730-4461","full_name":"Dos Santos Caldas, Paulo R","id":"38FCDB4C-F248-11E8-B48F-1D18A9856A87","first_name":"Paulo R"},{"first_name":"Maria D","id":"319AA9CE-F248-11E8-B48F-1D18A9856A87","last_name":"Lopez Pelegrin","full_name":"Lopez Pelegrin, Maria D"},{"full_name":"Pearce, Daniel J. G.","last_name":"Pearce","first_name":"Daniel J. G."},{"id":"3EA1010E-F248-11E8-B48F-1D18A9856A87","first_name":"Nazmi B","last_name":"Budanur","full_name":"Budanur, Nazmi B","orcid":"0000-0003-0423-5010"},{"first_name":"Jan","full_name":"Brugués, Jan","last_name":"Brugués"},{"id":"462D4284-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Loose","full_name":"Loose, Martin","orcid":"0000-0001-7309-9724"}],"article_processing_charge":"No","external_id":{"isi":["000503009300001"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"apa":"Dos Santos Caldas, P. R., Lopez Pelegrin, M. D., Pearce, D. J. G., Budanur, N. B., Brugués, J., & Loose, M. (2019). Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA. Nature Communications. Springer Nature. https://doi.org/10.1038/s41467-019-13702-4","ama":"Dos Santos Caldas PR, Lopez Pelegrin MD, Pearce DJG, Budanur NB, Brugués J, Loose M. Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA. Nature Communications. 2019;10. doi:10.1038/s41467-019-13702-4","short":"P.R. Dos Santos Caldas, M.D. Lopez Pelegrin, D.J.G. Pearce, N.B. Budanur, J. Brugués, M. Loose, Nature Communications 10 (2019).","ieee":"P. R. Dos Santos Caldas, M. D. Lopez Pelegrin, D. J. G. Pearce, N. B. Budanur, J. Brugués, and M. Loose, “Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA,” Nature Communications, vol. 10. Springer Nature, 2019.","mla":"Dos Santos Caldas, Paulo R., et al. “Cooperative Ordering of Treadmilling Filaments in Cytoskeletal Networks of FtsZ and Its Crosslinker ZapA.” Nature Communications, vol. 10, 5744, Springer Nature, 2019, doi:10.1038/s41467-019-13702-4.","ista":"Dos Santos Caldas PR, Lopez Pelegrin MD, Pearce DJG, Budanur NB, Brugués J, Loose M. 2019. Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA. Nature Communications. 10, 5744.","chicago":"Dos Santos Caldas, Paulo R, Maria D Lopez Pelegrin, Daniel J. G. Pearce, Nazmi B Budanur, Jan Brugués, and Martin Loose. “Cooperative Ordering of Treadmilling Filaments in Cytoskeletal Networks of FtsZ and Its Crosslinker ZapA.” Nature Communications. Springer Nature, 2019. https://doi.org/10.1038/s41467-019-13702-4."},"month":"12","intvolume":" 10","scopus_import":"1","oa_version":"Published Version","acknowledged_ssus":[{"_id":"LifeSc"},{"_id":"Bio"}],"abstract":[{"text":"During bacterial cell division, the tubulin-homolog FtsZ forms a ring-like structure at the center of the cell. This Z-ring not only organizes the division machinery, but treadmilling of FtsZ filaments was also found to play a key role in distributing proteins at the division site. What regulates the architecture, dynamics and stability of the Z-ring is currently unknown, but FtsZ-associated proteins are known to play an important role. Here, using an in vitro reconstitution approach, we studied how the well-conserved protein ZapA affects FtsZ treadmilling and filament organization into large-scale patterns. Using high-resolution fluorescence microscopy and quantitative image analysis, we found that ZapA cooperatively increases the spatial order of the filament network, but binds only transiently to FtsZ filaments and has no effect on filament length and treadmilling velocity. Together, our data provides a model for how FtsZ-associated proteins can increase the precision and stability of the bacterial cell division machinery in a switch-like manner.","lang":"eng"}],"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"8358"}]},"volume":10,"ec_funded":1,"file":[{"file_name":"2019_NatureComm_Caldas.pdf","date_created":"2019-12-23T07:34:56Z","creator":"dernst","file_size":8488733,"date_updated":"2020-07-14T12:47:53Z","checksum":"a1b44b427ba341383197790d0e8789fa","file_id":"7208","relation":"main_file","access_level":"open_access","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"publication_identifier":{"issn":["2041-1723"]},"publication_status":"published","status":"public","article_type":"original","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"_id":"7197","file_date_updated":"2020-07-14T12:47:53Z","department":[{"_id":"MaLo"},{"_id":"BjHo"}],"ddc":["570"],"date_updated":"2023-09-07T13:18:51Z"},{"project":[{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","call_identifier":"FWF","_id":"2584A770-B435-11E9-9278-68D0E5697425"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425"}],"article_number":"138","author":[{"last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef","id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef"},{"first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87","last_name":"Pavlogiannis","full_name":"Pavlogiannis, Andreas","orcid":"0000-0002-8943-0722"},{"last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"full_name":"Nowak, Martin A.","last_name":"Nowak","first_name":"Martin A."}],"external_id":{"pmid":["31044163"],"isi":["000465425700006"]},"article_processing_charge":"No","title":"Population structure determines the tradeoff between fixation probability and fixation time","citation":{"ama":"Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Population structure determines the tradeoff between fixation probability and fixation time. Communications Biology. 2019;2. doi:10.1038/s42003-019-0373-y","apa":"Tkadlec, J., Pavlogiannis, A., Chatterjee, K., & Nowak, M. A. (2019). Population structure determines the tradeoff between fixation probability and fixation time. Communications Biology. Springer Nature. https://doi.org/10.1038/s42003-019-0373-y","short":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, Communications Biology 2 (2019).","ieee":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, and M. A. Nowak, “Population structure determines the tradeoff between fixation probability and fixation time,” Communications Biology, vol. 2. Springer Nature, 2019.","mla":"Tkadlec, Josef, et al. “Population Structure Determines the Tradeoff between Fixation Probability and Fixation Time.” Communications Biology, vol. 2, 138, Springer Nature, 2019, doi:10.1038/s42003-019-0373-y.","ista":"Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. 2019. Population structure determines the tradeoff between fixation probability and fixation time. Communications Biology. 2, 138.","chicago":"Tkadlec, Josef, Andreas Pavlogiannis, Krishnendu Chatterjee, and Martin A. Nowak. “Population Structure Determines the Tradeoff between Fixation Probability and Fixation Time.” Communications Biology. Springer Nature, 2019. https://doi.org/10.1038/s42003-019-0373-y."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publisher":"Springer Nature","quality_controlled":"1","oa":1,"doi":"10.1038/s42003-019-0373-y","date_published":"2019-04-23T00:00:00Z","date_created":"2019-12-23T13:36:50Z","has_accepted_license":"1","isi":1,"year":"2019","day":"23","publication":"Communications Biology","type":"journal_article","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"status":"public","_id":"7210","department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:47:53Z","date_updated":"2023-09-07T13:19:22Z","ddc":["000"],"scopus_import":"1","month":"04","intvolume":" 2","abstract":[{"lang":"eng","text":"The rate of biological evolution depends on the fixation probability and on the fixation time of new mutants. Intensive research has focused on identifying population structures that augment the fixation probability of advantageous mutants. But these amplifiers of natural selection typically increase fixation time. Here we study population structures that achieve a tradeoff between fixation probability and time. First, we show that no amplifiers can have an asymptotically lower absorption time than the well-mixed population. Then we design population structures that substantially augment the fixation probability with just a minor increase in fixation time. Finally, we show that those structures enable higher effective rate of evolution than the well-mixed population provided that the rate of generating advantageous mutants is relatively low. Our work sheds light on how population structure affects the rate of evolution. Moreover, our structures could be useful for lab-based, medical, or industrial applications of evolutionary optimization."}],"oa_version":"Published Version","pmid":1,"related_material":{"record":[{"status":"public","id":"7196","relation":"part_of_dissertation"}]},"volume":2,"ec_funded":1,"publication_identifier":{"issn":["2399-3642"]},"publication_status":"published","file":[{"date_created":"2019-12-23T13:39:30Z","file_name":"2019_CommBio_Tkadlec.pdf","creator":"dernst","date_updated":"2020-07-14T12:47:53Z","file_size":1670274,"checksum":"d1a69bfe73767e4246f0a38e4e1554dd","file_id":"7211","access_level":"open_access","relation":"main_file","content_type":"application/pdf"}],"language":[{"iso":"eng"}]}]