[{"title":"On lexicographic proof rules for probabilistic termination","intvolume":"        35","publication_status":"published","article_processing_charge":"Yes (via OA deal)","date_created":"2024-01-10T09:27:43Z","department":[{"_id":"KrCh"}],"author":[{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Ehsan","last_name":"Kafshdar Goharshady","full_name":"Kafshdar Goharshady, Ehsan"},{"id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","first_name":"Petr","last_name":"Novotný","full_name":"Novotný, Petr"},{"full_name":"Zárevúcky, Jiří","first_name":"Jiří","last_name":"Zárevúcky"},{"id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-4681-1699","full_name":"Zikelic, Dorde","first_name":"Dorde","last_name":"Zikelic"}],"issue":"2","_id":"14778","article_type":"original","publisher":"Association for Computing Machinery","file_date_updated":"2024-01-16T08:11:24Z","ec_funded":1,"quality_controlled":"1","abstract":[{"lang":"eng","text":"We consider the almost-sure (a.s.) termination problem for probabilistic programs, which are a stochastic extension of classical imperative programs. Lexicographic ranking functions provide a sound and practical approach for termination of non-probabilistic programs, and their extension to probabilistic programs is achieved via lexicographic ranking supermartingales (LexRSMs). However, LexRSMs introduced in the previous work have a limitation that impedes their automation: all of their components have to be non-negative in all reachable states. This might result in a LexRSM not existing even for simple terminating programs. Our contributions are twofold. First, we introduce a generalization of LexRSMs that allows for some components to be negative. This standard feature of non-probabilistic termination proofs was hitherto not known to be sound in the probabilistic setting, as the soundness proof requires a careful analysis of the underlying stochastic process. Second, we present polynomial-time algorithms using our generalized LexRSMs for proving a.s. termination in broad classes of linear-arithmetic programs."}],"arxiv":1,"doi":"10.1145/3585391","day":"23","external_id":{"arxiv":["2108.02188"]},"date_updated":"2025-07-14T09:10:10Z","year":"2023","citation":{"ieee":"K. Chatterjee, E. Kafshdar Goharshady, P. Novotný, J. Zárevúcky, and D. Zikelic, “On lexicographic proof rules for probabilistic termination,” <i>Formal Aspects of Computing</i>, vol. 35, no. 2. Association for Computing Machinery, 2023.","chicago":"Chatterjee, Krishnendu, Ehsan Kafshdar Goharshady, Petr Novotný, Jiří Zárevúcky, and Dorde Zikelic. “On Lexicographic Proof Rules for Probabilistic Termination.” <i>Formal Aspects of Computing</i>. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3585391\">https://doi.org/10.1145/3585391</a>.","ama":"Chatterjee K, Kafshdar Goharshady E, Novotný P, Zárevúcky J, Zikelic D. On lexicographic proof rules for probabilistic termination. <i>Formal Aspects of Computing</i>. 2023;35(2). doi:<a href=\"https://doi.org/10.1145/3585391\">10.1145/3585391</a>","apa":"Chatterjee, K., Kafshdar Goharshady, E., Novotný, P., Zárevúcky, J., &#38; Zikelic, D. (2023). On lexicographic proof rules for probabilistic termination. <i>Formal Aspects of Computing</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3585391\">https://doi.org/10.1145/3585391</a>","ista":"Chatterjee K, Kafshdar Goharshady E, Novotný P, Zárevúcky J, Zikelic D. 2023. On lexicographic proof rules for probabilistic termination. Formal Aspects of Computing. 35(2), 11.","short":"K. Chatterjee, E. Kafshdar Goharshady, P. Novotný, J. Zárevúcky, D. Zikelic, Formal Aspects of Computing 35 (2023).","mla":"Chatterjee, Krishnendu, et al. “On Lexicographic Proof Rules for Probabilistic Termination.” <i>Formal Aspects of Computing</i>, vol. 35, no. 2, 11, Association for Computing Machinery, 2023, doi:<a href=\"https://doi.org/10.1145/3585391\">10.1145/3585391</a>."},"ddc":["000"],"acknowledgement":"This research was partially supported by the ERC CoG (grant no. 863818; ForM-SMArt), the Czech Science Foundation (grant no. GA21-24711S), and the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie Grant Agreement No. 665385.","volume":35,"month":"06","article_number":"11","oa_version":"Published Version","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"},{"name":"International IST Doctoral Program","grant_number":"665385","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"publication":"Formal Aspects of Computing","has_accepted_license":"1","language":[{"iso":"eng"}],"keyword":["Theoretical Computer Science","Software"],"oa":1,"publication_identifier":{"eissn":["1433-299X"],"issn":["0934-5043"]},"date_published":"2023-06-23T00:00:00Z","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"10414"}]},"file":[{"content_type":"application/pdf","file_name":"2023_FormalAspectsComputing_Chatterjee.pdf","date_updated":"2024-01-16T08:11:24Z","file_size":502522,"checksum":"3bb133eeb27ec01649a9a36445d952d9","date_created":"2024-01-16T08:11:24Z","creator":"dernst","file_id":"14804","access_level":"open_access","success":1,"relation":"main_file"}]},{"day":"01","doi":"10.1007/s00446-022-00439-5","abstract":[{"lang":"eng","text":"A shared-memory counter is a widely-used and well-studied concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. In Jayanti et al (SIAM J Comput, 30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read-write registers, of a large class of shared objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity. In this work, we address this gap. We show that n-process, wait-free and linearizable counters can be implemented from read-write registers with O(log2n) amortized step complexity. This is the first counter algorithm from read-write registers that provides sub-linear amortized step complexity in executions of arbitrary length. Since a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations exists, our upper bound is within a logarithmic factor of the optimal. The worst-case step complexity of the construction remains linear, which is optimal. This is obtained thanks to a new max register construction with O(logn) amortized step complexity in executions of arbitrary length in which the value stored in the register does not grow too quickly. We then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel [1] in which we “plug” our max register implementation to show that it remains linearizable while achieving O(log2n) amortized step complexity."}],"year":"2023","citation":{"ista":"Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic amortized step complexity. Distributed Computing. 36, 29–43.","short":"M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023) 29–43.","mla":"Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023, pp. 29–43, doi:<a href=\"https://doi.org/10.1007/s00446-022-00439-5\">10.1007/s00446-022-00439-5</a>.","chicago":"Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed Computing</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00446-022-00439-5\">https://doi.org/10.1007/s00446-022-00439-5</a>.","ieee":"M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with polylogarithmic amortized step complexity,” <i>Distributed Computing</i>, vol. 36. Springer Nature, pp. 29–43, 2023.","apa":"Baig, M. A., Hendler, D., Milani, A., &#38; Travers, C. (2023). Long-lived counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00446-022-00439-5\">https://doi.org/10.1007/s00446-022-00439-5</a>","ama":"Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>. 2023;36:29-43. doi:<a href=\"https://doi.org/10.1007/s00446-022-00439-5\">10.1007/s00446-022-00439-5</a>"},"date_updated":"2023-08-16T08:39:36Z","external_id":{"isi":["000890138700001"]},"isi":1,"acknowledgement":"A preliminary version of this work appeared in DISC’19. Mirza Ahad Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes and FREDDA. Mirza Ahad Baig is supported by UMI Relax. Danny Hendler is supported by the Israel Science Foundation (Grants 380/18 and 1425/22).","volume":36,"date_created":"2023-01-12T12:10:08Z","article_processing_charge":"No","department":[{"_id":"KrPi"}],"publication_status":"published","intvolume":"        36","title":"Long-lived counters with polylogarithmic amortized step complexity","scopus_import":"1","_id":"12164","author":[{"full_name":"Baig, Mirza Ahad","last_name":"Baig","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"first_name":"Danny","last_name":"Hendler","full_name":"Hendler, Danny"},{"full_name":"Milani, Alessia","first_name":"Alessia","last_name":"Milani"},{"first_name":"Corentin","last_name":"Travers","full_name":"Travers, Corentin"}],"publisher":"Springer Nature","article_type":"original","quality_controlled":"1","page":"29-43","publication_identifier":{"eissn":["1432-0452"],"issn":["0178-2770"]},"oa":1,"type":"journal_article","date_published":"2023-03-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://drops.dagstuhl.de/opus/volltexte/2019/11310/"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","oa_version":"Preprint","month":"03","publication":"Distributed Computing","keyword":["Computational Theory and Mathematics","Computer Networks and Communications","Hardware and Architecture","Theoretical Computer Science"],"language":[{"iso":"eng"}]},{"file":[{"date_updated":"2023-02-02T11:01:10Z","file_name":"2023_DiscreteCompGeometry_Boissonnat.pdf","content_type":"application/pdf","date_created":"2023-02-02T11:01:10Z","checksum":"46352e0ee71e460848f88685ca852681","file_size":582850,"file_id":"12488","creator":"dernst","access_level":"open_access","success":1,"relation":"main_file"}],"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2023-01-01T00:00:00Z","type":"journal_article","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"oa":1,"language":[{"iso":"eng"}],"keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"publication":"Discrete & Computational Geometry","has_accepted_license":"1","oa_version":"Published Version","project":[{"grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"grant_number":"M03073","name":"Learning and triangulating manifolds via collapses","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2"}],"month":"01","volume":69,"acknowledgement":"This work has been funded by the European Research Council under the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). Arijit Ghosh is supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015). Part of this work was done when Arijit Ghosh was a Researcher at Max-Planck-Institute for Informatics, Germany, supported by the IndoGerman Max Planck Center for Computer Science (IMPECS). Mathijs Wintraecken also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411 and the Austrian Science Fund (FWF): M-3073. A part of the results described in this paper were presented at SoCG 2018 and in [3]. \r\nOpen access funding provided by the Austrian Science Fund (FWF).","ddc":["510"],"date_updated":"2023-08-01T12:47:32Z","year":"2023","citation":{"short":"J.-D. Boissonnat, R. Dyer, A. Ghosh, M. Wintraecken, Discrete &#38; Computational Geometry 69 (2023) 156–191.","mla":"Boissonnat, Jean-Daniel, et al. “Local Criteria for Triangulating General Manifolds.” <i>Discrete &#38; Computational Geometry</i>, vol. 69, Springer Nature, 2023, pp. 156–91, doi:<a href=\"https://doi.org/10.1007/s00454-022-00431-7\">10.1007/s00454-022-00431-7</a>.","ista":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. 2023. Local criteria for triangulating general manifolds. Discrete &#38; Computational Geometry. 69, 156–191.","ama":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. Local criteria for triangulating general manifolds. <i>Discrete &#38; Computational Geometry</i>. 2023;69:156-191. doi:<a href=\"https://doi.org/10.1007/s00454-022-00431-7\">10.1007/s00454-022-00431-7</a>","apa":"Boissonnat, J.-D., Dyer, R., Ghosh, A., &#38; Wintraecken, M. (2023). Local criteria for triangulating general manifolds. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00431-7\">https://doi.org/10.1007/s00454-022-00431-7</a>","chicago":"Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken. “Local Criteria for Triangulating General Manifolds.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-022-00431-7\">https://doi.org/10.1007/s00454-022-00431-7</a>.","ieee":"J.-D. Boissonnat, R. Dyer, A. Ghosh, and M. Wintraecken, “Local criteria for triangulating general manifolds,” <i>Discrete &#38; Computational Geometry</i>, vol. 69. Springer Nature, pp. 156–191, 2023."},"isi":1,"external_id":{"isi":["000862193600001"]},"doi":"10.1007/s00454-022-00431-7","day":"01","abstract":[{"text":"We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.","lang":"eng"}],"page":"156-191","quality_controlled":"1","ec_funded":1,"file_date_updated":"2023-02-02T11:01:10Z","publisher":"Springer Nature","article_type":"original","_id":"12287","scopus_import":"1","author":[{"full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat","first_name":"Jean-Daniel"},{"first_name":"Ramsay","last_name":"Dyer","full_name":"Dyer, Ramsay"},{"first_name":"Arijit","last_name":"Ghosh","full_name":"Ghosh, Arijit"},{"last_name":"Wintraecken","first_name":"Mathijs","full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87"}],"publication_status":"published","date_created":"2023-01-16T10:04:06Z","department":[{"_id":"HeEd"}],"article_processing_charge":"No","title":"Local criteria for triangulating general manifolds","intvolume":"        69"},{"publication_identifier":{"eissn":["2050-5094"]},"oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2022-01-18T00:00:00Z","type":"journal_article","file":[{"success":1,"access_level":"open_access","relation":"main_file","file_id":"10646","creator":"cchlebak","date_created":"2022-01-19T09:27:43Z","file_size":705323,"checksum":"87592a755adcef22ea590a99dc728dd3","date_updated":"2022-01-19T09:27:43Z","content_type":"application/pdf","file_name":"2022_ForumMathSigma_Henheik.pdf"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","oa_version":"Published Version","project":[{"grant_number":"101020331","name":"Random matrices beyond Wigner-Dyson-Mehta","call_identifier":"H2020","_id":"62796744-2b32-11ec-9570-940b20777f1d"}],"month":"01","article_number":"e4","publication":"Forum of Mathematics, Sigma","has_accepted_license":"1","language":[{"iso":"eng"}],"keyword":["computational mathematics","discrete mathematics and combinatorics","geometry and topology","mathematical physics","statistics and probability","algebra and number theory","theoretical computer science","analysis"],"doi":"10.1017/fms.2021.80","arxiv":1,"day":"18","abstract":[{"lang":"eng","text":"We prove a generalised super-adiabatic theorem for extended fermionic systems assuming a spectral gap only in the bulk. More precisely, we assume that the infinite system has a unique ground state and that the corresponding Gelfand–Naimark–Segal Hamiltonian has a spectral gap above its eigenvalue zero. Moreover, we show that a similar adiabatic theorem also holds in the bulk of finite systems up to errors that vanish faster than any inverse power of the system size, although the corresponding finite-volume Hamiltonians need not have a spectral gap.\r\n\r\n"}],"date_updated":"2023-08-02T13:53:11Z","citation":{"chicago":"Henheik, Sven Joscha, and Stefan Teufel. “Adiabatic Theorem in the Thermodynamic Limit: Systems with a Gap in the Bulk.” <i>Forum of Mathematics, Sigma</i>. Cambridge University Press, 2022. <a href=\"https://doi.org/10.1017/fms.2021.80\">https://doi.org/10.1017/fms.2021.80</a>.","ieee":"S. J. Henheik and S. Teufel, “Adiabatic theorem in the thermodynamic limit: Systems with a gap in the bulk,” <i>Forum of Mathematics, Sigma</i>, vol. 10. Cambridge University Press, 2022.","ama":"Henheik SJ, Teufel S. Adiabatic theorem in the thermodynamic limit: Systems with a gap in the bulk. <i>Forum of Mathematics, Sigma</i>. 2022;10. doi:<a href=\"https://doi.org/10.1017/fms.2021.80\">10.1017/fms.2021.80</a>","apa":"Henheik, S. J., &#38; Teufel, S. (2022). Adiabatic theorem in the thermodynamic limit: Systems with a gap in the bulk. <i>Forum of Mathematics, Sigma</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fms.2021.80\">https://doi.org/10.1017/fms.2021.80</a>","ista":"Henheik SJ, Teufel S. 2022. Adiabatic theorem in the thermodynamic limit: Systems with a gap in the bulk. Forum of Mathematics, Sigma. 10, e4.","mla":"Henheik, Sven Joscha, and Stefan Teufel. “Adiabatic Theorem in the Thermodynamic Limit: Systems with a Gap in the Bulk.” <i>Forum of Mathematics, Sigma</i>, vol. 10, e4, Cambridge University Press, 2022, doi:<a href=\"https://doi.org/10.1017/fms.2021.80\">10.1017/fms.2021.80</a>.","short":"S.J. Henheik, S. Teufel, Forum of Mathematics, Sigma 10 (2022)."},"year":"2022","isi":1,"external_id":{"arxiv":["2012.15239"],"isi":["000743615000001"]},"acknowledgement":"J.H. acknowledges partial financial support by the ERC Advanced Grant ‘RMTBeyond’ No. 101020331. Support for publication costs from the Deutsche Forschungsgemeinschaft and the Open Access Publishing Fund of the University of Tübingen is gratefully acknowledged.","volume":10,"ddc":["510"],"publication_status":"published","date_created":"2022-01-18T16:18:51Z","department":[{"_id":"GradSch"},{"_id":"LaEr"}],"article_processing_charge":"Yes","title":"Adiabatic theorem in the thermodynamic limit: Systems with a gap in the bulk","intvolume":"        10","_id":"10643","author":[{"last_name":"Henheik","first_name":"Sven Joscha","full_name":"Henheik, Sven Joscha","orcid":"0000-0003-1106-327X","id":"31d731d7-d235-11ea-ad11-b50331c8d7fb"},{"full_name":"Teufel, Stefan","first_name":"Stefan","last_name":"Teufel"}],"publisher":"Cambridge University Press","article_type":"original","ec_funded":1,"quality_controlled":"1","file_date_updated":"2022-01-19T09:27:43Z"},{"_id":"12129","scopus_import":"1","author":[{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"issue":"4","publication_status":"published","article_processing_charge":"No","date_created":"2023-01-12T12:02:28Z","department":[{"_id":"UlWa"}],"title":"Connectivity of triangulation flip graphs in the plane","intvolume":"        68","page":"1227-1284","quality_controlled":"1","file_date_updated":"2023-01-23T11:10:03Z","publisher":"Springer Nature","article_type":"original","date_updated":"2023-08-04T08:51:08Z","citation":{"chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00454-022-00436-2\">https://doi.org/10.1007/s00454-022-00436-2</a>.","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane,” <i>Discrete &#38; Computational Geometry</i>, vol. 68, no. 4. Springer Nature, pp. 1227–1284, 2022.","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane. <i>Discrete &#38; Computational Geometry</i>. 2022;68(4):1227-1284. doi:<a href=\"https://doi.org/10.1007/s00454-022-00436-2\">10.1007/s00454-022-00436-2</a>","apa":"Wagner, U., &#38; Welzl, E. (2022). Connectivity of triangulation flip graphs in the plane. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00436-2\">https://doi.org/10.1007/s00454-022-00436-2</a>","ista":"Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the plane. Discrete &#38; Computational Geometry. 68(4), 1227–1284.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” <i>Discrete &#38; Computational Geometry</i>, vol. 68, no. 4, Springer Nature, 2022, pp. 1227–84, doi:<a href=\"https://doi.org/10.1007/s00454-022-00436-2\">10.1007/s00454-022-00436-2</a>.","short":"U. Wagner, E. Welzl, Discrete &#38; Computational Geometry 68 (2022) 1227–1284."},"year":"2022","isi":1,"external_id":{"isi":["000883222200003"]},"doi":"10.1007/s00454-022-00436-2","day":"14","abstract":[{"lang":"eng","text":"Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P′ of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P∖P′ as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is ⌈n/2−2⌉-vertex connected, and the bistellar flip graph is (n−3)-vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where (n−3)-vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski’s Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2−2⌉ (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n−3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n−3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n−3. (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations."}],"volume":68,"acknowledgement":"This is a full and revised version of [38] (on partial triangulations) in Proceedings of the 36th Annual International Symposium on Computational Geometry (SoCG‘20) and of some of the results in [37] (on full triangulations) in Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA‘20).\r\nThis research started at the 11th Gremo’s Workshop on Open Problems (GWOP), Alp Sellamatt, Switzerland, June 24–28, 2013, motivated by a question posed by Filip Mori´c on full triangulations. Research was supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681, and by IST Austria and Berlin Free University during a sabbatical stay of the second author. We thank Michael Joswig, Jesús De Loera, and Francisco Santos for helpful discussions on the topics of this paper, and Daniel Bertschinger and Valentin Stoppiello for carefully reading earlier versions and for many helpful comments.\r\nOpen access funding provided by the Swiss Federal Institute of Technology Zürich","ddc":["510"],"publication":"Discrete & Computational Geometry","has_accepted_license":"1","oa_version":"Published Version","month":"11","language":[{"iso":"eng"}],"keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2022-11-14T00:00:00Z","type":"journal_article","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"oa":1,"file":[{"success":1,"access_level":"open_access","relation":"main_file","file_id":"12345","creator":"dernst","date_created":"2023-01-23T11:10:03Z","file_size":1747581,"checksum":"307e879d09e52eddf5b225d0aaa9213a","date_updated":"2023-01-23T11:10:03Z","file_name":"2022_DiscreteCompGeometry_Wagner.pdf","content_type":"application/pdf"}],"related_material":{"record":[{"status":"public","id":"7807","relation":"earlier_version"},{"status":"public","relation":"earlier_version","id":"7990"}]},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public"},{"file":[{"creator":"dernst","file_id":"12356","access_level":"open_access","relation":"main_file","success":1,"file_name":"2022_ForumMath_Cipolloni.pdf","content_type":"application/pdf","date_updated":"2023-01-24T10:02:40Z","checksum":"94a049aeb1eea5497aa097712a73c400","file_size":817089,"date_created":"2023-01-24T10:02:40Z"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"journal_article","date_published":"2022-10-27T00:00:00Z","publication_identifier":{"issn":["2050-5094"]},"oa":1,"keyword":["Computational Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Mathematical Physics","Statistics and Probability","Algebra and Number Theory","Theoretical Computer Science","Analysis"],"language":[{"iso":"eng"}],"has_accepted_license":"1","publication":"Forum of Mathematics, Sigma","project":[{"name":"Random matrices beyond Wigner-Dyson-Mehta","grant_number":"101020331","call_identifier":"H2020","_id":"62796744-2b32-11ec-9570-940b20777f1d"}],"oa_version":"Published Version","article_number":"e96","month":"10","volume":10,"acknowledgement":"L.E. acknowledges support by ERC Advanced Grant ‘RMTBeyond’ No. 101020331. D.S. acknowledges the support of Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation.","ddc":["510"],"year":"2022","citation":{"short":"G. Cipolloni, L. Erdös, D.J. Schröder, Forum of Mathematics, Sigma 10 (2022).","mla":"Cipolloni, Giorgio, et al. “Rank-Uniform Local Law for Wigner Matrices.” <i>Forum of Mathematics, Sigma</i>, vol. 10, e96, Cambridge University Press, 2022, doi:<a href=\"https://doi.org/10.1017/fms.2022.86\">10.1017/fms.2022.86</a>.","ista":"Cipolloni G, Erdös L, Schröder DJ. 2022. Rank-uniform local law for Wigner matrices. Forum of Mathematics, Sigma. 10, e96.","ama":"Cipolloni G, Erdös L, Schröder DJ. Rank-uniform local law for Wigner matrices. <i>Forum of Mathematics, Sigma</i>. 2022;10. doi:<a href=\"https://doi.org/10.1017/fms.2022.86\">10.1017/fms.2022.86</a>","apa":"Cipolloni, G., Erdös, L., &#38; Schröder, D. J. (2022). Rank-uniform local law for Wigner matrices. <i>Forum of Mathematics, Sigma</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fms.2022.86\">https://doi.org/10.1017/fms.2022.86</a>","chicago":"Cipolloni, Giorgio, László Erdös, and Dominik J Schröder. “Rank-Uniform Local Law for Wigner Matrices.” <i>Forum of Mathematics, Sigma</i>. Cambridge University Press, 2022. <a href=\"https://doi.org/10.1017/fms.2022.86\">https://doi.org/10.1017/fms.2022.86</a>.","ieee":"G. Cipolloni, L. Erdös, and D. J. Schröder, “Rank-uniform local law for Wigner matrices,” <i>Forum of Mathematics, Sigma</i>, vol. 10. Cambridge University Press, 2022."},"date_updated":"2023-08-04T09:00:35Z","external_id":{"isi":["000873719200001"]},"isi":1,"day":"27","doi":"10.1017/fms.2022.86","abstract":[{"lang":"eng","text":"We prove a general local law for Wigner matrices that optimally handles observables of arbitrary rank and thus unifies the well-known averaged and isotropic local laws. As an application, we prove a central limit theorem in quantum unique ergodicity (QUE): that is, we show that the quadratic forms of a general deterministic matrix A on the bulk eigenvectors of a Wigner matrix have approximately Gaussian fluctuation. For the bulk spectrum, we thus generalise our previous result [17] as valid for test matrices A of large rank as well as the result of Benigni and Lopatto [7] as valid for specific small-rank observables."}],"ec_funded":1,"quality_controlled":"1","file_date_updated":"2023-01-24T10:02:40Z","publisher":"Cambridge University Press","article_type":"original","scopus_import":"1","_id":"12148","author":[{"full_name":"Cipolloni, Giorgio","orcid":"0000-0002-4901-7992","last_name":"Cipolloni","first_name":"Giorgio","id":"42198EFA-F248-11E8-B48F-1D18A9856A87"},{"id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-5366-9603","full_name":"Erdös, László","first_name":"László","last_name":"Erdös"},{"id":"408ED176-F248-11E8-B48F-1D18A9856A87","first_name":"Dominik J","last_name":"Schröder","orcid":"0000-0002-2904-1856","full_name":"Schröder, Dominik J"}],"department":[{"_id":"LaEr"}],"date_created":"2023-01-12T12:07:30Z","article_processing_charge":"No","publication_status":"published","intvolume":"        10","title":"Rank-uniform local law for Wigner matrices"},{"keyword":["Computational Theory and Mathematics","Geometry and Topology","Theoretical Computer Science","Applied Mathematics","Discrete Mathematics and Combinatorics"],"language":[{"iso":"eng"}],"has_accepted_license":"1","publication":"The Electronic Journal of Combinatorics","oa_version":"Published Version","article_number":"P4.13","month":"10","file":[{"date_updated":"2023-01-30T11:45:13Z","content_type":"application/pdf","file_name":"2022_ElecJournCombinatorics_Cooley_Kang_Zalla.pdf","date_created":"2023-01-30T11:45:13Z","checksum":"00122b2459f09b5ae43073bfba565e94","file_size":626953,"file_id":"12462","creator":"dernst","success":1,"access_level":"open_access","relation":"main_file"}],"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","image":"/image/cc_by_nd.png","short":"CC BY-ND (4.0)"},"type":"journal_article","date_published":"2022-10-21T00:00:00Z","publication_identifier":{"eissn":["1077-8926"]},"oa":1,"quality_controlled":"1","file_date_updated":"2023-01-30T11:45:13Z","publisher":"The Electronic Journal of Combinatorics","article_type":"original","scopus_import":"1","license":"https://creativecommons.org/licenses/by-nd/4.0/","_id":"12286","issue":"4","author":[{"id":"43f4ddd0-a46b-11ec-8df6-ef3703bd721d","full_name":"Cooley, Oliver","last_name":"Cooley","first_name":"Oliver"},{"full_name":"Kang, Mihyun","first_name":"Mihyun","last_name":"Kang"},{"last_name":"Zalla","first_name":"Julian","full_name":"Zalla, Julian"}],"department":[{"_id":"MaKw"}],"date_created":"2023-01-16T10:03:57Z","article_processing_charge":"No","publication_status":"published","intvolume":"        29","title":"Loose cores and cycles in random hypergraphs","volume":29,"acknowledgement":"Supported by Austrian Science Fund (FWF): I3747, W1230.","ddc":["510"],"citation":{"ama":"Cooley O, Kang M, Zalla J. Loose cores and cycles in random hypergraphs. <i>The Electronic Journal of Combinatorics</i>. 2022;29(4). doi:<a href=\"https://doi.org/10.37236/10794\">10.37236/10794</a>","apa":"Cooley, O., Kang, M., &#38; Zalla, J. (2022). Loose cores and cycles in random hypergraphs. <i>The Electronic Journal of Combinatorics</i>. The Electronic Journal of Combinatorics. <a href=\"https://doi.org/10.37236/10794\">https://doi.org/10.37236/10794</a>","chicago":"Cooley, Oliver, Mihyun Kang, and Julian Zalla. “Loose Cores and Cycles in Random Hypergraphs.” <i>The Electronic Journal of Combinatorics</i>. The Electronic Journal of Combinatorics, 2022. <a href=\"https://doi.org/10.37236/10794\">https://doi.org/10.37236/10794</a>.","ieee":"O. Cooley, M. Kang, and J. Zalla, “Loose cores and cycles in random hypergraphs,” <i>The Electronic Journal of Combinatorics</i>, vol. 29, no. 4. The Electronic Journal of Combinatorics, 2022.","mla":"Cooley, Oliver, et al. “Loose Cores and Cycles in Random Hypergraphs.” <i>The Electronic Journal of Combinatorics</i>, vol. 29, no. 4, P4.13, The Electronic Journal of Combinatorics, 2022, doi:<a href=\"https://doi.org/10.37236/10794\">10.37236/10794</a>.","short":"O. Cooley, M. Kang, J. Zalla, The Electronic Journal of Combinatorics 29 (2022).","ista":"Cooley O, Kang M, Zalla J. 2022. Loose cores and cycles in random hypergraphs. The Electronic Journal of Combinatorics. 29(4), P4.13."},"year":"2022","date_updated":"2023-08-04T10:29:18Z","external_id":{"isi":["000876763300001"]},"isi":1,"day":"21","doi":"10.37236/10794","abstract":[{"text":"Inspired by the study of loose cycles in hypergraphs, we define the loose core in hypergraphs as a structurewhich mirrors the close relationship between cycles and $2$-cores in graphs. We prove that in the $r$-uniform binomial random hypergraph $H^r(n,p)$, the order of the loose core undergoes a phase transition at a certain critical threshold and determine this order, as well as the number of edges, asymptotically in the subcritical and supercritical regimes.&#x0D;\r\nOur main tool is an algorithm called CoreConstruct, which enables us to analyse a peeling process for the loose core. By analysing this algorithm we determine the asymptotic degree distribution of vertices in the loose core and in particular how many vertices and edges the loose core contains. As a corollary we obtain an improved upper bound on the length of the longest loose cycle in $H^r(n,p)$.","lang":"eng"}]},{"month":"10","oa_version":"Preprint","publication":"Discrete & Computational Geometry","language":[{"iso":"eng"}],"keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"date_published":"2021-10-01T00:00:00Z","type":"journal_article","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"relation":"earlier_version","id":"8182","status":"public"}]},"status":"public","title":"Vanishing of all equivariant obstructions and the mapping degree","intvolume":"        66","publication_status":"published","date_created":"2022-06-17T08:45:15Z","article_processing_charge":"No","author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","last_name":"Avvakumov","full_name":"Avvakumov, Sergey"},{"full_name":"Kudrya, Sergey","last_name":"Kudrya","first_name":"Sergey","id":"ecf01965-d252-11ea-95a5-8ada5f6c6a67"}],"issue":"3","_id":"11446","scopus_import":"1","article_type":"original","publisher":"Springer Nature","page":"1202-1216","quality_controlled":"1","abstract":[{"lang":"eng","text":"Suppose that n is not a prime power and not twice a prime power. We prove that for any Hausdorff compactum X with a free action of the symmetric group Sn, there exists an Sn-equivariant map X→Rn whose image avoids the diagonal {(x,x,…,x)∈Rn∣x∈R}. Previously, the special cases of this statement for certain X were usually proved using the equivartiant obstruction theory. Such calculations are difficult and may become infeasible past the first (primary) obstruction. We take a different approach which allows us to prove the vanishing of all obstructions simultaneously. The essential step in the proof is classifying the possible degrees of Sn-equivariant maps from the boundary ∂Δn−1 of (n−1)-simplex to itself. Existence of equivariant maps between spaces is important for many questions arising from discrete mathematics and geometry, such as Kneser’s conjecture, the Square Peg conjecture, the Splitting Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate the utility of our result applying it to one such question, a specific instance of envy-free division problem."}],"arxiv":1,"doi":"10.1007/s00454-021-00299-z","day":"01","external_id":{"arxiv":["1910.12628"]},"date_updated":"2023-02-23T13:26:41Z","year":"2021","citation":{"ama":"Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping degree. <i>Discrete &#38; Computational Geometry</i>. 2021;66(3):1202-1216. doi:<a href=\"https://doi.org/10.1007/s00454-021-00299-z\">10.1007/s00454-021-00299-z</a>","apa":"Avvakumov, S., &#38; Kudrya, S. (2021). Vanishing of all equivariant obstructions and the mapping degree. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-021-00299-z\">https://doi.org/10.1007/s00454-021-00299-z</a>","ieee":"S. Avvakumov and S. Kudrya, “Vanishing of all equivariant obstructions and the mapping degree,” <i>Discrete &#38; Computational Geometry</i>, vol. 66, no. 3. Springer Nature, pp. 1202–1216, 2021.","chicago":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s00454-021-00299-z\">https://doi.org/10.1007/s00454-021-00299-z</a>.","mla":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” <i>Discrete &#38; Computational Geometry</i>, vol. 66, no. 3, Springer Nature, 2021, pp. 1202–16, doi:<a href=\"https://doi.org/10.1007/s00454-021-00299-z\">10.1007/s00454-021-00299-z</a>.","short":"S. Avvakumov, S. Kudrya, Discrete &#38; Computational Geometry 66 (2021) 1202–1216.","ista":"Avvakumov S, Kudrya S. 2021. Vanishing of all equivariant obstructions and the mapping degree. Discrete &#38; Computational Geometry. 66(3), 1202–1216."},"extern":"1","acknowledgement":"S. Avvakumov has received funding from the European Research Council under the European Union’s Seventh Framework Programme ERC Grant agreement ERC StG 716424–CASe. S. Kudrya was supported by the Austrian Academic Exchange Service (OeAD), ICM-2019-13577.","volume":66},{"external_id":{"isi":["000597770300001"]},"isi":1,"citation":{"ieee":"J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Triangulating submanifolds: An elementary and quantified version of Whitney’s method,” <i>Discrete &#38; Computational Geometry</i>, vol. 66, no. 1. Springer Nature, pp. 386–434, 2021.","chicago":"Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Triangulating Submanifolds: An Elementary and Quantified Version of Whitney’s Method.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s00454-020-00250-8\">https://doi.org/10.1007/s00454-020-00250-8</a>.","ama":"Boissonnat J-D, Kachanovich S, Wintraecken M. Triangulating submanifolds: An elementary and quantified version of Whitney’s method. <i>Discrete &#38; Computational Geometry</i>. 2021;66(1):386-434. doi:<a href=\"https://doi.org/10.1007/s00454-020-00250-8\">10.1007/s00454-020-00250-8</a>","apa":"Boissonnat, J.-D., Kachanovich, S., &#38; Wintraecken, M. (2021). Triangulating submanifolds: An elementary and quantified version of Whitney’s method. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-020-00250-8\">https://doi.org/10.1007/s00454-020-00250-8</a>","ista":"Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Triangulating submanifolds: An elementary and quantified version of Whitney’s method. Discrete &#38; Computational Geometry. 66(1), 386–434.","mla":"Boissonnat, Jean-Daniel, et al. “Triangulating Submanifolds: An Elementary and Quantified Version of Whitney’s Method.” <i>Discrete &#38; Computational Geometry</i>, vol. 66, no. 1, Springer Nature, 2021, pp. 386–434, doi:<a href=\"https://doi.org/10.1007/s00454-020-00250-8\">10.1007/s00454-020-00250-8</a>.","short":"J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, Discrete &#38; Computational Geometry 66 (2021) 386–434."},"year":"2021","date_updated":"2023-09-05T15:02:40Z","abstract":[{"lang":"eng","text":"We quantise Whitney’s construction to prove the existence of a triangulation for any C^2 manifold, so that we get an algorithm with explicit bounds. We also give a new elementary proof, which is completely geometric."}],"day":"01","doi":"10.1007/s00454-020-00250-8","ddc":["516"],"volume":66,"acknowledgement":"This work has been funded by the European Research Council under the European Union’s ERC Grant Agreement Number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). The third author also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411. Open access funding provided by the Institute of Science and Technology (IST Austria).","issue":"1","author":[{"last_name":"Boissonnat","first_name":"Jean-Daniel","full_name":"Boissonnat, Jean-Daniel"},{"full_name":"Kachanovich, Siargey","last_name":"Kachanovich","first_name":"Siargey"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs","first_name":"Mathijs","last_name":"Wintraecken"}],"_id":"8940","intvolume":"        66","title":"Triangulating submanifolds: An elementary and quantified version of Whitney’s method","article_processing_charge":"Yes (via OA deal)","department":[{"_id":"HeEd"}],"date_created":"2020-12-12T11:07:02Z","publication_status":"published","file_date_updated":"2021-08-06T09:52:29Z","ec_funded":1,"quality_controlled":"1","page":"386-434","article_type":"original","publisher":"Springer Nature","type":"journal_article","date_published":"2021-07-01T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","status":"public","file":[{"checksum":"c848986091e56699dc12de85adb1e39c","file_size":983307,"date_created":"2021-08-06T09:52:29Z","content_type":"application/pdf","file_name":"2021_DescreteCompGeopmetry_Boissonnat.pdf","date_updated":"2021-08-06T09:52:29Z","success":1,"access_level":"open_access","relation":"main_file","creator":"kschuh","file_id":"9795"}],"has_accepted_license":"1","publication":"Discrete & Computational Geometry","month":"07","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"oa_version":"Published Version","keyword":["Theoretical Computer Science","Computational Theory and Mathematics","Geometry and Topology","Discrete Mathematics and Combinatorics"],"language":[{"iso":"eng"}]},{"title":"Practical minimum cut algorithms","intvolume":"        23","publication_status":"published","date_created":"2022-07-27T08:28:26Z","article_processing_charge":"No","author":[{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"full_name":"Noe, Alexander","first_name":"Alexander","last_name":"Noe"},{"full_name":"Schulz, Christian","last_name":"Schulz","first_name":"Christian"},{"first_name":"Darren","last_name":"Strash","full_name":"Strash, Darren"}],"_id":"11657","scopus_import":"1","article_type":"original","publisher":"Association for Computing Machinery","page":"1-22","quality_controlled":"1","abstract":[{"lang":"eng","text":"The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weight sum of the cut edges. Here, we introduce a linear-time algorithm to compute near-minimum cuts. Our algorithm is based on cluster contraction using label propagation and Padberg and Rinaldi’s contraction heuristics [SIAM Review, 1991]. We give both sequential and shared-memory parallel implementations of our algorithm. Extensive experiments on both real-world and generated instances show that our algorithm finds the optimal cut on nearly all instances significantly faster than other state-of-the-art exact algorithms, and our error rate is lower than that of other heuristic algorithms. In addition, our parallel algorithm runs a factor 7.5× faster on average when using 32 threads. To further speed up computations, we also give a version of our algorithm that performs random edge contractions as preprocessing. This version achieves a lower running time and better parallel scalability at the expense of a higher error rate."}],"doi":"10.1145/3274662","arxiv":1,"day":"01","external_id":{"arxiv":["1708.06127"]},"date_updated":"2022-09-09T11:32:52Z","year":"2018","citation":{"ista":"Henzinger MH, Noe A, Schulz C, Strash D. 2018. Practical minimum cut algorithms. ACM Journal of Experimental Algorithmics. 23, 1–22.","mla":"Henzinger, Monika H., et al. “Practical Minimum Cut Algorithms.” <i>ACM Journal of Experimental Algorithmics</i>, vol. 23, Association for Computing Machinery, 2018, pp. 1–22, doi:<a href=\"https://doi.org/10.1145/3274662\">10.1145/3274662</a>.","short":"M.H. Henzinger, A. Noe, C. Schulz, D. Strash, ACM Journal of Experimental Algorithmics 23 (2018) 1–22.","chicago":"Henzinger, Monika H, Alexander Noe, Christian Schulz, and Darren Strash. “Practical Minimum Cut Algorithms.” <i>ACM Journal of Experimental Algorithmics</i>. Association for Computing Machinery, 2018. <a href=\"https://doi.org/10.1145/3274662\">https://doi.org/10.1145/3274662</a>.","ieee":"M. H. Henzinger, A. Noe, C. Schulz, and D. Strash, “Practical minimum cut algorithms,” <i>ACM Journal of Experimental Algorithmics</i>, vol. 23. Association for Computing Machinery, pp. 1–22, 2018.","ama":"Henzinger MH, Noe A, Schulz C, Strash D. Practical minimum cut algorithms. <i>ACM Journal of Experimental Algorithmics</i>. 2018;23:1-22. doi:<a href=\"https://doi.org/10.1145/3274662\">10.1145/3274662</a>","apa":"Henzinger, M. H., Noe, A., Schulz, C., &#38; Strash, D. (2018). Practical minimum cut algorithms. <i>ACM Journal of Experimental Algorithmics</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3274662\">https://doi.org/10.1145/3274662</a>"},"extern":"1","volume":23,"month":"10","oa_version":"Preprint","publication":"ACM Journal of Experimental Algorithmics","language":[{"iso":"eng"}],"keyword":["Theoretical Computer Science"],"oa":1,"publication_identifier":{"eissn":["1084-6654"],"issn":["1084-6654"]},"date_published":"2018-10-01T00:00:00Z","type":"journal_article","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"url":"https://arxiv.org/abs/1708.06127","open_access":"1"}]},{"author":[{"id":"FE553552-CDE8-11E9-B324-C0EBE5697425","last_name":"Kaloshin","first_name":"Vadim","full_name":"Kaloshin, Vadim","orcid":"0000-0002-6051-2628"},{"last_name":"Levi","first_name":"Mark","full_name":"Levi, Mark"}],"issue":"4","_id":"8509","publication":"SIAM Review","month":"11","title":"Geometry of Arnold diffusion","intvolume":"        50","publication_status":"published","oa_version":"None","article_processing_charge":"No","date_created":"2020-09-18T10:48:12Z","language":[{"iso":"eng"}],"keyword":["Theoretical Computer Science","Applied Mathematics","Computational Mathematics"],"page":"702-720","quality_controlled":"1","article_type":"original","publisher":"Society for Industrial & Applied Mathematics","date_published":"2008-11-05T00:00:00Z","type":"journal_article","date_updated":"2021-01-12T08:19:46Z","citation":{"ama":"Kaloshin V, Levi M. Geometry of Arnold diffusion. <i>SIAM Review</i>. 2008;50(4):702-720. doi:<a href=\"https://doi.org/10.1137/070703235\">10.1137/070703235</a>","apa":"Kaloshin, V., &#38; Levi, M. (2008). Geometry of Arnold diffusion. <i>SIAM Review</i>. Society for Industrial &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/070703235\">https://doi.org/10.1137/070703235</a>","ieee":"V. Kaloshin and M. Levi, “Geometry of Arnold diffusion,” <i>SIAM Review</i>, vol. 50, no. 4. Society for Industrial &#38; Applied Mathematics, pp. 702–720, 2008.","chicago":"Kaloshin, Vadim, and Mark Levi. “Geometry of Arnold Diffusion.” <i>SIAM Review</i>. Society for Industrial &#38; Applied Mathematics, 2008. <a href=\"https://doi.org/10.1137/070703235\">https://doi.org/10.1137/070703235</a>.","mla":"Kaloshin, Vadim, and Mark Levi. “Geometry of Arnold Diffusion.” <i>SIAM Review</i>, vol. 50, no. 4, Society for Industrial &#38; Applied Mathematics, 2008, pp. 702–20, doi:<a href=\"https://doi.org/10.1137/070703235\">10.1137/070703235</a>.","short":"V. Kaloshin, M. Levi, SIAM Review 50 (2008) 702–720.","ista":"Kaloshin V, Levi M. 2008. Geometry of Arnold diffusion. SIAM Review. 50(4), 702–720."},"year":"2008","abstract":[{"lang":"eng","text":"The goal of this paper is to present to nonspecialists what is perhaps the simplest possible geometrical picture explaining the mechanism of Arnold diffusion. We choose to speak of a specific model—that of geometric rays in a periodic optical medium. This model is equivalent to that of a particle in a periodic potential in ${\\mathbb R}^{n}$ with energy prescribed and to the geodesic flow in a Riemannian metric on ${\\mathbb R}^{n} $."}],"doi":"10.1137/070703235","day":"05","publication_identifier":{"issn":["0036-1445","1095-7200"]},"extern":"1","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","volume":50}]