--- _id: '11525' abstract: - lang: eng text: The intensity of the Cosmic UV background (UVB), coming from all sources of ionizing photons such as star-forming galaxies and quasars, determines the thermal evolution and ionization state of the intergalactic medium (IGM) and is, therefore, a critical ingredient for models of cosmic structure formation. Most of the previous estimates are based on the comparison between observed and simulated Lyman-α forest. We present the results of an independent method to constrain the product of the UVB photoionization rate and the covering fraction of Lyman limit systems (LLSs) by searching for the fluorescent Lyman-α emission produced by self-shielded clouds. Because the expected surface brightness is well below current sensitivity limits for direct imaging, we developed a new method based on 3D stacking of the IGM around Lyman-α emitting galaxies (LAEs) between 2.9 < z < 6.6 using deep MUSE observations. Combining our results with covering fractions of LLSs obtained from mock cubes extracted from the EAGLE simulation, we obtain new and independent constraints on the UVB at z > 3 that are consistent with previous measurements, with a preference for relatively low UVB intensities at z = 3, and which suggest a non-monotonic decrease of ΓH I with increasing redshift between 3 < z < 5. This could suggest a possible tension between some UVB models and current observations which however require deeper and wider observations in Lyman-α emission and absorption to be confirmed. Assuming instead a value of UVB from current models, our results constrain the covering fraction of LLSs at 3 < z < 4.5 to be less than 25 per cent within 150 kpc from LAEs. acknowledgement: This research made use of Astropy, a community developed core Python package for Astronomy (Astropy Collaboration et al. 2013). topcat, a graphical tool for manipulating tabular data, was also utilized in this analysis (Taylor 2005). SG would like to thank Nastasha Wijers for the discussion on the column density distribution in EAGLE. SC gratefully acknowledges support from Swiss National Science Foundation grants PP00P2 163824 and PP00P2 190092, and from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme grant agreement No 864361. GP acknowledges support from the Swiss National Science Foundation (SNF) and from the Netherlands Research School for Astronomy (NOVA). article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Sofia G full_name: Gallego, Sofia G last_name: Gallego - first_name: Sebastiano full_name: Cantalupo, Sebastiano last_name: Cantalupo - first_name: Saeed full_name: Sarpas, Saeed last_name: Sarpas - first_name: Bastien full_name: Duboeuf, Bastien last_name: Duboeuf - first_name: Simon full_name: Lilly, Simon last_name: Lilly - first_name: Gabriele full_name: Pezzulli, Gabriele last_name: Pezzulli - first_name: Raffaella Anna full_name: Marino, Raffaella Anna last_name: Marino - first_name: Jorryt J full_name: Matthee, Jorryt J id: 7439a258-f3c0-11ec-9501-9df22fe06720 last_name: Matthee orcid: 0000-0003-2871-127X - first_name: Lutz full_name: Wisotzki, Lutz last_name: Wisotzki - first_name: Joop full_name: Schaye, Joop last_name: Schaye - first_name: Johan full_name: Richard, Johan last_name: Richard - first_name: Haruka full_name: Kusakabe, Haruka last_name: Kusakabe - first_name: Valentin full_name: Mauerhofer, Valentin last_name: Mauerhofer citation: ama: Gallego SG, Cantalupo S, Sarpas S, et al. Constraining the cosmic UV background at z > 3 with MUSE Lyman-α emission observations. Monthly Notices of the Royal Astronomical Society. 2021;504(1):16-32. doi:10.1093/mnras/stab796 apa: Gallego, S. G., Cantalupo, S., Sarpas, S., Duboeuf, B., Lilly, S., Pezzulli, G., … Mauerhofer, V. (2021). Constraining the cosmic UV background at z > 3 with MUSE Lyman-α emission observations. Monthly Notices of the Royal Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/stab796 chicago: Gallego, Sofia G, Sebastiano Cantalupo, Saeed Sarpas, Bastien Duboeuf, Simon Lilly, Gabriele Pezzulli, Raffaella Anna Marino, et al. “Constraining the Cosmic UV Background at z > 3 with MUSE Lyman-α Emission Observations.” Monthly Notices of the Royal Astronomical Society. Oxford University Press, 2021. https://doi.org/10.1093/mnras/stab796. ieee: S. G. Gallego et al., “Constraining the cosmic UV background at z > 3 with MUSE Lyman-α emission observations,” Monthly Notices of the Royal Astronomical Society, vol. 504, no. 1. Oxford University Press, pp. 16–32, 2021. ista: Gallego SG, Cantalupo S, Sarpas S, Duboeuf B, Lilly S, Pezzulli G, Marino RA, Matthee JJ, Wisotzki L, Schaye J, Richard J, Kusakabe H, Mauerhofer V. 2021. Constraining the cosmic UV background at z > 3 with MUSE Lyman-α emission observations. Monthly Notices of the Royal Astronomical Society. 504(1), 16–32. mla: Gallego, Sofia G., et al. “Constraining the Cosmic UV Background at z > 3 with MUSE Lyman-α Emission Observations.” Monthly Notices of the Royal Astronomical Society, vol. 504, no. 1, Oxford University Press, 2021, pp. 16–32, doi:10.1093/mnras/stab796. short: S.G. Gallego, S. Cantalupo, S. Sarpas, B. Duboeuf, S. Lilly, G. Pezzulli, R.A. Marino, J.J. Matthee, L. Wisotzki, J. Schaye, J. Richard, H. Kusakabe, V. Mauerhofer, Monthly Notices of the Royal Astronomical Society 504 (2021) 16–32. date_created: 2022-07-07T10:07:11Z date_published: 2021-06-01T00:00:00Z date_updated: 2022-08-18T10:54:19Z day: '01' doi: 10.1093/mnras/stab796 extern: '1' external_id: arxiv: - '2103.09250' intvolume: ' 504' issue: '1' keyword: - Space and Planetary Science - Astronomy and Astrophysics language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2103.09250 month: '06' oa: 1 oa_version: Preprint page: 16-32 publication: Monthly Notices of the Royal Astronomical Society publication_identifier: eissn: - 1365-2966 issn: - 0035-8711 publication_status: published publisher: Oxford University Press quality_controlled: '1' scopus_import: '1' status: public title: Constraining the cosmic UV background at z > 3 with MUSE Lyman-α emission observations type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 504 year: '2021' ... --- _id: '11526' abstract: - lang: eng text: We present the results from a MUSE survey of twelve z ≃ 3.15 quasars, which were selected to be much fainter (20 < iSDSS < 23) than in previous studies of giant Ly α nebulae around the brightest quasars (16.6 < iAB < 18.7). We detect H I Ly α nebulae around 100 per cent of our target quasars, with emission extending to scales of at least 60 physical kpc, and up to 190 pkpc. We explore correlations between properties of the nebulae and their host quasars, with the goal of connecting variations in the properties of the illuminating QSO to the response in nebular emission. We show that the surface brightness profiles of the nebulae are similar to those of nebulae around bright quasars, but with a lower normalization. Our targeted quasars are on average 3.7 mag (≃30 times) fainter in UV continuum than our bright reference sample, and yet the nebulae around them are only 4.3 times fainter in mean Ly α surface brightness, measured between 20 and 50 pkpc. We find significant correlations between the surface brightness of the nebula and the luminosity of the quasar in both UV continuum and Ly α. The latter can be interpreted as evidence for a substantial contribution from unresolved inner parts of the nebulae to the narrow components seen in the Ly α lines of some of our faint quasars, possibly from the inner circumgalactic medium or from the host galaxy’s interstellar medium. acknowledgement: The authors thank Daichi Kashino, for providing access to unpublished zCOSMOS Deep data, and Jakob S. den Brok for sharing code used in den Brok et al. (2020). GP and SC acknowledge the support of the Swiss National Science Foundation [grant PP00P2163824]. SM is supported by the Experienced Researchers Fellowship, Alexander von Humboldt-Stiftung, Germany. This work is based on observations collected at the European Organisation for Astronomical Research in the Southern Hemisphere under the MUSE GTO programme. The major analysis and production of figures in this work was conducted in Python, using standard libraries which include NumPy (Harris et al. 2020), SciPy (Virtanen et al. 2020), Matplotlib (Hunter 2007) and the interactive command shell IPython (Pérez & Granger 2007). This research also made use of Astropy, a community-developed core Python package for Astronomy (Astropy Collaboration et al. 2013), and Photutils, an Astropy package for detection and photometry of astronomica sources (Bradley et al. 2019). The python interface dustmaps (Green 2018) was used to query galactic extinction maps. topcat, a graphical tool for manipulating tabular data, was also utilized in this analysis (Taylor 2005). This research has made use of the "Aladin sky atlas" developed at CDS, Strasbourg Observatory, France (Bonnarel et al. 2000). article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Ruari full_name: Mackenzie, Ruari last_name: Mackenzie - first_name: Gabriele full_name: Pezzulli, Gabriele last_name: Pezzulli - first_name: Sebastiano full_name: Cantalupo, Sebastiano last_name: Cantalupo - first_name: Raffaella A full_name: Marino, Raffaella A last_name: Marino - first_name: Simon full_name: Lilly, Simon last_name: Lilly - first_name: Sowgat full_name: Muzahid, Sowgat last_name: Muzahid - first_name: Jorryt J full_name: Matthee, Jorryt J id: 7439a258-f3c0-11ec-9501-9df22fe06720 last_name: Matthee orcid: 0000-0003-2871-127X - first_name: Joop full_name: Schaye, Joop last_name: Schaye - first_name: Lutz full_name: Wisotzki, Lutz last_name: Wisotzki citation: ama: Mackenzie R, Pezzulli G, Cantalupo S, et al. Revealing the impact of quasar luminosity on giant Lyα nebulae. Monthly Notices of the Royal Astronomical Society. 2021;502(1):494-509. doi:10.1093/mnras/staa3277 apa: Mackenzie, R., Pezzulli, G., Cantalupo, S., Marino, R. A., Lilly, S., Muzahid, S., … Wisotzki, L. (2021). Revealing the impact of quasar luminosity on giant Lyα nebulae. Monthly Notices of the Royal Astronomical Society. Oxford University Press. https://doi.org/10.1093/mnras/staa3277 chicago: Mackenzie, Ruari, Gabriele Pezzulli, Sebastiano Cantalupo, Raffaella A Marino, Simon Lilly, Sowgat Muzahid, Jorryt J Matthee, Joop Schaye, and Lutz Wisotzki. “Revealing the Impact of Quasar Luminosity on Giant Lyα Nebulae.” Monthly Notices of the Royal Astronomical Society. Oxford University Press, 2021. https://doi.org/10.1093/mnras/staa3277. ieee: R. Mackenzie et al., “Revealing the impact of quasar luminosity on giant Lyα nebulae,” Monthly Notices of the Royal Astronomical Society, vol. 502, no. 1. Oxford University Press, pp. 494–509, 2021. ista: Mackenzie R, Pezzulli G, Cantalupo S, Marino RA, Lilly S, Muzahid S, Matthee JJ, Schaye J, Wisotzki L. 2021. Revealing the impact of quasar luminosity on giant Lyα nebulae. Monthly Notices of the Royal Astronomical Society. 502(1), 494–509. mla: Mackenzie, Ruari, et al. “Revealing the Impact of Quasar Luminosity on Giant Lyα Nebulae.” Monthly Notices of the Royal Astronomical Society, vol. 502, no. 1, Oxford University Press, 2021, pp. 494–509, doi:10.1093/mnras/staa3277. short: R. Mackenzie, G. Pezzulli, S. Cantalupo, R.A. Marino, S. Lilly, S. Muzahid, J.J. Matthee, J. Schaye, L. Wisotzki, Monthly Notices of the Royal Astronomical Society 502 (2021) 494–509. date_created: 2022-07-07T10:11:15Z date_published: 2021-03-01T00:00:00Z date_updated: 2022-08-18T10:56:28Z day: '01' doi: 10.1093/mnras/staa3277 extern: '1' external_id: arxiv: - '2010.12589' intvolume: ' 502' issue: '1' keyword: - Space and Planetary Science - Astronomy and Astrophysics - 'techniques: imaging spectroscopy' - intergalactic medium - 'quasars: emission lines' - 'quasars: general' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2010.12589 month: '03' oa: 1 oa_version: Preprint page: 494-509 publication: Monthly Notices of the Royal Astronomical Society publication_identifier: eissn: - 1365-2966 issn: - 0035-8711 publication_status: published publisher: Oxford University Press quality_controlled: '1' scopus_import: '1' status: public title: Revealing the impact of quasar luminosity on giant Lyα nebulae type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 502 year: '2021' ... --- _id: '11585' abstract: - lang: eng text: "Observations show that star-forming galaxies reside on a tight three-dimensional plane between mass, gas-phase metallicity and star formation rate (SFR), which can be explained by the interplay between metal-poor gas inflows, SFR and outflows. However, different metals are released on different time-scales, which may affect the slope of this relation. Here, we use central, star-forming galaxies with Mstar = 109.0−10.5 M\f from the EAGLE hydrodynamical simulation to examine three-dimensional relations between mass, SFR and chemical enrichment using absolute and relative C, N, O and Fe abundances. We show that the scatter is smaller when gas-phase α-enhancement is used rather than metallicity. A similar plane also exists for stellar α-enhancement, implying that present-day specific SFRs are correlated with long time-scale star formation histories. Between z = 0 and 1, the α-enhancement plane is even more insensitive to redshift than the plane using metallicity. However, it evolves at z > 1 due to lagging iron yields. At fixed mass, galaxies with higher SFRs have star formation histories shifted toward late times, are more α-enhanced and this α-enhancement increases with redshift as observed. These findings suggest that relations between physical properties inferred from observations may be affected by systematic variations in α-enhancements." acknowledgement: We thank the anonymous referee for their constructive comments. JM acknowledges the support of a Huygens PhD fellowship from Leiden University. We thank Jarle Brinchmann, Rob Crain and David Sobral for discussions. We acknowledge the use of the Topcat software (Taylor 2013) for assisting in rapid exploration of multi-dimensional datasets and the use of Python and its numpy, matplotlib and pandas packages. article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Jorryt J full_name: Matthee, Jorryt J id: 7439a258-f3c0-11ec-9501-9df22fe06720 last_name: Matthee orcid: 0000-0003-2871-127X citation: ama: Matthee JJ. Differences in galaxy colours are not just about the mass. Nature Astronomy. 2021;5:984-985. doi:10.1038/s41550-021-01415-y apa: Matthee, J. J. (2021). Differences in galaxy colours are not just about the mass. Nature Astronomy. Springer Nature. https://doi.org/10.1038/s41550-021-01415-y chicago: Matthee, Jorryt J. “Differences in Galaxy Colours Are Not Just about the Mass.” Nature Astronomy. Springer Nature, 2021. https://doi.org/10.1038/s41550-021-01415-y. ieee: J. J. Matthee, “Differences in galaxy colours are not just about the mass,” Nature Astronomy, vol. 5. Springer Nature, pp. 984–985, 2021. ista: Matthee JJ. 2021. Differences in galaxy colours are not just about the mass. Nature Astronomy. 5, 984–985. mla: Matthee, Jorryt J. “Differences in Galaxy Colours Are Not Just about the Mass.” Nature Astronomy, vol. 5, Springer Nature, 2021, pp. 984–85, doi:10.1038/s41550-021-01415-y. short: J.J. Matthee, Nature Astronomy 5 (2021) 984–985. date_created: 2022-07-14T13:13:39Z date_published: 2021-07-05T00:00:00Z date_updated: 2024-10-14T11:38:08Z day: '05' doi: 10.1038/s41550-021-01415-y extern: '1' external_id: arxiv: - '1802.06786' intvolume: ' 5' keyword: - Astronomy and Astrophysics - galaxies - formation - galaxies - evolution - galaxies - star formation - galaxies - abundances language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1802.06786 month: '07' oa: 1 oa_version: Preprint page: 984-985 publication: Nature Astronomy publication_identifier: eissn: - 2397-3366 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Differences in galaxy colours are not just about the mass type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 5 year: '2021' ... --- _id: '11604' abstract: - lang: eng text: The NASA Transiting Exoplanet Survey Satellite (TESS) is observing tens of millions of stars with time spans ranging from ∼27 days to about 1 yr of continuous observations. This vast amount of data contains a wealth of information for variability, exoplanet, and stellar astrophysics studies but requires a number of processing steps before it can be fully utilized. In order to efficiently process all the TESS data and make it available to the wider scientific community, the TESS Data for Asteroseismology working group, as part of the TESS Asteroseismic Science Consortium, has created an automated open-source processing pipeline to produce light curves corrected for systematics from the short- and long-cadence raw photometry data and to classify these according to stellar variability type. We will process all stars down to a TESS magnitude of 15. This paper is the next in a series detailing how the pipeline works. Here, we present our methodology for the automatic variability classification of TESS photometry using an ensemble of supervised learners that are combined into a metaclassifier. We successfully validate our method using a carefully constructed labeled sample of Kepler Q9 light curves with a 27.4 days time span mimicking single-sector TESS observations, on which we obtain an overall accuracy of 94.9%. We demonstrate that our methodology can successfully classify stars outside of our labeled sample by applying it to all ∼167,000 stars observed in Q9 of the Kepler space mission. acknowledgement: "The research leading to these results has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 670519: MAMSIE), from the KU Leuven Research Council (grant C16/18/005: PARADISE), from the Research Foundation Flanders (FWO) under grant agreement G0H5416N (ERC Runner Up Project), as well as from the BELgian federal Science Policy Office (BELSPO) through PRODEX grant PLATO. D.J.A acknowledges support from the STFC via an Ernest Rutherford Fellowship (ST/R00384X/1). Funding for the Stellar Astrophysics Centre is provided by The Danish National Research Foundation (grant agreement No.: DNRF106). R.H. and M.N.L. acknowledge the ESA PRODEX program. This research was supported by the National Aeronautics and Space Administration (80NSSC18K1585 and 80NSSC19K0379) awarded through the TESS Guest Investigator Program. K.J.B. is supported by the National Science Foundation under Award AST-1903828. J.S.K and K.J.B. were supported by funding from the European Research Council under the European Community's Seventh Framework Programme (FP7/2007-2013)/ERC grant agreement no. 338251 (StellarAges). D.M.B. gratefully acknowledges funding from a senior postdoctoral fellowship from the Research Foundation Flanders (FWO) with grant agreement No. 1286521N. The research leading to these results has received funding from the Research Foundation Flanders (FWO) under grant agreement G0A2917N (BlackGEM). R.A.G. acknowledges support from the GOLF and PLATO CNES grants. L.M. was supported by the Premium Postdoctoral Research Program of the Hungarian Academy of Sciences. The research leading to these results has been supported by the Hungarian National Research, Development, and Innovation Office (NKFIH) grant KH_18 130405 and the Lendület LP2014-17 and LP2018-7/2020 grants of the Hungarian Academy of Sciences. D.B. acknowledges support from the NASA TESS Guest Investigator Program under award 80NSSC19K0385.\r\n\r\nThis paper includes data collected by the TESS mission, which are publicly available from the Mikulski Archive for Space Telescopes (MAST). Funding for the TESS mission is provided by NASA's Science Mission directorate. This research has made use of NASA's Astrophysics Data System as well as the NASA/IPAC Extragalactic Database (NED) which is operated by the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration. Funding for the TESS Asteroseismic Science Operations Centre is provided by the Danish National Research Foundation (Grant agreement no.: DNRF106), ESA PRODEX (PEA 4000119301), and the Stellar Astrophysics Centre (SAC) at Aarhus University. We thank the TESS team and staff and TASC/TASOC for their support of the present work.\r\n\r\nThis paper includes data collected by the Kepler mission. Funding for the Kepler and K2 mission was provided by NASA's Science Mission Directorate. The authors acknowledge the efforts of the Kepler Mission team in obtaining the light-curve data and data validation products used in this publication. These data were generated by the Kepler Mission science pipeline through the efforts of the Kepler Science Operations Center and Science Office. The Kepler light curves are archived at the Mikulski Archive for Space Telescopes.\r\n\r\nThe numerical results presented in this work were obtained at the Centre for Scientific Computing, Aarhus. 37 This research made use of Astropy, a community-developed core Python package for Astronomy (Astropy Collaboration et al. 2013, 2018).\r\n\r\nSoftware: Scikit-learn (Pedregosa et al. 2011), Numpy (Harris et al. 2020), Astropy (Astropy Collaboration et al. 2013, 2018), Scipy (Virtanen et al. 2020), Pandas (McKinney 2010; Pandas Development Team 2020), Lightkurve (Lightkurve Collaboration et al. 2018), XGBoost (Chen & Guestrin 2016), Tensorflow (Abadi et al. 2015)." article_number: '209' article_processing_charge: No article_type: original arxiv: 1 author: - first_name: J. full_name: Audenaert, J. last_name: Audenaert - first_name: J. S. full_name: Kuszlewicz, J. S. last_name: Kuszlewicz - first_name: R. full_name: Handberg, R. last_name: Handberg - first_name: A. full_name: Tkachenko, A. last_name: Tkachenko - first_name: D. J. full_name: Armstrong, D. J. last_name: Armstrong - first_name: M. full_name: Hon, M. last_name: Hon - first_name: R. full_name: Kgoadi, R. last_name: Kgoadi - first_name: M. N. full_name: Lund, M. N. last_name: Lund - first_name: K. J. full_name: Bell, K. J. last_name: Bell - first_name: Lisa Annabelle full_name: Bugnet, Lisa Annabelle id: d9edb345-f866-11ec-9b37-d119b5234501 last_name: Bugnet orcid: 0000-0003-0142-4000 - first_name: D. M. full_name: Bowman, D. M. last_name: Bowman - first_name: C. full_name: Johnston, C. last_name: Johnston - first_name: R. A. full_name: García, R. A. last_name: García - first_name: D. full_name: Stello, D. last_name: Stello - first_name: L. full_name: Molnár, L. last_name: Molnár - first_name: E. full_name: Plachy, E. last_name: Plachy - first_name: D. full_name: Buzasi, D. last_name: Buzasi - first_name: C. full_name: Aerts, C. last_name: Aerts citation: ama: 'Audenaert J, Kuszlewicz JS, Handberg R, et al. TESS Data for Asteroseismology (T’DA) stellar variability classification pipeline: Setup and application to the Kepler Q9 data. The Astronomical Journal. 2021;162(5). doi:10.3847/1538-3881/ac166a' apa: 'Audenaert, J., Kuszlewicz, J. S., Handberg, R., Tkachenko, A., Armstrong, D. J., Hon, M., … Aerts, C. (2021). TESS Data for Asteroseismology (T’DA) stellar variability classification pipeline: Setup and application to the Kepler Q9 data. The Astronomical Journal. IOP Publishing. https://doi.org/10.3847/1538-3881/ac166a' chicago: 'Audenaert, J., J. S. Kuszlewicz, R. Handberg, A. Tkachenko, D. J. Armstrong, M. Hon, R. Kgoadi, et al. “TESS Data for Asteroseismology (T’DA) Stellar Variability Classification Pipeline: Setup and Application to the Kepler Q9 Data.” The Astronomical Journal. IOP Publishing, 2021. https://doi.org/10.3847/1538-3881/ac166a.' ieee: 'J. Audenaert et al., “TESS Data for Asteroseismology (T’DA) stellar variability classification pipeline: Setup and application to the Kepler Q9 data,” The Astronomical Journal, vol. 162, no. 5. IOP Publishing, 2021.' ista: 'Audenaert J, Kuszlewicz JS, Handberg R, Tkachenko A, Armstrong DJ, Hon M, Kgoadi R, Lund MN, Bell KJ, Bugnet LA, Bowman DM, Johnston C, García RA, Stello D, Molnár L, Plachy E, Buzasi D, Aerts C. 2021. TESS Data for Asteroseismology (T’DA) stellar variability classification pipeline: Setup and application to the Kepler Q9 data. The Astronomical Journal. 162(5), 209.' mla: 'Audenaert, J., et al. “TESS Data for Asteroseismology (T’DA) Stellar Variability Classification Pipeline: Setup and Application to the Kepler Q9 Data.” The Astronomical Journal, vol. 162, no. 5, 209, IOP Publishing, 2021, doi:10.3847/1538-3881/ac166a.' short: J. Audenaert, J.S. Kuszlewicz, R. Handberg, A. Tkachenko, D.J. Armstrong, M. Hon, R. Kgoadi, M.N. Lund, K.J. Bell, L.A. Bugnet, D.M. Bowman, C. Johnston, R.A. García, D. Stello, L. Molnár, E. Plachy, D. Buzasi, C. Aerts, The Astronomical Journal 162 (2021). date_created: 2022-07-18T11:54:55Z date_published: 2021-10-21T00:00:00Z date_updated: 2022-08-19T10:01:56Z day: '21' doi: 10.3847/1538-3881/ac166a extern: '1' external_id: arxiv: - '2107.06301' intvolume: ' 162' issue: '5' keyword: - Space and Planetary Science - Astronomy and Astrophysics language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2107.06301 month: '10' oa: 1 oa_version: Preprint publication: The Astronomical Journal publication_identifier: eissn: - 1538-3881 issn: - 0004-6256 publication_status: published publisher: IOP Publishing quality_controlled: '1' scopus_import: '1' status: public title: 'TESS Data for Asteroseismology (T’DA) stellar variability classification pipeline: Setup and application to the Kepler Q9 data' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 162 year: '2021' ... --- _id: '11605' abstract: - lang: eng text: "Context. The discovery of moderate differential rotation between the core and the envelope of evolved solar-like stars could be the signature of a strong magnetic field trapped inside the radiative interior. The population of intermediate-mass red giants presenting surprisingly low-amplitude mixed modes (i.e. oscillation modes that behave as acoustic modes in their external envelope and as gravity modes in their core) could also arise from the effect of an internal magnetic field. Indeed, stars more massive than about 1.1 solar masses are known to develop a convective core during their main sequence. The field generated by the dynamo triggered by this convection could be the progenitor of a strong fossil magnetic field trapped inside the core of the star for the remainder of its evolution.\r\n\r\nAims. Observations of mixed modes can constitute an excellent probe of the deepest layers of evolved solar-like stars, and magnetic fields in those regions can impact their propagation. The magnetic perturbation on mixed modes may therefore be visible in asteroseismic data. To unravel which constraints can be obtained from observations, we theoretically investigate the effects of a plausible mixed axisymmetric magnetic field with various amplitudes on the mixed-mode frequencies of evolved solar-like stars.\r\n\r\nMethods. First-order frequency perturbations due to an axisymmetric magnetic field were computed for dipolar and quadrupolar mixed modes. These computations were carried out for a range of stellar ages, masses, and metallicities.\r\n\r\nConclusions. We show that typical fossil-field strengths of 0.1 − 1 MG, consistent with the presence of a dynamo in the convective core during the main sequence, provoke significant asymmetries on mixed-mode frequency multiplets during the red giant branch. We provide constraints and methods for the detectability of such magnetic signatures. We show that these signatures may be detectable in asteroseismic data for field amplitudes small enough for the amplitude of the modes not to be affected by the conversion of gravity into Alfvén waves inside the magnetised interior. Finally, we infer an upper limit for the strength of the field and the associated lower limit for the timescale of its action in order to redistribute angular momentum in stellar interiors." article_number: A53 article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Lisa Annabelle full_name: Bugnet, Lisa Annabelle id: d9edb345-f866-11ec-9b37-d119b5234501 last_name: Bugnet orcid: 0000-0003-0142-4000 - first_name: V. full_name: Prat, V. last_name: Prat - first_name: S. full_name: Mathis, S. last_name: Mathis - first_name: A. full_name: Astoul, A. last_name: Astoul - first_name: K. full_name: Augustson, K. last_name: Augustson - first_name: R. A. full_name: García, R. A. last_name: García - first_name: S. full_name: Mathur, S. last_name: Mathur - first_name: L. full_name: Amard, L. last_name: Amard - first_name: C. full_name: Neiner, C. last_name: Neiner citation: ama: 'Bugnet LA, Prat V, Mathis S, et al. Magnetic signatures on mixed-mode frequencies: I. An axisymmetric fossil field inside the core of red giants. Astronomy & Astrophysics. 2021;650. doi:10.1051/0004-6361/202039159' apa: 'Bugnet, L. A., Prat, V., Mathis, S., Astoul, A., Augustson, K., García, R. A., … Neiner, C. (2021). Magnetic signatures on mixed-mode frequencies: I. An axisymmetric fossil field inside the core of red giants. Astronomy & Astrophysics. EDP Sciences. https://doi.org/10.1051/0004-6361/202039159' chicago: 'Bugnet, Lisa Annabelle, V. Prat, S. Mathis, A. Astoul, K. Augustson, R. A. García, S. Mathur, L. Amard, and C. Neiner. “Magnetic Signatures on Mixed-Mode Frequencies: I. An Axisymmetric Fossil Field inside the Core of Red Giants.” Astronomy & Astrophysics. EDP Sciences, 2021. https://doi.org/10.1051/0004-6361/202039159.' ieee: 'L. A. Bugnet et al., “Magnetic signatures on mixed-mode frequencies: I. An axisymmetric fossil field inside the core of red giants,” Astronomy & Astrophysics, vol. 650. EDP Sciences, 2021.' ista: 'Bugnet LA, Prat V, Mathis S, Astoul A, Augustson K, García RA, Mathur S, Amard L, Neiner C. 2021. Magnetic signatures on mixed-mode frequencies: I. An axisymmetric fossil field inside the core of red giants. Astronomy & Astrophysics. 650, A53.' mla: 'Bugnet, Lisa Annabelle, et al. “Magnetic Signatures on Mixed-Mode Frequencies: I. An Axisymmetric Fossil Field inside the Core of Red Giants.” Astronomy & Astrophysics, vol. 650, A53, EDP Sciences, 2021, doi:10.1051/0004-6361/202039159.' short: L.A. Bugnet, V. Prat, S. Mathis, A. Astoul, K. Augustson, R.A. García, S. Mathur, L. Amard, C. Neiner, Astronomy & Astrophysics 650 (2021). date_created: 2022-07-18T12:10:59Z date_published: 2021-06-07T00:00:00Z date_updated: 2024-10-14T11:39:01Z day: '07' doi: 10.1051/0004-6361/202039159 extern: '1' external_id: arxiv: - '2102.01216' intvolume: ' 650' keyword: - Space and Planetary Science - Astronomy and Astrophysics - stars - oscillations / stars - magnetic field / stars - interiors / stars - evolution / stars - rotation language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2102.01216 month: '06' oa: 1 oa_version: Preprint publication: Astronomy & Astrophysics publication_identifier: eissn: - 1432-0746 issn: - 0004-6361 publication_status: published publisher: EDP Sciences quality_controlled: '1' scopus_import: '1' status: public title: 'Magnetic signatures on mixed-mode frequencies: I. An axisymmetric fossil field inside the core of red giants' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 650 year: '2021' ... --- _id: '11606' abstract: - lang: eng text: "Context. Our knowledge of the dynamics of stars has undergone a revolution through the simultaneous large amount of high-quality photometric observations collected by space-based asteroseismology and ground-based high-precision spectropolarimetry. They allowed us to probe the internal rotation of stars and their surface magnetism in the whole Hertzsprung-Russell diagram. However, new methods should still be developed to probe the deep magnetic fields in these stars.\r\n\r\nAims. Our goal is to provide seismic diagnoses that allow us to probe the internal magnetism of stars.\r\n\r\nMethods. We focused on asymptotic low-frequency gravity modes and high-frequency acoustic modes. Using a first-order perturbative theory, we derived magnetic splittings of their frequencies as explicit functions of stellar parameters.\r\n\r\nResults. As in the case of rotation, we show that asymptotic gravity and acoustic modes can allow us to probe the different components of the magnetic field in the cavities in which they propagate. This again demonstrates the high potential of using mixed-modes when this is possible." acknowledgement: The authors thank the referee and Pr. J. Christensen-Dalsgaard for their very constructive comments and remarks that allowed us to improve the article. St. M., L. B., V. P., and K. A. acknowledge support from the European Research Council through ERC grant SPIRE 647383. All the members from CEA acknowledge support from GOLF and PLATO CNES grants of the Astrophysics Division at CEA. S. Mathur acknowledges support by the Ramon y Cajal fellowship number RYC-2015-17697. We made great use of the megyr python package for interfacing MESA and GYRE codes. article_number: A122 article_processing_charge: No article_type: original arxiv: 1 author: - first_name: S. full_name: Mathis, S. last_name: Mathis - first_name: Lisa Annabelle full_name: Bugnet, Lisa Annabelle id: d9edb345-f866-11ec-9b37-d119b5234501 last_name: Bugnet orcid: 0000-0003-0142-4000 - first_name: V. full_name: Prat, V. last_name: Prat - first_name: K. full_name: Augustson, K. last_name: Augustson - first_name: S. full_name: Mathur, S. last_name: Mathur - first_name: R. A. full_name: Garcia, R. A. last_name: Garcia citation: ama: Mathis S, Bugnet LA, Prat V, Augustson K, Mathur S, Garcia RA. Probing the internal magnetism of stars using asymptotic magneto-asteroseismology. Astronomy & Astrophysics. 2021;647. doi:10.1051/0004-6361/202039180 apa: Mathis, S., Bugnet, L. A., Prat, V., Augustson, K., Mathur, S., & Garcia, R. A. (2021). Probing the internal magnetism of stars using asymptotic magneto-asteroseismology. Astronomy & Astrophysics. EDP Sciences. https://doi.org/10.1051/0004-6361/202039180 chicago: Mathis, S., Lisa Annabelle Bugnet, V. Prat, K. Augustson, S. Mathur, and R. A. Garcia. “Probing the Internal Magnetism of Stars Using Asymptotic Magneto-Asteroseismology.” Astronomy & Astrophysics. EDP Sciences, 2021. https://doi.org/10.1051/0004-6361/202039180. ieee: S. Mathis, L. A. Bugnet, V. Prat, K. Augustson, S. Mathur, and R. A. Garcia, “Probing the internal magnetism of stars using asymptotic magneto-asteroseismology,” Astronomy & Astrophysics, vol. 647. EDP Sciences, 2021. ista: Mathis S, Bugnet LA, Prat V, Augustson K, Mathur S, Garcia RA. 2021. Probing the internal magnetism of stars using asymptotic magneto-asteroseismology. Astronomy & Astrophysics. 647, A122. mla: Mathis, S., et al. “Probing the Internal Magnetism of Stars Using Asymptotic Magneto-Asteroseismology.” Astronomy & Astrophysics, vol. 647, A122, EDP Sciences, 2021, doi:10.1051/0004-6361/202039180. short: S. Mathis, L.A. Bugnet, V. Prat, K. Augustson, S. Mathur, R.A. Garcia, Astronomy & Astrophysics 647 (2021). date_created: 2022-07-18T12:15:27Z date_published: 2021-03-18T00:00:00Z date_updated: 2024-10-14T11:39:21Z day: '18' doi: 10.1051/0004-6361/202039180 extern: '1' external_id: arxiv: - '2012.11050' intvolume: ' 647' keyword: - Space and Planetary Science - Astronomy and Astrophysics - asteroseismology / waves / stars - magnetic field / stars - oscillations / methods - analytical language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2012.11050 month: '03' oa: 1 oa_version: Preprint publication: Astronomy & Astrophysics publication_identifier: eissn: - 1432-0746 issn: - 0004-6361 publication_status: published publisher: EDP Sciences quality_controlled: '1' scopus_import: '1' status: public title: Probing the internal magnetism of stars using asymptotic magneto-asteroseismology type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 647 year: '2021' ... --- _id: '11608' abstract: - lang: eng text: 'In order to understand stellar evolution, it is crucial to efficiently determine stellar surface rotation periods. Indeed, while they are of great importance in stellar models, angular momentum transport processes inside stars are still poorly understood today. Surface rotation, which is linked to the age of the star, is one of the constraints needed to improve the way those processes are modelled. Statistics of the surface rotation periods for a large sample of stars of different spectral types are thus necessary. An efficient tool to automatically determine reliable rotation periods is needed when dealing with large samples of stellar photometric datasets. The objective of this work is to develop such a tool. For this purpose, machine learning classifiers constitute relevant bases to build our new methodology. Random forest learning abilities are exploited to automate the extraction of rotation periods in Kepler light curves. Rotation periods and complementary parameters are obtained via three different methods: a wavelet analysis, the autocorrelation function of the light curve, and the composite spectrum. We trained three different classifiers: one to detect if rotational modulations are present in the light curve, one to flag close binary or classical pulsators candidates that can bias our rotation period determination, and finally one classifier to provide the final rotation period. We tested our machine learning pipeline on 23 431 stars of the Kepler K and M dwarf reference rotation catalogue for which 60% of the stars have been visually inspected. For the sample of 21 707 stars where all the input parameters are provided to the algorithm, 94.2% of them are correctly classified (as rotating or not). Among the stars that have a rotation period in the reference catalogue, the machine learning provides a period that agrees within 10% of the reference value for 95.3% of the stars. Moreover, the yield of correct rotation periods is raised to 99.5% after visually inspecting 25.2% of the stars. Over the two main analysis steps, rotation classification and period selection, the pipeline yields a global agreement with the reference values of 92.1% and 96.9% before and after visual inspection. Random forest classifiers are efficient tools to determine reliable rotation periods in large samples of stars. The methodology presented here could be easily adapted to extract surface rotation periods for stars with different spectral types or observed by other instruments such as K2, TESS or by PLATO in the near future.' acknowledgement: 'We thank Suzanne Aigrain and Joe Llama for providing us with the simulated data used in Aigrain et al. (2015). S. N. B., L. B. and R. A. G. acknowledge the support from PLATO and GOLF CNES grants. A. R. G. S. acknowledges the support from NASA under grant NNX17AF27G. S. M. acknowledges the support from the Spanish Ministry of Science and Innovation with the Ramon y Cajal fellowship number RYC-2015-17697. P. L. P. and S. M. acknowledge support from the Spanish Ministry of Science and Innovation with the grant number PID2019-107187GB-I00. This research has made use of the NASA Exoplanet Archive, which is operated by the California Institute of Technology, under contract with the National Aeronautics and Space Administration under the Exoplanet Exploration Program. Software: Python (Van Rossum & Drake 2009), numpy (Oliphant 2006), pandas (The pandas development team 2020; McKinney 2010), matplotlib (Hunter 2007), scikit-learn (Pedregosa et al. 2011). The source code used to obtain the present results can be found at: https://gitlab.com/sybreton/pushkin ; https://gitlab.com/sybreton/ml_surface_rotation_paper .' article_number: A125 article_processing_charge: No article_type: original arxiv: 1 author: - first_name: S. N. full_name: Breton, S. N. last_name: Breton - first_name: A. R. G. full_name: Santos, A. R. G. last_name: Santos - first_name: Lisa Annabelle full_name: Bugnet, Lisa Annabelle id: d9edb345-f866-11ec-9b37-d119b5234501 last_name: Bugnet orcid: 0000-0003-0142-4000 - first_name: S. full_name: Mathur, S. last_name: Mathur - first_name: R. A. full_name: García, R. A. last_name: García - first_name: P. L. full_name: Pallé, P. L. last_name: Pallé citation: ama: 'Breton SN, Santos ARG, Bugnet LA, Mathur S, García RA, Pallé PL. ROOSTER: A machine-learning analysis tool for Kepler stellar rotation periods. Astronomy & Astrophysics. 2021;647. doi:10.1051/0004-6361/202039947' apa: 'Breton, S. N., Santos, A. R. G., Bugnet, L. A., Mathur, S., García, R. A., & Pallé, P. L. (2021). ROOSTER: A machine-learning analysis tool for Kepler stellar rotation periods. Astronomy & Astrophysics. EDP Sciences. https://doi.org/10.1051/0004-6361/202039947' chicago: 'Breton, S. N., A. R. G. Santos, Lisa Annabelle Bugnet, S. Mathur, R. A. García, and P. L. Pallé. “ROOSTER: A Machine-Learning Analysis Tool for Kepler Stellar Rotation Periods.” Astronomy & Astrophysics. EDP Sciences, 2021. https://doi.org/10.1051/0004-6361/202039947.' ieee: 'S. N. Breton, A. R. G. Santos, L. A. Bugnet, S. Mathur, R. A. García, and P. L. Pallé, “ROOSTER: A machine-learning analysis tool for Kepler stellar rotation periods,” Astronomy & Astrophysics, vol. 647. EDP Sciences, 2021.' ista: 'Breton SN, Santos ARG, Bugnet LA, Mathur S, García RA, Pallé PL. 2021. ROOSTER: A machine-learning analysis tool for Kepler stellar rotation periods. Astronomy & Astrophysics. 647, A125.' mla: 'Breton, S. N., et al. “ROOSTER: A Machine-Learning Analysis Tool for Kepler Stellar Rotation Periods.” Astronomy & Astrophysics, vol. 647, A125, EDP Sciences, 2021, doi:10.1051/0004-6361/202039947.' short: S.N. Breton, A.R.G. Santos, L.A. Bugnet, S. Mathur, R.A. García, P.L. Pallé, Astronomy & Astrophysics 647 (2021). date_created: 2022-07-18T12:21:32Z date_published: 2021-03-19T00:00:00Z date_updated: 2022-08-22T08:47:47Z day: '19' doi: 10.1051/0004-6361/202039947 extern: '1' external_id: arxiv: - '2101.10152' intvolume: ' 647' keyword: - Space and Planetary Science - Astronomy and Astrophysics - 'methods: data analysis / stars: solar-type / stars: activity / stars: rotation / starspots' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2101.10152 month: '03' oa: 1 oa_version: Preprint publication: Astronomy & Astrophysics publication_identifier: eissn: - 1432-0746 issn: - 0004-6361 publication_status: published publisher: EDP Sciences quality_controlled: '1' scopus_import: '1' status: public title: 'ROOSTER: A machine-learning analysis tool for Kepler stellar rotation periods' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 647 year: '2021' ... --- _id: '11609' abstract: - lang: eng text: "Context. Stellar interiors are the seat of efficient transport of angular momentum all along their evolution. In this context, understanding the dependence of the turbulent transport triggered by the instabilities of the vertical and horizontal shears of the differential rotation in stellar radiation zones as a function of their rotation, stratification, and thermal diffusivity is mandatory. Indeed, it constitutes one of the cornerstones of the rotational transport and mixing theory, which is implemented in stellar evolution codes to predict the rotational and chemical evolutions of stars.\r\n\r\nAims. We investigate horizontal shear instabilities in rotating stellar radiation zones by considering the full Coriolis acceleration with both the dimensionless horizontal Coriolis component f̃ and the vertical component f.\r\n\r\nMethods. We performed a linear stability analysis using linearized equations derived from the Navier-Stokes and heat transport equations in the rotating nontraditional f-plane. We considered a horizontal shear flow with a hyperbolic tangent profile as the base flow. The linear stability was analyzed numerically in wide ranges of parameters, and we performed an asymptotic analysis for large vertical wavenumbers using the Wentzel-Kramers-Brillouin-Jeffreys (WKBJ) approximation for nondiffusive and highly-diffusive fluids.\r\n\r\nResults. As in the traditional f-plane approximation, we identify two types of instabilities: the inflectional and inertial instabilities. The inflectional instability is destabilized as f̃ increases and its maximum growth rate increases significantly, while the thermal diffusivity stabilizes the inflectional instability similarly to the traditional case. The inertial instability is also strongly affected; for instance, the inertially unstable regime is also extended in the nondiffusive limit as 0 < f < 1 + f̃ 2/N2, where N is the dimensionless Brunt-Väisälä frequency. More strikingly, in the high thermal diffusivity limit, it is always inertially unstable at any colatitude θ except at the poles (i.e., 0° < θ <  180°). We also derived the critical Reynolds numbers for the inertial instability using the asymptotic dispersion relations obtained from the WKBJ analysis. Using the asymptotic and numerical results, we propose a prescription for the effective turbulent viscosities induced by the inertial and inflectional instabilities that can be possibly used in stellar evolution models. The characteristic time of this turbulence is short enough so that it is efficient to redistribute angular momentum and to mix chemicals in stellar radiation zones." acknowledgement: The authors acknowledge support from the European Research Council through ERC grant SPIRE 647383 and from GOLF and PLATO CNES grants at the Department of Astrophysics at CEA Paris-Saclay. We thank the referee, Prof. A. J. Barker, for his constructive comments that allow us to improve the article. article_number: A64 article_processing_charge: No article_type: original arxiv: 1 author: - first_name: J. full_name: Park, J. last_name: Park - first_name: V. full_name: Prat, V. last_name: Prat - first_name: S. full_name: Mathis, S. last_name: Mathis - first_name: Lisa Annabelle full_name: Bugnet, Lisa Annabelle id: d9edb345-f866-11ec-9b37-d119b5234501 last_name: Bugnet orcid: 0000-0003-0142-4000 citation: ama: 'Park J, Prat V, Mathis S, Bugnet LA. Horizontal shear instabilities in rotating stellar radiation zones: II. Effects of the full Coriolis acceleration. Astronomy & Astrophysics. 2021;646. doi:10.1051/0004-6361/202038654' apa: 'Park, J., Prat, V., Mathis, S., & Bugnet, L. A. (2021). Horizontal shear instabilities in rotating stellar radiation zones: II. Effects of the full Coriolis acceleration. Astronomy & Astrophysics. EDP Sciences. https://doi.org/10.1051/0004-6361/202038654' chicago: 'Park, J., V. Prat, S. Mathis, and Lisa Annabelle Bugnet. “Horizontal Shear Instabilities in Rotating Stellar Radiation Zones: II. Effects of the Full Coriolis Acceleration.” Astronomy & Astrophysics. EDP Sciences, 2021. https://doi.org/10.1051/0004-6361/202038654.' ieee: 'J. Park, V. Prat, S. Mathis, and L. A. Bugnet, “Horizontal shear instabilities in rotating stellar radiation zones: II. Effects of the full Coriolis acceleration,” Astronomy & Astrophysics, vol. 646. EDP Sciences, 2021.' ista: 'Park J, Prat V, Mathis S, Bugnet LA. 2021. Horizontal shear instabilities in rotating stellar radiation zones: II. Effects of the full Coriolis acceleration. Astronomy & Astrophysics. 646, A64.' mla: 'Park, J., et al. “Horizontal Shear Instabilities in Rotating Stellar Radiation Zones: II. Effects of the Full Coriolis Acceleration.” Astronomy & Astrophysics, vol. 646, A64, EDP Sciences, 2021, doi:10.1051/0004-6361/202038654.' short: J. Park, V. Prat, S. Mathis, L.A. Bugnet, Astronomy & Astrophysics 646 (2021). date_created: 2022-07-18T13:24:32Z date_published: 2021-02-08T00:00:00Z date_updated: 2022-08-19T10:18:03Z day: '08' doi: 10.1051/0004-6361/202038654 extern: '1' external_id: arxiv: - '2006.10660' intvolume: ' 646' keyword: - Space and Planetary Science - Astronomy and Astrophysics - hydrodynamics / turbulence / stars - rotation / stars - evolution language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2006.10660 month: '02' oa: 1 oa_version: Preprint publication: Astronomy & Astrophysics publication_identifier: eissn: - 1432-0746 issn: - 0004-6361 publication_status: published publisher: EDP Sciences quality_controlled: '1' scopus_import: '1' status: public title: 'Horizontal shear instabilities in rotating stellar radiation zones: II. Effects of the full Coriolis acceleration' type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 646 year: '2021' ... --- _id: '11649' abstract: - lang: eng text: 'While operating communication networks adaptively may improve utilization and performance, frequent adjustments also introduce an algorithmic challenge: the re-optimization of traffic engineering solutions is time-consuming and may limit the granularity at which a network can be adjusted. This paper is motivated by question whether the reactivity of a network can be improved by re-optimizing solutions dynamically rather than from scratch, especially if inputs such as link weights do not change significantly. This paper explores to what extent dynamic algorithms can be used to speed up fundamental tasks in network operations. We specifically investigate optimizations related to traffic engineering (namely shortest paths and maximum flow computations), but also consider spanning tree and matching applications. While prior work on dynamic graph algorithms focusses on link insertions and deletions, we are interested in the practical problem of link weight changes. We revisit existing upper bounds in the weight-dynamic model, and present several novel lower bounds on the amortized runtime for recomputing solutions. In general, we find that the potential performance gains depend on the application, and there are also strict limitations on what can be achieved, even if link weights change only slightly.' article_processing_charge: No arxiv: 1 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: Ami full_name: Paz, Ami last_name: Paz - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid citation: ama: 'Henzinger M, Paz A, Schmid S. On the complexity of weight-dynamic network algorithms. In: IFIP Networking Conference. Institute of Electrical and Electronics Engineers; 2021. doi:10.23919/ifipnetworking52078.2021.9472803' apa: 'Henzinger, M., Paz, A., & Schmid, S. (2021). On the complexity of weight-dynamic network algorithms. In IFIP Networking Conference. Espoo and Helsinki, Finland: Institute of Electrical and Electronics Engineers. https://doi.org/10.23919/ifipnetworking52078.2021.9472803' chicago: Henzinger, Monika, Ami Paz, and Stefan Schmid. “On the Complexity of Weight-Dynamic Network Algorithms.” In IFIP Networking Conference. Institute of Electrical and Electronics Engineers, 2021. https://doi.org/10.23919/ifipnetworking52078.2021.9472803. ieee: M. Henzinger, A. Paz, and S. Schmid, “On the complexity of weight-dynamic network algorithms,” in IFIP Networking Conference, Espoo and Helsinki, Finland, 2021. ista: 'Henzinger M, Paz A, Schmid S. 2021. On the complexity of weight-dynamic network algorithms. IFIP Networking Conference. IFIP: Networking.' mla: Henzinger, Monika, et al. “On the Complexity of Weight-Dynamic Network Algorithms.” IFIP Networking Conference, Institute of Electrical and Electronics Engineers, 2021, doi:10.23919/ifipnetworking52078.2021.9472803. short: M. Henzinger, A. Paz, S. Schmid, in:, IFIP Networking Conference, Institute of Electrical and Electronics Engineers, 2021. conference: end_date: 2021-06-24 location: ' Espoo and Helsinki, Finland' name: 'IFIP: Networking' start_date: 2021-06-21 date_created: 2022-07-25T11:13:06Z date_published: 2021-06-21T00:00:00Z date_updated: 2024-11-06T12:04:45Z day: '21' doi: 10.23919/ifipnetworking52078.2021.9472803 extern: '1' external_id: arxiv: - '2105.13172' language: - iso: eng main_file_link: - open_access: '1' url: ' https://doi.org/10.48550/arXiv.2105.13172' month: '06' oa: 1 oa_version: Preprint publication: IFIP Networking Conference publication_identifier: eissn: - 1861-2288 publication_status: published publisher: Institute of Electrical and Electronics Engineers quality_controlled: '1' scopus_import: '1' status: public title: On the complexity of weight-dynamic network algorithms type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2021' ... --- _id: '11663' abstract: - lang: eng text: "Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas) and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability.\r\n\r\nIn this article, we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem.\r\n\r\n(1)\r\n\r\nFor dynamic spanner, the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case update time for maintaining a 3-spanner and O(n5/9) for maintaining a 5-spanner. We give a O(1)k log3 (n) high-probability worst-case time bound for maintaining a (2k-1)-spanner, which yields the first worst-case polylog update time for all constant k. (All the results above maintain the optimal tradeoff of stretch 2k-1 and Õ(n1+1/k) edges.)\r\n\r\n(2)\r\n\r\nFor dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O(log 5 (n)) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2+ϵ)-approximate, and hence not maximal.\r\n\r\nOur results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: An algorithm is said to have worst-case expected update time ɑ if for every update σ, the expected time to process σ is at most ɑ. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: A worst-case expected update time of O(1) still allows for the possibility that every 1/f(n) updates requires ϴ (f(n)) time to process, for arbitrarily high f(n). In this article, we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: The query time remains the same, while the update time increases by a factor of O(log 2(n)).\r\n\r\nThus, we achieve our results in two steps:\r\n\r\n(1) First, we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times.\r\n\r\n(2) Then, we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms." acknowledgement: 'The conference version of this article [10] had an error in the analysis of the dynamic matching algorithm. In particular, Lemma 4.5 assumed an independence between adversarial updates to the hierarchy that is in fact true, but which requires a sophisticated proof. We are very grateful to the anonymous reviewers of Transactions on Algorithms for pointing out this mistake in our analysis. The mistake is fixed in Section 4.5. Almost the entire fix is a matter of analysis: the only change to the algorithm itself is the introduction of responsible bits in Algorithm 2. The first author would like to thank Mikkel Thorup and Alan Roytman for a very helpful discussion of the proof of Theorem 1.1.' article_number: '29' article_processing_charge: No article_type: original arxiv: 1 author: - first_name: Aaron full_name: Bernstein, Aaron last_name: Bernstein - first_name: Sebastian full_name: Forster, Sebastian last_name: Forster - 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: Bernstein A, Forster S, Henzinger M. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 2021;17(4). doi:10.1145/3469833 apa: Bernstein, A., Forster, S., & Henzinger, M. (2021). A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. Association for Computing Machinery. https://doi.org/10.1145/3469833 chicago: Bernstein, Aaron, Sebastian Forster, and Monika Henzinger. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” ACM Transactions on Algorithms. Association for Computing Machinery, 2021. https://doi.org/10.1145/3469833. ieee: A. Bernstein, S. Forster, and M. Henzinger, “A deamortization approach for dynamic spanner and dynamic maximal matching,” ACM Transactions on Algorithms, vol. 17, no. 4. Association for Computing Machinery, 2021. ista: Bernstein A, Forster S, Henzinger M. 2021. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Transactions on Algorithms. 17(4), 29. mla: Bernstein, Aaron, et al. “A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.” ACM Transactions on Algorithms, vol. 17, no. 4, 29, Association for Computing Machinery, 2021, doi:10.1145/3469833. short: A. Bernstein, S. Forster, M. Henzinger, ACM Transactions on Algorithms 17 (2021). date_created: 2022-07-27T11:09:06Z date_published: 2021-10-04T00:00:00Z date_updated: 2024-11-06T12:05:37Z day: '04' doi: 10.1145/3469833 extern: '1' external_id: arxiv: - '1810.10932' intvolume: ' 17' issue: '4' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1810.10932 month: '10' oa: 1 oa_version: Preprint publication: ACM Transactions on Algorithms publication_identifier: eissn: - 1549-6333 issn: - 1549-6325 publication_status: published publisher: Association for Computing Machinery quality_controlled: '1' scopus_import: '1' status: public title: A deamortization approach for dynamic spanner and dynamic maximal matching type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 17 year: '2021' ... --- _id: '11756' abstract: - lang: eng text: We give two fully dynamic algorithms that maintain a (1 + ε)-approximation of the weight M of a minimum spanning forest (MSF) of an n-node graph G with edges weights in [1, W ], for any ε > 0. (1) Our deterministic algorithm takes O (W 2 log W /ε3) worst-case update time, which is O (1) if both W and ε are constants. (2) Our randomized (Monte-Carlo style) algorithm works with high probability and runs in worst-case O (log W /ε4) update time if W = O ((m∗)1/6/log2/3 n), where m∗ is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. We complement our algorithmic results with two cell-probe lower bounds for dynamically maintaining an approximation of the weight of an MSF of a graph. article_number: '104805' article_processing_charge: No article_type: original arxiv: 1 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: Pan full_name: Peng, Pan last_name: Peng citation: ama: Henzinger M, Peng P. Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. 2021;281(12). doi:10.1016/j.ic.2021.104805 apa: Henzinger, M., & Peng, P. (2021). Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. Elsevier. https://doi.org/10.1016/j.ic.2021.104805 chicago: Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.” Information and Computation. Elsevier, 2021. https://doi.org/10.1016/j.ic.2021.104805. ieee: M. Henzinger and P. Peng, “Constant-time dynamic weight approximation for minimum spanning forest,” Information and Computation, vol. 281, no. 12. Elsevier, 2021. ista: Henzinger M, Peng P. 2021. Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation. 281(12), 104805. mla: Henzinger, Monika, and Pan Peng. “Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest.” Information and Computation, vol. 281, no. 12, 104805, Elsevier, 2021, doi:10.1016/j.ic.2021.104805. short: M. Henzinger, P. Peng, Information and Computation 281 (2021). date_created: 2022-08-08T10:58:29Z date_published: 2021-12-01T00:00:00Z date_updated: 2024-11-06T12:09:22Z day: '01' doi: 10.1016/j.ic.2021.104805 extern: '1' external_id: arxiv: - '2011.00977' intvolume: ' 281' issue: '12' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2011.00977 month: '12' oa: 1 oa_version: Preprint publication: Information and Computation publication_identifier: issn: - 0890-5401 publication_status: published publisher: Elsevier quality_controlled: '1' scopus_import: '1' status: public title: Constant-time dynamic weight approximation for minimum spanning forest type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 281 year: '2021' ... --- _id: '11771' abstract: - lang: eng text: "Classic dynamic data structure problems maintain a data structure subject to a sequence S of updates and they answer queries using the latest version of the data structure, i.e., the data structure after processing the whole sequence. To handle operations that change the sequence S of updates, Demaine et al. [7] introduced retroactive data structures (RDS). A retroactive operation modifies the update sequence S in a given position t, called time, and either creates or cancels an update in S at time t. A fully retroactive data structure supports queries at any time t: a query at time t is answered using only the updates of S up to time t. While efficient RDS have been proposed for classic data structures, e.g., stack, priority queue and binary search tree, the retroactive version of graph problems are rarely studied.\r\n\r\nIn this paper we study retroactive graph problems including connectivity, minimum spanning forest (MSF), maximum degree, etc. We show that under the OMv conjecture (proposed by Henzinger et al. [15]), there does not exist fully RDS maintaining connectivity or MSF, or incremental fully RDS maintaining the maximum degree with \U0001D442(\U0001D45B1−\U0001D716) time per operation, for any constant \U0001D716>0. Furthermore, We provide RDS with almost tight time per operation. We give fully RDS for maintaining the maximum degree, connectivity and MSF in \U0001D442̃ (\U0001D45B) time per operation. We also give an algorithm for the incremental (insertion-only) fully retroactive connectivity with \U0001D442̃ (1) time per operation, showing that the lower bound cannot be extended to this setting.\r\n\r\nWe also study a restricted version of RDS, where the only change to S is the swap of neighboring updates and show that for this problem we can beat the above hardness result. This also implies the first non-trivial dynamic Reeb graph computation algorithm." alternative_title: - LNCS article_processing_charge: No arxiv: 1 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: Xiaowei full_name: Wu, Xiaowei last_name: Wu citation: ama: 'Henzinger M, Wu X. Upper and lower bounds for fully retroactive graph problems. In: 17th International Symposium on Algorithms and Data Structures. Vol 12808. Springer Nature; 2021:471–484. doi:10.1007/978-3-030-83508-8_34' apa: 'Henzinger, M., & Wu, X. (2021). Upper and lower bounds for fully retroactive graph problems. In 17th International Symposium on Algorithms and Data Structures (Vol. 12808, pp. 471–484). Virtual: Springer Nature. https://doi.org/10.1007/978-3-030-83508-8_34' chicago: Henzinger, Monika, and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive Graph Problems.” In 17th International Symposium on Algorithms and Data Structures, 12808:471–484. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-83508-8_34. ieee: M. Henzinger and X. Wu, “Upper and lower bounds for fully retroactive graph problems,” in 17th International Symposium on Algorithms and Data Structures, Virtual, 2021, vol. 12808, pp. 471–484. ista: 'Henzinger M, Wu X. 2021. Upper and lower bounds for fully retroactive graph problems. 17th International Symposium on Algorithms and Data Structures. WADS: Workshop on Algorithms and Data Structures, LNCS, vol. 12808, 471–484.' mla: Henzinger, Monika, and Xiaowei Wu. “Upper and Lower Bounds for Fully Retroactive Graph Problems.” 17th International Symposium on Algorithms and Data Structures, vol. 12808, Springer Nature, 2021, pp. 471–484, doi:10.1007/978-3-030-83508-8_34. short: M. Henzinger, X. Wu, in:, 17th International Symposium on Algorithms and Data Structures, Springer Nature, 2021, pp. 471–484. conference: end_date: 2021-08-11 location: Virtual name: 'WADS: Workshop on Algorithms and Data Structures' start_date: 2021-08-09 date_created: 2022-08-08T13:01:29Z date_published: 2021-08-09T00:00:00Z date_updated: 2024-11-06T12:10:14Z day: '09' doi: 10.1007/978-3-030-83508-8_34 extern: '1' external_id: arxiv: - '1910.03332' intvolume: ' 12808' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1910.03332 month: '08' oa: 1 oa_version: Preprint page: 471–484 publication: 17th International Symposium on Algorithms and Data Structures publication_identifier: eisbn: - '9783030835088' eissn: - 1611-3349 isbn: - '9783030835071' issn: - 0302-9743 publication_status: published publisher: Springer Nature quality_controlled: '1' scopus_import: '1' status: public title: Upper and lower bounds for fully retroactive graph problems type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 12808 year: '2021' ... --- _id: '11814' abstract: - lang: eng text: "Differentially private algorithms protect individuals in data analysis scenarios by ensuring that there is only a weak correlation between the existence of the user in the data and the result of the analysis. Dynamic graph algorithms maintain the solution to a problem (e.g., a matching) on an evolving input, i.e., a graph where nodes or edges are inserted or deleted over time. They output the value of the solution after each update operation, i.e., continuously. We study (event-level and user-level) differentially private algorithms for graph problems under continual observation, i.e., differentially private dynamic graph algorithms. We present event-level private algorithms for partially dynamic counting-based problems such as triangle count that improve the additive error by a polynomial factor (in the length T of the update sequence) on the state of the art, resulting in the first algorithms with additive error polylogarithmic in T.\r\nWe also give ε-differentially private and partially dynamic algorithms for minimum spanning tree, minimum cut, densest subgraph, and maximum matching. The additive error of our improved MST algorithm is O(W log^{3/2}T / ε), where W is the maximum weight of any edge, which, as we show, is tight up to a (√{log T} / ε)-factor. For the other problems, we present a partially-dynamic algorithm with multiplicative error (1+β) for any constant β > 0 and additive error O(W log(nW) log(T) / (ε β)). Finally, we show that the additive error for a broad class of dynamic graph algorithms with user-level privacy must be linear in the value of the output solution’s range." alternative_title: - LIPIcs article_number: '42' article_processing_charge: No arxiv: 1 author: - first_name: Hendrik full_name: Fichtenberger, Hendrik last_name: Fichtenberger - 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: Wolfgang full_name: Ost, Wolfgang last_name: Ost citation: ama: 'Fichtenberger H, Henzinger M, Ost W. Differentially private algorithms for graphs under continual observation. In: 29th Annual European Symposium on Algorithms. Vol 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2021. doi:10.4230/LIPIcs.ESA.2021.42' apa: 'Fichtenberger, H., Henzinger, M., & Ost, W. (2021). Differentially private algorithms for graphs under continual observation. In 29th Annual European Symposium on Algorithms (Vol. 204). Lisbon, Portual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2021.42' chicago: Fichtenberger, Hendrik, Monika Henzinger, and Wolfgang Ost. “Differentially Private Algorithms for Graphs under Continual Observation.” In 29th Annual European Symposium on Algorithms, Vol. 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. https://doi.org/10.4230/LIPIcs.ESA.2021.42. ieee: H. Fichtenberger, M. Henzinger, and W. Ost, “Differentially private algorithms for graphs under continual observation,” in 29th Annual European Symposium on Algorithms, Lisbon, Portual, 2021, vol. 204. ista: 'Fichtenberger H, Henzinger M, Ost W. 2021. Differentially private algorithms for graphs under continual observation. 29th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 204, 42.' mla: Fichtenberger, Hendrik, et al. “Differentially Private Algorithms for Graphs under Continual Observation.” 29th Annual European Symposium on Algorithms, vol. 204, 42, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, doi:10.4230/LIPIcs.ESA.2021.42. short: H. Fichtenberger, M. Henzinger, W. Ost, in:, 29th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. conference: end_date: 2021-09-08 location: Lisbon, Portual name: 'ESA: Annual European Symposium on Algorithms' start_date: 2021-09-06 date_created: 2022-08-12T07:04:44Z date_published: 2021-08-31T00:00:00Z date_updated: 2024-11-06T08:22:28Z day: '31' doi: 10.4230/LIPIcs.ESA.2021.42 extern: '1' external_id: arxiv: - '2106.14756' intvolume: ' 204' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.4230/LIPIcs.ESA.2021.42 month: '08' oa: 1 oa_version: Published Version publication: 29th Annual European Symposium on Algorithms publication_identifier: isbn: - '9783959772044' issn: - 1868-8969 publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik quality_controlled: '1' scopus_import: '1' status: public title: Differentially private algorithms for graphs under continual observation type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 204 year: '2021' ... --- _id: '11886' abstract: - lang: eng text: "We present a deterministic (1+\U0001D45C(1))-approximation (\U0001D45B1/2+\U0001D45C(1)+\U0001D4371+\U0001D45C(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the \\sf CONGEST model); here \U0001D45B is the number of nodes in the network, \U0001D437 is its (hop) diameter, and edge weights are positive integers from 1 to poly(\U0001D45B). This is the first nontrivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+\U0001D45C(1))-approximation \U0001D442̃ (\U0001D45B√\U0001D4371/4+\U0001D437)-time algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565--573] by a factor of as large as \U0001D45B1/8, and (ii) the \U0001D442(\U0001D716−1log\U0001D716−1)-approximation factor of Lenzen and Patt-Shamir's \U0001D442̃ (\U0001D45B1/2+\U0001D716+\U0001D437)-time algorithm [in Proceedings of STOC, 2013, pp. 381--390] within the same running time. (Throughout, we use \U0001D442̃ (⋅) to hide polylogarithmic factors in \U0001D45B.) Our running time matches the known time lower bound of Ω(\U0001D45B/log\U0001D45B‾‾‾‾‾‾‾√+\U0001D437) [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433--456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40--57]. It also implies a (2+\U0001D45C(1))-approximation (\U0001D45B1/2+\U0001D45C(1)+\U0001D4371+\U0001D45C(1))-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an (\U0001D45B\U0001D45C(1),\U0001D45C(1))-hop set of size \U0001D45B1+\U0001D45C(1). We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434--446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375--382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153--162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a (1+\U0001D45C(1))-approximation \U0001D45B\U0001D45C(1)-time algorithm on congested cliques, and (ii) a (1+\U0001D45C(1))-approximation \U0001D45B\U0001D45C(1)-pass \U0001D45B1+\U0001D45C(1)-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565--573]. The second result partially answers an open problem raised by McGregor in 2006 [List of Open Problems in Sublinear Algorithms: Problem 14]." article_processing_charge: No article_type: original arxiv: 1 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: Sebastian full_name: Krinninger, Sebastian last_name: Krinninger - first_name: Danupon full_name: Nanongkai, Danupon last_name: Nanongkai citation: ama: Henzinger M, Krinninger S, Nanongkai D. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 2021;50(3):STOC16-98-STOC16-137. doi:10.1137/16m1097808 apa: Henzinger, M., Krinninger, S., & Nanongkai, D. (2021). A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. Society for Industrial & Applied Mathematics. https://doi.org/10.1137/16m1097808 chicago: Henzinger, Monika, Sebastian Krinninger, and Danupon Nanongkai. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” SIAM Journal on Computing. Society for Industrial & Applied Mathematics, 2021. https://doi.org/10.1137/16m1097808. ieee: M. Henzinger, S. Krinninger, and D. Nanongkai, “A deterministic almost-tight distributed algorithm for approximating single-source shortest paths,” SIAM Journal on Computing, vol. 50, no. 3. Society for Industrial & Applied Mathematics, pp. STOC16-98-STOC16-137, 2021. ista: Henzinger M, Krinninger S, Nanongkai D. 2021. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. SIAM Journal on Computing. 50(3), STOC16-98-STOC16-137. mla: Henzinger, Monika, et al. “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths.” SIAM Journal on Computing, vol. 50, no. 3, Society for Industrial & Applied Mathematics, 2021, pp. STOC16-98-STOC16-137, doi:10.1137/16m1097808. short: M. Henzinger, S. Krinninger, D. Nanongkai, SIAM Journal on Computing 50 (2021) STOC16-98-STOC16-137. date_created: 2022-08-17T07:54:45Z date_published: 2021-05-01T00:00:00Z date_updated: 2024-11-06T12:22:31Z day: '01' doi: 10.1137/16m1097808 extern: '1' external_id: arxiv: - '1504.07056' intvolume: ' 50' issue: '3' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/1504.07056 month: '05' oa: 1 oa_version: Preprint page: STOC16-98-STOC16-137 publication: SIAM Journal on Computing publication_identifier: eissn: - 1095-7111 issn: - 0097-5397 publication_status: published publisher: Society for Industrial & Applied Mathematics quality_controlled: '1' scopus_import: '1' status: public title: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 50 year: '2021' ... --- _id: '11919' abstract: - lang: eng text: "Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and it is preferable to perform the computations on a sparse skeleton of the given graph that roughly preserves the shortest paths information. Spanners and emulators serve this purpose. Unfortunately, very little is known about dynamically maintaining sparse spanners and emulators as the graph is modified by a sequence of edge insertions and deletions. This paper develops fast dynamic algorithms for spanner and emulator maintenance and provides evidence from fine-grained complexity that these algorithms are tight. For unweighted undirected m-edge n-node graphs we obtain the following results.\r\n\r\nUnder the popular OMv conjecture, there can be no decremental or incremental algorithm that maintains an n1+o(1) edge (purely additive) +nδ-emulator for any δ < 1/2 with arbitrary polynomial preprocessing time and total update time m1+o(1). Also, under the Combinatorial k-Clique hypothesis, any fully dynamic combinatorial algorithm that maintains an n1+o(1) edge (1 + ∊, no(1))-spanner or emulator for small ∊ must either have preprocessing time mn1–o(1) or amortized update time m1–o(1). Both of our conditional lower bounds are tight.\r\n\r\nAs the above fully dynamic lower bound only applies to combinatorial algorithms, we also develop an algebraic spanner algorithm that improves over the m1–o(1) update time for dense graphs. For any constant ∊ ∊ (0, 1], there is a fully dynamic algorithm with worst-case update time O(n1.529) that whp maintains an n1+o(1) edge (1 + ∊, no(1))-spanner.\r\n\r\nOur new algebraic techniques allow us to also obtain a new fully dynamic algorithm for All-Pairs Shortest Paths (APSP) that can perform both edge updates and can report shortest paths in worst-case time O(n1.9), which are correct whp. This is the first path-reporting fully dynamic APSP algorithm with a truly subquadratic query time that beats O(n2.5) update time. It works against an oblivious adversary.\r\n\r\nFinally, we give two applications of our new dynamic spanner algorithms: (1) a fully dynamic (1 + ∊)-approximate APSP algorithm with update time O(n1.529) that can report approximate shortest paths in n1+o(1) time per query; previous subquadratic update/query algorithms could only report the distance, but not obtain the paths; (2) a fully dynamic algorithm for near-2-approximate Steiner tree maintenance with both terminal and edge updates." article_processing_charge: No arxiv: 1 author: - first_name: Thiago full_name: Bergamaschi, Thiago last_name: Bergamaschi - 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: Maximilian Probst full_name: Gutenberg, Maximilian Probst last_name: Gutenberg - first_name: Virginia Vassilevska full_name: Williams, Virginia Vassilevska last_name: Williams - first_name: Nicole full_name: Wein, Nicole last_name: Wein citation: ama: 'Bergamaschi T, Henzinger M, Gutenberg MP, Williams VV, Wein N. New techniques and fine-grained hardness for dynamic near-additive spanners. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2021:1836-1855. doi:10.1137/1.9781611976465.110' apa: 'Bergamaschi, T., Henzinger, M., Gutenberg, M. P., Williams, V. V., & Wein, N. (2021). New techniques and fine-grained hardness for dynamic near-additive spanners. In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1836–1855). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611976465.110' chicago: Bergamaschi, Thiago, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. “New Techniques and Fine-Grained Hardness for Dynamic near-Additive Spanners.” In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 1836–55. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976465.110. ieee: T. Bergamaschi, M. Henzinger, M. P. Gutenberg, V. V. Williams, and N. Wein, “New techniques and fine-grained hardness for dynamic near-additive spanners,” in 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States, 2021, pp. 1836–1855. ista: 'Bergamaschi T, Henzinger M, Gutenberg MP, Williams VV, Wein N. 2021. New techniques and fine-grained hardness for dynamic near-additive spanners. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 1836–1855.' mla: Bergamaschi, Thiago, et al. “New Techniques and Fine-Grained Hardness for Dynamic near-Additive Spanners.” 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2021, pp. 1836–55, doi:10.1137/1.9781611976465.110. short: T. Bergamaschi, M. Henzinger, M.P. Gutenberg, V.V. Williams, N. Wein, in:, 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2021, pp. 1836–1855. conference: end_date: 2021-01-13 location: Alexandria, VA, United States name: 'SODA: Symposium on Discrete Algorithms' start_date: 2021-01-10 date_created: 2022-08-18T07:37:36Z date_published: 2021-01-01T00:00:00Z date_updated: 2024-11-06T12:26:04Z day: '01' doi: 10.1137/1.9781611976465.110 extern: '1' external_id: arxiv: - '2010.10134' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2010.10134 month: '01' oa: 1 oa_version: Preprint page: 1836-1855 publication: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms publication_identifier: eisbn: - 978-1-61197-646-5 publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' scopus_import: '1' status: public title: New techniques and fine-grained hardness for dynamic near-additive spanners type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2021' ... --- _id: '11920' abstract: - lang: eng text: 'In the dynamic minimum set cover problem, a challenge is to minimize the update time while guaranteeing close to the optimal min(O(log n), f) approximation factor. (Throughout, m, n, f, and C are parameters denoting the maximum number of sets, number of elements, frequency, and the cost range.) In the high-frequency range, when f = Ω(log n), this was achieved by a deterministic O(log n)-approximation algorithm with O(f log n) amortized update time [Gupta et al. STOC''17]. In the low-frequency range, the line of work by Gupta et al. [STOC''17], Abboud et al. [STOC''19], and Bhattacharya et al. [ICALP''15, IPCO''17, FOCS''19] led to a deterministic (1 + ∊) f-approximation algorithm with O(f log(Cn)/∊2) amortized update time. In this paper we improve the latter update time and provide the first bounds that subsume (and sometimes improve) the state-of-the-art dynamic vertex cover algorithms. We obtain: (1) (1 + ∊) f-approximation ratio in O(f log2(Cn)/∊3) worst-case update time: No non-trivial worst-case update time was previously known for dynamic set cover. Our bound subsumes and improves by a logarithmic factor the O(log3 n/poly(∊)) worst-case update time for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1) by Bhattacharya et al. [SODA''17]. (2) (1 + ∊) f-approximation ratio in O ((f2/∊3) + (f/∊2) log C) amortized update time: This result improves the previous O(f log (Cn)/∊2) update time bound for most values of f in the low-frequency range, i.e. whenever f = o(log n). It is the first that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [SODA''19] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). These results are achieved by leveraging the approximate complementary slackness and background schedulers techniques. These techniques were used in the local update scheme for dynamic vertex cover. Our main technical contribution is to adapt these techniques within the global update scheme of Bhattacharya et al. [FOCS''19] for the dynamic set cover problem.' article_processing_charge: No arxiv: 1 author: - first_name: Sayan full_name: Bhattacharya, Sayan last_name: Bhattacharya - 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: Danupon full_name: Nanongkai, Danupon last_name: Nanongkai - first_name: Xiaowei full_name: Wu, Xiaowei last_name: Wu citation: ama: 'Bhattacharya S, Henzinger M, Nanongkai D, Wu X. Dynamic set cover: Improved amortized and worst-case update time. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2021:2537-2549. doi:10.1137/1.9781611976465.150' apa: 'Bhattacharya, S., Henzinger, M., Nanongkai, D., & Wu, X. (2021). Dynamic set cover: Improved amortized and worst-case update time. In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 2537–2549). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611976465.150' chicago: 'Bhattacharya, Sayan, Monika Henzinger, Danupon Nanongkai, and Xiaowei Wu. “Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.” In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2537–49. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976465.150.' ieee: 'S. Bhattacharya, M. Henzinger, D. Nanongkai, and X. Wu, “Dynamic set cover: Improved amortized and worst-case update time,” in 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States, 2021, pp. 2537–2549.' ista: 'Bhattacharya S, Henzinger M, Nanongkai D, Wu X. 2021. Dynamic set cover: Improved amortized and worst-case update time. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2537–2549.' mla: 'Bhattacharya, Sayan, et al. “Dynamic Set Cover: Improved Amortized and Worst-Case Update Time.” 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2021, pp. 2537–49, doi:10.1137/1.9781611976465.150.' short: S. Bhattacharya, M. Henzinger, D. Nanongkai, X. Wu, in:, 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2021, pp. 2537–2549. conference: end_date: 2021-01-13 location: Alexandria, VA, United States name: 'SODA: Symposium on Discrete Algorithms' start_date: 2021-01-10 date_created: 2022-08-18T07:46:54Z date_published: 2021-01-01T00:00:00Z date_updated: 2024-11-06T12:26:16Z day: '01' doi: 10.1137/1.9781611976465.150 extern: '1' external_id: arxiv: - '2002.11171' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2002.11171 month: '01' oa: 1 oa_version: Preprint page: 2537-2549 publication: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms publication_identifier: eisbn: - 978-1-61197-646-5 publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' scopus_import: '1' status: public title: 'Dynamic set cover: Improved amortized and worst-case update time' type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2021' ... --- _id: '11923' abstract: - lang: eng text: "We consider the following online optimization problem. We are given a graph G and each vertex of the graph is assigned to one of ℓ servers, where servers have capacity k and we assume that the graph has ℓ · k vertices. Initially, G does not contain any edges and then the edges of G are revealed one-by-one. The goal is to design an online algorithm ONL, which always places the connected components induced by the revealed edges on the same server and never exceeds the server capacities by more than ∊k for constant ∊ > 0. Whenever ONL learns about a new edge, the algorithm is allowed to move vertices from one server to another. Its objective is to minimize the number of vertex moves. More specifically, ONL should minimize the competitive ratio: the total cost ONL incurs compared to an optimal offline algorithm OPT.\r\n\r\nThe problem was recently introduced by Henzinger et al. (SIGMETRICS'2019) and is related to classic online problems such as online paging and scheduling. It finds applications in the context of resource allocation in the cloud and for optimizing distributed data structures such as union–find data structures.\r\n\r\nOur main contribution is a polynomial-time randomized algorithm, that is asymptotically optimal: we derive an upper bound of O(log ℓ + log k) on its competitive ratio and show that no randomized online algorithm can achieve a competitive ratio of less than Ω(log ℓ + log k). We also settle the open problem of the achievable competitive ratio by deterministic online algorithms, by deriving a competitive ratio of Θ(ℓ log k); to this end, we present an improved lower bound as well as a deterministic polynomial-time online algorithm.\r\n\r\nOur algorithms rely on a novel technique which combines efficient integer programming with a combinatorial approach for maintaining ILP solutions. More precisely, we use an ILP to assign the connected components induced by the revealed edges to the servers; this is similar to existing approximation schemes for scheduling algorithms. However, we cannot obtain our competitive ratios if we run the ILP after each edge insertion. Instead, we identify certain types of edge insertions, after which we can manually obtain an optimal ILP solution at zero cost without resolving the ILP. We believe this technique is of independent interest and will find further applications in the future." article_processing_charge: No arxiv: 1 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: Stefan full_name: Neumann, Stefan last_name: Neumann - first_name: Harald full_name: Räcke, Harald last_name: Räcke - first_name: Stefan full_name: Schmid, Stefan last_name: Schmid citation: ama: 'Henzinger M, Neumann S, Räcke H, Schmid S. Tight bounds for online graph partitioning. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2021:2799-2818. doi:10.1137/1.9781611976465.166' apa: 'Henzinger, M., Neumann, S., Räcke, H., & Schmid, S. (2021). Tight bounds for online graph partitioning. In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 2799–2818). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611976465.166' chicago: Henzinger, Monika, Stefan Neumann, Harald Räcke, and Stefan Schmid. “Tight Bounds for Online Graph Partitioning.” In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2799–2818. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976465.166. ieee: M. Henzinger, S. Neumann, H. Räcke, and S. Schmid, “Tight bounds for online graph partitioning,” in 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States, 2021, pp. 2799–2818. ista: 'Henzinger M, Neumann S, Räcke H, Schmid S. 2021. Tight bounds for online graph partitioning. 32nd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 2799–2818.' mla: Henzinger, Monika, et al. “Tight Bounds for Online Graph Partitioning.” 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2021, pp. 2799–818, doi:10.1137/1.9781611976465.166. short: M. Henzinger, S. Neumann, H. Räcke, S. Schmid, in:, 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2021, pp. 2799–2818. conference: end_date: 2021-01-13 location: Alexandria, VA, United States name: 'SODA: Symposium on Discrete Algorithms' start_date: 2021-01-10 date_created: 2022-08-18T10:31:58Z date_published: 2021-01-01T00:00:00Z date_updated: 2024-11-06T12:26:29Z day: '01' doi: 10.1137/1.9781611976465.166 extern: '1' external_id: arxiv: - '2011.01017' language: - iso: eng main_file_link: - open_access: '1' url: https://arxiv.org/abs/2011.01017 month: '01' oa: 1 oa_version: Preprint page: 2799-2818 publication: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms publication_identifier: eisbn: - 978-161197646-5 publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' scopus_import: '1' status: public title: Tight bounds for online graph partitioning type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2021' ... --- _id: '11931' abstract: - lang: eng text: Clustering is one of the most fundamental problems in unsupervised learning with a large number of applications. However, classical clustering algorithms assume that the data is static, thus failing to capture many real-world applications where data is constantly changing and evolving. Driven by this, we study the metric k-center clustering problem in the fully dynamic setting, where the goal is to efficiently maintain a clustering while supporting an intermixed sequence of insertions and deletions of points. This model also supports queries of the form (1) report whether a given point is a center or (2) determine the cluster a point is assigned to. We present a deterministic dynamic algorithm for the k-center clustering problem that provably achieves a (2 + ∊)-approximation in nearly logarithmic update and query time, if the underlying metric has bounded doubling dimension, its aspect ratio is bounded by a polynomial and ∊ is a constant. An important feature of our algorithm is that the update and query times are independent of k. We confirm the practical relevance of this feature via an extensive experimental study which shows that for large values of k, our algorithmic construction outperforms the state-of-the-art algorithm in terms of solution quality and running time. article_processing_charge: No 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 - first_name: Dariusz full_name: Leniowski, Dariusz last_name: Leniowski - first_name: Christian full_name: Schulz, Christian last_name: Schulz - first_name: Alexander full_name: Svozil, Alexander last_name: Svozil citation: ama: 'Goranci G, Henzinger M, Leniowski D, Schulz C, Svozil A. Fully dynamic k-center clustering in low dimensional metrics. In: 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2021:143-153. doi:10.1137/1.9781611976472.11' apa: 'Goranci, G., Henzinger, M., Leniowski, D., Schulz, C., & Svozil, A. (2021). Fully dynamic k-center clustering in low dimensional metrics. In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (pp. 143–153). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611976472.11' chicago: Goranci, Gramoz, Monika Henzinger, Dariusz Leniowski, Christian Schulz, and Alexander Svozil. “Fully Dynamic K-Center Clustering in Low Dimensional Metrics.” In 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments, 143–53. Society for Industrial and Applied Mathematics, 2021. https://doi.org/10.1137/1.9781611976472.11. ieee: G. Goranci, M. Henzinger, D. Leniowski, C. Schulz, and A. Svozil, “Fully dynamic k-center clustering in low dimensional metrics,” in 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments, Alexandria, VA, United States, 2021, pp. 143–153. ista: 'Goranci G, Henzinger M, Leniowski D, Schulz C, Svozil A. 2021. Fully dynamic k-center clustering in low dimensional metrics. 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 143–153.' mla: Goranci, Gramoz, et al. “Fully Dynamic K-Center Clustering in Low Dimensional Metrics.” 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2021, pp. 143–53, doi:10.1137/1.9781611976472.11. short: G. Goranci, M. Henzinger, D. Leniowski, C. Schulz, A. Svozil, in:, 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2021, pp. 143–153. conference: end_date: 2021-01-11 location: Alexandria, VA, United States name: 'ALENEX: Symposium on Algorithm Engineering and Experiments' start_date: 2021-01-10 date_created: 2022-08-19T07:33:37Z date_published: 2021-01-01T00:00:00Z date_updated: 2024-11-06T12:27:01Z day: '01' doi: 10.1137/1.9781611976472.11 extern: '1' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1137/1.9781611976472.11 month: '01' oa: 1 oa_version: Published Version page: 143 -153 publication: 2021 Proceedings of the Workshop on Algorithm Engineering and Experiments publication_identifier: eisbn: - 978-1-61197-647-2 issn: - 2164-0300 publication_status: published publisher: Society for Industrial and Applied Mathematics quality_controlled: '1' scopus_import: '1' status: public title: Fully dynamic k-center clustering in low dimensional metrics type: conference user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 year: '2021' ... --- _id: '11956' abstract: - lang: eng text: Controlling the selectivity of a chemical reaction with external stimuli is common in thermal processes, but rare in visible-light photocatalysis. Here we show that the redox potential of a carbon nitride photocatalyst (CN-OA-m) can be tuned by changing the irradiation wavelength to generate electron holes with different oxidation potentials. This tuning was the key to realizing photo-chemo-enzymatic cascades that give either the (S)- or the (R)-enantiomer of phenylethanol. In combination with an unspecific peroxygenase from Agrocybe aegerita, green light irradiation of CN-OA-m led to the enantioselective hydroxylation of ethylbenzene to (R)-1-phenylethanol (99 % ee). In contrast, blue light irradiation triggered the photocatalytic oxidation of ethylbenzene to acetophenone, which in turn was enantioselectively reduced with an alcohol dehydrogenase from Rhodococcus ruber to form (S)-1-phenylethanol (93 % ee). article_processing_charge: No article_type: original author: - first_name: Luca full_name: Schmermund, Luca last_name: Schmermund - first_name: Susanne full_name: Reischauer, Susanne last_name: Reischauer - first_name: Sarah full_name: Bierbaumer, Sarah last_name: Bierbaumer - first_name: Christoph K. full_name: Winkler, Christoph K. last_name: Winkler - first_name: Alba full_name: Diaz‐Rodriguez, Alba last_name: Diaz‐Rodriguez - first_name: Lee J. full_name: Edwards, Lee J. last_name: Edwards - first_name: Selin full_name: Kara, Selin last_name: Kara - first_name: Tamara full_name: Mielke, Tamara last_name: Mielke - first_name: Jared full_name: Cartwright, Jared last_name: Cartwright - first_name: Gideon full_name: Grogan, Gideon last_name: Grogan - first_name: Bartholomäus full_name: Pieber, Bartholomäus id: 93e5e5b2-0da6-11ed-8a41-af589a024726 last_name: Pieber orcid: 0000-0001-8689-388X - first_name: Wolfgang full_name: Kroutil, Wolfgang last_name: Kroutil citation: ama: Schmermund L, Reischauer S, Bierbaumer S, et al. Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways. Angewandte Chemie International Edition. 2021;60(13):6965-6969. doi:10.1002/anie.202100164 apa: Schmermund, L., Reischauer, S., Bierbaumer, S., Winkler, C. K., Diaz‐Rodriguez, A., Edwards, L. J., … Kroutil, W. (2021). Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways. Angewandte Chemie International Edition. Wiley. https://doi.org/10.1002/anie.202100164 chicago: Schmermund, Luca, Susanne Reischauer, Sarah Bierbaumer, Christoph K. Winkler, Alba Diaz‐Rodriguez, Lee J. Edwards, Selin Kara, et al. “Chromoselective Photocatalysis Enables Stereocomplementary Biocatalytic Pathways.” Angewandte Chemie International Edition. Wiley, 2021. https://doi.org/10.1002/anie.202100164. ieee: L. Schmermund et al., “Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways,” Angewandte Chemie International Edition, vol. 60, no. 13. Wiley, pp. 6965–6969, 2021. ista: Schmermund L, Reischauer S, Bierbaumer S, Winkler CK, Diaz‐Rodriguez A, Edwards LJ, Kara S, Mielke T, Cartwright J, Grogan G, Pieber B, Kroutil W. 2021. Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways. Angewandte Chemie International Edition. 60(13), 6965–6969. mla: Schmermund, Luca, et al. “Chromoselective Photocatalysis Enables Stereocomplementary Biocatalytic Pathways.” Angewandte Chemie International Edition, vol. 60, no. 13, Wiley, 2021, pp. 6965–69, doi:10.1002/anie.202100164. short: L. Schmermund, S. Reischauer, S. Bierbaumer, C.K. Winkler, A. Diaz‐Rodriguez, L.J. Edwards, S. Kara, T. Mielke, J. Cartwright, G. Grogan, B. Pieber, W. Kroutil, Angewandte Chemie International Edition 60 (2021) 6965–6969. date_created: 2022-08-24T10:47:16Z date_published: 2021-03-22T00:00:00Z date_updated: 2024-10-14T11:43:06Z day: '22' doi: 10.1002/anie.202100164 extern: '1' intvolume: ' 60' issue: '13' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1002/anie.202100164 month: '03' oa: 1 oa_version: Published Version page: 6965-6969 publication: Angewandte Chemie International Edition publication_identifier: eissn: - 1521-3773 issn: - 1433-7851 publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: Chromoselective photocatalysis enables stereocomplementary biocatalytic pathways type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 60 year: '2021' ... --- _id: '11965' abstract: - lang: eng text: Metallaphotocatalytic cross-coupling reactions are typically carried out by combining homogeneous or heterogeneous photocatalysts with a soluble nickel complex. Previous attempts to realize recyclable catalytic systems use immobilized iridium complexes to harvest light. We present bifunctional materials based on semiconductors for metallaphotocatalytic C−S cross-coupling reactions that can be reused without losing their catalytic activity. Key to the success is the permanent immobilization of a nickel complex on the surface of a heterogeneous semiconductor through phosphonic acid anchors. The optimized catalyst harvests a broad range of the visible light spectrum and requires a nickel loading of only ∼0.1 mol %. article_processing_charge: No article_type: letter_note author: - first_name: Susanne full_name: Reischauer, Susanne last_name: Reischauer - first_name: Bartholomäus full_name: Pieber, Bartholomäus id: 93e5e5b2-0da6-11ed-8a41-af589a024726 last_name: Pieber orcid: 0000-0001-8689-388X citation: ama: Reischauer S, Pieber B. Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions. ChemPhotoChem. 2021;5(8):716-720. doi:10.1002/cptc.202100062 apa: Reischauer, S., & Pieber, B. (2021). Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions. ChemPhotoChem. Wiley. https://doi.org/10.1002/cptc.202100062 chicago: Reischauer, Susanne, and Bartholomäus Pieber. “Recyclable, Bifunctional Metallaphotocatalysts for C−S Cross‐coupling Reactions.” ChemPhotoChem. Wiley, 2021. https://doi.org/10.1002/cptc.202100062. ieee: S. Reischauer and B. Pieber, “Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions,” ChemPhotoChem, vol. 5, no. 8. Wiley, pp. 716–720, 2021. ista: Reischauer S, Pieber B. 2021. Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions. ChemPhotoChem. 5(8), 716–720. mla: Reischauer, Susanne, and Bartholomäus Pieber. “Recyclable, Bifunctional Metallaphotocatalysts for C−S Cross‐coupling Reactions.” ChemPhotoChem, vol. 5, no. 8, Wiley, 2021, pp. 716–20, doi:10.1002/cptc.202100062. short: S. Reischauer, B. Pieber, ChemPhotoChem 5 (2021) 716–720. date_created: 2022-08-25T08:31:11Z date_published: 2021-08-01T00:00:00Z date_updated: 2024-10-14T11:43:32Z day: '01' doi: 10.1002/cptc.202100062 extern: '1' intvolume: ' 5' issue: '8' language: - iso: eng main_file_link: - open_access: '1' url: https://doi.org/10.1002/cptc.202100062 month: '08' oa: 1 oa_version: Published Version page: 716-720 publication: ChemPhotoChem publication_identifier: eissn: - 2367-0932 publication_status: published publisher: Wiley quality_controlled: '1' scopus_import: '1' status: public title: Recyclable, bifunctional metallaphotocatalysts for C−S cross‐coupling reactions type: journal_article user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87 volume: 5 year: '2021' ...