[{"year":"2020","extern":"1","oa":1,"acknowledgement":"We are grateful to the Schiff Foundation (AJD), Peterhouse, Cambridge (TCTM), the Swiss National Science foundation (TCTM), Ramon Jenkins Fellowship, Sidney Sussex, Cambridge (GM), the Royal Society (AŠ), the Academy of Medical Sciences and Wellcome Trust (AŠ), the Danish Research Council (MK), the Lundbeck Foundation (MK), the Swedish Research Council (SL), the Wellcome Trust (TPJK), the Cambridge Centre for Misfolding Diseases (TPJK), the BBSRC (TPJK), the Frances and Augustus Newman Foundation (TPJK) for financial support. The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013) through the ERC grants PhysProt (agreement no. 337969), MAMBA (agreement no. 340890) and NovoNordiskFonden (SL).","publisher":"Royal Society of Chemistry","language":[{"iso":"eng"}],"article_processing_charge":"No","quality_controlled":"1","_id":"10350","publication":"Chemical Science","citation":{"ama":"Dear AJ, Meisl G, Šarić A, et al. Identification of on- and off-pathway oligomers in amyloid fibril formation. <i>Chemical Science</i>. 2020;11(24):6236-6247. doi:<a href=\"https://doi.org/10.1039/c9sc06501f\">10.1039/c9sc06501f</a>","ieee":"A. J. Dear <i>et al.</i>, “Identification of on- and off-pathway oligomers in amyloid fibril formation,” <i>Chemical Science</i>, vol. 11, no. 24. Royal Society of Chemistry, pp. 6236–6247, 2020.","mla":"Dear, Alexander J., et al. “Identification of On- and off-Pathway Oligomers in Amyloid Fibril Formation.” <i>Chemical Science</i>, vol. 11, no. 24, Royal Society of Chemistry, 2020, pp. 6236–47, doi:<a href=\"https://doi.org/10.1039/c9sc06501f\">10.1039/c9sc06501f</a>.","apa":"Dear, A. J., Meisl, G., Šarić, A., Michaels, T. C. T., Kjaergaard, M., Linse, S., &#38; Knowles, T. P. J. (2020). Identification of on- and off-pathway oligomers in amyloid fibril formation. <i>Chemical Science</i>. Royal Society of Chemistry. <a href=\"https://doi.org/10.1039/c9sc06501f\">https://doi.org/10.1039/c9sc06501f</a>","ista":"Dear AJ, Meisl G, Šarić A, Michaels TCT, Kjaergaard M, Linse S, Knowles TPJ. 2020. Identification of on- and off-pathway oligomers in amyloid fibril formation. Chemical Science. 11(24), 6236–6247.","short":"A.J. Dear, G. Meisl, A. Šarić, T.C.T. Michaels, M. Kjaergaard, S. Linse, T.P.J. Knowles, Chemical Science 11 (2020) 6236–6247.","chicago":"Dear, Alexander J., Georg Meisl, Anđela Šarić, Thomas C. T. Michaels, Magnus Kjaergaard, Sara Linse, and Tuomas P. J. Knowles. “Identification of On- and off-Pathway Oligomers in Amyloid Fibril Formation.” <i>Chemical Science</i>. Royal Society of Chemistry, 2020. <a href=\"https://doi.org/10.1039/c9sc06501f\">https://doi.org/10.1039/c9sc06501f</a>."},"type":"journal_article","date_updated":"2021-11-26T11:21:20Z","issue":"24","title":"Identification of on- and off-pathway oligomers in amyloid fibril formation","day":"08","pmid":1,"month":"06","keyword":["general chemistry"],"intvolume":"        11","abstract":[{"lang":"eng","text":"The misfolding and aberrant aggregation of proteins into fibrillar structures is a key factor in some of the most prevalent human diseases, including diabetes and dementia. Low molecular weight oligomers are thought to be a central factor in the pathology of these diseases, as well as critical intermediates in the fibril formation process, and as such have received much recent attention. Moreover, on-pathway oligomeric intermediates are potential targets for therapeutic strategies aimed at interrupting the fibril formation process. However, a consistent framework for distinguishing on-pathway from off-pathway oligomers has hitherto been lacking and, in particular, no consensus definition of on- and off-pathway oligomers is available. In this paper, we argue that a non-binary definition of oligomers' contribution to fibril-forming pathways may be more informative and we suggest a quantitative framework, in which each oligomeric species is assigned a value between 0 and 1 describing its relative contribution to the formation of fibrils. First, we clarify the distinction between oligomers and fibrils, and then we use the formalism of reaction networks to develop a general definition for on-pathway oligomers, that yields meaningful classifications in the context of amyloid formation. By applying these concepts to Monte Carlo simulations of a minimal aggregating system, and by revisiting several previous studies of amyloid oligomers in light of our new framework, we demonstrate how to perform these classifications in practice. For each oligomeric species we obtain the degree to which it is on-pathway, highlighting the most effective pharmaceutical targets for the inhibition of amyloid fibril formation."}],"page":"6236-6247","main_file_link":[{"url":"https://pubs.rsc.org/en/content/articlehtml/2020/sc/c9sc06501f","open_access":"1"}],"date_published":"2020-06-08T00:00:00Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","license":"https://creativecommons.org/licenses/by-nc/3.0/","oa_version":"Published Version","volume":11,"publication_status":"published","scopus_import":"1","author":[{"full_name":"Dear, Alexander J.","last_name":"Dear","first_name":"Alexander J."},{"first_name":"Georg","last_name":"Meisl","full_name":"Meisl, Georg"},{"last_name":"Šarić","first_name":"Anđela","full_name":"Šarić, Anđela","orcid":"0000-0002-7854-2139","id":"bf63d406-f056-11eb-b41d-f263a6566d8b"},{"full_name":"Michaels, Thomas C. T.","first_name":"Thomas C. T.","last_name":"Michaels"},{"full_name":"Kjaergaard, Magnus","last_name":"Kjaergaard","first_name":"Magnus"},{"full_name":"Linse, Sara","first_name":"Sara","last_name":"Linse"},{"first_name":"Tuomas P. J.","last_name":"Knowles","full_name":"Knowles, Tuomas P. J."}],"tmp":{"name":"Creative Commons Attribution-NonCommercial 3.0 Unported (CC BY-NC 3.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc/3.0/legalcode","short":"CC BY-NC (3.0)","image":"/images/cc_by_nc.png"},"status":"public","external_id":{"pmid":["32953019"]},"article_type":"original","date_created":"2021-11-26T09:08:19Z","publication_identifier":{"eissn":["2041-6539"],"issn":["2041-6520"]},"doi":"10.1039/c9sc06501f"},{"abstract":[{"text":"Oligomeric species populated during the aggregation of the Aβ42 peptide have been identified as potent cytotoxins linked to Alzheimer’s disease, but the fundamental molecular pathways that control their dynamics have yet to be elucidated. By developing a general approach that combines theory, experiment and simulation, we reveal, in molecular detail, the mechanisms of Aβ42 oligomer dynamics during amyloid fibril formation. Even though all mature amyloid fibrils must originate as oligomers, we found that most Aβ42 oligomers dissociate into their monomeric precursors without forming new fibrils. Only a minority of oligomers converts into fibrillar structures. Moreover, the heterogeneous ensemble of oligomeric species interconverts on timescales comparable to those of aggregation. Our results identify fundamentally new steps that could be targeted by therapeutic interventions designed to combat protein misfolding diseases.","lang":"eng"}],"page":"445-451","main_file_link":[{"open_access":"1","url":"https://www.biorxiv.org/content/10.1101/2020.01.08.897488"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_published":"2020-04-13T00:00:00Z","oa_version":"None","volume":12,"publication_status":"published","scopus_import":"1","author":[{"full_name":"Michaels, Thomas C. T.","first_name":"Thomas C. T.","last_name":"Michaels"},{"last_name":"Šarić","first_name":"Anđela","orcid":"0000-0002-7854-2139","full_name":"Šarić, Anđela","id":"bf63d406-f056-11eb-b41d-f263a6566d8b"},{"first_name":"Samo","last_name":"Curk","full_name":"Curk, Samo"},{"full_name":"Bernfur, Katja","first_name":"Katja","last_name":"Bernfur"},{"full_name":"Arosio, Paolo","last_name":"Arosio","first_name":"Paolo"},{"last_name":"Meisl","first_name":"Georg","full_name":"Meisl, Georg"},{"last_name":"Dear","first_name":"Alexander J.","full_name":"Dear, Alexander J."},{"last_name":"Cohen","first_name":"Samuel I. A.","full_name":"Cohen, Samuel I. A."},{"first_name":"Christopher M.","last_name":"Dobson","full_name":"Dobson, Christopher M."},{"last_name":"Vendruscolo","first_name":"Michele","full_name":"Vendruscolo, Michele"},{"first_name":"Sara","last_name":"Linse","full_name":"Linse, Sara"},{"full_name":"Knowles, Tuomas P. J.","last_name":"Knowles","first_name":"Tuomas P. J."}],"external_id":{"pmid":["32303714"]},"status":"public","article_type":"original","date_created":"2021-11-26T09:15:13Z","publication_identifier":{"eissn":["1755-4349"],"issn":["1755-4330"]},"doi":"10.1038/s41557-020-0452-1","year":"2020","extern":"1","oa":1,"related_material":{"link":[{"url":"https://doi.org/10.1038/s41557-020-0468-6","relation":"erratum"}]},"acknowledgement":"We acknowledge support from Peterhouse (T.C.T.M.), the Swiss National Science foundation (T.C.T.M.), the Royal Society (A.Š.), the Academy of Medical Sciences (A.Š.), the UCL Institute for the Physics of Living Systems (S.C.), Sidney Sussex College (G.M.), the Wellcome Trust (A.Š., M.V., C.M.D. and T.P.J.K.), the Schiff Foundation (A.J.D.), the Cambridge Centre for Misfolding Diseases (M.V., C.M.D. and T.P.J.K.), the BBSRC (C.M.D. and T.P.J.K.), the Frances and Augustus Newman Foundation (T.P.J.K.), the Swedish Research Council (S.L.) and the ERC grant MAMBA (S.L., agreement no. 340890). The research that led to these results received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007-2013) through the ERC grant PhysProt (agreement no. 337969).","publisher":"Springer Nature","language":[{"iso":"eng"}],"article_processing_charge":"No","_id":"10351","quality_controlled":"1","publication":"Nature Chemistry","citation":{"short":"T.C.T. Michaels, A. Šarić, S. Curk, K. Bernfur, P. Arosio, G. Meisl, A.J. Dear, S.I.A. Cohen, C.M. Dobson, M. Vendruscolo, S. Linse, T.P.J. Knowles, Nature Chemistry 12 (2020) 445–451.","ista":"Michaels TCT, Šarić A, Curk S, Bernfur K, Arosio P, Meisl G, Dear AJ, Cohen SIA, Dobson CM, Vendruscolo M, Linse S, Knowles TPJ. 2020. Dynamics of oligomer populations formed during the aggregation of Alzheimer’s Aβ42 peptide. Nature Chemistry. 12(5), 445–451.","chicago":"Michaels, Thomas C. T., Anđela Šarić, Samo Curk, Katja Bernfur, Paolo Arosio, Georg Meisl, Alexander J. Dear, et al. “Dynamics of Oligomer Populations Formed during the Aggregation of Alzheimer’s Aβ42 Peptide.” <i>Nature Chemistry</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1038/s41557-020-0452-1\">https://doi.org/10.1038/s41557-020-0452-1</a>.","ieee":"T. C. T. Michaels <i>et al.</i>, “Dynamics of oligomer populations formed during the aggregation of Alzheimer’s Aβ42 peptide,” <i>Nature Chemistry</i>, vol. 12, no. 5. Springer Nature, pp. 445–451, 2020.","ama":"Michaels TCT, Šarić A, Curk S, et al. Dynamics of oligomer populations formed during the aggregation of Alzheimer’s Aβ42 peptide. <i>Nature Chemistry</i>. 2020;12(5):445-451. doi:<a href=\"https://doi.org/10.1038/s41557-020-0452-1\">10.1038/s41557-020-0452-1</a>","mla":"Michaels, Thomas C. T., et al. “Dynamics of Oligomer Populations Formed during the Aggregation of Alzheimer’s Aβ42 Peptide.” <i>Nature Chemistry</i>, vol. 12, no. 5, Springer Nature, 2020, pp. 445–51, doi:<a href=\"https://doi.org/10.1038/s41557-020-0452-1\">10.1038/s41557-020-0452-1</a>.","apa":"Michaels, T. C. T., Šarić, A., Curk, S., Bernfur, K., Arosio, P., Meisl, G., … Knowles, T. P. J. (2020). Dynamics of oligomer populations formed during the aggregation of Alzheimer’s Aβ42 peptide. <i>Nature Chemistry</i>. Springer Nature. <a href=\"https://doi.org/10.1038/s41557-020-0452-1\">https://doi.org/10.1038/s41557-020-0452-1</a>"},"type":"journal_article","date_updated":"2021-11-26T11:21:08Z","title":"Dynamics of oligomer populations formed during the aggregation of Alzheimer’s Aβ42 peptide","issue":"5","day":"13","pmid":1,"month":"04","keyword":["general chemical engineering","general chemistry"],"intvolume":"        12"},{"date_updated":"2021-11-26T11:21:16Z","type":"journal_article","intvolume":"       101","month":"02","title":"Intrinsically disordered nuclear pore proteins show ideal-polymer morphologies and dynamics","issue":"2","day":"28","pmid":1,"language":[{"iso":"eng"}],"acknowledgement":"We thank Dino Osmanović (MIT), Roy Beck (Tel-Aviv), Larissa Kapinos (Basel), Roderick Lim (Basel), Ralf Richter (Leeds), and Anton Zilman (Toronto) for discussions. This work was funded by the Royal Society (A.Š.) and the UK Engineering and Physical Sciences Research Council (EP/L504889/1, B.W.H.).","publisher":"American Physical Society","article_processing_charge":"No","extern":"1","year":"2020","oa":1,"citation":{"ista":"Davis LK, Ford IJ, Šarić A, Hoogenboom BW. 2020. Intrinsically disordered nuclear pore proteins show ideal-polymer morphologies and dynamics. Physical Review E. 101(2), 022420.","short":"L.K. Davis, I.J. Ford, A. Šarić, B.W. Hoogenboom, Physical Review E 101 (2020).","chicago":"Davis, Luke K., Ian J. Ford, Anđela Šarić, and Bart W. Hoogenboom. “Intrinsically Disordered Nuclear Pore Proteins Show Ideal-Polymer Morphologies and Dynamics.” <i>Physical Review E</i>. American Physical Society, 2020. <a href=\"https://doi.org/10.1103/physreve.101.022420\">https://doi.org/10.1103/physreve.101.022420</a>.","ieee":"L. K. Davis, I. J. Ford, A. Šarić, and B. W. Hoogenboom, “Intrinsically disordered nuclear pore proteins show ideal-polymer morphologies and dynamics,” <i>Physical Review E</i>, vol. 101, no. 2. American Physical Society, 2020.","ama":"Davis LK, Ford IJ, Šarić A, Hoogenboom BW. Intrinsically disordered nuclear pore proteins show ideal-polymer morphologies and dynamics. <i>Physical Review E</i>. 2020;101(2). doi:<a href=\"https://doi.org/10.1103/physreve.101.022420\">10.1103/physreve.101.022420</a>","mla":"Davis, Luke K., et al. “Intrinsically Disordered Nuclear Pore Proteins Show Ideal-Polymer Morphologies and Dynamics.” <i>Physical Review E</i>, vol. 101, no. 2, 022420, American Physical Society, 2020, doi:<a href=\"https://doi.org/10.1103/physreve.101.022420\">10.1103/physreve.101.022420</a>.","apa":"Davis, L. K., Ford, I. J., Šarić, A., &#38; Hoogenboom, B. W. (2020). Intrinsically disordered nuclear pore proteins show ideal-polymer morphologies and dynamics. <i>Physical Review E</i>. American Physical Society. <a href=\"https://doi.org/10.1103/physreve.101.022420\">https://doi.org/10.1103/physreve.101.022420</a>"},"_id":"10352","quality_controlled":"1","article_number":"022420","publication":"Physical Review E","external_id":{"pmid":["32168597"]},"status":"public","scopus_import":"1","publication_status":"published","volume":101,"author":[{"first_name":"Luke K.","last_name":"Davis","full_name":"Davis, Luke K."},{"full_name":"Ford, Ian J.","first_name":"Ian J.","last_name":"Ford"},{"last_name":"Šarić","first_name":"Anđela","orcid":"0000-0002-7854-2139","full_name":"Šarić, Anđela","id":"bf63d406-f056-11eb-b41d-f263a6566d8b"},{"full_name":"Hoogenboom, Bart W.","last_name":"Hoogenboom","first_name":"Bart W."}],"date_created":"2021-11-26T09:41:04Z","doi":"10.1103/physreve.101.022420","publication_identifier":{"eissn":["2470-0053"],"issn":["2470-0045"]},"article_type":"original","abstract":[{"text":"In the nuclear pore complex, intrinsically disordered nuclear pore proteins (FG Nups) form a selective barrier for transport into and out of the cell nucleus, in a way that remains poorly understood. The collective FG Nup behavior has long been conceptualized either as a polymer brush, dominated by entropic and excluded-volume (repulsive) interactions, or as a hydrogel, dominated by cohesive (attractive) interactions between FG Nups. Here we compare mesoscale computational simulations with a wide range of experimental data to demonstrate that FG Nups are at the crossover point between these two regimes. Specifically, we find that repulsive and attractive interactions are balanced, resulting in morphologies and dynamics that are close to those of ideal polymer chains. We demonstrate that this property of FG Nups yields sufficient cohesion to seal the transport barrier, and yet maintains fast dynamics at the molecular scale, permitting the rapid polymer rearrangements needed for transport events.","lang":"eng"}],"main_file_link":[{"open_access":"1","url":"https://www.biorxiv.org/content/10.1101/571687"}],"oa_version":"Preprint","date_published":"2020-02-28T00:00:00Z","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9"},{"pmid":1,"day":"31","title":"Dynamic clustering regulates activity of mechanosensitive membrane channels","issue":"4","month":"01","intvolume":"       124","keyword":["general physics and astronomy"],"type":"journal_article","date_updated":"2021-11-26T11:21:12Z","publication":"Physical Review Letters","article_number":"048102","_id":"10353","quality_controlled":"1","citation":{"apa":"Paraschiv, A., Hegde, S., Ganti, R., Pilizota, T., &#38; Šarić, A. (2020). Dynamic clustering regulates activity of mechanosensitive membrane channels. <i>Physical Review Letters</i>. American Physical Society. <a href=\"https://doi.org/10.1103/physrevlett.124.048102\">https://doi.org/10.1103/physrevlett.124.048102</a>","mla":"Paraschiv, Alexandru, et al. “Dynamic Clustering Regulates Activity of Mechanosensitive Membrane Channels.” <i>Physical Review Letters</i>, vol. 124, no. 4, 048102, American Physical Society, 2020, doi:<a href=\"https://doi.org/10.1103/physrevlett.124.048102\">10.1103/physrevlett.124.048102</a>.","ama":"Paraschiv A, Hegde S, Ganti R, Pilizota T, Šarić A. Dynamic clustering regulates activity of mechanosensitive membrane channels. <i>Physical Review Letters</i>. 2020;124(4). doi:<a href=\"https://doi.org/10.1103/physrevlett.124.048102\">10.1103/physrevlett.124.048102</a>","ieee":"A. Paraschiv, S. Hegde, R. Ganti, T. Pilizota, and A. Šarić, “Dynamic clustering regulates activity of mechanosensitive membrane channels,” <i>Physical Review Letters</i>, vol. 124, no. 4. American Physical Society, 2020.","chicago":"Paraschiv, Alexandru, Smitha Hegde, Raman Ganti, Teuta Pilizota, and Anđela Šarić. “Dynamic Clustering Regulates Activity of Mechanosensitive Membrane Channels.” <i>Physical Review Letters</i>. American Physical Society, 2020. <a href=\"https://doi.org/10.1103/physrevlett.124.048102\">https://doi.org/10.1103/physrevlett.124.048102</a>.","short":"A. Paraschiv, S. Hegde, R. Ganti, T. Pilizota, A. Šarić, Physical Review Letters 124 (2020).","ista":"Paraschiv A, Hegde S, Ganti R, Pilizota T, Šarić A. 2020. Dynamic clustering regulates activity of mechanosensitive membrane channels. Physical Review Letters. 124(4), 048102."},"oa":1,"year":"2020","extern":"1","article_processing_charge":"No","publisher":"American Physical Society","language":[{"iso":"eng"}],"acknowledgement":"We thank Samantha Miller, Bert Poolman, and the members of Šarić and Pilizota laboratories for useful discussion. We acknowledge support from the Engineering and Physical Sciences Research Council (A.P. and A.Š.), the UCL Institute for the Physics of Living Systems (A.P. and A.Š.), Darwin Trust of University of Edinburgh (H.S.), Industrial Biotechnology Innovation Centre (H.S. and T.P.), BBSRC Council Crossing Biological Membrane Network (H.S. and T.P.), BBSRC/EPSRC/MRC Synthetic Biology Research Centre (T.P.), and the Royal Society (A.Š.).","article_type":"original","publication_identifier":{"issn":["0031-9007"],"eissn":["1079-7114"]},"doi":"10.1103/physrevlett.124.048102","date_created":"2021-11-26T09:57:01Z","author":[{"first_name":"Alexandru","last_name":"Paraschiv","full_name":"Paraschiv, Alexandru"},{"first_name":"Smitha","last_name":"Hegde","full_name":"Hegde, Smitha"},{"full_name":"Ganti, Raman","last_name":"Ganti","first_name":"Raman"},{"last_name":"Pilizota","first_name":"Teuta","full_name":"Pilizota, Teuta"},{"orcid":"0000-0002-7854-2139","full_name":"Šarić, Anđela","id":"bf63d406-f056-11eb-b41d-f263a6566d8b","last_name":"Šarić","first_name":"Anđela"}],"volume":124,"publication_status":"published","scopus_import":"1","external_id":{"pmid":["32058787"]},"status":"public","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_published":"2020-01-31T00:00:00Z","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://www.biorxiv.org/content/10.1101/553248"}],"abstract":[{"text":"Experiments have suggested that bacterial mechanosensitive channels separate into 2D clusters, the role of which is unclear. By developing a coarse-grained computer model we find that clustering promotes the channel closure, which is highly dependent on the channel concentration and membrane stress. This behaviour yields a tightly regulated gating system, whereby at high tensions channels gate individually, and at lower tensions the channels spontaneously aggregate and inactivate. We implement this positive feedback into the model for cell volume regulation, and find that the channel clustering protects the cell against excessive loss of cytoplasmic content.","lang":"eng"}]},{"_id":"10556","quality_controlled":"1","publication":"Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security","citation":{"ieee":"E. Kokoris Kogias, D. Malkhi, and A. Spiegelman, “Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures,” in <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>, Virtual, United States, 2020, pp. 1751–1767.","ama":"Kokoris Kogias E, Malkhi D, Spiegelman A. Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. In: <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>. Association for Computing Machinery; 2020:1751–1767. doi:<a href=\"https://doi.org/10.1145/3372297.3423364\">10.1145/3372297.3423364</a>","apa":"Kokoris Kogias, E., Malkhi, D., &#38; Spiegelman, A. (2020). Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. In <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i> (pp. 1751–1767). Virtual, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3372297.3423364\">https://doi.org/10.1145/3372297.3423364</a>","mla":"Kokoris Kogias, Eleftherios, et al. “Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures.” <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>, Association for Computing Machinery, 2020, pp. 1751–1767, doi:<a href=\"https://doi.org/10.1145/3372297.3423364\">10.1145/3372297.3423364</a>.","ista":"Kokoris Kogias E, Malkhi D, Spiegelman A. 2020. Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. CCS: Computer and Communications Security, 1751–1767.","short":"E. Kokoris Kogias, D. Malkhi, A. Spiegelman, in:, Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery, 2020, pp. 1751–1767.","chicago":"Kokoris Kogias, Eleftherios, Dahlia Malkhi, and Alexander Spiegelman. “Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures.” In <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>, 1751–1767. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3372297.3423364\">https://doi.org/10.1145/3372297.3423364</a>."},"year":"2020","conference":{"location":"Virtual, United States","end_date":"2020-11-13","name":"CCS: Computer and Communications Security","start_date":"2020-11-09"},"oa":1,"acknowledgement":"We would like to thank Ittai Abraham for the discussions and guidance during the initial conception of the project, especially for HAVSS. Furthermore, we would like to thank the anonymous reviewers for pointing out the relevance of this work to MPC protocols.","language":[{"iso":"eng"}],"publisher":"Association for Computing Machinery","article_processing_charge":"No","title":"Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures","day":"30","month":"10","type":"conference","date_updated":"2024-02-22T13:10:45Z","department":[{"_id":"ElKo"}],"date_published":"2020-10-30T00:00:00Z","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","page":"1751–1767","abstract":[{"lang":"eng","text":"In this paper, we present the first Asynchronous Distributed Key Generation (ADKG) algorithm which is also the first distributed key generation algorithm that can generate cryptographic keys with a dual (f,2f+1)-threshold (where f is the number of faulty parties). As a result, using our ADKG we remove the trusted setup assumption that the most scalable consensus algorithms make. In order to create a DKG with a dual (f,2f+1)- threshold we first answer in the affirmative the open question posed by Cachin et al. [7] on how to create an Asynchronous Verifiable Secret Sharing (AVSS) protocol with a reconstruction threshold of f+1<k łe 2f+1, which is of independent interest. Our High-threshold-AVSS (HAVSS) uses an asymmetric bivariate polynomial to encode the secret. This enables the reconstruction of the secret only if a set of k nodes contribute while allowing an honest node that did not participate in the sharing phase to recover his share with the help of f+1 honest parties. Once we have HAVSS we can use it to bootstrap scalable partially synchronous consensus protocols, but the question on how to get a DKG in asynchrony remains as we need a way to produce common randomness. The solution comes from a novel Eventually Perfect Common Coin (EPCC) abstraction that enables the generation of a common coin from n concurrent HAVSS invocations. EPCC's key property is that it is eventually reliable, as it might fail to agree at most f times (even if invoked a polynomial number of times). Using EPCC we implement an Eventually Efficient Asynchronous Binary Agreement (EEABA) which is optimal when the EPCC agrees and protects safety when EPCC fails. Finally, using EEABA we construct the first ADKG which has the same overhead and expected runtime as the best partially-synchronous DKG (O(n4) words, O(f) rounds). As a corollary of our ADKG, we can also create the first Validated Asynchronous Byzantine Agreement (VABA) that does not need a trusted dealer to setup threshold signatures of degree n-f. Our VABA has an overhead of expected O(n2) words and O(1) time per instance, after an initial O(n4) words and O(f) time bootstrap via ADKG."}],"main_file_link":[{"url":"https://eprint.iacr.org/2019/1015","open_access":"1"}],"date_created":"2021-12-16T13:23:27Z","doi":"10.1145/3372297.3423364","publication_identifier":{"isbn":["978-1-4503-7089-9"]},"publication_status":"published","scopus_import":"1","author":[{"full_name":"Kokoris Kogias, Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"Kokoris Kogias","first_name":"Eleftherios"},{"last_name":"Malkhi","first_name":"Dahlia","full_name":"Malkhi, Dahlia"},{"first_name":"Alexander","last_name":"Spiegelman","full_name":"Spiegelman, Alexander"}],"isi":1,"external_id":{"isi":["000768470400104"]},"status":"public"},{"day":"03","title":"Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods","month":"03","date_created":"2021-12-16T13:28:59Z","application_date":"2017-06-09","author":[{"first_name":"Bryan","last_name":"Ford","full_name":"Ford, Bryan"},{"first_name":"Linus","last_name":"Gasse","full_name":"Gasse, Linus"},{"id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","full_name":"Kokoris Kogias, Eleftherios","first_name":"Eleftherios","last_name":"Kokoris Kogias"},{"full_name":"Jovanovic, Philipp","first_name":"Philipp","last_name":"Jovanovic"}],"ipc":" H04L9/3247 ; G06Q20/29 ; G06Q20/382 ; H04L9/3236","type":"patent","status":"public","publication_date":"2020-03-03","department":[{"_id":"ElKo"}],"date_updated":"2021-12-21T10:04:50Z","date_published":"2020-03-03T00:00:00Z","_id":"10557","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","oa_version":"Published Version","citation":{"mla":"Ford, Bryan, et al. <i>Cryptographically Verifiable Data Structure Having Multi-Hop Forward and Backwards Links and Associated Systems and Methods</i>. 2020.","apa":"Ford, B., Gasse, L., Kokoris Kogias, E., &#38; Jovanovic, P. (2020). Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods.","ieee":"B. Ford, L. Gasse, E. Kokoris Kogias, and P. Jovanovic, “Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods.” 2020.","ama":"Ford B, Gasse L, Kokoris Kogias E, Jovanovic P. Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods. 2020.","chicago":"Ford, Bryan, Linus Gasse, Eleftherios Kokoris Kogias, and Philipp Jovanovic. “Cryptographically Verifiable Data Structure Having Multi-Hop Forward and Backwards Links and Associated Systems and Methods,” 2020.","short":"B. Ford, L. Gasse, E. Kokoris Kogias, P. Jovanovic, (2020).","ista":"Ford B, Gasse L, Kokoris Kogias E, Jovanovic P. 2020. Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods."},"oa":1,"main_file_link":[{"url":"https://patents.google.com/patent/US10581613B2/en","open_access":"1"}],"related_material":{"link":[{"relation":"earlier_version","url":"https://patents.google.com/patent/US20180359096A1/en"}]},"year":"2020","abstract":[{"lang":"eng","text":"Data storage and retrieval systems, methods, and computer-readable media utilize a cryptographically verifiable data structure that facilitates verification of a transaction in a decentralized peer-to-peer environment using multi-hop backwards and forwards links. Backward links are cryptographic hashes of past records. Forward links are cryptographic signatures of future records that are added retroactively to records once the target block has been appended to the data structure."}],"extern":"1","applicant":["Ecole Polytechnique Federale de Lausanne"],"ipn":"10581613","article_processing_charge":"No"},{"volume":588,"scopus_import":"1","publication_status":"published","author":[{"full_name":"Polshyn, Hryhoriy","orcid":"0000-0001-8223-8896","id":"edfc7cb1-526e-11ec-b05a-e6ecc27e4e48","last_name":"Polshyn","first_name":"Hryhoriy"},{"last_name":"Zhu","first_name":"J.","full_name":"Zhu, J."},{"first_name":"M. A.","last_name":"Kumar","full_name":"Kumar, M. A."},{"first_name":"Y.","last_name":"Zhang","full_name":"Zhang, Y."},{"full_name":"Yang, F.","first_name":"F.","last_name":"Yang"},{"full_name":"Tschirhart, C. L.","last_name":"Tschirhart","first_name":"C. L."},{"last_name":"Serlin","first_name":"M.","full_name":"Serlin, M."},{"first_name":"K.","last_name":"Watanabe","full_name":"Watanabe, K."},{"full_name":"Taniguchi, T.","first_name":"T.","last_name":"Taniguchi"},{"full_name":"MacDonald, A. H.","first_name":"A. H.","last_name":"MacDonald"},{"last_name":"Young","first_name":"A. F.","full_name":"Young, A. F."}],"external_id":{"arxiv":["2004.11353"],"pmid":["33230333"]},"status":"public","article_type":"original","date_created":"2022-01-13T14:12:17Z","publication_identifier":{"eissn":["1476-4687"],"issn":["0028-0836"]},"doi":"10.1038/s41586-020-2963-8","abstract":[{"text":"Magnetism typically arises from the joint effect of Fermi statistics and repulsive Coulomb interactions, which favours ground states with non-zero electron spin. As a result, controlling spin magnetism with electric fields—a longstanding technological goal in spintronics and multiferroics1,2—can be achieved only indirectly. Here we experimentally demonstrate direct electric-field control of magnetic states in an orbital Chern insulator3,4,5,6, a magnetic system in which non-trivial band topology favours long-range order of orbital angular momentum but the spins are thought to remain disordered7,8,9,10,11,12,13,14. We use van der Waals heterostructures consisting of a graphene monolayer rotationally faulted with respect to a Bernal-stacked bilayer to realize narrow and topologically non-trivial valley-projected moiré minibands15,16,17. At fillings of one and three electrons per moiré unit cell within these bands, we observe quantized anomalous Hall effects18 with transverse resistance approximately equal to h/2e2 (where h is Planck’s constant and e is the charge on the electron), which is indicative of spontaneous polarization of the system into a single-valley-projected band with a Chern number equal to two. At a filling of three electrons per moiré unit cell, we find that the sign of the quantum anomalous Hall effect can be reversed via field-effect control of the chemical potential; moreover, this transition is hysteretic, which we use to demonstrate non-volatile electric-field-induced reversal of the magnetic state. A theoretical analysis19 indicates that the effect arises from the topological edge states, which drive a change in sign of the magnetization and thus a reversal in the favoured magnetic state. Voltage control of magnetic states can be used to electrically pattern non-volatile magnetic-domain structures hosting chiral edge states, with applications ranging from reconfigurable microwave circuit elements to ultralow-power magnetic memories.","lang":"eng"}],"page":"66-70","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2004.11353"}],"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_published":"2020-11-23T00:00:00Z","oa_version":"Preprint","type":"journal_article","date_updated":"2022-01-13T14:21:04Z","title":"Electrical switching of magnetic order in an orbital Chern insulator","issue":"7836","day":"23","pmid":1,"month":"11","keyword":["multidisciplinary"],"intvolume":"       588","year":"2020","extern":"1","oa":1,"arxiv":1,"language":[{"iso":"eng"}],"acknowledgement":"We acknowledge discussions with J. Checkelsky, S. Chen, C. Dean, M. Yankowitz, D. Reilly, I. Sodemann and M. Zaletel. Work at UCSB was primarily supported by the ARO under MURI W911NF-16-1-0361. Measurements of twisted bilayer graphene (Extended Data Fig. 8) and measurements at elevated temperatures (Extended Data Fig. 3) were supported by a SEED grant and made use of shared facilities of the UCSB MRSEC (NSF DMR 1720256), a member of the Materials Research Facilities Network (www.mrfn.org). A.F.Y. acknowledges the support of the David and Lucille Packard Foundation under award 2016-65145. A.H.M. and J.Z. were supported by the National Science Foundation through the Center for Dynamics and Control of Materials, an NSF MRSEC under Cooperative Agreement number DMR-1720595, and by the Welch Foundation under grant TBF1473. C.L.T. acknowledges support from the Hertz Foundation and from the National Science Foundation Graduate Research Fellowship Program under grant 1650114. K.W. and T.T. acknowledge support from the Elemental Strategy Initiative conducted by the MEXT, Japan, Grant Number JPMXP0112101001, JSPS KAKENHI grant numbers JP20H00354 and the CREST(JPMJCR15F3), JST.","publisher":"Springer Nature","article_processing_charge":"No","quality_controlled":"1","_id":"10618","publication":"Nature","citation":{"ieee":"H. Polshyn <i>et al.</i>, “Electrical switching of magnetic order in an orbital Chern insulator,” <i>Nature</i>, vol. 588, no. 7836. Springer Nature, pp. 66–70, 2020.","ama":"Polshyn H, Zhu J, Kumar MA, et al. Electrical switching of magnetic order in an orbital Chern insulator. <i>Nature</i>. 2020;588(7836):66-70. doi:<a href=\"https://doi.org/10.1038/s41586-020-2963-8\">10.1038/s41586-020-2963-8</a>","apa":"Polshyn, H., Zhu, J., Kumar, M. A., Zhang, Y., Yang, F., Tschirhart, C. L., … Young, A. F. (2020). Electrical switching of magnetic order in an orbital Chern insulator. <i>Nature</i>. Springer Nature. <a href=\"https://doi.org/10.1038/s41586-020-2963-8\">https://doi.org/10.1038/s41586-020-2963-8</a>","mla":"Polshyn, Hryhoriy, et al. “Electrical Switching of Magnetic Order in an Orbital Chern Insulator.” <i>Nature</i>, vol. 588, no. 7836, Springer Nature, 2020, pp. 66–70, doi:<a href=\"https://doi.org/10.1038/s41586-020-2963-8\">10.1038/s41586-020-2963-8</a>.","ista":"Polshyn H, Zhu J, Kumar MA, Zhang Y, Yang F, Tschirhart CL, Serlin M, Watanabe K, Taniguchi T, MacDonald AH, Young AF. 2020. Electrical switching of magnetic order in an orbital Chern insulator. Nature. 588(7836), 66–70.","short":"H. Polshyn, J. Zhu, M.A. Kumar, Y. Zhang, F. Yang, C.L. Tschirhart, M. Serlin, K. Watanabe, T. Taniguchi, A.H. MacDonald, A.F. Young, Nature 588 (2020) 66–70.","chicago":"Polshyn, Hryhoriy, J. Zhu, M. A. Kumar, Y. Zhang, F. Yang, C. L. Tschirhart, M. Serlin, et al. “Electrical Switching of Magnetic Order in an Orbital Chern Insulator.” <i>Nature</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1038/s41586-020-2963-8\">https://doi.org/10.1038/s41586-020-2963-8</a>."}},{"author":[{"full_name":"Alexandradinata, A","first_name":"A","last_name":"Alexandradinata"},{"full_name":"Armitage, N.P.","first_name":"N.P.","last_name":"Armitage"},{"full_name":"Baydin, Andrey","first_name":"Andrey","last_name":"Baydin"},{"last_name":"Bi","first_name":"Wenli","full_name":"Bi, Wenli"},{"full_name":"Cao, Yue","last_name":"Cao","first_name":"Yue"},{"first_name":"Hitesh J.","last_name":"Changlani","full_name":"Changlani, Hitesh J."},{"first_name":"Eli","last_name":"Chertkov","full_name":"Chertkov, Eli"},{"last_name":"da Silva Neto","first_name":"Eduardo H.","full_name":"da Silva Neto, Eduardo H."},{"full_name":"Delacretaz, Luca","first_name":"Luca","last_name":"Delacretaz"},{"full_name":"El Baggari, Ismail","first_name":"Ismail","last_name":"El Baggari"},{"full_name":"Ferguson, G.M.","first_name":"G.M.","last_name":"Ferguson"},{"full_name":"Gannon, William J.","first_name":"William J.","last_name":"Gannon"},{"first_name":"Sayed Ali Akbar","last_name":"Ghorashi","full_name":"Ghorashi, Sayed Ali Akbar"},{"full_name":"Goodge, Berit H.","last_name":"Goodge","first_name":"Berit H."},{"last_name":"Goulko","first_name":"Olga","full_name":"Goulko, Olga"},{"full_name":"Grissonnache, G.","first_name":"G.","last_name":"Grissonnache"},{"last_name":"Hallas","first_name":"Alannah","full_name":"Hallas, Alannah"},{"full_name":"Hayes, Ian M.","last_name":"Hayes","first_name":"Ian M."},{"last_name":"He","first_name":"Yu","full_name":"He, Yu"},{"full_name":"Huang, Edwin W.","last_name":"Huang","first_name":"Edwin W."},{"first_name":"Anshu","last_name":"Kogar","full_name":"Kogar, Anshu"},{"last_name":"Kumah","first_name":"Divine","full_name":"Kumah, Divine"},{"full_name":"Lee, Jong Yeon","first_name":"Jong Yeon","last_name":"Lee"},{"full_name":"Legros, A.","first_name":"A.","last_name":"Legros"},{"first_name":"Fahad","last_name":"Mahmood","full_name":"Mahmood, Fahad"},{"full_name":"Maximenko, Yulia","last_name":"Maximenko","first_name":"Yulia"},{"full_name":"Pellatz, Nick","last_name":"Pellatz","first_name":"Nick"},{"orcid":"0000-0001-8223-8896","full_name":"Polshyn, Hryhoriy","id":"edfc7cb1-526e-11ec-b05a-e6ecc27e4e48","last_name":"Polshyn","first_name":"Hryhoriy"},{"full_name":"Sarkar, Tarapada","first_name":"Tarapada","last_name":"Sarkar"},{"full_name":"Scheie, Allen","last_name":"Scheie","first_name":"Allen"},{"full_name":"Seyler, Kyle L.","first_name":"Kyle L.","last_name":"Seyler"},{"full_name":"Shi, Zhenzhong","last_name":"Shi","first_name":"Zhenzhong"},{"first_name":"Brian","last_name":"Skinner","full_name":"Skinner, Brian"},{"first_name":"Lucia","last_name":"Steinke","full_name":"Steinke, Lucia"},{"full_name":"Thirunavukkuarasu, K.","last_name":"Thirunavukkuarasu","first_name":"K."},{"full_name":"Trevisan, Thaís Victa","first_name":"Thaís Victa","last_name":"Trevisan"},{"full_name":"Vogl, Michael","first_name":"Michael","last_name":"Vogl"},{"first_name":"Pavel A.","last_name":"Volkov","full_name":"Volkov, Pavel A."},{"last_name":"Wang","first_name":"Yao","full_name":"Wang, Yao"},{"full_name":"Wang, Yishu","last_name":"Wang","first_name":"Yishu"},{"full_name":"Wei, Di","last_name":"Wei","first_name":"Di"},{"first_name":"Kaya","last_name":"Wei","full_name":"Wei, Kaya"},{"full_name":"Yang, Shuolong","first_name":"Shuolong","last_name":"Yang"},{"full_name":"Zhang, Xian","last_name":"Zhang","first_name":"Xian"},{"last_name":"Zhang","first_name":"Ya-Hui","full_name":"Zhang, Ya-Hui"},{"full_name":"Zhao, Liuyan","last_name":"Zhao","first_name":"Liuyan"},{"full_name":"Zong, Alfred","first_name":"Alfred","last_name":"Zong"}],"type":"preprint","publication_status":"submitted","status":"public","external_id":{"arxiv":["2010.00584"]},"date_updated":"2022-01-24T08:05:51Z","day":"01","title":"The future of the correlated electron problem","month":"10","date_created":"2022-01-20T10:55:36Z","oa":1,"main_file_link":[{"url":"https://arxiv.org/abs/2010.00584","open_access":"1"}],"page":"55","extern":"1","year":"2020","abstract":[{"lang":"eng","text":"The understanding of material systems with strong electron-electron interactions is the central problem in modern condensed matter physics. Despite this, the essential physics of many of these materials is still not understood and we have no overall perspective on their properties. Moreover, we have very little ability to make predictions in this class of systems. In this manuscript we share our personal views of what the major open problems are in correlated electron systems and we discuss some possible routes to make progress in this rich and fascinating field. This manuscript is the result of the vigorous discussions and deliberations that took place at Johns Hopkins University during a three-day workshop January 27, 28, and 29, 2020 that brought together six senior scientists and 46 more junior scientists. Our hope, is that the topics we have presented will provide inspiration for others working in this field and motivation for the idea that significant progress can be made on very hard problems if we focus our collective energies."}],"article_processing_charge":"No","language":[{"iso":"eng"}],"arxiv":1,"acknowledgement":"We thank NSF CMP program for suggestions regarding the topic and general structure of the workshop. This project was supported by the NSF DMR-2002329 and The Gordon and Betty Moore Foundation (GBMF) EPiQS initiative. We would like to sincerely thank A. Kapitulnik, A. J. Leggett, M.B. Maple, T.M. McQueen, M. Norman, P. S. Riseborough, and G. A. Sawatzky for their lectures at the workshop and advice on the writing of this manuscript. We would also like to thank G. Blumberg, C. Broholm, S. Crooker, N. Drichko, and A. Patel for helpful consultation on topics discussed\r\nherein. A number of individuals also had independent support: (AA, EH; GBMF-4305), (IMH; GBMF-9071), (HJC; NHMFL is supported by the NSF DMR-1644779 and the state of Florida), (YH, AZ; Miller Institute for Basic Research in Science), (YC; US DOE-BES DEAC02-06CH11357), (AS; Spallation Neutron Source, a DOE Office of Science User Facility operated by ORNL), (SAAG; ARO-W911NF-18-1-0290, NSF DMR-1455233), (YW; DOE-BES DE-SC0019331, GBMF-4532).","publication":"arXiv","_id":"10650","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_published":"2020-10-01T00:00:00Z","citation":{"chicago":"Alexandradinata, A, N.P. Armitage, Andrey Baydin, Wenli Bi, Yue Cao, Hitesh J. Changlani, Eli Chertkov, et al. “The Future of the Correlated Electron Problem.” <i>ArXiv</i>, n.d.","short":"A. Alexandradinata, N.P. Armitage, A. Baydin, W. Bi, Y. Cao, H.J. Changlani, E. Chertkov, E.H. da Silva Neto, L. Delacretaz, I. El Baggari, G.M. Ferguson, W.J. Gannon, S.A.A. Ghorashi, B.H. Goodge, O. Goulko, G. Grissonnache, A. Hallas, I.M. Hayes, Y. He, E.W. Huang, A. Kogar, D. Kumah, J.Y. Lee, A. Legros, F. Mahmood, Y. Maximenko, N. Pellatz, H. Polshyn, T. Sarkar, A. Scheie, K.L. Seyler, Z. Shi, B. Skinner, L. Steinke, K. Thirunavukkuarasu, T.V. Trevisan, M. Vogl, P.A. Volkov, Y. Wang, Y. Wang, D. Wei, K. Wei, S. Yang, X. Zhang, Y.-H. Zhang, L. Zhao, A. Zong, ArXiv (n.d.).","ista":"Alexandradinata A, Armitage NP, Baydin A, Bi W, Cao Y, Changlani HJ, Chertkov E, da Silva Neto EH, Delacretaz L, El Baggari I, Ferguson GM, Gannon WJ, Ghorashi SAA, Goodge BH, Goulko O, Grissonnache G, Hallas A, Hayes IM, He Y, Huang EW, Kogar A, Kumah D, Lee JY, Legros A, Mahmood F, Maximenko Y, Pellatz N, Polshyn H, Sarkar T, Scheie A, Seyler KL, Shi Z, Skinner B, Steinke L, Thirunavukkuarasu K, Trevisan TV, Vogl M, Volkov PA, Wang Y, Wang Y, Wei D, Wei K, Yang S, Zhang X, Zhang Y-H, Zhao L, Zong A. The future of the correlated electron problem. arXiv, .","mla":"Alexandradinata, A., et al. “The Future of the Correlated Electron Problem.” <i>ArXiv</i>.","apa":"Alexandradinata, A., Armitage, N. P., Baydin, A., Bi, W., Cao, Y., Changlani, H. J., … Zong, A. (n.d.). The future of the correlated electron problem. <i>arXiv</i>.","ama":"Alexandradinata A, Armitage NP, Baydin A, et al. The future of the correlated electron problem. <i>arXiv</i>.","ieee":"A. Alexandradinata <i>et al.</i>, “The future of the correlated electron problem,” <i>arXiv</i>. ."},"oa_version":"Preprint"},{"type":"conference","date_updated":"2023-02-14T08:57:55Z","title":"Dynamic matching algorithms in practice","day":"26","month":"08","intvolume":"       173","extern":"1","year":"2020","conference":{"start_date":"2020-09-07","location":"Pisa, Italy","end_date":"2020-09-09","name":"ESA: Annual European Symposium on Algorithms"},"oa":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"language":[{"iso":"eng"}],"article_processing_charge":"No","_id":"11816","quality_controlled":"1","article_number":"58","publication":"8th Annual European Symposium on Algorithms","citation":{"short":"M.H. Henzinger, K. Shahbaz, R. Paul, C. Schulz, in:, 8th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ista":"Henzinger MH, Shahbaz K, Paul R, Schulz C. 2020. Dynamic matching algorithms in practice. 8th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 58.","chicago":"Henzinger, Monika H, Khan Shahbaz, Richard Paul, and Christian Schulz. “Dynamic Matching Algorithms in Practice.” In <i>8th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">https://doi.org/10.4230/LIPIcs.ESA.2020.58</a>.","ama":"Henzinger MH, Shahbaz K, Paul R, Schulz C. Dynamic matching algorithms in practice. In: <i>8th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">10.4230/LIPIcs.ESA.2020.58</a>","ieee":"M. H. Henzinger, K. Shahbaz, R. Paul, and C. Schulz, “Dynamic matching algorithms in practice,” in <i>8th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.","apa":"Henzinger, M. H., Shahbaz, K., Paul, R., &#38; Schulz, C. (2020). Dynamic matching algorithms in practice. In <i>8th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">https://doi.org/10.4230/LIPIcs.ESA.2020.58</a>","mla":"Henzinger, Monika H., et al. “Dynamic Matching Algorithms in Practice.” <i>8th Annual European Symposium on Algorithms</i>, vol. 173, 58, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.58\">10.4230/LIPIcs.ESA.2020.58</a>."},"scopus_import":"1","publication_status":"published","volume":173,"author":[{"first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Shahbaz","first_name":"Khan","full_name":"Shahbaz, Khan"},{"last_name":"Paul","first_name":"Richard","full_name":"Paul, Richard"},{"first_name":"Christian","last_name":"Schulz","full_name":"Schulz, Christian"}],"external_id":{"arxiv":["2004.09099"]},"status":"public","date_created":"2022-08-12T07:13:25Z","doi":"10.4230/LIPIcs.ESA.2020.58","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771627"]},"abstract":[{"lang":"eng","text":"In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. In this paper, we attempt to bridge the gap between theory and practice that is currently observed for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study those algorithms on an extensive set of dynamic instances."}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2020.58"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2020-08-26T00:00:00Z","alternative_title":["LIPIcs"],"oa_version":"Published Version"},{"abstract":[{"text":"With input sizes becoming massive, coresets - small yet representative summary of the input - are relevant more than ever. A weighted set C_w that is a subset of the input is an ε-coreset if the cost of any feasible solution S with respect to C_w is within [1±ε] of the cost of S with respect to the original input. We give a very general technique to compute coresets in the fully-dynamic setting where input points can be added or deleted. Given a static (i.e., not dynamic) ε-coreset-construction algorithm that runs in time t(n, ε, λ) and computes a coreset of size s(n, ε, λ), where n is the number of input points and 1-λ is the success probability, we give a fully-dynamic algorithm that computes an ε-coreset with worst-case update time O((log n) ⋅ t(s(n, ε/log n, λ/n), ε/log n, λ/n)) (this bound is stated informally), where the success probability is 1-λ. Our technique is a fully-dynamic analog of the merge-and-reduce technique, which is due to Har-Peled and Mazumdar [Har-Peled and Mazumdar, 2004] and is based on a technique of Bentley and Saxe [Jon Louis Bentley and James B. Saxe, 1980], that applies to the insertion-only setting where points can only be added. Although, our space usage is O(n), our technique works in the presence of an adaptive adversary, and we show that Ω(n) space is required when adversary is adaptive.\r\nAs a concrete implication of our technique, using the result of Braverman et al. [{Braverman} et al., 2016], we get fully-dynamic ε-coreset-construction algorithms for k-median and k-means with worst-case update time O(ε^{-2} k² log⁵ n log³ k) and coreset size O(ε^{-2} k log n log² k) ignoring log log n and log(1/ε) factors and assuming that ε = Ω(1/poly(n)) and λ = Ω(1/poly(n)) (which are very weak assumptions made only to make these bounds easy to parse). This results in the first fully-dynamic constant-approximation algorithms for k-median and k-means with update times O(poly(k, log n, ε^{-1})). Specifically, the dependence on k is only quadratic, and the bounds are worst-case. The best previous bound for both problems was amortized O(nlog n) by Cohen-Addad et al. [Cohen-Addad et al., 2019] via randomized O(1)-coresets in O(n) space.\r\nWe also show that under the OMv conjecture [Monika Henzinger et al., 2015], a fully-dynamic (4 - δ)-approximation algorithm for k-means must either have an amortized update time of Ω(k^{1-γ}) or amortized query time of Ω(k^{2 - γ}), where γ > 0 is a constant.","lang":"eng"}],"main_file_link":[{"url":"https://doi.org/10.4230/LIPIcs.ESA.2020.57","open_access":"1"}],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2020-08-26T00:00:00Z","alternative_title":["LIPIcs"],"external_id":{"arxiv":["2004.14891"]},"status":"public","scopus_import":"1","publication_status":"published","volume":173,"author":[{"last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Kale, Sagar","last_name":"Kale","first_name":"Sagar"}],"date_created":"2022-08-12T07:22:55Z","doi":"10.4230/LIPIcs.ESA.2020.57","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771627"]},"language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"article_processing_charge":"No","extern":"1","year":"2020","conference":{"location":"Pisa, Italy","end_date":"2020-09-09","name":"ESA: Annual European Symposium on Algorithms","start_date":"2020-09-07"},"oa":1,"citation":{"chicago":"Henzinger, Monika H, and Sagar Kale. “Fully-Dynamic Coresets.” In <i>28th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">https://doi.org/10.4230/LIPIcs.ESA.2020.57</a>.","ista":"Henzinger MH, Kale S. 2020. Fully-dynamic coresets. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 57.","short":"M.H. Henzinger, S. Kale, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","mla":"Henzinger, Monika H., and Sagar Kale. “Fully-Dynamic Coresets.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">10.4230/LIPIcs.ESA.2020.57</a>.","apa":"Henzinger, M. H., &#38; Kale, S. (2020). Fully-dynamic coresets. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">https://doi.org/10.4230/LIPIcs.ESA.2020.57</a>","ieee":"M. H. Henzinger and S. Kale, “Fully-dynamic coresets,” in <i>28th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.","ama":"Henzinger MH, Kale S. Fully-dynamic coresets. In: <i>28th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.57\">10.4230/LIPIcs.ESA.2020.57</a>"},"quality_controlled":"1","_id":"11818","article_number":"57","publication":"28th Annual European Symposium on Algorithms","date_updated":"2023-02-14T09:29:51Z","type":"conference","intvolume":"       173","month":"08","title":"Fully-dynamic coresets","day":"26"},{"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2020-08-26T00:00:00Z","alternative_title":["LIPIcs"],"abstract":[{"text":"We present a practically efficient algorithm that finds all global minimum cuts in huge undirected graphs. Our algorithm uses a multitude of kernelization rules to reduce the graph to a small equivalent instance and then finds all minimum cuts using an optimized version of the algorithm of Nagamochi, Nakao and Ibaraki. In shared memory we are able to find all minimum cuts of graphs with up to billions of edges and millions of minimum cuts in a few minutes. We also give a new linear time algorithm to find the most balanced minimum cuts given as input the representation of all minimum cuts.","lang":"eng"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.ESA.2020.59"}],"date_created":"2022-08-12T07:27:42Z","doi":"10.4230/LIPIcs.ESA.2020.59","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771627"]},"external_id":{"arxiv":["2002.06948"]},"status":"public","publication_status":"published","scopus_import":"1","volume":173,"author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger"},{"last_name":"Noe","first_name":"Alexander","full_name":"Noe, Alexander"},{"last_name":"Schulz","first_name":"Christian","full_name":"Schulz, Christian"},{"full_name":"Strash, Darren","last_name":"Strash","first_name":"Darren"}],"citation":{"ista":"Henzinger MH, Noe A, Schulz C, Strash D. 2020. Finding all global minimum cuts in practice. 28th Annual European Symposium on Algorithms. ESA: Annual European Symposium on Algorithms, LIPIcs, vol. 173, 59.","short":"M.H. Henzinger, A. Noe, C. Schulz, D. Strash, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Finding All Global Minimum Cuts in Practice.” In <i>28th Annual European Symposium on Algorithms</i>, Vol. 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">https://doi.org/10.4230/LIPIcs.ESA.2020.59</a>.","ieee":"M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Finding all global minimum cuts in practice,” in <i>28th Annual European Symposium on Algorithms</i>, Pisa, Italy, 2020, vol. 173.","ama":"Henzinger MH, Noe A, Schulz C, Strash D. Finding all global minimum cuts in practice. In: <i>28th Annual European Symposium on Algorithms</i>. Vol 173. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">10.4230/LIPIcs.ESA.2020.59</a>","mla":"Henzinger, Monika H., et al. “Finding All Global Minimum Cuts in Practice.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 59, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">10.4230/LIPIcs.ESA.2020.59</a>.","apa":"Henzinger, M. H., Noe, A., Schulz, C., &#38; Strash, D. (2020). Finding all global minimum cuts in practice. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.59\">https://doi.org/10.4230/LIPIcs.ESA.2020.59</a>"},"quality_controlled":"1","_id":"11819","article_number":"59","publication":"28th Annual European Symposium on Algorithms","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"article_processing_charge":"No","extern":"1","year":"2020","conference":{"start_date":"2020-09-07","name":"ESA: Annual European Symposium on Algorithms","end_date":"2020-09-09","location":"Pisa, Italy"},"oa":1,"month":"08","intvolume":"       173","title":"Finding all global minimum cuts in practice","day":"26","date_updated":"2023-02-14T09:39:18Z","type":"conference"},{"citation":{"ista":"Hanauer K, Henzinger MH, Schulz C. 2020. Faster fully dynamic transitive closure in practice. 18th International Symposium on Experimental Algorithms. SEA: Symposium on Experimental Algorithms, LIPIcs, vol. 160, 14.","short":"K. Hanauer, M.H. Henzinger, C. Schulz, in:, 18th International Symposium on Experimental Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Faster Fully Dynamic Transitive Closure in Practice.” In <i>18th International Symposium on Experimental Algorithms</i>, Vol. 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">https://doi.org/10.4230/LIPIcs.SEA.2020.14</a>.","ama":"Hanauer K, Henzinger MH, Schulz C. Faster fully dynamic transitive closure in practice. In: <i>18th International Symposium on Experimental Algorithms</i>. Vol 160. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">10.4230/LIPIcs.SEA.2020.14</a>","ieee":"K. Hanauer, M. H. Henzinger, and C. Schulz, “Faster fully dynamic transitive closure in practice,” in <i>18th International Symposium on Experimental Algorithms</i>, Pisa, Italy, 2020, vol. 160.","apa":"Hanauer, K., Henzinger, M. H., &#38; Schulz, C. (2020). Faster fully dynamic transitive closure in practice. In <i>18th International Symposium on Experimental Algorithms</i> (Vol. 160). Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">https://doi.org/10.4230/LIPIcs.SEA.2020.14</a>","mla":"Hanauer, Kathrin, et al. “Faster Fully Dynamic Transitive Closure in Practice.” <i>18th International Symposium on Experimental Algorithms</i>, vol. 160, 14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SEA.2020.14\">10.4230/LIPIcs.SEA.2020.14</a>."},"publication":"18th International Symposium on Experimental Algorithms","article_number":"14","_id":"11822","quality_controlled":"1","article_processing_charge":"No","language":[{"iso":"eng"}],"arxiv":1,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","oa":1,"conference":{"start_date":"2020-09-07","end_date":"2020-09-09","name":"SEA: Symposium on Experimental Algorithms","location":"Pisa, Italy"},"year":"2020","extern":"1","month":"06","intvolume":"       160","day":"12","title":"Faster fully dynamic transitive closure in practice","date_updated":"2023-02-14T09:58:42Z","type":"conference","oa_version":"Published Version","alternative_title":["LIPIcs"],"date_published":"2020-06-12T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.SEA.2020.14"}],"abstract":[{"lang":"eng","text":"The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence of edge insertions and deletions. The problem has been thoroughly investigated in theory and many specialized algorithms for solving it have been proposed in the last decades. In two large studies [Frigioni ea, 2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been evaluated experimentally against simple, static algorithms for graph traversal, showing the competitiveness and even superiority of the simple algorithms in practice, except for very dense random graphs or very high ratios of queries. A major drawback of those studies is that only small and mostly randomly generated graphs are considered.\r\nIn this paper, we engineer new algorithms to maintain all-pairs reachability information which are simple and space-efficient. Moreover, we perform an extensive experimental evaluation on both generated and real-world instances that are several orders of magnitude larger than those in the previous studies. Our results indicate that our new algorithms outperform all state-of-the-art algorithms on all types of input considerably in practice."}],"publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771481"]},"doi":"10.4230/LIPIcs.SEA.2020.14","date_created":"2022-08-12T07:32:53Z","external_id":{"arxiv":["2002.00813"]},"status":"public","author":[{"first_name":"Kathrin","last_name":"Hanauer","full_name":"Hanauer, Kathrin"},{"last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Christian","last_name":"Schulz","full_name":"Schulz, Christian"}],"volume":160,"scopus_import":"1","publication_status":"published"},{"date_created":"2022-08-12T07:46:44Z","publication_identifier":{"isbn":["9783959771436"],"issn":["1868-8969"]},"doi":"10.4230/LIPIcs.SoCG.2020.51","external_id":{"arxiv":["2003.02605"]},"status":"public","volume":164,"publication_status":"published","scopus_import":"1","author":[{"last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Neumann, Stefan","first_name":"Stefan","last_name":"Neumann"},{"full_name":"Wiese, Andreas","first_name":"Andreas","last_name":"Wiese"}],"oa_version":"Published Version","date_published":"2020-06-08T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","alternative_title":["LIPIcs"],"abstract":[{"lang":"eng","text":"Independent set is a fundamental problem in combinatorial optimization. While in general graphs the problem is essentially inapproximable, for many important graph classes there are approximation algorithms known in the offline setting. These graph classes include interval graphs and geometric intersection graphs, where vertices correspond to intervals/geometric objects and an edge indicates that the two corresponding objects intersect.\r\nWe present dynamic approximation algorithms for independent set of intervals, hypercubes and hyperrectangles in d dimensions. They work in the fully dynamic model where each update inserts or deletes a geometric object. All our algorithms are deterministic and have worst-case update times that are polylogarithmic for constant d and ε>0, assuming that the coordinates of all input objects are in [0, N]^d and each of their edges has length at least 1. We obtain the following results:\r\n- For weighted intervals, we maintain a (1+ε)-approximate solution.\r\n- For d-dimensional hypercubes we maintain a (1+ε)2^d-approximate solution in the unweighted case and a O(2^d)-approximate solution in the weighted case. Also, we show that for maintaining an unweighted (1+ε)-approximate solution one needs polynomial update time for d ≥ 2 if the ETH holds.\r\n- For weighted d-dimensional hyperrectangles we present a dynamic algorithm with approximation ratio (1+ε)log^{d-1}N."}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.SoCG.2020.51"}],"intvolume":"       164","month":"06","title":"Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles","day":"08","date_updated":"2023-02-14T10:00:58Z","type":"conference","citation":{"ista":"Henzinger MH, Neumann S, Wiese A. 2020. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. 36th International Symposium on Computational Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 51.","short":"M.H. Henzinger, S. Neumann, A. Wiese, in:, 36th International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","chicago":"Henzinger, Monika H, Stefan Neumann, and Andreas Wiese. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” In <i>36th International Symposium on Computational Geometry</i>, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">https://doi.org/10.4230/LIPIcs.SoCG.2020.51</a>.","ieee":"M. H. Henzinger, S. Neumann, and A. Wiese, “Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles,” in <i>36th International Symposium on Computational Geometry</i>, Zurich, Switzerland, 2020, vol. 164.","ama":"Henzinger MH, Neumann S, Wiese A. Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In: <i>36th International Symposium on Computational Geometry</i>. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">10.4230/LIPIcs.SoCG.2020.51</a>","mla":"Henzinger, Monika H., et al. “Dynamic Approximate Maximum Independent Set of Intervals, Hypercubes and Hyperrectangles.” <i>36th International Symposium on Computational Geometry</i>, vol. 164, 51, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">10.4230/LIPIcs.SoCG.2020.51</a>.","apa":"Henzinger, M. H., Neumann, S., &#38; Wiese, A. (2020). Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles. In <i>36th International Symposium on Computational Geometry</i> (Vol. 164). Zurich, Switzerland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.SoCG.2020.51\">https://doi.org/10.4230/LIPIcs.SoCG.2020.51</a>"},"_id":"11824","quality_controlled":"1","publication":"36th International Symposium on Computational Geometry","article_number":"51","language":[{"iso":"eng"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"article_processing_charge":"No","year":"2020","extern":"1","oa":1,"conference":{"start_date":"2020-06-23","end_date":"2020-06-26","name":"SoCG: Symposium on Computational Geometry","location":"Zurich, Switzerland"}},{"abstract":[{"text":"We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper (Δ+1)-vertex coloring of a graph with maximum degree at most Δ. This improves upon the previous O(log Δ)-time algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning random ranks to vertices and does not need to maintain a hierarchical graph decomposition. We show that our result does not only have optimal running time, but is also optimal in the sense that already deciding whether a Δ-coloring exists in a dynamically changing graph with maximum degree at most Δ takes Ω(log n) time per operation.","lang":"eng"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.4230/LIPIcs.STACS.2020.53"}],"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2020-03-04T00:00:00Z","alternative_title":["LIPIcs"],"status":"public","external_id":{"arxiv":["1907.04745"]},"scopus_import":"1","publication_status":"published","volume":154,"author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"},{"full_name":"Peng, Pan","last_name":"Peng","first_name":"Pan"}],"date_created":"2022-08-12T07:53:05Z","doi":"10.4230/LIPIcs.STACS.2020.53","publication_identifier":{"isbn":["9783959771405"],"issn":["1868-8969"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","language":[{"iso":"eng"}],"arxiv":1,"article_processing_charge":"No","extern":"1","year":"2020","conference":{"start_date":"2020-03-10","end_date":"2020-03-13","name":"STACS: Symposium on Theoretical Aspects of Computer Science","location":"Montpellier, France"},"oa":1,"citation":{"mla":"Henzinger, Monika H., and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, vol. 154, 53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">10.4230/LIPIcs.STACS.2020.53</a>.","apa":"Henzinger, M. H., &#38; Peng, P. (2020). Constant-time dynamic (Δ+1)-coloring. In <i>37th International Symposium on Theoretical Aspects of Computer Science</i> (Vol. 154). Montpellier, France: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">https://doi.org/10.4230/LIPIcs.STACS.2020.53</a>","ama":"Henzinger MH, Peng P. Constant-time dynamic (Δ+1)-coloring. In: <i>37th International Symposium on Theoretical Aspects of Computer Science</i>. Vol 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">10.4230/LIPIcs.STACS.2020.53</a>","ieee":"M. H. Henzinger and P. Peng, “Constant-time dynamic (Δ+1)-coloring,” in <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, Montpellier, France, 2020, vol. 154.","chicago":"Henzinger, Monika H, and Pan Peng. “Constant-Time Dynamic (Δ+1)-Coloring.” In <i>37th International Symposium on Theoretical Aspects of Computer Science</i>, Vol. 154. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.STACS.2020.53\">https://doi.org/10.4230/LIPIcs.STACS.2020.53</a>.","short":"M.H. Henzinger, P. Peng, in:, 37th International Symposium on Theoretical Aspects of Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ista":"Henzinger MH, Peng P. 2020. Constant-time dynamic (Δ+1)-coloring. 37th International Symposium on Theoretical Aspects of Computer Science. STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 154, 53."},"quality_controlled":"1","_id":"11825","article_number":"53","publication":"37th International Symposium on Theoretical Aspects of Computer Science","date_updated":"2023-02-14T10:03:43Z","type":"conference","intvolume":"       154","month":"03","title":"Constant-time dynamic (Δ+1)-coloring","day":"04"},{"type":"conference","date_updated":"2023-02-17T09:47:36Z","title":"Fast dynamic cuts, distances and effective resistances via vertex sparsifiers","day":"01","month":"11","extern":"1","year":"2020","conference":{"start_date":"2020-11-16","name":"FOCS: Annual Symposium on Foundations of Computer Science","end_date":"2020-11-19","location":"Durham, NC, United States"},"oa":1,"language":[{"iso":"eng"}],"arxiv":1,"publisher":"Institute of Electrical and Electronics Engineers","article_processing_charge":"No","_id":"11852","quality_controlled":"1","publication":"61st Annual Symposium on Foundations of Computer Science","citation":{"chicago":"Chen, Li, Gramoz Goranci, Monika H Henzinger, Richard Peng, and Thatchaphol Saranurak. “Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.” In <i>61st Annual Symposium on Foundations of Computer Science</i>, 1135–46. Institute of Electrical and Electronics Engineers, 2020. <a href=\"https://doi.org/10.1109/focs46700.2020.00109\">https://doi.org/10.1109/focs46700.2020.00109</a>.","ista":"Chen L, Goranci G, Henzinger MH, Peng R, Saranurak T. 2020. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. 61st Annual Symposium on Foundations of Computer Science. FOCS: Annual Symposium on Foundations of Computer Science, 1135–1146.","short":"L. Chen, G. Goranci, M.H. Henzinger, R. Peng, T. Saranurak, in:, 61st Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, 2020, pp. 1135–1146.","mla":"Chen, Li, et al. “Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers.” <i>61st Annual Symposium on Foundations of Computer Science</i>, Institute of Electrical and Electronics Engineers, 2020, pp. 1135–46, doi:<a href=\"https://doi.org/10.1109/focs46700.2020.00109\">10.1109/focs46700.2020.00109</a>.","apa":"Chen, L., Goranci, G., Henzinger, M. H., Peng, R., &#38; Saranurak, T. (2020). Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In <i>61st Annual Symposium on Foundations of Computer Science</i> (pp. 1135–1146). Durham, NC, United States: Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/focs46700.2020.00109\">https://doi.org/10.1109/focs46700.2020.00109</a>","ieee":"L. Chen, G. Goranci, M. H. Henzinger, R. Peng, and T. Saranurak, “Fast dynamic cuts, distances and effective resistances via vertex sparsifiers,” in <i>61st Annual Symposium on Foundations of Computer Science</i>, Durham, NC, United States, 2020, pp. 1135–1146.","ama":"Chen L, Goranci G, Henzinger MH, Peng R, Saranurak T. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In: <i>61st Annual Symposium on Foundations of Computer Science</i>. Institute of Electrical and Electronics Engineers; 2020:1135-1146. doi:<a href=\"https://doi.org/10.1109/focs46700.2020.00109\">10.1109/focs46700.2020.00109</a>"},"scopus_import":"1","publication_status":"published","author":[{"first_name":"Li","last_name":"Chen","full_name":"Chen, Li"},{"last_name":"Goranci","first_name":"Gramoz","full_name":"Goranci, Gramoz"},{"first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"first_name":"Richard","last_name":"Peng","full_name":"Peng, Richard"},{"last_name":"Saranurak","first_name":"Thatchaphol","full_name":"Saranurak, Thatchaphol"}],"status":"public","external_id":{"arxiv":["2005.02368"]},"date_created":"2022-08-16T07:33:12Z","doi":"10.1109/focs46700.2020.00109","publication_identifier":{"eissn":["2575-8454"],"eisbn":["978-1-7281-9621-3"],"isbn":["978-1-7281-9622-0"]},"page":"1135-1146","abstract":[{"lang":"eng","text":"We present a general framework of designing efficient dynamic approximate algorithms for optimization problems on undirected graphs. In particular, we develop a technique that, given any problem that admits a certain notion of vertex sparsifiers, gives data structures that maintain approximate solutions in sub-linear update and query time. We illustrate the applicability of our paradigm to the following problems. (1)A fully-dynamic algorithm that approximates all-pair maximum-flows/minimum-cuts up to a nearly logarithmic factor in O~(n2/3) 11The O~(⋅) notation is used in this paper to hide poly-logarithmic factors. amortized time against an oblivious adversary, and O~(m3/4) time against an adaptive adversary. (2)An incremental data structure that maintains O(1) - approximate shortest path in no(1) time per operation, as well as fully dynamic approximate all-pair shortest path and transshipment in O~(n2/3+o(1)) amortized time per operation. (3)A fully-dynamic algorithm that approximates all-pair effective resistance up to an (1+ϵ) factor in O~(n2/3+o(1)ϵ−O(1)) amortized update time per operation. The key tool behind result (1) is the dynamic maintenance of an algorithmic construction due to Madry [FOCS' 10], which partitions a graph into a collection of simpler graph structures (known as j-trees) and approximately captures the cut-flow and metric structure of the graph. The O(1)-approximation guarantee of (2) is by adapting the distance oracles by [Thorup-Zwick JACM '05]. Result (3) is obtained by invoking the random-walk based spectral vertex sparsifier by [Durfee et al. STOC '19] in a hierarchical manner, while carefully keeping track of the recourse among levels in the hierarchy. See https://arxiv.org/pdf/2005.02368.pdf for the full version of this paper."}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2005.02368"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2020-11-01T00:00:00Z","oa_version":"Preprint"},{"main_file_link":[{"url":"https://arxiv.org/abs/1905.01216","open_access":"1"}],"abstract":[{"text":"Given a directed graph and a source vertex, the fully dynamic single-source reachability problem is to maintain the set of vertices that are reachable from the given vertex, subject to edge deletions and insertions. It is one of the most fundamental problems on graphs and appears directly or indirectly in many and varied applications. While there has been theoretical work on this problem, showing both linear conditional lower bounds for the fully dynamic problem and insertions-only and deletions-only upper bounds beating these conditional lower bounds, there has been no experimental study that compares the performance of fully dynamic reachability algorithms in practice. Previous experimental studies in this area concentrated only on the more general all-pairs reachability or transitive closure problem and did not use real-world dynamic graphs.\r\n\r\nIn this paper, we bridge this gap by empirically studying an extensive set of algorithms for the single-source reachability problem in the fully dynamic setting. In particular, we design several fully dynamic variants of well-known approaches to obtain and maintain reachability information with respect to a distinguished source. Moreover, we extend the existing insertions-only or deletions-only upper bounds into fully dynamic algorithms. Even though the worst-case time per operation of all the fully dynamic algorithms we evaluate is at least linear in the number of edges in the graph (as is to be expected given the conditional lower bounds) we show in our extensive experimental evaluation that their performance differs greatly, both on generated as well as on real-world instances.","lang":"eng"}],"page":"106-119","date_published":"2020-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","author":[{"last_name":"Hanauer","first_name":"Kathrin","full_name":"Hanauer, Kathrin"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H"},{"last_name":"Schulz","first_name":"Christian","full_name":"Schulz, Christian"}],"scopus_import":"1","publication_status":"published","external_id":{"arxiv":["1905.01216"]},"status":"public","publication_identifier":{"eisbn":["978-1-61197-600-7"]},"doi":"10.1137/1.9781611976007.9","date_created":"2022-08-17T06:39:32Z","oa":1,"conference":{"name":"ALENEX: Symposium on Algorithm Engineering and Experiments","end_date":"2020-01-06","location":"Salt Lake City, UT, United States","start_date":"2020-01-05"},"year":"2020","extern":"1","article_processing_charge":"No","language":[{"iso":"eng"}],"arxiv":1,"publisher":"Society for Industrial and Applied Mathematics","publication":"2020 Symposium on Algorithm Engineering and Experiments","quality_controlled":"1","_id":"11880","citation":{"ista":"Hanauer K, Henzinger MH, Schulz C. 2020. Fully dynamic single-source reachability in practice: An experimental study. 2020 Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 106–119.","short":"K. Hanauer, M.H. Henzinger, C. Schulz, in:, 2020 Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2020, pp. 106–119.","chicago":"Hanauer, Kathrin, Monika H Henzinger, and Christian Schulz. “Fully Dynamic Single-Source Reachability in Practice: An Experimental Study.” In <i>2020 Symposium on Algorithm Engineering and Experiments</i>, 106–19. Society for Industrial and Applied Mathematics, 2020. <a href=\"https://doi.org/10.1137/1.9781611976007.9\">https://doi.org/10.1137/1.9781611976007.9</a>.","ama":"Hanauer K, Henzinger MH, Schulz C. Fully dynamic single-source reachability in practice: An experimental study. In: <i>2020 Symposium on Algorithm Engineering and Experiments</i>. Society for Industrial and Applied Mathematics; 2020:106-119. doi:<a href=\"https://doi.org/10.1137/1.9781611976007.9\">10.1137/1.9781611976007.9</a>","ieee":"K. Hanauer, M. H. Henzinger, and C. Schulz, “Fully dynamic single-source reachability in practice: An experimental study,” in <i>2020 Symposium on Algorithm Engineering and Experiments</i>, Salt Lake City, UT, United States, 2020, pp. 106–119.","apa":"Hanauer, K., Henzinger, M. H., &#38; Schulz, C. (2020). Fully dynamic single-source reachability in practice: An experimental study. In <i>2020 Symposium on Algorithm Engineering and Experiments</i> (pp. 106–119). Salt Lake City, UT, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611976007.9\">https://doi.org/10.1137/1.9781611976007.9</a>","mla":"Hanauer, Kathrin, et al. “Fully Dynamic Single-Source Reachability in Practice: An Experimental Study.” <i>2020 Symposium on Algorithm Engineering and Experiments</i>, Society for Industrial and Applied Mathematics, 2020, pp. 106–19, doi:<a href=\"https://doi.org/10.1137/1.9781611976007.9\">10.1137/1.9781611976007.9</a>."},"type":"conference","date_updated":"2023-02-17T14:00:37Z","day":"01","title":"Fully dynamic single-source reachability in practice: An experimental study","month":"01"},{"doi":"10.1137/1.9781611976007.4","publication_identifier":{"eisbn":["978-1-61197-600-7"]},"date_created":"2022-08-17T06:47:40Z","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger"},{"first_name":"Alexander","last_name":"Noe","full_name":"Noe, Alexander"},{"full_name":"Schulz, Christian","first_name":"Christian","last_name":"Schulz"}],"scopus_import":"1","publication_status":"published","external_id":{"arxiv":["1908.04141"]},"status":"public","date_published":"2020-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1908.04141"}],"page":"42-55","abstract":[{"text":"We introduce the fastest known exact algorithm for the multiterminal cut problem with k terminals. In particular, we engineer existing as well as new data reduction rules. We use the rules within a branch-and-reduce framework and to boost the performance of an ILP formulation. Our algorithms achieve improvements in running time of up to multiple orders of magnitudes over the ILP formulation without data reductions, which has been the de facto standard used by practitioners. This allows us to solve instances to optimality that are significantly larger than was previously possible.","lang":"eng"}],"day":"01","title":"Shared-memory branch-and-reduce for multiterminal cuts","month":"01","type":"conference","date_updated":"2023-02-17T14:02:04Z","publication":"2020 Symposium on Algorithm Engineering and Experiments","_id":"11881","quality_controlled":"1","citation":{"ista":"Henzinger MH, Noe A, Schulz C. 2020. Shared-memory branch-and-reduce for multiterminal cuts. 2020 Symposium on Algorithm Engineering and Experiments. ALENEX: Symposium on Algorithm Engineering and Experiments, 42–55.","short":"M.H. Henzinger, A. Noe, C. Schulz, in:, 2020 Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2020, pp. 42–55.","chicago":"Henzinger, Monika H, Alexander Noe, and Christian Schulz. “Shared-Memory Branch-and-Reduce for Multiterminal Cuts.” In <i>2020 Symposium on Algorithm Engineering and Experiments</i>, 42–55. Society for Industrial and Applied Mathematics, 2020. <a href=\"https://doi.org/10.1137/1.9781611976007.4\">https://doi.org/10.1137/1.9781611976007.4</a>.","ama":"Henzinger MH, Noe A, Schulz C. Shared-memory branch-and-reduce for multiterminal cuts. In: <i>2020 Symposium on Algorithm Engineering and Experiments</i>. Society for Industrial and Applied Mathematics; 2020:42-55. doi:<a href=\"https://doi.org/10.1137/1.9781611976007.4\">10.1137/1.9781611976007.4</a>","ieee":"M. H. Henzinger, A. Noe, and C. Schulz, “Shared-memory branch-and-reduce for multiterminal cuts,” in <i>2020 Symposium on Algorithm Engineering and Experiments</i>, Salt Lake City, UT, United States, 2020, pp. 42–55.","mla":"Henzinger, Monika H., et al. “Shared-Memory Branch-and-Reduce for Multiterminal Cuts.” <i>2020 Symposium on Algorithm Engineering and Experiments</i>, Society for Industrial and Applied Mathematics, 2020, pp. 42–55, doi:<a href=\"https://doi.org/10.1137/1.9781611976007.4\">10.1137/1.9781611976007.4</a>.","apa":"Henzinger, M. H., Noe, A., &#38; Schulz, C. (2020). Shared-memory branch-and-reduce for multiterminal cuts. In <i>2020 Symposium on Algorithm Engineering and Experiments</i> (pp. 42–55). Salt Lake City, UT, United States: Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/1.9781611976007.4\">https://doi.org/10.1137/1.9781611976007.4</a>"},"conference":{"start_date":"2020-01-05","name":"ALENEX: Symposium on Algorithm Engineering and Experiments","end_date":"2020-01-06","location":"Salt Lake City, UT, United States"},"oa":1,"extern":"1","year":"2020","article_processing_charge":"No","publisher":"Society for Industrial and Applied Mathematics","arxiv":1,"language":[{"iso":"eng"}]},{"main_file_link":[{"url":"https://arxiv.org/abs/1704.01254"}],"abstract":[{"lang":"eng","text":"We study the problem of computing a minimum cut in a simple, undirected graph and give a deterministic 𝑂(𝑚log2𝑛loglog2𝑛) time algorithm. This improves on both the best previously known deterministic running time of 𝑂(𝑚log12𝑛) (Kawarabayashi and Thorup [J. ACM, 66 (2018), 4]) and the best previously known randomized running time of 𝑂(𝑚log3𝑛) (Karger [J. ACM, 47 (2000), pp. 46--76]) for this problem, though Karger's algorithm can be further applied to weighted graphs. Moreover, our result extends to balanced directed graphs, where the balance of a directed graph captures how close the graph is to being Eulerian. Our approach is using the Kawarabayashi and Thorup graph compression technique, which repeatedly finds low conductance cuts. To find these cuts they use a diffusion-based local algorithm. We use instead a flow-based local algorithm and suitably adjust their framework to work with our flow-based subroutine. Both flow- and diffusion-based methods have a long history of being applied to finding low conductance cuts. Diffusion algorithms have several variants that are naturally local, while it is more complicated to make flow methods local. Some prior work has proven nice properties for local flow-based algorithms with respect to improving or cleaning up low conductance cuts. Our flow subroutine, however, is the first that both is local and produces low conductance cuts. Thus, it may be of independent interest."}],"page":"1-36","oa_version":"Preprint","date_published":"2020-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["1704.01254"]},"status":"public","author":[{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H"},{"full_name":"Rao, Satish","first_name":"Satish","last_name":"Rao"},{"full_name":"Wang, Di","last_name":"Wang","first_name":"Di"}],"volume":49,"scopus_import":"1","publication_status":"published","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"doi":"10.1137/18m1180335","date_created":"2022-08-17T08:09:31Z","article_type":"original","article_processing_charge":"No","arxiv":1,"publisher":"Society for Industrial & Applied Mathematics","language":[{"iso":"eng"}],"related_material":{"record":[{"status":"public","id":"11873","relation":"later_version"}]},"year":"2020","extern":"1","citation":{"ieee":"M. H. Henzinger, S. Rao, and D. Wang, “Local flow partitioning for faster edge connectivity,” <i>SIAM Journal on Computing</i>, vol. 49, no. 1. Society for Industrial &#38; Applied Mathematics, pp. 1–36, 2020.","ama":"Henzinger MH, Rao S, Wang D. Local flow partitioning for faster edge connectivity. <i>SIAM Journal on Computing</i>. 2020;49(1):1-36. doi:<a href=\"https://doi.org/10.1137/18m1180335\">10.1137/18m1180335</a>","mla":"Henzinger, Monika H., et al. “Local Flow Partitioning for Faster Edge Connectivity.” <i>SIAM Journal on Computing</i>, vol. 49, no. 1, Society for Industrial &#38; Applied Mathematics, 2020, pp. 1–36, doi:<a href=\"https://doi.org/10.1137/18m1180335\">10.1137/18m1180335</a>.","apa":"Henzinger, M. H., Rao, S., &#38; Wang, D. (2020). Local flow partitioning for faster edge connectivity. <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/18m1180335\">https://doi.org/10.1137/18m1180335</a>","short":"M.H. Henzinger, S. Rao, D. Wang, SIAM Journal on Computing 49 (2020) 1–36.","ista":"Henzinger MH, Rao S, Wang D. 2020. Local flow partitioning for faster edge connectivity. SIAM Journal on Computing. 49(1), 1–36.","chicago":"Henzinger, Monika H, Satish Rao, and Di Wang. “Local Flow Partitioning for Faster Edge Connectivity.” <i>SIAM Journal on Computing</i>. Society for Industrial &#38; Applied Mathematics, 2020. <a href=\"https://doi.org/10.1137/18m1180335\">https://doi.org/10.1137/18m1180335</a>."},"publication":"SIAM Journal on Computing","_id":"11889","quality_controlled":"1","date_updated":"2023-02-21T16:31:25Z","type":"journal_article","month":"01","intvolume":"        49","day":"01","title":"Local flow partitioning for faster edge connectivity","issue":"1"},{"scopus_import":"1","publication_status":"published","volume":34,"author":[{"full_name":"Goranci, Gramoz","last_name":"Goranci","first_name":"Gramoz"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger"},{"first_name":"Pan","last_name":"Peng","full_name":"Peng, Pan"}],"status":"public","external_id":{"arxiv":["1702.01136"]},"article_type":"original","date_created":"2022-08-17T08:50:24Z","doi":"10.1137/17m1163153","publication_identifier":{"issn":["0895-4801"],"eissn":["1095-7146"]},"page":"130-162","abstract":[{"lang":"eng","text":"Graph sparsification aims at compressing large graphs into smaller ones while preserving important characteristics of the input graph. In this work we study vertex sparsifiers, i.e., sparsifiers whose goal is to reduce the number of vertices. We focus on the following notions: (1) Given a digraph 𝐺=(𝑉,𝐸) and terminal vertices 𝐾⊂𝑉 with |𝐾|=𝑘, a (vertex) reachability sparsifier of 𝐺 is a digraph 𝐻=(𝑉𝐻,𝐸𝐻), 𝐾⊂𝑉𝐻 that preserves all reachability information among terminal pairs. Let |𝑉𝐻| denote the size of 𝐻. In this work we introduce the notion of reachability-preserving minors (RPMs), i.e., we require 𝐻 to be a minor of 𝐺. We show any directed graph 𝐺 admits an RPM 𝐻 of size 𝑂(𝑘3), and if 𝐺 is planar, then the size of 𝐻 improves to 𝑂(𝑘2log𝑘). We complement our upper bound by showing that there exists an infinite family of grids such that any RPM must have Ω(𝑘2) vertices. (2) Given a weighted undirected graph 𝐺=(𝑉,𝐸) and terminal vertices 𝐾 with |𝐾|=𝑘, an exact (vertex) cut sparsifier of 𝐺 is a graph 𝐻 with 𝐾⊂𝑉𝐻 that preserves the value of minimum cuts separating any bipartition of 𝐾. We show that planar graphs with all the 𝑘 terminals lying on the same face admit exact cut sparsifiers of size 𝑂(𝑘2) that are also planar. Our result extends to flow and distance sparsifiers. It improves the previous best-known bound of 𝑂(𝑘222𝑘) for cut and flow sparsifiers by an exponential factor and matches an Ω(𝑘2) lower-bound for this class of graphs."}],"main_file_link":[{"url":"https://arxiv.org/abs/1702.01136","open_access":"1"}],"date_published":"2020-01-01T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Preprint","type":"journal_article","date_updated":"2023-02-21T16:29:44Z","issue":"1","title":"Improved guarantees for vertex sparsification in planar graphs","day":"01","month":"01","intvolume":"        34","extern":"1","year":"2020","related_material":{"record":[{"relation":"earlier_version","id":"11831","status":"public"}]},"oa":1,"arxiv":1,"language":[{"iso":"eng"}],"publisher":"Society for Industrial & Applied Mathematics","article_processing_charge":"No","quality_controlled":"1","_id":"11894","publication":"SIAM Journal on Discrete Mathematics","citation":{"short":"G. Goranci, M.H. Henzinger, P. Peng, SIAM Journal on Discrete Mathematics 34 (2020) 130–162.","ista":"Goranci G, Henzinger MH, Peng P. 2020. Improved guarantees for vertex sparsification in planar graphs. SIAM Journal on Discrete Mathematics. 34(1), 130–162.","chicago":"Goranci, Gramoz, Monika H Henzinger, and Pan Peng. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial &#38; Applied Mathematics, 2020. <a href=\"https://doi.org/10.1137/17m1163153\">https://doi.org/10.1137/17m1163153</a>.","ama":"Goranci G, Henzinger MH, Peng P. Improved guarantees for vertex sparsification in planar graphs. <i>SIAM Journal on Discrete Mathematics</i>. 2020;34(1):130-162. doi:<a href=\"https://doi.org/10.1137/17m1163153\">10.1137/17m1163153</a>","ieee":"G. Goranci, M. H. Henzinger, and P. Peng, “Improved guarantees for vertex sparsification in planar graphs,” <i>SIAM Journal on Discrete Mathematics</i>, vol. 34, no. 1. Society for Industrial &#38; Applied Mathematics, pp. 130–162, 2020.","mla":"Goranci, Gramoz, et al. “Improved Guarantees for Vertex Sparsification in Planar Graphs.” <i>SIAM Journal on Discrete Mathematics</i>, vol. 34, no. 1, Society for Industrial &#38; Applied Mathematics, 2020, pp. 130–62, doi:<a href=\"https://doi.org/10.1137/17m1163153\">10.1137/17m1163153</a>.","apa":"Goranci, G., Henzinger, M. H., &#38; Peng, P. (2020). Improved guarantees for vertex sparsification in planar graphs. <i>SIAM Journal on Discrete Mathematics</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/17m1163153\">https://doi.org/10.1137/17m1163153</a>"}},{"date_updated":"2023-02-21T10:09:09Z","type":"journal_article","month":"11","intvolume":"        10","day":"02","title":"Modular, self-assembling metallaphotocatalyst for cross-couplings using the full visible-light spectrum","issue":"22","article_processing_charge":"No","publisher":"American Chemical Society","language":[{"iso":"eng"}],"oa":1,"extern":"1","year":"2020","citation":{"ama":"Reischauer S, Strauss V, Pieber B. Modular, self-assembling metallaphotocatalyst for cross-couplings using the full visible-light spectrum. <i>ACS Catalysis</i>. 2020;10(22):13269–13274. doi:<a href=\"https://doi.org/10.1021/acscatal.0c03950\">10.1021/acscatal.0c03950</a>","ieee":"S. Reischauer, V. Strauss, and B. Pieber, “Modular, self-assembling metallaphotocatalyst for cross-couplings using the full visible-light spectrum,” <i>ACS Catalysis</i>, vol. 10, no. 22. American Chemical Society, pp. 13269–13274, 2020.","apa":"Reischauer, S., Strauss, V., &#38; Pieber, B. (2020). Modular, self-assembling metallaphotocatalyst for cross-couplings using the full visible-light spectrum. <i>ACS Catalysis</i>. American Chemical Society. <a href=\"https://doi.org/10.1021/acscatal.0c03950\">https://doi.org/10.1021/acscatal.0c03950</a>","mla":"Reischauer, Susanne, et al. “Modular, Self-Assembling Metallaphotocatalyst for Cross-Couplings Using the Full Visible-Light Spectrum.” <i>ACS Catalysis</i>, vol. 10, no. 22, American Chemical Society, 2020, pp. 13269–13274, doi:<a href=\"https://doi.org/10.1021/acscatal.0c03950\">10.1021/acscatal.0c03950</a>.","ista":"Reischauer S, Strauss V, Pieber B. 2020. Modular, self-assembling metallaphotocatalyst for cross-couplings using the full visible-light spectrum. ACS Catalysis. 10(22), 13269–13274.","short":"S. Reischauer, V. Strauss, B. Pieber, ACS Catalysis 10 (2020) 13269–13274.","chicago":"Reischauer, Susanne, Volker Strauss, and Bartholomäus Pieber. “Modular, Self-Assembling Metallaphotocatalyst for Cross-Couplings Using the Full Visible-Light Spectrum.” <i>ACS Catalysis</i>. American Chemical Society, 2020. <a href=\"https://doi.org/10.1021/acscatal.0c03950\">https://doi.org/10.1021/acscatal.0c03950</a>."},"publication":"ACS Catalysis","_id":"11954","quality_controlled":"1","status":"public","author":[{"full_name":"Reischauer, Susanne","last_name":"Reischauer","first_name":"Susanne"},{"last_name":"Strauss","first_name":"Volker","full_name":"Strauss, Volker"},{"first_name":"Bartholomäus","last_name":"Pieber","id":"93e5e5b2-0da6-11ed-8a41-af589a024726","orcid":"0000-0001-8689-388X","full_name":"Pieber, Bartholomäus"}],"scopus_import":"1","publication_status":"published","volume":10,"doi":"10.1021/acscatal.0c03950","publication_identifier":{"eissn":["2155-5435"]},"date_created":"2022-08-24T10:40:46Z","article_type":"original","main_file_link":[{"url":"https://doi.org/10.26434/chemrxiv.12444908","open_access":"1"}],"page":"13269–13274","abstract":[{"lang":"eng","text":"The combination of nickel and photocatalysis has unlocked a variety of cross-couplings. These protocols rely on a few photocatalysts that can only convert a small portion of visible light (<500 nm) into chemical energy. The high-energy photons that excite the photocatalyst can result in unwanted side reactions. Dyes that absorb a much broader spectrum of light are not applicable because of their short-lived singlet excited states. Here, we describe a self-assembling catalyst system that overcomes this limitation. Immobilization of a nickel catalyst on dye-sensitized titanium dioxide results in a material that catalyzes carbon–heteroatom and carbon–carbon bond formations. The modular approach of dye-sensitized metallaphotocatalysts accesses the entire visible light spectrum and allows tackling selectivity issues resulting from low wavelengths strategically. The concept overcomes current limitations of metallaphotocatalysis by unlocking the potential of dyes that were previously unsuitable."}],"oa_version":"Preprint","date_published":"2020-11-02T00:00:00Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"}]