--- _id: '63' abstract: - lang: eng text: African cichlids display a remarkable assortment of jaw morphologies, pigmentation patterns, and mating behaviors. In addition to this previously documented diversity, recent studies have documented a rich diversity of sex chromosomes within these fishes. Here we review the known sex-determination network within vertebrates, and the extraordinary number of sex chromosomes systems segregating in African cichlids. We also propose a model for understanding the unusual number of sex chromosome systems within this clade. acknowledgement: NSF DEB-1830753 and ISTPlus Fellowship article_number: '480' article_processing_charge: No author: - first_name: William J full_name: Gammerdinger, William J id: 3A7E01BC-F248-11E8-B48F-1D18A9856A87 last_name: Gammerdinger orcid: 0000-0001-9638-1220 - first_name: Thomas full_name: Kocher, Thomas last_name: Kocher citation: ama: Gammerdinger WJ, Kocher T. Unusual diversity of sex chromosomes in African cichlid fishes. Genes. 2018;9(10). doi:10.3390/genes9100480 apa: Gammerdinger, W. J., & Kocher, T. (2018). Unusual diversity of sex chromosomes in African cichlid fishes. Genes. MDPI AG. https://doi.org/10.3390/genes9100480 chicago: Gammerdinger, William J, and Thomas Kocher. “Unusual Diversity of Sex Chromosomes in African Cichlid Fishes.” Genes. MDPI AG, 2018. https://doi.org/10.3390/genes9100480. ieee: W. J. Gammerdinger and T. Kocher, “Unusual diversity of sex chromosomes in African cichlid fishes,” Genes, vol. 9, no. 10. MDPI AG, 2018. ista: Gammerdinger WJ, Kocher T. 2018. Unusual diversity of sex chromosomes in African cichlid fishes. Genes. 9(10), 480. mla: Gammerdinger, William J., and Thomas Kocher. “Unusual Diversity of Sex Chromosomes in African Cichlid Fishes.” Genes, vol. 9, no. 10, 480, MDPI AG, 2018, doi:10.3390/genes9100480. short: W.J. Gammerdinger, T. Kocher, Genes 9 (2018). date_created: 2018-12-11T11:44:26Z date_published: 2018-10-04T00:00:00Z date_updated: 2023-09-19T10:37:03Z day: '04' ddc: - '570' department: - _id: BeVi doi: 10.3390/genes9100480 ec_funded: 1 external_id: isi: - '000448656700018' file: - access_level: open_access checksum: bec527692e2c9b56919c0429634ff337 content_type: application/pdf creator: dernst date_created: 2018-12-18T09:54:46Z date_updated: 2020-07-14T12:47:27Z file_id: '5743' file_name: 2018_Genes_Gammerdinger.pdf file_size: 1415791 relation: main_file file_date_updated: 2020-07-14T12:47:27Z has_accepted_license: '1' intvolume: ' 9' isi: 1 issue: '10' language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ month: '10' oa: 1 oa_version: Published Version project: - _id: 25681D80-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '291734' name: International IST Postdoc Fellowship Programme publication: Genes publication_status: published publisher: MDPI AG publist_id: '7991' quality_controlled: '1' scopus_import: '1' status: public title: Unusual diversity of sex chromosomes in African cichlid fishes tmp: image: /images/cc_by.png legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0) short: CC BY (4.0) type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 9 year: '2018' ... --- _id: '296' abstract: - lang: eng text: The thermodynamic description of many-particle systems rests on the assumption of ergodicity, the ability of a system to explore all allowed configurations in the phase space. Recent studies on many-body localization have revealed the existence of systems that strongly violate ergodicity in the presence of quenched disorder. Here, we demonstrate that ergodicity can be weakly broken by a different mechanism, arising from the presence of special eigenstates in the many-body spectrum that are reminiscent of quantum scars in chaotic non-interacting systems. In the single-particle case, quantum scars correspond to wavefunctions that concentrate in the vicinity of unstable periodic classical trajectories. We show that many-body scars appear in the Fibonacci chain, a model with a constrained local Hilbert space that has recently been experimentally realized in a Rydberg-atom quantum simulator. The quantum scarred eigenstates are embedded throughout the otherwise thermalizing many-body spectrum but lead to direct experimental signatures, as we show for periodic recurrences that reproduce those observed in the experiment. Our results suggest that scarred many-body bands give rise to a new universality class of quantum dynamics, opening up opportunities for the creation of novel states with long-lived coherence in systems that are now experimentally realizable. acknowledgement: C.J.T., A.M. and Z.P. acknowledge support from EPSRC grants EP/P009409/1 and EP/M50807X/1, and Royal Society Research Grant RG160635. D.A. acknowledges support from the Swiss National Science Foundation. article_processing_charge: No article_type: original author: - first_name: Christopher full_name: Turner, Christopher last_name: Turner - first_name: Alexios full_name: Michailidis, Alexios id: 36EBAD38-F248-11E8-B48F-1D18A9856A87 last_name: Michailidis orcid: 0000-0002-8443-1064 - first_name: Dmitry full_name: Abanin, Dmitry last_name: Abanin - first_name: Maksym full_name: Serbyn, Maksym id: 47809E7E-F248-11E8-B48F-1D18A9856A87 last_name: Serbyn orcid: 0000-0002-2399-5827 - first_name: Zlatko full_name: Papić, Zlatko last_name: Papić citation: ama: Turner C, Michailidis A, Abanin D, Serbyn M, Papić Z. Weak ergodicity breaking from quantum many-body scars. Nature Physics. 2018;14:745-749. doi:10.1038/s41567-018-0137-5 apa: Turner, C., Michailidis, A., Abanin, D., Serbyn, M., & Papić, Z. (2018). Weak ergodicity breaking from quantum many-body scars. Nature Physics. Nature Publishing Group. https://doi.org/10.1038/s41567-018-0137-5 chicago: Turner, Christopher, Alexios Michailidis, Dmitry Abanin, Maksym Serbyn, and Zlatko Papić. “Weak Ergodicity Breaking from Quantum Many-Body Scars.” Nature Physics. Nature Publishing Group, 2018. https://doi.org/10.1038/s41567-018-0137-5. ieee: C. Turner, A. Michailidis, D. Abanin, M. Serbyn, and Z. Papić, “Weak ergodicity breaking from quantum many-body scars,” Nature Physics, vol. 14. Nature Publishing Group, pp. 745–749, 2018. ista: Turner C, Michailidis A, Abanin D, Serbyn M, Papić Z. 2018. Weak ergodicity breaking from quantum many-body scars. Nature Physics. 14, 745–749. mla: Turner, Christopher, et al. “Weak Ergodicity Breaking from Quantum Many-Body Scars.” Nature Physics, vol. 14, Nature Publishing Group, 2018, pp. 745–49, doi:10.1038/s41567-018-0137-5. short: C. Turner, A. Michailidis, D. Abanin, M. Serbyn, Z. Papić, Nature Physics 14 (2018) 745–749. date_created: 2018-12-11T11:45:40Z date_published: 2018-05-14T00:00:00Z date_updated: 2023-09-19T10:37:55Z day: '14' department: - _id: MaSe doi: 10.1038/s41567-018-0137-5 external_id: isi: - '000438253600028' intvolume: ' 14' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: http://eprints.whiterose.ac.uk/130860/ month: '05' oa: 1 oa_version: Submitted Version page: 745 - 749 publication: Nature Physics publication_status: published publisher: Nature Publishing Group publist_id: '7585' quality_controlled: '1' scopus_import: '1' status: public title: Weak ergodicity breaking from quantum many-body scars type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 14 year: '2018' ... --- _id: '607' abstract: - lang: eng text: We study the Fokker-Planck equation derived in the large system limit of the Markovian process describing the dynamics of quantitative traits. The Fokker-Planck equation is posed on a bounded domain and its transport and diffusion coefficients vanish on the domain's boundary. We first argue that, despite this degeneracy, the standard no-flux boundary condition is valid. We derive the weak formulation of the problem and prove the existence and uniqueness of its solutions by constructing the corresponding contraction semigroup on a suitable function space. Then, we prove that for the parameter regime with high enough mutation rate the problem exhibits a positive spectral gap, which implies exponential convergence to equilibrium.Next, we provide a simple derivation of the so-called Dynamic Maximum Entropy (DynMaxEnt) method for approximation of observables (moments) of the Fokker-Planck solution, which can be interpreted as a nonlinear Galerkin approximation. The limited applicability of the DynMaxEnt method inspires us to introduce its modified version that is valid for the whole range of admissible parameters. Finally, we present several numerical experiments to demonstrate the performance of both the original and modified DynMaxEnt methods. We observe that in the parameter regimes where both methods are valid, the modified one exhibits slightly better approximation properties compared to the original one. acknowledgement: "JH and PM are funded by KAUST baseline funds and grant no. 1000000193 .\r\nWe thank Nicholas Barton (IST Austria) for his useful comments and suggestions. \r\n\r\n" article_processing_charge: No author: - first_name: Katarina full_name: Bodova, Katarina id: 2BA24EA0-F248-11E8-B48F-1D18A9856A87 last_name: Bodova orcid: 0000-0002-7214-0171 - first_name: Jan full_name: Haskovec, Jan last_name: Haskovec - first_name: Peter full_name: Markowich, Peter last_name: Markowich citation: ama: 'Bodova K, Haskovec J, Markowich P. Well posedness and maximum entropy approximation for the dynamics of quantitative traits. Physica D: Nonlinear Phenomena. 2018;376-377:108-120. doi:10.1016/j.physd.2017.10.015' apa: 'Bodova, K., Haskovec, J., & Markowich, P. (2018). Well posedness and maximum entropy approximation for the dynamics of quantitative traits. Physica D: Nonlinear Phenomena. Elsevier. https://doi.org/10.1016/j.physd.2017.10.015' chicago: 'Bodova, Katarina, Jan Haskovec, and Peter Markowich. “Well Posedness and Maximum Entropy Approximation for the Dynamics of Quantitative Traits.” Physica D: Nonlinear Phenomena. Elsevier, 2018. https://doi.org/10.1016/j.physd.2017.10.015.' ieee: 'K. Bodova, J. Haskovec, and P. Markowich, “Well posedness and maximum entropy approximation for the dynamics of quantitative traits,” Physica D: Nonlinear Phenomena, vol. 376–377. Elsevier, pp. 108–120, 2018.' ista: 'Bodova K, Haskovec J, Markowich P. 2018. Well posedness and maximum entropy approximation for the dynamics of quantitative traits. Physica D: Nonlinear Phenomena. 376–377, 108–120.' mla: 'Bodova, Katarina, et al. “Well Posedness and Maximum Entropy Approximation for the Dynamics of Quantitative Traits.” Physica D: Nonlinear Phenomena, vol. 376–377, Elsevier, 2018, pp. 108–20, doi:10.1016/j.physd.2017.10.015.' short: 'K. Bodova, J. Haskovec, P. Markowich, Physica D: Nonlinear Phenomena 376–377 (2018) 108–120.' date_created: 2018-12-11T11:47:28Z date_published: 2018-08-01T00:00:00Z date_updated: 2023-09-19T10:38:34Z day: '01' department: - _id: NiBa - _id: GaTk doi: 10.1016/j.physd.2017.10.015 external_id: arxiv: - '1704.08757' isi: - '000437962900012' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1704.08757 month: '08' oa: 1 oa_version: Submitted Version page: 108-120 publication: 'Physica D: Nonlinear Phenomena' publication_status: published publisher: Elsevier publist_id: '7198' quality_controlled: '1' scopus_import: '1' status: public title: Well posedness and maximum entropy approximation for the dynamics of quantitative traits type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 376-377 year: '2018' ... --- _id: '294' abstract: - lang: eng text: We developed a method to calculate two-photon processes in quantum mechanics that replaces the infinite summation over the intermediate states by a perturbation expansion. This latter consists of a series of commutators that involve position, momentum, and Hamiltonian quantum operators. We analyzed several single- and many-particle cases for which a closed-form solution to the perturbation expansion exists, as well as more complicated cases for which a solution is found by convergence. Throughout the article, Rayleigh and Raman scattering are taken as examples of two-photon processes. The present method provides a clear distinction between the Thomson scattering, regarded as classical scattering, and quantum contributions. Such a distinction lets us derive general results concerning light scattering. Finally, possible extensions to the developed formalism are discussed. article_processing_charge: No author: - first_name: Filippo full_name: Fratini, Filippo last_name: Fratini - first_name: Laleh full_name: Safari, Laleh id: 3C325E5E-F248-11E8-B48F-1D18A9856A87 last_name: Safari - first_name: Pedro full_name: Amaro, Pedro last_name: Amaro - first_name: José full_name: Santos, José last_name: Santos citation: ama: Fratini F, Safari L, Amaro P, Santos J. Two-photon processes based on quantum commutators. Physical Review A - Atomic, Molecular, and Optical Physics. 2018;97(4). doi:10.1103/PhysRevA.97.043842 apa: Fratini, F., Safari, L., Amaro, P., & Santos, J. (2018). Two-photon processes based on quantum commutators. Physical Review A - Atomic, Molecular, and Optical Physics. American Physical Society. https://doi.org/10.1103/PhysRevA.97.043842 chicago: Fratini, Filippo, Laleh Safari, Pedro Amaro, and José Santos. “Two-Photon Processes Based on Quantum Commutators.” Physical Review A - Atomic, Molecular, and Optical Physics. American Physical Society, 2018. https://doi.org/10.1103/PhysRevA.97.043842. ieee: F. Fratini, L. Safari, P. Amaro, and J. Santos, “Two-photon processes based on quantum commutators,” Physical Review A - Atomic, Molecular, and Optical Physics, vol. 97, no. 4. American Physical Society, 2018. ista: Fratini F, Safari L, Amaro P, Santos J. 2018. Two-photon processes based on quantum commutators. Physical Review A - Atomic, Molecular, and Optical Physics. 97(4). mla: Fratini, Filippo, et al. “Two-Photon Processes Based on Quantum Commutators.” Physical Review A - Atomic, Molecular, and Optical Physics, vol. 97, no. 4, American Physical Society, 2018, doi:10.1103/PhysRevA.97.043842. short: F. Fratini, L. Safari, P. Amaro, J. Santos, Physical Review A - Atomic, Molecular, and Optical Physics 97 (2018). date_created: 2018-12-11T11:45:40Z date_published: 2018-04-18T00:00:00Z date_updated: 2023-09-19T10:17:56Z day: '18' department: - _id: MiLe doi: 10.1103/PhysRevA.97.043842 ec_funded: 1 external_id: arxiv: - '1801.06892' isi: - '000430296800008' intvolume: ' 97' isi: 1 issue: '4' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1801.06892 month: '04' oa: 1 oa_version: Submitted Version project: - _id: 25681D80-B435-11E9-9278-68D0E5697425 call_identifier: FP7 grant_number: '291734' name: International IST Postdoc Fellowship Programme publication: Physical Review A - Atomic, Molecular, and Optical Physics publication_status: published publisher: American Physical Society publist_id: '7587' quality_controlled: '1' scopus_import: '1' status: public title: Two-photon processes based on quantum commutators type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 97 year: '2018' ... --- _id: '606' abstract: - lang: eng text: We establish the existence of a global solution for a new family of fluid-like equations, which are obtained in certain regimes in as the mean-field evolution of the supercurrent density in a (2D section of a) type-II superconductor with pinning and with imposed electric current. We also consider general vortex-sheet initial data, and investigate the uniqueness and regularity properties of the solution. For some choice of parameters, the equation under investigation coincides with the so-called lake equation from 2D shallow water fluid dynamics, and our analysis then leads to a new existence result for rough initial data. acknowledgement: "The work of the author is supported by F.R.S.-FNRS ( Fonds de la Recherche Scientifique - FNRS ) through a Research Fellowship.\r\n\r\n" article_processing_charge: No author: - first_name: Mitia full_name: Duerinckx, Mitia last_name: Duerinckx - first_name: Julian L full_name: Fischer, Julian L id: 2C12A0B0-F248-11E8-B48F-1D18A9856A87 last_name: Fischer orcid: 0000-0002-0479-558X citation: ama: Duerinckx M, Fischer JL. Well-posedness for mean-field evolutions arising in superconductivity. Annales de l’Institut Henri Poincare (C) Non Linear Analysis. 2018;35(5):1267-1319. doi:10.1016/j.anihpc.2017.11.004 apa: Duerinckx, M., & Fischer, J. L. (2018). Well-posedness for mean-field evolutions arising in superconductivity. Annales de l’Institut Henri Poincare (C) Non Linear Analysis. Elsevier. https://doi.org/10.1016/j.anihpc.2017.11.004 chicago: Duerinckx, Mitia, and Julian L Fischer. “Well-Posedness for Mean-Field Evolutions Arising in Superconductivity.” Annales de l’Institut Henri Poincare (C) Non Linear Analysis. Elsevier, 2018. https://doi.org/10.1016/j.anihpc.2017.11.004. ieee: M. Duerinckx and J. L. Fischer, “Well-posedness for mean-field evolutions arising in superconductivity,” Annales de l’Institut Henri Poincare (C) Non Linear Analysis, vol. 35, no. 5. Elsevier, pp. 1267–1319, 2018. ista: Duerinckx M, Fischer JL. 2018. Well-posedness for mean-field evolutions arising in superconductivity. Annales de l’Institut Henri Poincare (C) Non Linear Analysis. 35(5), 1267–1319. mla: Duerinckx, Mitia, and Julian L. Fischer. “Well-Posedness for Mean-Field Evolutions Arising in Superconductivity.” Annales de l’Institut Henri Poincare (C) Non Linear Analysis, vol. 35, no. 5, Elsevier, 2018, pp. 1267–319, doi:10.1016/j.anihpc.2017.11.004. short: M. Duerinckx, J.L. Fischer, Annales de l’Institut Henri Poincare (C) Non Linear Analysis 35 (2018) 1267–1319. date_created: 2018-12-11T11:47:27Z date_published: 2018-08-01T00:00:00Z date_updated: 2023-09-19T10:39:09Z day: '01' department: - _id: JuFi doi: 10.1016/j.anihpc.2017.11.004 external_id: arxiv: - '1607.00268' isi: - '000437975500005' intvolume: ' 35' isi: 1 issue: '5' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1607.00268 month: '08' oa: 1 oa_version: Submitted Version page: 1267-1319 publication: Annales de l'Institut Henri Poincare (C) Non Linear Analysis publication_status: published publisher: Elsevier publist_id: '7199' quality_controlled: '1' scopus_import: '1' status: public title: Well-posedness for mean-field evolutions arising in superconductivity type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 35 year: '2018' ... --- _id: '5959' abstract: - lang: eng text: Formalizing properties of systems with continuous dynamics is a challenging task. In this paper, we propose a formal framework for specifying and monitoring rich temporal properties of real-valued signals. We introduce signal first-order logic (SFO) as a specification language that combines first-order logic with linear-real arithmetic and unary function symbols interpreted as piecewise-linear signals. We first show that while the satisfiability problem for SFO is undecidable, its membership and monitoring problems are decidable. We develop an offline monitoring procedure for SFO that has polynomial complexity in the size of the input trace and the specification, for a fixed number of quantifiers and function symbols. We show that the algorithm has computation time linear in the size of the input trace for the important fragment of bounded-response specifications interpreted over input traces with finite variability. We can use our results to extend signal temporal logic with first-order quantifiers over time and value parameters, while preserving its efficient monitoring. We finally demonstrate the practical appeal of our logic through a case study in the micro-electronics domain. article_processing_charge: No author: - first_name: Alexey full_name: Bakhirkin, Alexey last_name: Bakhirkin - first_name: Thomas full_name: Ferrere, Thomas id: 40960E6E-F248-11E8-B48F-1D18A9856A87 last_name: Ferrere orcid: 0000-0001-5199-3143 - first_name: Thomas A full_name: Henzinger, Thomas A id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 - first_name: Deian full_name: Nickovicl, Deian last_name: Nickovicl citation: ama: 'Bakhirkin A, Ferrere T, Henzinger TA, Nickovicl D. Keynote: The first-order logic of signals. In: 2018 International Conference on Embedded Software. IEEE; 2018:1-10. doi:10.1109/emsoft.2018.8537203' apa: 'Bakhirkin, A., Ferrere, T., Henzinger, T. A., & Nickovicl, D. (2018). Keynote: The first-order logic of signals. In 2018 International Conference on Embedded Software (pp. 1–10). Turin, Italy: IEEE. https://doi.org/10.1109/emsoft.2018.8537203' chicago: 'Bakhirkin, Alexey, Thomas Ferrere, Thomas A Henzinger, and Deian Nickovicl. “Keynote: The First-Order Logic of Signals.” In 2018 International Conference on Embedded Software, 1–10. IEEE, 2018. https://doi.org/10.1109/emsoft.2018.8537203.' ieee: 'A. Bakhirkin, T. Ferrere, T. A. Henzinger, and D. Nickovicl, “Keynote: The first-order logic of signals,” in 2018 International Conference on Embedded Software, Turin, Italy, 2018, pp. 1–10.' ista: 'Bakhirkin A, Ferrere T, Henzinger TA, Nickovicl D. 2018. Keynote: The first-order logic of signals. 2018 International Conference on Embedded Software. EMSOFT: International Conference on Embedded Software, 1–10.' mla: 'Bakhirkin, Alexey, et al. “Keynote: The First-Order Logic of Signals.” 2018 International Conference on Embedded Software, IEEE, 2018, pp. 1–10, doi:10.1109/emsoft.2018.8537203.' short: A. Bakhirkin, T. Ferrere, T.A. Henzinger, D. Nickovicl, in:, 2018 International Conference on Embedded Software, IEEE, 2018, pp. 1–10. conference: end_date: 2018-10-05 location: Turin, Italy name: 'EMSOFT: International Conference on Embedded Software' start_date: 2018-09-30 date_created: 2019-02-13T09:19:28Z date_published: 2018-09-30T00:00:00Z date_updated: 2023-09-19T10:41:29Z day: '30' ddc: - '000' department: - _id: ToHe doi: 10.1109/emsoft.2018.8537203 external_id: isi: - '000492828500005' file: - access_level: open_access checksum: 234a33ad9055b3458fcdda6af251b33a content_type: application/pdf creator: dernst date_created: 2020-05-14T16:01:29Z date_updated: 2020-07-14T12:47:13Z file_id: '7839' file_name: 2018_EMSOFT_Bakhirkin.pdf file_size: 338006 relation: main_file file_date_updated: 2020-07-14T12:47:13Z has_accepted_license: '1' isi: 1 language: - iso: eng month: '09' oa: 1 oa_version: Published Version page: 1-10 project: - _id: 25832EC2-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: S 11407_N23 name: Rigorous Systems Engineering - _id: 25F42A32-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z211 name: The Wittgenstein Prize publication: 2018 International Conference on Embedded Software publication_identifier: isbn: - '9781538655603' publication_status: published publisher: IEEE quality_controlled: '1' scopus_import: '1' status: public title: 'Keynote: The first-order logic of signals' type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2018' ... --- _id: '5962' abstract: - lang: eng text: Stochastic Gradient Descent (SGD) is a fundamental algorithm in machine learning, representing the optimization backbone for training several classic models, from regression to neural networks. Given the recent practical focus on distributed machine learning, significant work has been dedicated to the convergence properties of this algorithm under the inconsistent and noisy updates arising from execution in a distributed environment. However, surprisingly, the convergence properties of this classic algorithm in the standard shared-memory model are still not well-understood. In this work, we address this gap, and provide new convergence bounds for lock-free concurrent stochastic gradient descent, executing in the classic asynchronous shared memory model, against a strong adaptive adversary. Our results give improved upper and lower bounds on the "price of asynchrony'' when executing the fundamental SGD algorithm in a concurrent setting. They show that this classic optimization tool can converge faster and with a wider range of parameters than previously known under asynchronous iterations. At the same time, we exhibit a fundamental trade-off between the maximum delay in the system and the rate at which SGD can converge, which governs the set of parameters under which this algorithm can still work efficiently. article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Christopher full_name: De Sa, Christopher last_name: De Sa - first_name: Nikola H full_name: Konstantinov, Nikola H id: 4B9D76E4-F248-11E8-B48F-1D18A9856A87 last_name: Konstantinov citation: ama: 'Alistarh D-A, De Sa C, Konstantinov NH. The convergence of stochastic gradient descent in asynchronous shared memory. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18. ACM Press; 2018:169-178. doi:10.1145/3212734.3212763' apa: 'Alistarh, D.-A., De Sa, C., & Konstantinov, N. H. (2018). The convergence of stochastic gradient descent in asynchronous shared memory. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18 (pp. 169–178). Egham, United Kingdom: ACM Press. https://doi.org/10.1145/3212734.3212763' chicago: Alistarh, Dan-Adrian, Christopher De Sa, and Nikola H Konstantinov. “The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory.” In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, 169–78. ACM Press, 2018. https://doi.org/10.1145/3212734.3212763. ieee: D.-A. Alistarh, C. De Sa, and N. H. Konstantinov, “The convergence of stochastic gradient descent in asynchronous shared memory,” in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, Egham, United Kingdom, 2018, pp. 169–178. ista: 'Alistarh D-A, De Sa C, Konstantinov NH. 2018. The convergence of stochastic gradient descent in asynchronous shared memory. Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18. PODC: Principles of Distributed Computing, 169–178.' mla: Alistarh, Dan-Adrian, et al. “The Convergence of Stochastic Gradient Descent in Asynchronous Shared Memory.” Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, ACM Press, 2018, pp. 169–78, doi:10.1145/3212734.3212763. short: D.-A. Alistarh, C. De Sa, N.H. Konstantinov, in:, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, ACM Press, 2018, pp. 169–178. conference: end_date: 2018-07-27 location: Egham, United Kingdom name: 'PODC: Principles of Distributed Computing' start_date: 2018-07-23 date_created: 2019-02-13T09:58:58Z date_published: 2018-07-23T00:00:00Z date_updated: 2023-09-19T10:42:53Z day: '23' department: - _id: DaAl doi: 10.1145/3212734.3212763 external_id: arxiv: - '1803.08841' isi: - '000458186900022' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1803.08841 month: '07' oa: 1 oa_version: Preprint page: 169-178 publication: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18 publication_identifier: isbn: - '9781450357951' publication_status: published publisher: ACM Press quality_controlled: '1' scopus_import: '1' status: public title: The convergence of stochastic gradient descent in asynchronous shared memory type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2018' ... --- _id: '5860' abstract: - lang: eng text: 'A major problem for evolutionary theory is understanding the so-called open-ended nature of evolutionary change, from its definition to its origins. Open-ended evolution (OEE) refers to the unbounded increase in complexity that seems to characterize evolution on multiple scales. This property seems to be a characteristic feature of biological and technological evolution and is strongly tied to the generative potential associated with combinatorics, which allows the system to grow and expand their available state spaces. Interestingly, many complex systems presumably displaying OEE, from language to proteins, share a common statistical property: the presence of Zipf''s Law. Given an inventory of basic items (such as words or protein domains) required to build more complex structures (sentences or proteins) Zipf''s Law tells us that most of these elements are rare whereas a few of them are extremely common. Using algorithmic information theory, in this paper we provide a fundamental definition for open-endedness, which can be understood as postulates. Its statistical counterpart, based on standard Shannon information theory, has the structure of a variational problem which is shown to lead to Zipf''s Law as the expected consequence of an evolutionary process displaying OEE. We further explore the problem of information conservation through an OEE process and we conclude that statistical information (standard Shannon information) is not conserved, resulting in the paradoxical situation in which the increase of information content has the effect of erasing itself. We prove that this paradox is solved if we consider non-statistical forms of information. This last result implies that standard information theory may not be a suitable theoretical framework to explore the persistence and increase of the information content in OEE systems.' article_number: '20180395' article_processing_charge: No author: - first_name: Bernat full_name: Corominas-Murtra, Bernat id: 43BE2298-F248-11E8-B48F-1D18A9856A87 last_name: Corominas-Murtra orcid: 0000-0001-9806-5643 - first_name: Luís F. full_name: Seoane, Luís F. last_name: Seoane - first_name: Ricard full_name: Solé, Ricard last_name: Solé citation: ama: Corominas-Murtra B, Seoane LF, Solé R. Zipf’s Law, unbounded complexity and open-ended evolution. Journal of the Royal Society Interface. 2018;15(149). doi:10.1098/rsif.2018.0395 apa: Corominas-Murtra, B., Seoane, L. F., & Solé, R. (2018). Zipf’s Law, unbounded complexity and open-ended evolution. Journal of the Royal Society Interface. Royal Society Publishing. https://doi.org/10.1098/rsif.2018.0395 chicago: Corominas-Murtra, Bernat, Luís F. Seoane, and Ricard Solé. “Zipf’s Law, Unbounded Complexity and Open-Ended Evolution.” Journal of the Royal Society Interface. Royal Society Publishing, 2018. https://doi.org/10.1098/rsif.2018.0395. ieee: B. Corominas-Murtra, L. F. Seoane, and R. Solé, “Zipf’s Law, unbounded complexity and open-ended evolution,” Journal of the Royal Society Interface, vol. 15, no. 149. Royal Society Publishing, 2018. ista: Corominas-Murtra B, Seoane LF, Solé R. 2018. Zipf’s Law, unbounded complexity and open-ended evolution. Journal of the Royal Society Interface. 15(149), 20180395. mla: Corominas-Murtra, Bernat, et al. “Zipf’s Law, Unbounded Complexity and Open-Ended Evolution.” Journal of the Royal Society Interface, vol. 15, no. 149, 20180395, Royal Society Publishing, 2018, doi:10.1098/rsif.2018.0395. short: B. Corominas-Murtra, L.F. Seoane, R. Solé, Journal of the Royal Society Interface 15 (2018). date_created: 2019-01-20T22:59:19Z date_published: 2018-12-12T00:00:00Z date_updated: 2023-09-19T10:40:38Z day: '12' department: - _id: EdHa doi: 10.1098/rsif.2018.0395 external_id: arxiv: - '1612.01605' isi: - '000456783800002' intvolume: ' 15' isi: 1 issue: '149' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1612.01605 month: '12' oa: 1 oa_version: Preprint publication: Journal of the Royal Society Interface publication_identifier: issn: - '17425689' publication_status: published publisher: Royal Society Publishing quality_controlled: '1' scopus_import: '1' status: public title: Zipf's Law, unbounded complexity and open-ended evolution type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 15 year: '2018' ... --- _id: '5960' abstract: - lang: eng text: In this paper we present a reliable method to verify the existence of loops along the uncertain trajectory of a robot, based on proprioceptive measurements only, within a bounded-error context. The loop closure detection is one of the key points in simultaneous localization and mapping (SLAM) methods, especially in homogeneous environments with difficult scenes recognitions. The proposed approach is generic and could be coupled with conventional SLAM algorithms to reliably reduce their computing burden, thus improving the localization and mapping processes in the most challenging environments such as unexplored underwater extents. To prove that a robot performed a loop whatever the uncertainties in its evolution, we employ the notion of topological degree that originates in the field of differential topology. We show that a verification tool based on the topological degree is an optimal method for proving robot loops. This is demonstrated both on datasets from real missions involving autonomous underwater vehicles and by a mathematical discussion. article_processing_charge: No author: - first_name: Simon full_name: Rohou, Simon last_name: Rohou - first_name: Peter full_name: Franek, Peter id: 473294AE-F248-11E8-B48F-1D18A9856A87 last_name: Franek orcid: 0000-0001-8878-8397 - first_name: Clément full_name: Aubry, Clément last_name: Aubry - first_name: Luc full_name: Jaulin, Luc last_name: Jaulin citation: ama: Rohou S, Franek P, Aubry C, Jaulin L. Proving the existence of loops in robot trajectories. The International Journal of Robotics Research. 2018;37(12):1500-1516. doi:10.1177/0278364918808367 apa: Rohou, S., Franek, P., Aubry, C., & Jaulin, L. (2018). Proving the existence of loops in robot trajectories. The International Journal of Robotics Research. SAGE Publications. https://doi.org/10.1177/0278364918808367 chicago: Rohou, Simon, Peter Franek, Clément Aubry, and Luc Jaulin. “Proving the Existence of Loops in Robot Trajectories.” The International Journal of Robotics Research. SAGE Publications, 2018. https://doi.org/10.1177/0278364918808367. ieee: S. Rohou, P. Franek, C. Aubry, and L. Jaulin, “Proving the existence of loops in robot trajectories,” The International Journal of Robotics Research, vol. 37, no. 12. SAGE Publications, pp. 1500–1516, 2018. ista: Rohou S, Franek P, Aubry C, Jaulin L. 2018. Proving the existence of loops in robot trajectories. The International Journal of Robotics Research. 37(12), 1500–1516. mla: Rohou, Simon, et al. “Proving the Existence of Loops in Robot Trajectories.” The International Journal of Robotics Research, vol. 37, no. 12, SAGE Publications, 2018, pp. 1500–16, doi:10.1177/0278364918808367. short: S. Rohou, P. Franek, C. Aubry, L. Jaulin, The International Journal of Robotics Research 37 (2018) 1500–1516. date_created: 2019-02-13T09:36:20Z date_published: 2018-10-24T00:00:00Z date_updated: 2023-09-19T10:41:59Z day: '24' department: - _id: UlWa doi: 10.1177/0278364918808367 external_id: arxiv: - '1712.01341' isi: - '000456881100004' intvolume: ' 37' isi: 1 issue: '12' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1712.01341 month: '10' oa: 1 oa_version: Preprint page: 1500-1516 publication: The International Journal of Robotics Research publication_identifier: eissn: - 1741-3176 issn: - 0278-3649 publication_status: published publisher: SAGE Publications quality_controlled: '1' scopus_import: '1' status: public title: Proving the existence of loops in robot trajectories type: journal_article user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 volume: 37 year: '2018' ... --- _id: '5963' abstract: - lang: eng text: 'There has been significant progress in understanding the parallelism inherent to iterative sequential algorithms: for many classic algorithms, the depth of the dependence structure is now well understood, and scheduling techniques have been developed to exploit this shallow dependence structure for efficient parallel implementations. A related, applied research strand has studied methods by which certain iterative task-based algorithms can be efficiently parallelized via relaxed concurrent priority schedulers. These allow for high concurrency when inserting and removing tasks, at the cost of executing superfluous work due to the relaxed semantics of the scheduler. In this work, we take a step towards unifying these two research directions, by showing that there exists a family of relaxed priority schedulers that can efficiently and deterministically execute classic iterative algorithms such as greedy maximal independent set (MIS) and matching. Our primary result shows that, given a randomized scheduler with an expected relaxation factor of k in terms of the maximum allowed priority inversions on a task, and any graph on n vertices, the scheduler is able to execute greedy MIS with only an additive factor of \poly(k) expected additional iterations compared to an exact (but not scalable) scheduler. This counter-intuitive result demonstrates that the overhead of relaxation when computing MIS is not dependent on the input size or structure of the input graph. Experimental results show that this overhead can be clearly offset by the gain in performance due to the highly scalable scheduler. In sum, we present an efficient method to deterministically parallelize iterative sequential algorithms, with provable runtime guarantees in terms of the number of executed tasks to completion.' article_processing_charge: No author: - first_name: Dan-Adrian full_name: Alistarh, Dan-Adrian id: 4A899BFC-F248-11E8-B48F-1D18A9856A87 last_name: Alistarh orcid: 0000-0003-3650-940X - first_name: Trevor A full_name: Brown, Trevor A id: 3569F0A0-F248-11E8-B48F-1D18A9856A87 last_name: Brown - first_name: Justin full_name: Kopinsky, Justin last_name: Kopinsky - first_name: Giorgi full_name: Nadiradze, Giorgi last_name: Nadiradze citation: ama: 'Alistarh D-A, Brown TA, Kopinsky J, Nadiradze G. Relaxed schedulers can efficiently parallelize iterative algorithms. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18. ACM Press; 2018:377-386. doi:10.1145/3212734.3212756' apa: 'Alistarh, D.-A., Brown, T. A., Kopinsky, J., & Nadiradze, G. (2018). Relaxed schedulers can efficiently parallelize iterative algorithms. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18 (pp. 377–386). Egham, United Kingdom: ACM Press. https://doi.org/10.1145/3212734.3212756' chicago: Alistarh, Dan-Adrian, Trevor A Brown, Justin Kopinsky, and Giorgi Nadiradze. “Relaxed Schedulers Can Efficiently Parallelize Iterative Algorithms.” In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, 377–86. ACM Press, 2018. https://doi.org/10.1145/3212734.3212756. ieee: D.-A. Alistarh, T. A. Brown, J. Kopinsky, and G. Nadiradze, “Relaxed schedulers can efficiently parallelize iterative algorithms,” in Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, Egham, United Kingdom, 2018, pp. 377–386. ista: 'Alistarh D-A, Brown TA, Kopinsky J, Nadiradze G. 2018. Relaxed schedulers can efficiently parallelize iterative algorithms. Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18. PODC: Principles of Distributed Computing, 377–386.' mla: Alistarh, Dan-Adrian, et al. “Relaxed Schedulers Can Efficiently Parallelize Iterative Algorithms.” Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, ACM Press, 2018, pp. 377–86, doi:10.1145/3212734.3212756. short: D.-A. Alistarh, T.A. Brown, J. Kopinsky, G. Nadiradze, in:, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing  - PODC ’18, ACM Press, 2018, pp. 377–386. conference: end_date: 2018-07-27 location: Egham, United Kingdom name: 'PODC: Principles of Distributed Computing' start_date: 2018-07-23 date_created: 2019-02-13T10:03:25Z date_published: 2018-07-23T00:00:00Z date_updated: 2023-09-19T10:43:21Z day: '23' department: - _id: DaAl doi: 10.1145/3212734.3212756 external_id: arxiv: - '1808.04155' isi: - '000458186900048' isi: 1 language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1808.04155 month: '07' oa: 1 oa_version: Preprint page: 377-386 publication: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing - PODC '18 publication_identifier: isbn: - '9781450357951' publication_status: published publisher: ACM Press quality_controlled: '1' scopus_import: '1' status: public title: Relaxed schedulers can efficiently parallelize iterative algorithms type: conference user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1 year: '2018' ...