--- _id: '12544' abstract: - lang: eng text: Geometry is crucial in our efforts to comprehend the structures and dynamics of biomolecules. For example, volume, surface area, and integrated mean and Gaussian curvature of the union of balls representing a molecule are used to quantify its interactions with the water surrounding it in the morphometric implicit solvent models. The Alpha Shape theory provides an accurate and reliable method for computing these geometric measures. In this paper, we derive homogeneous formulas for the expressions of these measures and their derivatives with respect to the atomic coordinates, and we provide algorithms that implement them into a new software package, AlphaMol. The only variables in these formulas are the interatomic distances, making them insensitive to translations and rotations. AlphaMol includes a sequential algorithm and a parallel algorithm. In the parallel version, we partition the atoms of the molecule of interest into 3D rectangular blocks, using a kd-tree algorithm. We then apply the sequential algorithm of AlphaMol to each block, augmented by a buffer zone to account for atoms whose ball representations may partially cover the block. The current parallel version of AlphaMol leads to a 20-fold speed-up compared to an independent serial implementation when using 32 processors. For instance, it takes 31 s to compute the geometric measures and derivatives of each atom in a viral capsid with more than 26 million atoms on 32 Intel processors running at 2.7 GHz. The presence of the buffer zones, however, leads to redundant computations, which ultimately limit the impact of using multiple processors. AlphaMol is available as an OpenSource software. acknowledgement: "P.K. acknowledges support from the University of California Multicampus Research Programs and Initiatives (Grant No. M21PR3267) and from the NSF (Grant No.1760485). H.E. acknowledges support from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program, Grant No. 788183, from the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and from the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, Austrian Science Fund (FWF), Grant No. I 02979-N35.\r\nOpen Access is funded by the Austrian Science Fund (FWF)." article_processing_charge: No article_type: original author: - first_name: Patrice full_name: Koehl, Patrice last_name: Koehl - first_name: Arseniy full_name: Akopyan, Arseniy id: 430D2C90-F248-11E8-B48F-1D18A9856A87 last_name: Akopyan orcid: 0000-0002-2548-617X - first_name: Herbert full_name: Edelsbrunner, Herbert id: 3FB178DA-F248-11E8-B48F-1D18A9856A87 last_name: Edelsbrunner orcid: 0000-0002-9823-6833 citation: ama: Koehl P, Akopyan A, Edelsbrunner H. Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. Journal of Chemical Information and Modeling. 2023;63(3):973-985. doi:10.1021/acs.jcim.2c01346 apa: Koehl, P., Akopyan, A., & Edelsbrunner, H. (2023). Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. Journal of Chemical Information and Modeling. American Chemical Society. https://doi.org/10.1021/acs.jcim.2c01346 chicago: Koehl, Patrice, Arseniy Akopyan, and Herbert Edelsbrunner. “Computing the Volume, Surface Area, Mean, and Gaussian Curvatures of Molecules and Their Derivatives.” Journal of Chemical Information and Modeling. American Chemical Society, 2023. https://doi.org/10.1021/acs.jcim.2c01346. ieee: P. Koehl, A. Akopyan, and H. Edelsbrunner, “Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives,” Journal of Chemical Information and Modeling, vol. 63, no. 3. American Chemical Society, pp. 973–985, 2023. ista: Koehl P, Akopyan A, Edelsbrunner H. 2023. Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives. Journal of Chemical Information and Modeling. 63(3), 973–985. mla: Koehl, Patrice, et al. “Computing the Volume, Surface Area, Mean, and Gaussian Curvatures of Molecules and Their Derivatives.” Journal of Chemical Information and Modeling, vol. 63, no. 3, American Chemical Society, 2023, pp. 973–85, doi:10.1021/acs.jcim.2c01346. short: P. Koehl, A. Akopyan, H. Edelsbrunner, Journal of Chemical Information and Modeling 63 (2023) 973–985. date_created: 2023-02-12T23:00:59Z date_published: 2023-02-13T00:00:00Z date_updated: 2023-08-16T12:22:07Z day: '13' ddc: - '510' - '540' department: - _id: HeEd doi: 10.1021/acs.jcim.2c01346 ec_funded: 1 external_id: isi: - '000920370700001' pmid: - '36638318' file: - access_level: open_access checksum: 7d20562269edff1e31b9d6019d4983b0 content_type: application/pdf creator: dernst date_created: 2023-08-16T12:21:13Z date_updated: 2023-08-16T12:21:13Z file_id: '14070' file_name: 2023_JCIM_Koehl.pdf file_size: 8069223 relation: main_file success: 1 file_date_updated: 2023-08-16T12:21:13Z has_accepted_license: '1' intvolume: ' 63' isi: 1 issue: '3' language: - iso: eng license: https://creativecommons.org/licenses/by/4.0/ month: '02' oa: 1 oa_version: Published Version page: 973-985 pmid: 1 project: - _id: 266A2E9E-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '788183' name: Alpha Shape Theory Extended - _id: 268116B8-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: Z00342 name: The Wittgenstein Prize - _id: 2561EBF4-B435-11E9-9278-68D0E5697425 call_identifier: FWF grant_number: I02979-N35 name: Persistence and stability of geometric complexes publication: Journal of Chemical Information and Modeling publication_identifier: eissn: - 1549-960X issn: - 1549-9596 publication_status: published publisher: American Chemical Society quality_controlled: '1' scopus_import: '1' status: public title: Computing the volume, surface area, mean, and Gaussian curvatures of molecules and their derivatives 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 63 year: '2023' ... --- _id: '12543' abstract: - lang: eng text: Treating sick group members is a hallmark of collective disease defence in vertebrates and invertebrates alike. Despite substantial effects on pathogen fitness and epidemiology, it is still largely unknown how pathogens react to the selection pressure imposed by care intervention. Using social insects and pathogenic fungi, we here performed a serial passage experiment in the presence or absence of colony members, which provide social immunity by grooming off infectious spores from exposed individuals. We found specific effects on pathogen diversity, virulence and transmission. Under selection of social immunity, pathogens invested into higher spore production, but spores were less virulent. Notably, they also elicited a lower grooming response in colony members, compared with spores from the individual host selection lines. Chemical spore analysis suggested that the spores from social selection lines escaped the caregivers’ detection by containing lower levels of ergosterol, a key fungal membrane component. Experimental application of chemically pure ergosterol indeed induced sanitary grooming, supporting its role as a microbe-associated cue triggering host social immunity against fungal pathogens. By reducing this detection cue, pathogens were able to evade the otherwise very effective collective disease defences of their social hosts. acknowledged_ssus: - _id: LifeSc acknowledgement: We thank B. M. Steinwender, N. V. Meyling and J. Eilenberg for the fungal strains; J. Anaya-Rojas for statistical advice; the Social Immunity team at ISTA for ant collection and experimental help, in particular H. Leitner, and the ISTA Lab Support Facility for general laboratory support; D. Ebert, H. Schulenburg and J. Heinze for continued project discussion; and M. Sixt, R. Roemhild and the Social Immunity team for comments on the manuscript. The study was funded by the German Research Foundation (CR118/3-1) within the Framework of the Priority Program SPP 1399, and the European Research Council (ERC) under the European Union’s Horizon 2020 Research and Innovation Programme (No. 771402; EPIDEMICSonCHIP), both to S.C. article_processing_charge: No article_type: original author: - first_name: Miriam full_name: Stock, Miriam id: 42462816-F248-11E8-B48F-1D18A9856A87 last_name: Stock - first_name: Barbara full_name: Milutinovic, Barbara id: 2CDC32B8-F248-11E8-B48F-1D18A9856A87 last_name: Milutinovic orcid: 0000-0002-8214-4758 - first_name: Michaela full_name: Hönigsberger, Michaela id: 953894f3-25bd-11ec-8556-f70a9d38ef60 last_name: Hönigsberger - first_name: Anna V full_name: Grasse, Anna V id: 406F989C-F248-11E8-B48F-1D18A9856A87 last_name: Grasse - first_name: Florian full_name: Wiesenhofer, Florian id: 39523C54-F248-11E8-B48F-1D18A9856A87 last_name: Wiesenhofer - first_name: Niklas full_name: Kampleitner, Niklas id: 2AC57FAC-F248-11E8-B48F-1D18A9856A87 last_name: Kampleitner - first_name: Madhumitha full_name: Narasimhan, Madhumitha id: 44BF24D0-F248-11E8-B48F-1D18A9856A87 last_name: Narasimhan orcid: 0000-0002-8600-0671 - first_name: Thomas full_name: Schmitt, Thomas last_name: Schmitt - first_name: Sylvia full_name: Cremer, Sylvia id: 2F64EC8C-F248-11E8-B48F-1D18A9856A87 last_name: Cremer orcid: 0000-0002-2193-3868 citation: ama: Stock M, Milutinovic B, Hönigsberger M, et al. Pathogen evasion of social immunity. Nature Ecology and Evolution. 2023;7:450-460. doi:10.1038/s41559-023-01981-6 apa: Stock, M., Milutinovic, B., Hönigsberger, M., Grasse, A. V., Wiesenhofer, F., Kampleitner, N., … Cremer, S. (2023). Pathogen evasion of social immunity. Nature Ecology and Evolution. Springer Nature. https://doi.org/10.1038/s41559-023-01981-6 chicago: Stock, Miriam, Barbara Milutinovic, Michaela Hönigsberger, Anna V Grasse, Florian Wiesenhofer, Niklas Kampleitner, Madhumitha Narasimhan, Thomas Schmitt, and Sylvia Cremer. “Pathogen Evasion of Social Immunity.” Nature Ecology and Evolution. Springer Nature, 2023. https://doi.org/10.1038/s41559-023-01981-6. ieee: M. Stock et al., “Pathogen evasion of social immunity,” Nature Ecology and Evolution, vol. 7. Springer Nature, pp. 450–460, 2023. ista: Stock M, Milutinovic B, Hönigsberger M, Grasse AV, Wiesenhofer F, Kampleitner N, Narasimhan M, Schmitt T, Cremer S. 2023. Pathogen evasion of social immunity. Nature Ecology and Evolution. 7, 450–460. mla: Stock, Miriam, et al. “Pathogen Evasion of Social Immunity.” Nature Ecology and Evolution, vol. 7, Springer Nature, 2023, pp. 450–60, doi:10.1038/s41559-023-01981-6. short: M. Stock, B. Milutinovic, M. Hönigsberger, A.V. Grasse, F. Wiesenhofer, N. Kampleitner, M. Narasimhan, T. Schmitt, S. Cremer, Nature Ecology and Evolution 7 (2023) 450–460. date_created: 2023-02-12T23:00:59Z date_published: 2023-03-01T00:00:00Z date_updated: 2023-08-16T11:55:48Z day: '01' ddc: - '570' department: - _id: SyCr - _id: LifeSc - _id: JiFr doi: 10.1038/s41559-023-01981-6 ec_funded: 1 external_id: isi: - '000924572800001' pmid: - '36732670' file: - access_level: open_access checksum: 8244f4650a0e7aeea488d1bcd4a31702 content_type: application/pdf creator: dernst date_created: 2023-08-16T11:54:59Z date_updated: 2023-08-16T11:54:59Z file_id: '14069' file_name: 2023_NatureEcoEvo_Stock.pdf file_size: 1600499 relation: main_file success: 1 file_date_updated: 2023-08-16T11:54:59Z has_accepted_license: '1' intvolume: ' 7' isi: 1 language: - iso: eng month: '03' oa: 1 oa_version: Published Version page: 450-460 pmid: 1 project: - _id: 2649B4DE-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '771402' name: Epidemics in ant societies on a chip - _id: 25DAF0B2-B435-11E9-9278-68D0E5697425 grant_number: CR-118/3-1 name: Host-Parasite Coevolution publication: Nature Ecology and Evolution publication_identifier: eissn: - 2397-334X publication_status: published publisher: Springer Nature quality_controlled: '1' related_material: link: - description: News on ISTA website relation: press_release url: https://ista.ac.at/en/news/how-sneaky-germs-hide-from-ants/ scopus_import: '1' status: public title: Pathogen evasion of social immunity 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 7 year: '2023' ... --- _id: '12521' abstract: - lang: eng text: Differentiated X chromosomes are expected to have higher rates of adaptive divergence than autosomes, if new beneficial mutations are recessive (the “faster-X effect”), largely because these mutations are immediately exposed to selection in males. The evolution of X chromosomes after they stop recombining in males, but before they become hemizygous, has not been well explored theoretically. We use the diffusion approximation to infer substitution rates of beneficial and deleterious mutations under such a scenario. Our results show that selection is less efficient on diploid X loci than on autosomal and hemizygous X loci under a wide range of parameters. This “slower-X” effect is stronger for genes affecting primarily (or only) male fitness, and for sexually antagonistic genes. These unusual dynamics suggest that some of the peculiar features of X chromosomes, such as the differential accumulation of genes with sex-specific functions, may start arising earlier than previously appreciated. acknowledgement: We thank the Vicoso and Barton groups and ISTA Scientific Computing Unit. We also thank two anonymous reviewers for their valuable comments. This work was supported by the European Research Council under the European Union’s Horizon 2020 research and innovation program (grant agreements no. 715257 and no. 716117). article_number: qrac004 article_processing_charge: Yes (via OA deal) article_type: original author: - first_name: Andrea full_name: Mrnjavac, Andrea id: 353FAC84-AE61-11E9-8BFC-00D3E5697425 last_name: Mrnjavac - first_name: Kseniia full_name: Khudiakova, Kseniia id: 4E6DC800-AE37-11E9-AC72-31CAE5697425 last_name: Khudiakova orcid: 0000-0002-6246-1465 - first_name: Nicholas H full_name: Barton, Nicholas H id: 4880FE40-F248-11E8-B48F-1D18A9856A87 last_name: Barton orcid: 0000-0002-8548-5240 - first_name: Beatriz full_name: Vicoso, Beatriz id: 49E1C5C6-F248-11E8-B48F-1D18A9856A87 last_name: Vicoso orcid: 0000-0002-4579-8306 citation: ama: 'Mrnjavac A, Khudiakova K, Barton NH, Vicoso B. Slower-X: Reduced efficiency of selection in the early stages of X chromosome evolution. Evolution Letters. 2023;7(1). doi:10.1093/evlett/qrac004' apa: 'Mrnjavac, A., Khudiakova, K., Barton, N. H., & Vicoso, B. (2023). Slower-X: Reduced efficiency of selection in the early stages of X chromosome evolution. Evolution Letters. Oxford University Press. https://doi.org/10.1093/evlett/qrac004' chicago: 'Mrnjavac, Andrea, Kseniia Khudiakova, Nicholas H Barton, and Beatriz Vicoso. “Slower-X: Reduced Efficiency of Selection in the Early Stages of X Chromosome Evolution.” Evolution Letters. Oxford University Press, 2023. https://doi.org/10.1093/evlett/qrac004.' ieee: 'A. Mrnjavac, K. Khudiakova, N. H. Barton, and B. Vicoso, “Slower-X: Reduced efficiency of selection in the early stages of X chromosome evolution,” Evolution Letters, vol. 7, no. 1. Oxford University Press, 2023.' ista: 'Mrnjavac A, Khudiakova K, Barton NH, Vicoso B. 2023. Slower-X: Reduced efficiency of selection in the early stages of X chromosome evolution. Evolution Letters. 7(1), qrac004.' mla: 'Mrnjavac, Andrea, et al. “Slower-X: Reduced Efficiency of Selection in the Early Stages of X Chromosome Evolution.” Evolution Letters, vol. 7, no. 1, qrac004, Oxford University Press, 2023, doi:10.1093/evlett/qrac004.' short: A. Mrnjavac, K. Khudiakova, N.H. Barton, B. Vicoso, Evolution Letters 7 (2023). date_created: 2023-02-06T13:59:12Z date_published: 2023-02-01T00:00:00Z date_updated: 2023-08-16T11:44:32Z day: '01' ddc: - '570' department: - _id: GradSch - _id: BeVi doi: 10.1093/evlett/qrac004 ec_funded: 1 external_id: isi: - '001021692200001' pmid: - '37065438' file: - access_level: open_access checksum: a240a041cb9b9b7c8ba93a4706674a3f content_type: application/pdf creator: dernst date_created: 2023-08-16T11:43:33Z date_updated: 2023-08-16T11:43:33Z file_id: '14068' file_name: 2023_EvLetters_Mrnjavac.pdf file_size: 2592189 relation: main_file success: 1 file_date_updated: 2023-08-16T11:43:33Z has_accepted_license: '1' intvolume: ' 7' isi: 1 issue: '1' keyword: - Genetics - Ecology - Evolution - Behavior and Systematics language: - iso: eng month: '02' oa: 1 oa_version: Published Version pmid: 1 project: - _id: 256E75B8-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '716117' name: Optimal Transport and Stochastic Dynamics - _id: 250BDE62-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '715257' name: Prevalence and Influence of Sexual Antagonism on Genome Evolution publication: Evolution Letters publication_identifier: issn: - 2056-3744 publication_status: published publisher: Oxford University Press quality_controlled: '1' scopus_import: '1' status: public title: 'Slower-X: Reduced efficiency of selection in the early stages of X chromosome evolution' 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 7 year: '2023' ... --- _id: '12679' abstract: - lang: eng text: How to generate a brain of correct size and with appropriate cell-type diversity during development is a major question in Neuroscience. In the developing neocortex, radial glial progenitor (RGP) cells are the main neural stem cells that produce cortical excitatory projection neurons, glial cells, and establish the prospective postnatal stem cell niche in the lateral ventricles. RGPs follow a tightly orchestrated developmental program that when disrupted can result in severe cortical malformations such as microcephaly and megalencephaly. The precise cellular and molecular mechanisms instructing faithful RGP lineage progression are however not well understood. This review will summarize recent conceptual advances that contribute to our understanding of the general principles of RGP lineage progression. acknowledgement: "I wish to thank all current and past members of the Hippenmeyer laboratory at ISTA for exciting discussions on the subject of this review. I apologize to colleagues whose work I could not cite and/or discuss in the frame of the available space. Work in the Hippenmeyer laboratory on the\r\ndiscussed topic is supported by ISTA institutional funds, FWF SFB F78 to S.H., and the European Research Council (ERC) under the European Union’s Horizon 2020 Research and Innovation Programme (grant agree-ment no. 725780 LinPro) to SH." article_number: '102695' article_processing_charge: Yes (via OA deal) article_type: review author: - first_name: Simon full_name: Hippenmeyer, Simon id: 37B36620-F248-11E8-B48F-1D18A9856A87 last_name: Hippenmeyer orcid: 0000-0003-2279-1061 citation: ama: 'Hippenmeyer S. Principles of neural stem cell lineage progression: Insights from developing cerebral cortex. Current Opinion in Neurobiology. 2023;79(4). doi:10.1016/j.conb.2023.102695' apa: 'Hippenmeyer, S. (2023). Principles of neural stem cell lineage progression: Insights from developing cerebral cortex. Current Opinion in Neurobiology. Elsevier. https://doi.org/10.1016/j.conb.2023.102695' chicago: 'Hippenmeyer, Simon. “Principles of Neural Stem Cell Lineage Progression: Insights from Developing Cerebral Cortex.” Current Opinion in Neurobiology. Elsevier, 2023. https://doi.org/10.1016/j.conb.2023.102695.' ieee: 'S. Hippenmeyer, “Principles of neural stem cell lineage progression: Insights from developing cerebral cortex,” Current Opinion in Neurobiology, vol. 79, no. 4. Elsevier, 2023.' ista: 'Hippenmeyer S. 2023. Principles of neural stem cell lineage progression: Insights from developing cerebral cortex. Current Opinion in Neurobiology. 79(4), 102695.' mla: 'Hippenmeyer, Simon. “Principles of Neural Stem Cell Lineage Progression: Insights from Developing Cerebral Cortex.” Current Opinion in Neurobiology, vol. 79, no. 4, 102695, Elsevier, 2023, doi:10.1016/j.conb.2023.102695.' short: S. Hippenmeyer, Current Opinion in Neurobiology 79 (2023). date_created: 2023-02-26T12:24:21Z date_published: 2023-04-01T00:00:00Z date_updated: 2023-08-16T12:30:25Z day: '01' ddc: - '570' department: - _id: SiHi doi: 10.1016/j.conb.2023.102695 ec_funded: 1 external_id: isi: - '000953497700001' pmid: - '36842274' file: - access_level: open_access checksum: 4d11c4ca87e6cbc4d2ac46d3225ea615 content_type: application/pdf creator: dernst date_created: 2023-08-16T12:29:06Z date_updated: 2023-08-16T12:29:06Z file_id: '14071' file_name: 2023_CurrentOpinionNeurobio_Hippenmeyer.pdf file_size: 1787894 relation: main_file success: 1 file_date_updated: 2023-08-16T12:29:06Z has_accepted_license: '1' intvolume: ' 79' isi: 1 issue: '4' keyword: - General Neuroscience language: - iso: eng month: '04' oa: 1 oa_version: Published Version pmid: 1 project: - _id: 059F6AB4-7A3F-11EA-A408-12923DDC885E grant_number: F07805 name: Molecular Mechanisms of Neural Stem Cell Lineage Progression - _id: 260018B0-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '725780' name: Principles of Neural Stem Cell Lineage Progression in Cerebral Cortex Development publication: Current Opinion in Neurobiology publication_identifier: issn: - 0959-4388 publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: 'Principles of neural stem cell lineage progression: Insights from developing cerebral cortex' 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 79 year: '2023' ... --- _id: '12429' abstract: - lang: eng text: In this paper, we consider traces at initial times for functions with mixed time-space smoothness. Such results are often needed in the theory of evolution equations. Our result extends and unifies many previous results. Our main improvement is that we can allow general interpolation couples. The abstract results are applied to regularity problems for fractional evolution equations and stochastic evolution equations, where uniform trace estimates on the half-line are shown. acknowledgement: The first author has been partially supported by the Nachwuchsring—Network for the promotion of young scientists—at TU Kaiserslautern. The second and third authors were supported by the Vidi subsidy 639.032.427 of the Netherlands Organisation for Scientific Research (NWO). article_processing_charge: No article_type: original author: - first_name: Antonio full_name: Agresti, Antonio id: 673cd0cc-9b9a-11eb-b144-88f30e1fbb72 last_name: Agresti orcid: 0000-0002-9573-2962 - first_name: Nick full_name: Lindemulder, Nick last_name: Lindemulder - first_name: Mark full_name: Veraar, Mark last_name: Veraar citation: ama: Agresti A, Lindemulder N, Veraar M. On the trace embedding and its applications to evolution equations. Mathematische Nachrichten. 2023;296(4):1319-1350. doi:10.1002/mana.202100192 apa: Agresti, A., Lindemulder, N., & Veraar, M. (2023). On the trace embedding and its applications to evolution equations. Mathematische Nachrichten. Wiley. https://doi.org/10.1002/mana.202100192 chicago: Agresti, Antonio, Nick Lindemulder, and Mark Veraar. “On the Trace Embedding and Its Applications to Evolution Equations.” Mathematische Nachrichten. Wiley, 2023. https://doi.org/10.1002/mana.202100192. ieee: A. Agresti, N. Lindemulder, and M. Veraar, “On the trace embedding and its applications to evolution equations,” Mathematische Nachrichten, vol. 296, no. 4. Wiley, pp. 1319–1350, 2023. ista: Agresti A, Lindemulder N, Veraar M. 2023. On the trace embedding and its applications to evolution equations. Mathematische Nachrichten. 296(4), 1319–1350. mla: Agresti, Antonio, et al. “On the Trace Embedding and Its Applications to Evolution Equations.” Mathematische Nachrichten, vol. 296, no. 4, Wiley, 2023, pp. 1319–50, doi:10.1002/mana.202100192. short: A. Agresti, N. Lindemulder, M. Veraar, Mathematische Nachrichten 296 (2023) 1319–1350. date_created: 2023-01-29T23:00:59Z date_published: 2023-04-01T00:00:00Z date_updated: 2023-08-16T11:41:42Z day: '01' ddc: - '510' department: - _id: JuFi doi: 10.1002/mana.202100192 external_id: arxiv: - '2104.05063' isi: - '000914134900001' file: - access_level: open_access checksum: 6f099f1d064173784d1a27716a2cc795 content_type: application/pdf creator: dernst date_created: 2023-08-16T11:40:02Z date_updated: 2023-08-16T11:40:02Z file_id: '14067' file_name: 2023_MathNachrichten_Agresti.pdf file_size: 449280 relation: main_file success: 1 file_date_updated: 2023-08-16T11:40:02Z has_accepted_license: '1' intvolume: ' 296' isi: 1 issue: '4' language: - iso: eng license: https://creativecommons.org/licenses/by-nc/4.0/ month: '04' oa: 1 oa_version: Published Version page: 1319-1350 publication: Mathematische Nachrichten publication_identifier: eissn: - 1522-2616 issn: - 0025-584X publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: On the trace embedding and its applications to evolution equations tmp: image: /images/cc_by_nc.png legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) short: CC BY-NC (4.0) type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 296 year: '2023' ... --- _id: '12430' abstract: - lang: eng text: We study the time evolution of the Nelson model in a mean-field limit in which N nonrelativistic bosons weakly couple (with respect to the particle number) to a positive or zero mass quantized scalar field. Our main result is the derivation of the Bogoliubov dynamics and higher-order corrections. More precisely, we prove the convergence of the approximate wave function to the many-body wave function in norm, with a convergence rate proportional to the number of corrections taken into account in the approximation. We prove an analogous result for the unitary propagator. As an application, we derive a simple system of partial differential equations describing the time evolution of the first- and second-order approximations to the one-particle reduced density matrices of the particles and the quantum field, respectively. article_number: '2350006' article_processing_charge: No article_type: original author: - first_name: Marco full_name: Falconi, Marco last_name: Falconi - first_name: Nikolai K full_name: Leopold, Nikolai K id: 4BC40BEC-F248-11E8-B48F-1D18A9856A87 last_name: Leopold orcid: 0000-0002-0495-6822 - first_name: David Johannes full_name: Mitrouskas, David Johannes id: cbddacee-2b11-11eb-a02e-a2e14d04e52d last_name: Mitrouskas - first_name: Sören P full_name: Petrat, Sören P id: 40AC02DC-F248-11E8-B48F-1D18A9856A87 last_name: Petrat orcid: 0000-0002-9166-5889 citation: ama: Falconi M, Leopold NK, Mitrouskas DJ, Petrat SP. Bogoliubov dynamics and higher-order corrections for the regularized Nelson model. Reviews in Mathematical Physics. 2023;35(4). doi:10.1142/S0129055X2350006X apa: Falconi, M., Leopold, N. K., Mitrouskas, D. J., & Petrat, S. P. (2023). Bogoliubov dynamics and higher-order corrections for the regularized Nelson model. Reviews in Mathematical Physics. World Scientific Publishing. https://doi.org/10.1142/S0129055X2350006X chicago: Falconi, Marco, Nikolai K Leopold, David Johannes Mitrouskas, and Sören P Petrat. “Bogoliubov Dynamics and Higher-Order Corrections for the Regularized Nelson Model.” Reviews in Mathematical Physics. World Scientific Publishing, 2023. https://doi.org/10.1142/S0129055X2350006X. ieee: M. Falconi, N. K. Leopold, D. J. Mitrouskas, and S. P. Petrat, “Bogoliubov dynamics and higher-order corrections for the regularized Nelson model,” Reviews in Mathematical Physics, vol. 35, no. 4. World Scientific Publishing, 2023. ista: Falconi M, Leopold NK, Mitrouskas DJ, Petrat SP. 2023. Bogoliubov dynamics and higher-order corrections for the regularized Nelson model. Reviews in Mathematical Physics. 35(4), 2350006. mla: Falconi, Marco, et al. “Bogoliubov Dynamics and Higher-Order Corrections for the Regularized Nelson Model.” Reviews in Mathematical Physics, vol. 35, no. 4, 2350006, World Scientific Publishing, 2023, doi:10.1142/S0129055X2350006X. short: M. Falconi, N.K. Leopold, D.J. Mitrouskas, S.P. Petrat, Reviews in Mathematical Physics 35 (2023). date_created: 2023-01-29T23:00:59Z date_published: 2023-01-09T00:00:00Z date_updated: 2023-08-16T11:47:27Z day: '09' department: - _id: RoSe doi: 10.1142/S0129055X2350006X external_id: arxiv: - '2110.00458' isi: - '000909760300001' intvolume: ' 35' isi: 1 issue: '4' language: - iso: eng main_file_link: - open_access: '1' url: ' https://doi.org/10.48550/arXiv.2110.00458' month: '01' oa: 1 oa_version: Preprint publication: Reviews in Mathematical Physics publication_identifier: issn: - 0129-055X publication_status: published publisher: World Scientific Publishing quality_controlled: '1' scopus_import: '1' status: public title: Bogoliubov dynamics and higher-order corrections for the regularized Nelson model type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 35 year: '2023' ... --- _id: '12762' abstract: - lang: eng text: Neurons in the brain are wired into adaptive networks that exhibit collective dynamics as diverse as scale-specific oscillations and scale-free neuronal avalanches. Although existing models account for oscillations and avalanches separately, they typically do not explain both phenomena, are too complex to analyze analytically or intractable to infer from data rigorously. Here we propose a feedback-driven Ising-like class of neural networks that captures avalanches and oscillations simultaneously and quantitatively. In the simplest yet fully microscopic model version, we can analytically compute the phase diagram and make direct contact with human brain resting-state activity recordings via tractable inference of the model’s two essential parameters. The inferred model quantitatively captures the dynamics over a broad range of scales, from single sensor oscillations to collective behaviors of extreme events and neuronal avalanches. Importantly, the inferred parameters indicate that the co-existence of scale-specific (oscillations) and scale-free (avalanches) dynamics occurs close to a non-equilibrium critical point at the onset of self-sustained oscillations. acknowledgement: This research was funded in whole, or in part, by the Austrian Science Fund (FWF) (grant no. PT1013M03318 to F.L. and no. P34015 to G.T.). For the purpose of open access, the author has applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission. The study was supported by the European Union Horizon 2020 research and innovation program under the Marie Sklodowska-Curie action (grant agreement No. 754411 to F.L.). article_processing_charge: No article_type: original author: - first_name: Fabrizio full_name: Lombardi, Fabrizio id: A057D288-3E88-11E9-986D-0CF4E5697425 last_name: Lombardi orcid: 0000-0003-2623-5249 - first_name: Selver full_name: Pepic, Selver id: F93245C4-C3CA-11E9-B4F0-C6F4E5697425 last_name: Pepic - first_name: Oren full_name: Shriki, Oren last_name: Shriki - first_name: Gašper full_name: Tkačik, Gašper id: 3D494DCA-F248-11E8-B48F-1D18A9856A87 last_name: Tkačik orcid: 0000-0002-6699-1455 - first_name: Daniele full_name: De Martino, Daniele id: 3FF5848A-F248-11E8-B48F-1D18A9856A87 last_name: De Martino orcid: 0000-0002-5214-4706 citation: ama: Lombardi F, Pepic S, Shriki O, Tkačik G, De Martino D. Statistical modeling of adaptive neural networks explains co-existence of avalanches and oscillations in resting human brain. Nature Computational Science. 2023;3:254-263. doi:10.1038/s43588-023-00410-9 apa: Lombardi, F., Pepic, S., Shriki, O., Tkačik, G., & De Martino, D. (2023). Statistical modeling of adaptive neural networks explains co-existence of avalanches and oscillations in resting human brain. Nature Computational Science. Springer Nature. https://doi.org/10.1038/s43588-023-00410-9 chicago: Lombardi, Fabrizio, Selver Pepic, Oren Shriki, Gašper Tkačik, and Daniele De Martino. “Statistical Modeling of Adaptive Neural Networks Explains Co-Existence of Avalanches and Oscillations in Resting Human Brain.” Nature Computational Science. Springer Nature, 2023. https://doi.org/10.1038/s43588-023-00410-9. ieee: F. Lombardi, S. Pepic, O. Shriki, G. Tkačik, and D. De Martino, “Statistical modeling of adaptive neural networks explains co-existence of avalanches and oscillations in resting human brain,” Nature Computational Science, vol. 3. Springer Nature, pp. 254–263, 2023. ista: Lombardi F, Pepic S, Shriki O, Tkačik G, De Martino D. 2023. Statistical modeling of adaptive neural networks explains co-existence of avalanches and oscillations in resting human brain. Nature Computational Science. 3, 254–263. mla: Lombardi, Fabrizio, et al. “Statistical Modeling of Adaptive Neural Networks Explains Co-Existence of Avalanches and Oscillations in Resting Human Brain.” Nature Computational Science, vol. 3, Springer Nature, 2023, pp. 254–63, doi:10.1038/s43588-023-00410-9. short: F. Lombardi, S. Pepic, O. Shriki, G. Tkačik, D. De Martino, Nature Computational Science 3 (2023) 254–263. date_created: 2023-03-26T22:01:08Z date_published: 2023-03-20T00:00:00Z date_updated: 2023-08-16T12:41:53Z day: '20' ddc: - '570' department: - _id: GaTk - _id: GradSch doi: 10.1038/s43588-023-00410-9 ec_funded: 1 external_id: arxiv: - '2108.06686' file: - access_level: open_access checksum: 7c63b2b2edfd68aaffe96d70ca6a865a content_type: application/pdf creator: dernst date_created: 2023-08-16T12:39:57Z date_updated: 2023-08-16T12:39:57Z file_id: '14073' file_name: 2023_NatureCompScience_Lombardi.pdf file_size: 4474284 relation: main_file success: 1 file_date_updated: 2023-08-16T12:39:57Z has_accepted_license: '1' intvolume: ' 3' language: - iso: eng month: '03' oa: 1 oa_version: Published Version page: 254-263 project: - _id: 260C2330-B435-11E9-9278-68D0E5697425 call_identifier: H2020 grant_number: '754411' name: ISTplus - Postdoctoral Fellowships - _id: eb943429-77a9-11ec-83b8-9f471cdf5c67 grant_number: M03318 name: Functional Advantages of Critical Brain Dynamics - _id: 626c45b5-2b32-11ec-9570-e509828c1ba6 grant_number: P34015 name: Efficient coding with biophysical realism publication: Nature Computational Science publication_identifier: eissn: - 2662-8457 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Statistical modeling of adaptive neural networks explains co-existence of avalanches and oscillations in resting human brain 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 3 year: '2023' ... --- _id: '14085' abstract: - lang: eng text: We show an (1+ϵ)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m1/2+o(1)ϵ−1/2 amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee. acknowledgement: "This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No.\r\n101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the\r\nAustrian Science Fund (FWF) project “Static and Dynamic Hierarchical Graph Decompositions”,\r\nI 5982-N, and project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nThis work was done in part while Gramoz Goranci was at Institute for Theoretical Studies, ETH Zurich, Switzerland. There, he was supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation. We also thank Richard Peng, Thatchaphol Saranurak, Sebastian Forster and Sushant Sachdeva for helpful discussions, and the anonymous reviewers for their insightful comments." alternative_title: - LIPIcs article_number: '69' article_processing_charge: Yes author: - first_name: Gramoz full_name: Goranci, Gramoz last_name: Goranci - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 citation: ama: 'Goranci G, Henzinger MH. Efficient data structures for incremental exact and approximate maximum flow. In: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.69' apa: 'Goranci, G., & Henzinger, M. H. (2023). Efficient data structures for incremental exact and approximate maximum flow. In 50th International Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.69' chicago: Goranci, Gramoz, and Monika H Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.69. ieee: G. Goranci and M. H. Henzinger, “Efficient data structures for incremental exact and approximate maximum flow,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261. ista: 'Goranci G, Henzinger MH. 2023. Efficient data structures for incremental exact and approximate maximum flow. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 69.' mla: Goranci, Gramoz, and Monika H. Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” 50th International Colloquium on Automata, Languages, and Programming, vol. 261, 69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.69. short: G. Goranci, M.H. Henzinger, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. conference: end_date: 2023-07-14 location: Paderborn, Germany name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2023-07-10 date_created: 2023-08-20T22:01:14Z date_published: 2023-07-01T00:00:00Z date_updated: 2023-08-21T07:00:49Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ICALP.2023.69 ec_funded: 1 external_id: unknown: - '2211.09606' file: - access_level: open_access checksum: 074177e815a1656de5d4071c7a3dffa6 content_type: application/pdf creator: dernst date_created: 2023-08-21T06:59:05Z date_updated: 2023-08-21T06:59:05Z file_id: '14089' file_name: 2023_LIPIcsICALP_Goranci.pdf file_size: 875910 relation: main_file success: 1 file_date_updated: 2023-08-21T06:59:05Z has_accepted_license: '1' intvolume: ' 261' language: - iso: eng month: '07' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: 'P33775 ' name: Fast Algorithms for a Reactive Network Layer publication: 50th International Colloquium on Automata, Languages, and Programming publication_identifier: isbn: - '9783959772785' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Efficient data structures for incremental exact and approximate maximum flow 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: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 261 year: '2023' ... --- _id: '14084' abstract: - lang: eng text: "A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We will consider sampling problems which come from Gibbs distributions, which are families of probability distributions over a discrete space Ω with probability mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max] and H(ω) ∈ {0} ∪ [1, n].\r\nThe partition function is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log Z(β_max))/Z(β_min)\r\nWe develop a number of algorithms to estimate the counts c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²) samples for integer-valued distributions (ignoring some second-order terms and parameters), We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs and perfect matchings in a graph." acknowledgement: We thank Heng Guo for helpful explanations of algorithms for sampling connected subgraphs and matchings, Maksym Serbyn for bringing to our attention the Wang-Landau algorithm and its use in physics. alternative_title: - LIPIcs article_number: '72' article_processing_charge: Yes author: - first_name: David G. full_name: Harris, David G. last_name: Harris - first_name: Vladimir full_name: Kolmogorov, Vladimir id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87 last_name: Kolmogorov citation: ama: 'Harris DG, Kolmogorov V. Parameter estimation for Gibbs distributions. In: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.72' apa: 'Harris, D. G., & Kolmogorov, V. (2023). Parameter estimation for Gibbs distributions. In 50th International Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.72' chicago: Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.72. ieee: D. G. Harris and V. Kolmogorov, “Parameter estimation for Gibbs distributions,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261. ista: 'Harris DG, Kolmogorov V. 2023. Parameter estimation for Gibbs distributions. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 72.' mla: Harris, David G., and Vladimir Kolmogorov. “Parameter Estimation for Gibbs Distributions.” 50th International Colloquium on Automata, Languages, and Programming, vol. 261, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.72. short: D.G. Harris, V. Kolmogorov, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. conference: end_date: 2023-07-14 location: Paderborn, Germany name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2023-07-10 date_created: 2023-08-20T22:01:14Z date_published: 2023-07-01T00:00:00Z date_updated: 2023-08-21T06:49:11Z day: '01' ddc: - '000' - '510' department: - _id: VlKo doi: 10.4230/LIPIcs.ICALP.2023.72 external_id: arxiv: - '2007.10824' file: - access_level: open_access checksum: 6dee0684245bb1c524b9c955db1e933d content_type: application/pdf creator: dernst date_created: 2023-08-21T06:45:16Z date_updated: 2023-08-21T06:45:16Z file_id: '14088' file_name: 2023_LIPIcsICALP_Harris.pdf file_size: 917791 relation: main_file success: 1 file_date_updated: 2023-08-21T06:45:16Z has_accepted_license: '1' intvolume: ' 261' language: - iso: eng month: '07' oa: 1 oa_version: Published Version publication: 50th International Colloquium on Automata, Languages, and Programming publication_identifier: isbn: - '9783959772785' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Parameter estimation for Gibbs distributions 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: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 261 year: '2023' ... --- _id: '14086' abstract: - lang: eng text: "The maximization of submodular functions have found widespread application in areas such as machine learning, combinatorial optimization, and economics, where practitioners often wish to enforce various constraints; the matroid constraint has been investigated extensively due to its algorithmic properties and expressive power. Though tight approximation algorithms for general matroid constraints exist in theory, the running times of such algorithms typically scale quadratically, and are not practical for truly large scale settings. Recent progress has focused on fast algorithms for important classes of matroids given in explicit form. Currently, nearly-linear time algorithms only exist for graphic and partition matroids [Alina Ene and Huy L. Nguyen, 2019]. In this work, we develop algorithms for monotone submodular maximization constrained by graphic, transversal matroids, or laminar matroids in time near-linear in the size of their representation. Our algorithms achieve an optimal approximation of 1-1/e-ε and both generalize and accelerate the results of Ene and Nguyen [Alina Ene and Huy L. Nguyen, 2019]. In fact, the running time of our algorithm cannot be improved within the fast continuous greedy framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák, 2014].\r\nTo achieve near-linear running time, we make use of dynamic data structures that maintain bases with approximate maximum cardinality and weight under certain element updates. These data structures need to support a weight decrease operation and a novel Freeze operation that allows the algorithm to freeze elements (i.e. force to be contained) in its basis regardless of future data structure operations. For the laminar matroid, we present a new dynamic data structure using the top tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et al., 2005] that maintains the maximum weight basis under insertions and deletions of elements in O(log n) time. This data structure needs to support certain subtree query and path update operations that are performed every insertion and deletion that are non-trivial to handle in conjunction. For the transversal matroid the Freeze operation corresponds to requiring the data structure to keep a certain set S of vertices matched, a property that we call S-stability. While there is a large body of work on dynamic matching algorithms, none are S-stable and maintain an approximate maximum weight matching under vertex updates. We give the first such algorithm for bipartite graphs with total running time linear (up to log factors) in the number of edges." acknowledgement: " Monika Henzinger: This project has received funding from the European Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project “Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, and project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. Jan Vondrák: Supported by NSF Award 2127781." alternative_title: - LIPIcs article_number: '74' article_processing_charge: Yes author: - first_name: Monika H full_name: Henzinger, Monika H id: 540c9bbd-f2de-11ec-812d-d04a5be85630 last_name: Henzinger orcid: 0000-0002-5008-6530 - first_name: Paul full_name: Liu, Paul last_name: Liu - first_name: Jan full_name: Vondrák, Jan last_name: Vondrák - first_name: Da Wei full_name: Zheng, Da Wei last_name: Zheng citation: ama: 'Henzinger MH, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for several classes of matroids. In: 50th International Colloquium on Automata, Languages, and Programming. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPIcs.ICALP.2023.74' apa: 'Henzinger, M. H., Liu, P., Vondrák, J., & Zheng, D. W. (2023). Faster submodular maximization for several classes of matroids. In 50th International Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.74' chicago: Henzinger, Monika H, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular Maximization for Several Classes of Matroids.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.74. ieee: M. H. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization for several classes of matroids,” in 50th International Colloquium on Automata, Languages, and Programming, Paderborn, Germany, 2023, vol. 261. ista: 'Henzinger MH, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization for several classes of matroids. 50th International Colloquium on Automata, Languages, and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs, vol. 261, 74.' mla: Henzinger, Monika H., et al. “Faster Submodular Maximization for Several Classes of Matroids.” 50th International Colloquium on Automata, Languages, and Programming, vol. 261, 74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.74. short: M.H. Henzinger, P. Liu, J. Vondrák, D.W. Zheng, in:, 50th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. conference: end_date: 2023-07-14 location: Paderborn, Germany name: 'ICALP: International Colloquium on Automata, Languages, and Programming' start_date: 2023-07-10 date_created: 2023-08-20T22:01:14Z date_published: 2023-07-01T00:00:00Z date_updated: 2023-08-21T07:05:47Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.4230/LIPIcs.ICALP.2023.74 ec_funded: 1 external_id: arxiv: - '2305.00122' file: - access_level: open_access checksum: a5eef225014e003efbfbe4830fdd23cb content_type: application/pdf creator: dernst date_created: 2023-08-21T07:04:36Z date_updated: 2023-08-21T07:04:36Z file_id: '14090' file_name: 2023_LIPIcsICALP_HenzingerM.pdf file_size: 930943 relation: main_file success: 1 file_date_updated: 2023-08-21T07:04:36Z has_accepted_license: '1' intvolume: ' 261' language: - iso: eng month: '07' oa: 1 oa_version: Published Version project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: 'P33775 ' name: Fast Algorithms for a Reactive Network Layer publication: 50th International Colloquium on Automata, Languages, and Programming publication_identifier: isbn: - '9783959772785' issn: - '18688969' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Faster submodular maximization for several classes of matroids 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: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 261 year: '2023' ...