[{"type":"journal_article","acknowledgement":"We thank Gesualdo Delfino, Michele Fabrizio, Piero Ferrarese, Robert Konik, Christoph Lampert and Mikhail Lemeshko for stimulating discussions at various stages of this work. WR has received funding from the EU Horizon 2020 program under the Marie Skłodowska-Curie Grant Agreement No. 665385 and is a recipient of a DOC Fellowship of the Austrian Academy of Sciences. GB acknowledges support from the Austrian Science Fund (FWF), under project No. M2641-N27. ND acknowledges support by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) via Collaborative Research Center SFB 1225 (ISOQUANT)--project-id 273811115--and under Germany's Excellence Strategy 'EXC-2181/1-390900948' (the Heidelberg STRUCTURES Excellence Cluster).","ec_funded":1,"status":"public","publication_identifier":{"issn":["1367-2630"]},"volume":22,"has_accepted_license":"1","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"10759"}]},"doi":"10.1088/1367-2630/abae44","issue":"9","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file":[{"date_created":"2020-10-12T12:18:47Z","relation":"main_file","file_size":2725143,"checksum":"c9238fff422e7a957c3a0d559f756b3a","content_type":"application/pdf","file_name":"2020_NewJournalPhysics_Rzdkowski.pdf","date_updated":"2020-10-12T12:18:47Z","file_id":"8650","access_level":"open_access","success":1,"creator":"dernst"}],"language":[{"iso":"eng"}],"oa":1,"year":"2020","isi":1,"month":"09","oa_version":"Published Version","article_processing_charge":"No","_id":"8644","day":"01","department":[{"_id":"MiLe"}],"intvolume":"        22","article_type":"original","scopus_import":"1","publisher":"IOP Publishing","ddc":["530"],"citation":{"ama":"Rzadkowski W, Defenu N, Chiacchiera S, Trombettoni A, Bighin G. Detecting composite orders in layered models via machine learning. <i>New Journal of Physics</i>. 2020;22(9). doi:<a href=\"https://doi.org/10.1088/1367-2630/abae44\">10.1088/1367-2630/abae44</a>","apa":"Rzadkowski, W., Defenu, N., Chiacchiera, S., Trombettoni, A., &#38; Bighin, G. (2020). Detecting composite orders in layered models via machine learning. <i>New Journal of Physics</i>. IOP Publishing. <a href=\"https://doi.org/10.1088/1367-2630/abae44\">https://doi.org/10.1088/1367-2630/abae44</a>","chicago":"Rzadkowski, Wojciech, N Defenu, S Chiacchiera, A Trombettoni, and Giacomo Bighin. “Detecting Composite Orders in Layered Models via Machine Learning.” <i>New Journal of Physics</i>. IOP Publishing, 2020. <a href=\"https://doi.org/10.1088/1367-2630/abae44\">https://doi.org/10.1088/1367-2630/abae44</a>.","ista":"Rzadkowski W, Defenu N, Chiacchiera S, Trombettoni A, Bighin G. 2020. Detecting composite orders in layered models via machine learning. New Journal of Physics. 22(9), 093026.","mla":"Rzadkowski, Wojciech, et al. “Detecting Composite Orders in Layered Models via Machine Learning.” <i>New Journal of Physics</i>, vol. 22, no. 9, 093026, IOP Publishing, 2020, doi:<a href=\"https://doi.org/10.1088/1367-2630/abae44\">10.1088/1367-2630/abae44</a>.","short":"W. Rzadkowski, N. Defenu, S. Chiacchiera, A. Trombettoni, G. Bighin, New Journal of Physics 22 (2020).","ieee":"W. Rzadkowski, N. Defenu, S. Chiacchiera, A. Trombettoni, and G. Bighin, “Detecting composite orders in layered models via machine learning,” <i>New Journal of Physics</i>, vol. 22, no. 9. IOP Publishing, 2020."},"quality_controlled":"1","corr_author":"1","article_number":"093026","date_published":"2020-09-01T00:00:00Z","file_date_updated":"2020-10-12T12:18:47Z","publication":"New Journal of Physics","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Determining the phase diagram of systems consisting of smaller subsystems 'connected' via a tunable coupling is a challenging task relevant for a variety of physical settings. A general question is whether new phases, not present in the uncoupled limit, may arise. We use machine learning and a suitable quasidistance between different points of the phase diagram to study layered spin models, in which the spin variables constituting each of the uncoupled systems (to which we refer as layers) are coupled to each other via an interlayer coupling. In such systems, in general, composite order parameters involving spins of different layers may emerge as a consequence of the interlayer coupling. We focus on the layered Ising and Ashkin–Teller models as a paradigmatic case study, determining their phase diagram via the application of a machine learning algorithm to the Monte Carlo data. Remarkably our technique is able to correctly characterize all the system phases also in the case of hidden order parameters, i.e. order parameters whose expression in terms of the microscopic configurations would require additional preprocessing of the data fed to the algorithm. We correctly retrieve the three known phases of the Ashkin–Teller model with ferromagnetic couplings, including the phase described by a composite order parameter. For the bilayer and trilayer Ising models the phases we find are only the ferromagnetic and the paramagnetic ones. Within the approach we introduce, owing to the construction of convolutional neural networks, naturally suitable for layered image-like data with arbitrary number of layers, no preprocessing of the Monte Carlo data is needed, also with regard to its spatial structure. The physical meaning of our results is discussed and compared with analytical data, where available. Yet, the method can be used without any a priori knowledge of the phases one seeks to find and can be applied to other models and structures."}],"date_updated":"2026-04-07T14:20:12Z","author":[{"full_name":"Rzadkowski, Wojciech","id":"48C55298-F248-11E8-B48F-1D18A9856A87","last_name":"Rzadkowski","first_name":"Wojciech","orcid":"0000-0002-1106-4419"},{"last_name":"Defenu","first_name":"N","full_name":"Defenu, N"},{"first_name":"S","last_name":"Chiacchiera","full_name":"Chiacchiera, S"},{"full_name":"Trombettoni, A","last_name":"Trombettoni","first_name":"A"},{"orcid":"0000-0001-8823-9777","last_name":"Bighin","first_name":"Giacomo","id":"4CA96FD4-F248-11E8-B48F-1D18A9856A87","full_name":"Bighin, Giacomo"}],"title":"Detecting composite orders in layered models via machine learning","external_id":{"isi":["000573298000001"]},"date_created":"2020-10-11T22:01:14Z","project":[{"grant_number":"665385","name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"},{"_id":"05A235A0-7A3F-11EA-A408-12923DDC885E","name":"Analytic and machine learning approaches to composite quantum impurities","grant_number":"25681"},{"_id":"26986C82-B435-11E9-9278-68D0E5697425","name":"A path-integral approach to composite impurities","grant_number":"M02641","call_identifier":"FWF"}]},{"arxiv":1,"isi":1,"month":"05","related_material":{"record":[{"relation":"dissertation_contains","id":"10759","status":"public"}]},"doi":"10.1063/5.0005194","issue":"20","oa":1,"year":"2020","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1089-7690"]},"ec_funded":1,"status":"public","volume":152,"type":"journal_article","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1063/5.0005194"}],"date_updated":"2026-04-07T14:20:12Z","abstract":[{"text":"When short-range attractions are combined with long-range repulsions in colloidal particle systems, complex microphases can emerge. Here, we study a system of isotropic particles, which can form lamellar structures or a disordered fluid phase when temperature is varied. We show that, at equilibrium, the lamellar structure crystallizes, while out of equilibrium, the system forms a variety of structures at different shear rates and temperatures above melting. The shear-induced ordering is analyzed by means of principal component analysis and artificial neural networks, which are applied to data of reduced dimensionality. Our results reveal the possibility of inducing ordering by shear, potentially providing a feasible route to the fabrication of ordered lamellar structures from isotropic particles.","lang":"eng"}],"project":[{"grant_number":"665385","name":"International IST Doctoral Program","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"}],"author":[{"last_name":"Pȩkalski","first_name":"J.","full_name":"Pȩkalski, J."},{"full_name":"Rzadkowski, Wojciech","id":"48C55298-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1106-4419","last_name":"Rzadkowski","first_name":"Wojciech"},{"first_name":"A. Z.","last_name":"Panagiotopoulos","full_name":"Panagiotopoulos, A. Z."}],"title":"Shear-induced ordering in systems with competing interactions: A machine learning study","external_id":{"pmid":["32486692"],"arxiv":["2002.07294"],"isi":["000537900300001"]},"date_created":"2020-06-14T22:00:49Z","date_published":"2020-05-29T00:00:00Z","article_number":"204905","publication_status":"published","pmid":1,"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication":"The Journal of chemical physics","publisher":"AIP Publishing","citation":{"chicago":"Pȩkalski, J., Wojciech Rzadkowski, and A. Z. Panagiotopoulos. “Shear-Induced Ordering in Systems with Competing Interactions: A Machine Learning Study.” <i>The Journal of Chemical Physics</i>. AIP Publishing, 2020. <a href=\"https://doi.org/10.1063/5.0005194\">https://doi.org/10.1063/5.0005194</a>.","ama":"Pȩkalski J, Rzadkowski W, Panagiotopoulos AZ. Shear-induced ordering in systems with competing interactions: A machine learning study. <i>The Journal of chemical physics</i>. 2020;152(20). doi:<a href=\"https://doi.org/10.1063/5.0005194\">10.1063/5.0005194</a>","apa":"Pȩkalski, J., Rzadkowski, W., &#38; Panagiotopoulos, A. Z. (2020). Shear-induced ordering in systems with competing interactions: A machine learning study. <i>The Journal of Chemical Physics</i>. AIP Publishing. <a href=\"https://doi.org/10.1063/5.0005194\">https://doi.org/10.1063/5.0005194</a>","ieee":"J. Pȩkalski, W. Rzadkowski, and A. Z. Panagiotopoulos, “Shear-induced ordering in systems with competing interactions: A machine learning study,” <i>The Journal of chemical physics</i>, vol. 152, no. 20. AIP Publishing, 2020.","mla":"Pȩkalski, J., et al. “Shear-Induced Ordering in Systems with Competing Interactions: A Machine Learning Study.” <i>The Journal of Chemical Physics</i>, vol. 152, no. 20, 204905, AIP Publishing, 2020, doi:<a href=\"https://doi.org/10.1063/5.0005194\">10.1063/5.0005194</a>.","short":"J. Pȩkalski, W. Rzadkowski, A.Z. Panagiotopoulos, The Journal of Chemical Physics 152 (2020).","ista":"Pȩkalski J, Rzadkowski W, Panagiotopoulos AZ. 2020. Shear-induced ordering in systems with competing interactions: A machine learning study. The Journal of chemical physics. 152(20), 204905."},"quality_controlled":"1","day":"29","article_processing_charge":"No","oa_version":"Published Version","_id":"7956","article_type":"original","scopus_import":"1","department":[{"_id":"MiLe"}],"intvolume":"       152"},{"publisher":"Elsevier","quality_controlled":"1","citation":{"chicago":"Gladbach, Peter, Eva Kopfer, Jan Maas, and Lorenzo Portinale. “Homogenisation of One-Dimensional Discrete Optimal Transport.” <i>Journal de Mathematiques Pures et Appliquees</i>. Elsevier, 2020. <a href=\"https://doi.org/10.1016/j.matpur.2020.02.008\">https://doi.org/10.1016/j.matpur.2020.02.008</a>.","apa":"Gladbach, P., Kopfer, E., Maas, J., &#38; Portinale, L. (2020). Homogenisation of one-dimensional discrete optimal transport. <i>Journal de Mathematiques Pures et Appliquees</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.matpur.2020.02.008\">https://doi.org/10.1016/j.matpur.2020.02.008</a>","ama":"Gladbach P, Kopfer E, Maas J, Portinale L. Homogenisation of one-dimensional discrete optimal transport. <i>Journal de Mathematiques Pures et Appliquees</i>. 2020;139(7):204-234. doi:<a href=\"https://doi.org/10.1016/j.matpur.2020.02.008\">10.1016/j.matpur.2020.02.008</a>","short":"P. Gladbach, E. Kopfer, J. Maas, L. Portinale, Journal de Mathematiques Pures et Appliquees 139 (2020) 204–234.","mla":"Gladbach, Peter, et al. “Homogenisation of One-Dimensional Discrete Optimal Transport.” <i>Journal de Mathematiques Pures et Appliquees</i>, vol. 139, no. 7, Elsevier, 2020, pp. 204–34, doi:<a href=\"https://doi.org/10.1016/j.matpur.2020.02.008\">10.1016/j.matpur.2020.02.008</a>.","ieee":"P. Gladbach, E. Kopfer, J. Maas, and L. Portinale, “Homogenisation of one-dimensional discrete optimal transport,” <i>Journal de Mathematiques Pures et Appliquees</i>, vol. 139, no. 7. Elsevier, pp. 204–234, 2020.","ista":"Gladbach P, Kopfer E, Maas J, Portinale L. 2020. Homogenisation of one-dimensional discrete optimal transport. Journal de Mathematiques Pures et Appliquees. 139(7), 204–234."},"oa_version":"Preprint","article_processing_charge":"No","_id":"7573","day":"01","department":[{"_id":"JaMa"}],"intvolume":"       139","article_type":"original","scopus_import":"1","abstract":[{"lang":"eng","text":"This paper deals with dynamical optimal transport metrics defined by spatial discretisation of the Benamou–Benamou formula for the Kantorovich metric . Such metrics appear naturally in discretisations of -gradient flow formulations for dissipative PDE. However, it has recently been shown that these metrics do not in general converge to , unless strong geometric constraints are imposed on the discrete mesh. In this paper we prove that, in a 1-dimensional periodic setting, discrete transport metrics converge to a limiting transport metric with a non-trivial effective mobility. This mobility depends sensitively on the geometry of the mesh and on the non-local mobility at the discrete level. Our result quantifies to what extent discrete transport can make use of microstructure in the mesh to reduce the cost of transport."}],"main_file_link":[{"url":"https://arxiv.org/abs/1905.05757","open_access":"1"}],"date_updated":"2026-04-08T07:00:03Z","author":[{"first_name":"Peter","last_name":"Gladbach","full_name":"Gladbach, Peter"},{"full_name":"Kopfer, Eva","last_name":"Kopfer","first_name":"Eva"},{"full_name":"Maas, Jan","id":"4C5696CE-F248-11E8-B48F-1D18A9856A87","first_name":"Jan","last_name":"Maas","orcid":"0000-0002-0845-1338"},{"id":"30AD2CBC-F248-11E8-B48F-1D18A9856A87","full_name":"Portinale, Lorenzo","last_name":"Portinale","first_name":"Lorenzo"}],"title":"Homogenisation of one-dimensional discrete optimal transport","external_id":{"arxiv":["1905.05757"],"isi":["000539439400008"]},"date_created":"2020-03-08T23:00:47Z","project":[{"call_identifier":"H2020","grant_number":"716117","name":"Optimal Transport and Stochastic Dynamics","_id":"256E75B8-B435-11E9-9278-68D0E5697425"},{"_id":"260482E2-B435-11E9-9278-68D0E5697425","grant_number":"F06504","name":"Taming Complexity in Partial Differential Systems","call_identifier":"FWF"},{"name":"Dissipation and dispersion in nonlinear partial differential equations","grant_number":"W1245","call_identifier":"FWF","_id":"260788DE-B435-11E9-9278-68D0E5697425"}],"date_published":"2020-07-01T00:00:00Z","publication":"Journal de Mathematiques Pures et Appliquees","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ec_funded":1,"status":"public","publication_identifier":{"issn":["0021-7824"]},"volume":139,"type":"journal_article","acknowledgement":"J.M. gratefully acknowledges support by the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 716117). J.M. and L.P. also acknowledge support from the Austrian Science Fund (FWF), grants No F65 and W1245. E.K. gratefully acknowledges support by the German Research Foundation through the Hausdorff Center for Mathematics and the Collaborative Research Center 1060. P.G. is partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – 350398276.","arxiv":1,"isi":1,"month":"07","related_material":{"record":[{"id":"10030","status":"public","relation":"dissertation_contains"}]},"page":"204-234","issue":"7","doi":"10.1016/j.matpur.2020.02.008","language":[{"iso":"eng"}],"oa":1,"year":"2020"},{"publication":"SIAM Journal on Mathematical Analysis","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","corr_author":"1","date_published":"2020-02-12T00:00:00Z","date_created":"2021-08-06T07:34:16Z","external_id":{"isi":["000546967700022"],"arxiv":["1904.08647 "]},"author":[{"last_name":"Feliciangeli","first_name":"Dario","orcid":"0000-0003-0754-8530","id":"41A639AA-F248-11E8-B48F-1D18A9856A87","full_name":"Feliciangeli, Dario"},{"id":"4AFD0470-F248-11E8-B48F-1D18A9856A87","full_name":"Seiringer, Robert","first_name":"Robert","last_name":"Seiringer","orcid":"0000-0002-6781-0521"}],"title":"Uniqueness and nondegeneracy of minimizers of the Pekar functional on a ball","project":[{"_id":"25C6DC12-B435-11E9-9278-68D0E5697425","grant_number":"694227","name":"Analysis of quantum many-body systems","call_identifier":"H2020"}],"abstract":[{"lang":"eng","text":"We consider the Pekar functional on a ball in ℝ3. We prove uniqueness of minimizers, and a quadratic lower bound in terms of the distance to the minimizer. The latter follows from nondegeneracy of the Hessian at the minimum."}],"date_updated":"2026-04-08T06:59:49Z","main_file_link":[{"url":"https://arxiv.org/abs/1904.08647","open_access":"1"}],"intvolume":"        52","department":[{"_id":"RoSe"}],"article_type":"original","scopus_import":"1","_id":"9781","article_processing_charge":"No","oa_version":"Preprint","day":"12","ddc":["510"],"quality_controlled":"1","citation":{"ista":"Feliciangeli D, Seiringer R. 2020. Uniqueness and nondegeneracy of minimizers of the Pekar functional on a ball. SIAM Journal on Mathematical Analysis. 52(1), 605–622.","short":"D. Feliciangeli, R. Seiringer, SIAM Journal on Mathematical Analysis 52 (2020) 605–622.","mla":"Feliciangeli, Dario, and Robert Seiringer. “Uniqueness and Nondegeneracy of Minimizers of the Pekar Functional on a Ball.” <i>SIAM Journal on Mathematical Analysis</i>, vol. 52, no. 1, Society for Industrial and Applied Mathematics , 2020, pp. 605–22, doi:<a href=\"https://doi.org/10.1137/19m126284x\">10.1137/19m126284x</a>.","ieee":"D. Feliciangeli and R. Seiringer, “Uniqueness and nondegeneracy of minimizers of the Pekar functional on a ball,” <i>SIAM Journal on Mathematical Analysis</i>, vol. 52, no. 1. Society for Industrial and Applied Mathematics , pp. 605–622, 2020.","ama":"Feliciangeli D, Seiringer R. Uniqueness and nondegeneracy of minimizers of the Pekar functional on a ball. <i>SIAM Journal on Mathematical Analysis</i>. 2020;52(1):605-622. doi:<a href=\"https://doi.org/10.1137/19m126284x\">10.1137/19m126284x</a>","apa":"Feliciangeli, D., &#38; Seiringer, R. (2020). Uniqueness and nondegeneracy of minimizers of the Pekar functional on a ball. <i>SIAM Journal on Mathematical Analysis</i>. Society for Industrial and Applied Mathematics . <a href=\"https://doi.org/10.1137/19m126284x\">https://doi.org/10.1137/19m126284x</a>","chicago":"Feliciangeli, Dario, and Robert Seiringer. “Uniqueness and Nondegeneracy of Minimizers of the Pekar Functional on a Ball.” <i>SIAM Journal on Mathematical Analysis</i>. Society for Industrial and Applied Mathematics , 2020. <a href=\"https://doi.org/10.1137/19m126284x\">https://doi.org/10.1137/19m126284x</a>."},"publisher":"Society for Industrial and Applied Mathematics ","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)","short":"CC BY-NC-ND (4.0)","image":"/images/cc_by_nc_nd.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode"},"year":"2020","oa":1,"issue":"1","doi":"10.1137/19m126284x","page":"605-622","has_accepted_license":"1","related_material":{"record":[{"status":"public","id":"9733","relation":"dissertation_contains"}]},"month":"02","isi":1,"arxiv":1,"acknowledgement":"We are grateful for the hospitality at the Mittag-Leffler Institute, where part of this work has been done. The work of the authors was supported by the European Research Council (ERC)under the European Union's Horizon 2020 research and innovation programme grant 694227.","type":"journal_article","keyword":["Applied Mathematics","Computational Mathematics","Analysis"],"volume":52,"status":"public","ec_funded":1,"publication_identifier":{"issn":["0036-1410"],"eissn":["1095-7154"]}},{"title":"Evolutionary Γ-convergence of entropic gradient flow structures for Fokker-Planck equations in multiple dimensions","author":[{"last_name":"Forkert","first_name":"Dominik L","id":"35C79D68-F248-11E8-B48F-1D18A9856A87","full_name":"Forkert, Dominik L"},{"first_name":"Jan","last_name":"Maas","orcid":"0000-0002-0845-1338","full_name":"Maas, Jan","id":"4C5696CE-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Portinale, Lorenzo","id":"30AD2CBC-F248-11E8-B48F-1D18A9856A87","last_name":"Portinale","first_name":"Lorenzo"}],"external_id":{"arxiv":["2008.10962"]},"date_created":"2021-09-17T10:57:27Z","project":[{"_id":"256E75B8-B435-11E9-9278-68D0E5697425","grant_number":"716117","name":"Optimal Transport and Stochastic Dynamics","call_identifier":"H2020"},{"_id":"fc31cba2-9c52-11eb-aca3-ff467d239cd2","name":"Taming Complexity in Partial Differential Systems","grant_number":"F6504"}],"abstract":[{"text":"We consider finite-volume approximations of Fokker-Planck equations on bounded convex domains in R^d and study the corresponding gradient flow structures. We reprove the convergence of the discrete to continuous Fokker-Planck equation via the method of Evolutionary Γ-convergence, i.e., we pass to the limit at the level of the gradient flow structures, generalising the one-dimensional result obtained by Disser and Liero. The proof is of variational nature and relies on a Mosco convergence result for functionals in the discrete-to-continuum limit that is of independent interest. Our results apply to arbitrary regular meshes, even though the associated discrete transport distances may fail to converge to the Wasserstein distance in this generality.","lang":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2008.10962"}],"date_updated":"2026-04-08T07:00:03Z","publication":"arXiv","publication_status":"draft","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","article_number":"2008.10962","date_published":"2020-08-25T00:00:00Z","citation":{"ista":"Forkert DL, Maas J, Portinale L. Evolutionary Γ-convergence of entropic gradient flow structures for Fokker-Planck equations in multiple dimensions. arXiv, 2008.10962.","mla":"Forkert, Dominik L., et al. “Evolutionary Γ-Convergence of Entropic Gradient Flow Structures for Fokker-Planck Equations in Multiple Dimensions.” <i>ArXiv</i>, 2008.10962, doi:<a href=\"https://doi.org/10.48550/arXiv.2008.10962\">10.48550/arXiv.2008.10962</a>.","short":"D.L. Forkert, J. Maas, L. Portinale, ArXiv (n.d.).","ieee":"D. L. Forkert, J. Maas, and L. Portinale, “Evolutionary Γ-convergence of entropic gradient flow structures for Fokker-Planck equations in multiple dimensions,” <i>arXiv</i>. .","apa":"Forkert, D. L., Maas, J., &#38; Portinale, L. (n.d.). Evolutionary Γ-convergence of entropic gradient flow structures for Fokker-Planck equations in multiple dimensions. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2008.10962\">https://doi.org/10.48550/arXiv.2008.10962</a>","ama":"Forkert DL, Maas J, Portinale L. Evolutionary Γ-convergence of entropic gradient flow structures for Fokker-Planck equations in multiple dimensions. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2008.10962\">10.48550/arXiv.2008.10962</a>","chicago":"Forkert, Dominik L, Jan Maas, and Lorenzo Portinale. “Evolutionary Γ-Convergence of Entropic Gradient Flow Structures for Fokker-Planck Equations in Multiple Dimensions.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2008.10962\">https://doi.org/10.48550/arXiv.2008.10962</a>."},"department":[{"_id":"JaMa"}],"oa_version":"Preprint","article_processing_charge":"No","_id":"10022","day":"25","month":"08","arxiv":1,"language":[{"iso":"eng"}],"oa":1,"year":"2020","related_material":{"record":[{"relation":"later_version","id":"11739","status":"public"},{"relation":"dissertation_contains","status":"public","id":"10030"}]},"doi":"10.48550/arXiv.2008.10962","ec_funded":1,"status":"public","acknowledgement":"This work is supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 716117) and by the Austrian Science Fund (FWF), grants No F65 and W1245.","type":"preprint"},{"project":[{"name":"International IST Doctoral Program","grant_number":"665385","call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425"},{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"external_id":{"isi":["000511060200001"]},"date_created":"2020-02-16T23:00:50Z","author":[{"orcid":"0000-0002-0479-558X","first_name":"Julian L","last_name":"Fischer","full_name":"Fischer, Julian L","id":"2C12A0B0-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0001-7252-8072","first_name":"Sebastian","last_name":"Hensel","full_name":"Hensel, Sebastian","id":"4D23B7DA-F248-11E8-B48F-1D18A9856A87"}],"title":"Weak–strong uniqueness for the Navier–Stokes equation for two fluids with surface tension","date_updated":"2026-04-08T07:01:01Z","abstract":[{"lang":"eng","text":"In the present work, we consider the evolution of two fluids separated by a sharp interface in the presence of surface tension—like, for example, the evolution of oil bubbles in water. Our main result is a weak–strong uniqueness principle for the corresponding free boundary problem for the incompressible Navier–Stokes equation: as long as a strong solution exists, any varifold solution must coincide with it. In particular, in the absence of physical singularities, the concept of varifold solutions—whose global in time existence has been shown by Abels (Interfaces Free Bound 9(1):31–65, 2007) for general initial data—does not introduce a mechanism for non-uniqueness. The key ingredient of our approach is the construction of a relative entropy functional capable of controlling the interface error. If the viscosities of the two fluids do not coincide, even for classical (strong) solutions the gradient of the velocity field becomes discontinuous at the interface, introducing the need for a careful additional adaption of the relative entropy."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","file_date_updated":"2020-11-20T09:14:22Z","publication":"Archive for Rational Mechanics and Analysis","date_published":"2020-05-01T00:00:00Z","corr_author":"1","citation":{"ieee":"J. L. Fischer and S. Hensel, “Weak–strong uniqueness for the Navier–Stokes equation for two fluids with surface tension,” <i>Archive for Rational Mechanics and Analysis</i>, vol. 236. Springer Nature, pp. 967–1087, 2020.","short":"J.L. Fischer, S. Hensel, Archive for Rational Mechanics and Analysis 236 (2020) 967–1087.","mla":"Fischer, Julian L., and Sebastian Hensel. “Weak–Strong Uniqueness for the Navier–Stokes Equation for Two Fluids with Surface Tension.” <i>Archive for Rational Mechanics and Analysis</i>, vol. 236, Springer Nature, 2020, pp. 967–1087, doi:<a href=\"https://doi.org/10.1007/s00205-019-01486-2\">10.1007/s00205-019-01486-2</a>.","ista":"Fischer JL, Hensel S. 2020. Weak–strong uniqueness for the Navier–Stokes equation for two fluids with surface tension. Archive for Rational Mechanics and Analysis. 236, 967–1087.","chicago":"Fischer, Julian L, and Sebastian Hensel. “Weak–Strong Uniqueness for the Navier–Stokes Equation for Two Fluids with Surface Tension.” <i>Archive for Rational Mechanics and Analysis</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s00205-019-01486-2\">https://doi.org/10.1007/s00205-019-01486-2</a>.","apa":"Fischer, J. L., &#38; Hensel, S. (2020). Weak–strong uniqueness for the Navier–Stokes equation for two fluids with surface tension. <i>Archive for Rational Mechanics and Analysis</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00205-019-01486-2\">https://doi.org/10.1007/s00205-019-01486-2</a>","ama":"Fischer JL, Hensel S. Weak–strong uniqueness for the Navier–Stokes equation for two fluids with surface tension. <i>Archive for Rational Mechanics and Analysis</i>. 2020;236:967-1087. doi:<a href=\"https://doi.org/10.1007/s00205-019-01486-2\">10.1007/s00205-019-01486-2</a>"},"quality_controlled":"1","ddc":["530","532"],"publisher":"Springer Nature","article_type":"original","scopus_import":"1","intvolume":"       236","department":[{"_id":"JuFi"}],"day":"01","_id":"7489","oa_version":"Published Version","article_processing_charge":"Yes (via OA deal)","month":"05","isi":1,"year":"2020","oa":1,"language":[{"iso":"eng"}],"file":[{"date_updated":"2020-11-20T09:14:22Z","file_name":"2020_ArchRatMechAn_Fischer.pdf","file_size":1897571,"checksum":"f107e21b58f5930876f47144be37cf6c","content_type":"application/pdf","date_created":"2020-11-20T09:14:22Z","relation":"main_file","access_level":"open_access","creator":"dernst","success":1,"file_id":"8779"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"doi":"10.1007/s00205-019-01486-2","has_accepted_license":"1","page":"967-1087","related_material":{"record":[{"status":"public","id":"10007","relation":"dissertation_contains"}]},"volume":236,"publication_identifier":{"issn":["0003-9527"],"eissn":["1432-0673"]},"status":"public","ec_funded":1,"type":"journal_article"},{"language":[{"iso":"eng"}],"publication":"arXiv","oa":1,"publication_status":"draft","year":"2020","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"status":"public","id":"10007","relation":"dissertation_contains"}]},"article_number":"2003.05478","doi":"10.48550/arXiv.2003.05478","date_published":"2020-03-11T00:00:00Z","author":[{"id":"2C12A0B0-F248-11E8-B48F-1D18A9856A87","full_name":"Fischer, Julian L","first_name":"Julian L","last_name":"Fischer","orcid":"0000-0002-0479-558X"},{"full_name":"Hensel, Sebastian","id":"4D23B7DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-7252-8072","last_name":"Hensel","first_name":"Sebastian"},{"first_name":"Tim","last_name":"Laux","full_name":"Laux, Tim"},{"first_name":"Thilo","last_name":"Simon","full_name":"Simon, Thilo"}],"title":"The local structure of the energy landscape in multiphase mean curvature flow: weak-strong uniqueness and stability of evolutions","date_created":"2021-09-13T12:17:11Z","external_id":{"arxiv":["2003.05478"]},"project":[{"_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"International IST Doctoral Program","grant_number":"665385"}],"month":"03","abstract":[{"lang":"eng","text":"We prove that in the absence of topological changes, the notion of BV solutions to planar multiphase mean curvature flow does not allow for a mechanism for (unphysical) non-uniqueness. Our approach is based on the local structure of the energy landscape near a classical evolution by mean curvature. Mean curvature flow being the gradient flow of the surface energy functional, we develop a gradient-flow analogue of the notion of calibrations. Just like the existence of a calibration guarantees that one has reached a global minimum in the energy landscape, the existence of a \"gradient flow calibration\" ensures that the route of steepest descent in the energy landscape is unique and stable."}],"arxiv":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2003.05478"}],"date_updated":"2026-04-08T07:01:01Z","department":[{"_id":"JuFi"}],"acknowledgement":"Parts of the paper were written during the visit of the authors to the Hausdorff Research Institute for Mathematics (HIM), University of Bonn, in the framework of the trimester program “Evolution of Interfaces”. The support and the hospitality of HIM are gratefully acknowledged. This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie Grant Agreement No. 665385.","article_processing_charge":"No","oa_version":"Preprint","type":"preprint","_id":"10012","day":"11","citation":{"short":"J.L. Fischer, S. Hensel, T. Laux, T. Simon, ArXiv (n.d.).","mla":"Fischer, Julian L., et al. “The Local Structure of the Energy Landscape in Multiphase Mean Curvature Flow: Weak-Strong Uniqueness and Stability of Evolutions.” <i>ArXiv</i>, 2003.05478, doi:<a href=\"https://doi.org/10.48550/arXiv.2003.05478\">10.48550/arXiv.2003.05478</a>.","ieee":"J. L. Fischer, S. Hensel, T. Laux, and T. Simon, “The local structure of the energy landscape in multiphase mean curvature flow: weak-strong uniqueness and stability of evolutions,” <i>arXiv</i>. .","ista":"Fischer JL, Hensel S, Laux T, Simon T. The local structure of the energy landscape in multiphase mean curvature flow: weak-strong uniqueness and stability of evolutions. arXiv, 2003.05478.","chicago":"Fischer, Julian L, Sebastian Hensel, Tim Laux, and Thilo Simon. “The Local Structure of the Energy Landscape in Multiphase Mean Curvature Flow: Weak-Strong Uniqueness and Stability of Evolutions.” <i>ArXiv</i>, n.d. <a href=\"https://doi.org/10.48550/arXiv.2003.05478\">https://doi.org/10.48550/arXiv.2003.05478</a>.","ama":"Fischer JL, Hensel S, Laux T, Simon T. The local structure of the energy landscape in multiphase mean curvature flow: weak-strong uniqueness and stability of evolutions. <i>arXiv</i>. doi:<a href=\"https://doi.org/10.48550/arXiv.2003.05478\">10.48550/arXiv.2003.05478</a>","apa":"Fischer, J. L., Hensel, S., Laux, T., &#38; Simon, T. (n.d.). The local structure of the energy landscape in multiphase mean curvature flow: weak-strong uniqueness and stability of evolutions. <i>arXiv</i>. <a href=\"https://doi.org/10.48550/arXiv.2003.05478\">https://doi.org/10.48550/arXiv.2003.05478</a>"},"ec_funded":1,"status":"public"},{"type":"conference","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959771627"]},"ec_funded":1,"status":"public","volume":173,"related_material":{"record":[{"status":"public","id":"9056","relation":"dissertation_contains"}]},"has_accepted_license":"1","conference":{"end_date":"2020-09-09","location":"Virtual, Online; Pisa, Italy","name":"ESA: European Symposium on Algorithms","start_date":"2020-09-07"},"doi":"10.4230/LIPIcs.ESA.2020.75","oa":1,"year":"2020","tmp":{"name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","short":"CC BY (3.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"file":[{"relation":"main_file","date_created":"2020-10-27T14:31:52Z","content_type":"application/pdf","checksum":"fe0f7c49a99ed870c671b911e10d5496","file_size":733291,"date_updated":"2020-10-27T14:31:52Z","file_name":"2020_LIPIcs_Osang.pdf","file_id":"8712","success":1,"creator":"cziletti","access_level":"open_access"}],"language":[{"iso":"eng"}],"month":"08","day":"26","article_processing_charge":"No","oa_version":"Published Version","_id":"8703","scopus_import":"1","department":[{"_id":"HeEd"}],"alternative_title":["LIPIcs"],"intvolume":"       173","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","quality_controlled":"1","citation":{"mla":"Osang, Georg F., et al. “Generalizing CGAL Periodic Delaunay Triangulations.” <i>28th Annual European Symposium on Algorithms</i>, vol. 173, 75, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">10.4230/LIPIcs.ESA.2020.75</a>.","short":"G.F. Osang, M. Rouxel-Labbé, M. Teillaud, in:, 28th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ieee":"G. F. Osang, M. Rouxel-Labbé, and M. Teillaud, “Generalizing CGAL periodic Delaunay triangulations,” in <i>28th Annual European Symposium on Algorithms</i>, Virtual, Online; Pisa, Italy, 2020, vol. 173.","ista":"Osang GF, Rouxel-Labbé M, Teillaud M. 2020. Generalizing CGAL periodic Delaunay triangulations. 28th Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 173, 75.","chicago":"Osang, Georg F, Mael Rouxel-Labbé, and Monique Teillaud. “Generalizing CGAL Periodic Delaunay Triangulations.” 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.75\">https://doi.org/10.4230/LIPIcs.ESA.2020.75</a>.","apa":"Osang, G. F., Rouxel-Labbé, M., &#38; Teillaud, M. (2020). Generalizing CGAL periodic Delaunay triangulations. In <i>28th Annual European Symposium on Algorithms</i> (Vol. 173). Virtual, Online; Pisa, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.ESA.2020.75\">https://doi.org/10.4230/LIPIcs.ESA.2020.75</a>","ama":"Osang GF, Rouxel-Labbé M, Teillaud M. Generalizing CGAL periodic Delaunay triangulations. 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.75\">10.4230/LIPIcs.ESA.2020.75</a>"},"ddc":["000"],"date_published":"2020-08-26T00:00:00Z","corr_author":"1","article_number":"75","publication_status":"published","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"28th Annual European Symposium on Algorithms","file_date_updated":"2020-10-27T14:31:52Z","date_updated":"2026-04-08T07:01:29Z","abstract":[{"text":"Even though Delaunay originally introduced his famous triangulations in the case of infinite point sets with translational periodicity, a software that computes such triangulations in the general case is not yet available, to the best of our knowledge. Combining and generalizing previous work, we present a practical algorithm for computing such triangulations. The algorithm has been implemented and experiments show that its performance is as good as the one of the CGAL package, which is restricted to cubic periodicity. ","lang":"eng"}],"project":[{"name":"Alpha Shape Theory Extended","grant_number":"788183","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"}],"author":[{"id":"464B40D6-F248-11E8-B48F-1D18A9856A87","full_name":"Osang, Georg F","orcid":"0000-0002-8882-5116","first_name":"Georg F","last_name":"Osang"},{"last_name":"Rouxel-Labbé","first_name":"Mael","full_name":"Rouxel-Labbé, Mael"},{"full_name":"Teillaud, Monique","first_name":"Monique","last_name":"Teillaud"}],"title":"Generalizing CGAL periodic Delaunay triangulations","date_created":"2020-10-25T23:01:18Z"},{"abstract":[{"text":"We address the following question:  How redundant is the parameterisation of ReLU networks? Specifically, we consider transformations of the weight space which leave the function implemented by the network intact.  Two such transformations are known for feed-forward architectures:  permutation of neurons within a layer, and positive scaling of all incoming weights of a neuron coupled with inverse scaling of its outgoing weights. In this work, we show for architectures with non-increasing widths that permutation and scaling are in fact the only function-preserving weight transformations.  For any eligible architecture we give an explicit construction of a neural network such that any other network that implements the same function can be obtained from the original one by the application of permutations and rescaling.  The proof relies on a geometric understanding of boundaries between linear regions of ReLU networks, and we hope the developed mathematical tools are of independent interest.","lang":"eng"}],"date_updated":"2026-04-08T07:01:16Z","author":[{"first_name":"Phuong","last_name":"Bui Thi Mai","full_name":"Bui Thi Mai, Phuong","id":"3EC6EE64-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Christoph","last_name":"Lampert","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87"}],"title":"Functional vs. parametric equivalence of ReLU networks","date_created":"2020-02-11T09:07:37Z","month":"04","conference":{"name":"ICLR: International Conference on Learning Representations","end_date":"2020-04-30","location":"Online","start_date":"2020-04-27"},"has_accepted_license":"1","corr_author":"1","related_material":{"link":[{"url":"https://iclr.cc/virtual_2020/poster_Bylx-TNKvH.html","relation":"supplementary_material"}],"record":[{"relation":"dissertation_contains","status":"public","id":"9418"}]},"date_published":"2020-04-26T00:00:00Z","language":[{"iso":"eng"}],"file":[{"file_name":"main.pdf","date_updated":"2020-07-14T12:47:59Z","content_type":"application/pdf","checksum":"8d372ea5defd8cb8fdc430111ed754a9","file_size":405469,"date_created":"2020-02-11T09:07:27Z","relation":"main_file","access_level":"open_access","creator":"bphuong","file_id":"7482"}],"file_date_updated":"2020-07-14T12:47:59Z","publication":"8th International Conference on Learning Representations","publication_status":"published","oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2020","status":"public","ddc":["000"],"quality_controlled":"1","citation":{"chicago":"Phuong, Mary, and Christoph Lampert. “Functional vs. Parametric Equivalence of ReLU Networks.” In <i>8th International Conference on Learning Representations</i>, 2020.","apa":"Phuong, M., &#38; Lampert, C. (2020). Functional vs. parametric equivalence of ReLU networks. In <i>8th International Conference on Learning Representations</i>. Online.","ama":"Phuong M, Lampert C. Functional vs. parametric equivalence of ReLU networks. In: <i>8th International Conference on Learning Representations</i>. ; 2020.","short":"M. Phuong, C. Lampert, in:, 8th International Conference on Learning Representations, 2020.","mla":"Phuong, Mary, and Christoph Lampert. “Functional vs. Parametric Equivalence of ReLU Networks.” <i>8th International Conference on Learning Representations</i>, 2020.","ieee":"M. Phuong and C. Lampert, “Functional vs. parametric equivalence of ReLU networks,” in <i>8th International Conference on Learning Representations</i>, Online, 2020.","ista":"Phuong M, Lampert C. 2020. Functional vs. parametric equivalence of ReLU networks. 8th International Conference on Learning Representations. ICLR: International Conference on Learning Representations."},"article_processing_charge":"No","oa_version":"Published Version","_id":"7481","type":"conference","day":"26","department":[{"_id":"ChLa"}]},{"ddc":["516","514"],"supervisor":[{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"},{"last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"citation":{"ista":"Masárová Z. 2020. Reconfiguration problems. Institute of Science and Technology Austria.","short":"Z. Masárová, Reconfiguration Problems, Institute of Science and Technology Austria, 2020.","mla":"Masárová, Zuzana. <i>Reconfiguration Problems</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7944\">10.15479/AT:ISTA:7944</a>.","ieee":"Z. Masárová, “Reconfiguration problems,” Institute of Science and Technology Austria, 2020.","apa":"Masárová, Z. (2020). <i>Reconfiguration problems</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:7944\">https://doi.org/10.15479/AT:ISTA:7944</a>","ama":"Masárová Z. Reconfiguration problems. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7944\">10.15479/AT:ISTA:7944</a>","chicago":"Masárová, Zuzana. “Reconfiguration Problems.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:7944\">https://doi.org/10.15479/AT:ISTA:7944</a>."},"publisher":"Institute of Science and Technology Austria","department":[{"_id":"HeEd"},{"_id":"UlWa"}],"alternative_title":["ISTA Thesis"],"_id":"7944","article_processing_charge":"No","oa_version":"Published Version","day":"09","date_created":"2020-06-08T00:49:46Z","author":[{"full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","first_name":"Zuzana","last_name":"Masárová"}],"title":"Reconfiguration problems","abstract":[{"lang":"eng","text":"This thesis considers two examples of reconfiguration problems: flipping edges in edge-labelled triangulations of planar point sets and swapping labelled tokens placed on vertices of a graph. In both cases the studied structures – all the triangulations of a given point set or all token placements on a given graph – can be thought of as vertices of the so-called reconfiguration graph, in which two vertices are adjacent if the corresponding structures differ by a single elementary operation – by a flip of a diagonal in a triangulation or by a swap of tokens on adjacent vertices, respectively. We study the reconfiguration of one instance of a structure into another via (shortest) paths in the reconfiguration graph.\r\n\r\nFor triangulations of point sets in which each edge has a unique label and a flip transfers the label from the removed edge to the new edge, we prove a polynomial-time testable condition, called the Orbit Theorem, that characterizes when two triangulations of the same point set lie in the same connected component of the reconfiguration graph. The condition was first conjectured by Bose, Lubiw, Pathak and Verdonschot. We additionally provide a polynomial time algorithm that computes a reconfiguring flip sequence, if it exists. Our proof of the Orbit Theorem uses topological properties of a certain high-dimensional cell complex that has the usual reconfiguration graph as its 1-skeleton.\r\n\r\nIn the context of token swapping on a tree graph, we make partial progress on the problem of finding shortest reconfiguration sequences. We disprove the so-called Happy Leaf Conjecture and demonstrate the importance of swapping tokens that are already placed at the correct vertices. We also prove that a generalization of the problem to weighted coloured token swapping is NP-hard on trees but solvable in polynomial time on paths and stars."}],"date_updated":"2026-04-08T07:23:01Z","file_date_updated":"2020-07-14T12:48:05Z","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_status":"published","corr_author":"1","date_published":"2020-06-09T00:00:00Z","keyword":["reconfiguration","reconfiguration graph","triangulations","flip","constrained triangulations","shellability","piecewise-linear balls","token swapping","trees","coloured weighted token swapping"],"OA_place":"publisher","status":"public","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-005-3"]},"type":"dissertation","degree_awarded":"PhD","month":"06","file":[{"date_created":"2020-06-08T00:34:00Z","relation":"main_file","file_size":13661779,"content_type":"application/pdf","checksum":"df688bc5a82b50baee0b99d25fc7b7f0","file_name":"THESIS_Zuzka_Masarova.pdf","date_updated":"2020-07-14T12:48:05Z","file_id":"7945","access_level":"open_access","creator":"zmasarov"},{"access_level":"closed","creator":"zmasarov","file_id":"7946","date_updated":"2020-07-14T12:48:05Z","file_name":"THESIS_Zuzka_Masarova_SOURCE_FILES.zip","file_size":32184006,"content_type":"application/zip","checksum":"45341a35b8f5529c74010b7af43ac188","date_created":"2020-06-08T00:35:30Z","relation":"source_file"}],"language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution-ShareAlike 4.0 International Public License (CC BY-SA 4.0)","short":"CC BY-SA (4.0)","image":"/images/cc_by_sa.png","legal_code_url":"https://creativecommons.org/licenses/by-sa/4.0/legalcode"},"year":"2020","oa":1,"doi":"10.15479/AT:ISTA:7944","page":"160","has_accepted_license":"1","related_material":{"record":[{"relation":"part_of_dissertation","id":"7950","status":"public"},{"relation":"part_of_dissertation","id":"5986","status":"public"}]}},{"month":"09","has_accepted_license":"1","page":"158","doi":"10.15479/AT:ISTA:8574","file":[{"access_level":"open_access","success":1,"creator":"dernst","file_id":"8575","checksum":"20e71f015fbbd78fea708893ad634ed0","file_size":6354833,"content_type":"application/pdf","file_name":"thesis_EnikoSzep_final.pdf","date_updated":"2020-09-28T07:25:35Z","date_created":"2020-09-28T07:25:35Z","relation":"main_file"},{"date_created":"2020-09-28T07:25:37Z","relation":"source_file","checksum":"a8de2c14a1bb4e53c857787efbb289e1","file_size":23020401,"content_type":"application/x-zip-compressed","date_updated":"2020-09-28T07:25:37Z","file_name":"thesisFiles_EnikoSzep.zip","file_id":"8576","access_level":"closed","creator":"dernst"}],"language":[{"iso":"eng"}],"oa":1,"year":"2020","status":"public","publication_identifier":{"eissn":["2663-337X"]},"OA_place":"publisher","degree_awarded":"PhD","type":"dissertation","abstract":[{"lang":"eng","text":"This thesis concerns itself with the interactions of evolutionary and ecological forces and the consequences on genetic diversity and the ultimate survival of populations. It is important to understand what signals processes \r\nleave on the genome and what we can infer from such data, which is usually abundant but noisy. Furthermore, understanding how and when populations adapt or go extinct is important for practical purposes,  such as the genetic management of populations, as well as for theoretical questions, since local adaptation can be the first step toward speciation. \r\nIn Chapter 2, we introduce the method of maximum entropy to approximate the demographic changes of a population in a simple setting, namely the logistic growth model with immigration. We show that this method is not only a powerful \r\ntool in physics but can be gainfully applied in an ecological framework. We investigate how well it approximates the real \r\nbehavior of the system, and find that is does so, even in unexpected situations. Finally, we illustrate how it can model changing environments.\r\nIn Chapter 3, we analyze the co-evolution of allele frequencies and population sizes in an infinite island model.\r\nWe give conditions under which polygenic adaptation to a rare habitat is possible. The model we use is based on the diffusion approximation, considers eco-evolutionary feedback mechanisms (hard selection), and treats both \r\ndrift and environmental fluctuations explicitly. We also look at limiting scenarios, for which we derive analytical expressions. \r\nIn Chapter 4, we present a coalescent based simulation tool to obtain patterns of diversity in a spatially explicit subdivided population, in which the demographic history of each subpopulation can be specified. We compare \r\nthe results to existing predictions, and explore the relative importance of time and space under a variety of spatial arrangements and demographic histories, such as expansion and extinction. \r\nIn the last chapter, we give a brief outlook to further research. "}],"date_updated":"2026-04-08T07:21:44Z","author":[{"id":"485BB5A4-F248-11E8-B48F-1D18A9856A87","full_name":"Szep, Eniko","last_name":"Szep","first_name":"Eniko"}],"title":"Local adaptation in metapopulations","date_created":"2020-09-28T07:33:38Z","corr_author":"1","date_published":"2020-09-20T00:00:00Z","file_date_updated":"2020-09-28T07:25:37Z","publication_status":"published","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publisher":"Institute of Science and Technology Austria","ddc":["570"],"supervisor":[{"id":"4880FE40-F248-11E8-B48F-1D18A9856A87","full_name":"Barton, Nicholas H","last_name":"Barton","first_name":"Nicholas H","orcid":"0000-0002-8548-5240"}],"citation":{"short":"E. Szep, Local Adaptation in Metapopulations, Institute of Science and Technology Austria, 2020.","mla":"Szep, Eniko. <i>Local Adaptation in Metapopulations</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8574\">10.15479/AT:ISTA:8574</a>.","ieee":"E. Szep, “Local adaptation in metapopulations,” Institute of Science and Technology Austria, 2020.","ista":"Szep E. 2020. Local adaptation in metapopulations. Institute of Science and Technology Austria.","chicago":"Szep, Eniko. “Local Adaptation in Metapopulations.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:8574\">https://doi.org/10.15479/AT:ISTA:8574</a>.","apa":"Szep, E. (2020). <i>Local adaptation in metapopulations</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:8574\">https://doi.org/10.15479/AT:ISTA:8574</a>","ama":"Szep E. Local adaptation in metapopulations. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8574\">10.15479/AT:ISTA:8574</a>"},"article_processing_charge":"No","oa_version":"Published Version","_id":"8574","day":"20","department":[{"_id":"NiBa"}],"alternative_title":["ISTA Thesis"]},{"supervisor":[{"id":"4C5696CE-F248-11E8-B48F-1D18A9856A87","full_name":"Maas, Jan","first_name":"Jan","last_name":"Maas","orcid":"0000-0002-0845-1338"}],"citation":{"ama":"Forkert DL. Gradient flows in spaces of probability measures for finite-volume schemes, metric graphs and non-reversible Markov chains. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7629\">10.15479/AT:ISTA:7629</a>","apa":"Forkert, D. L. (2020). <i>Gradient flows in spaces of probability measures for finite-volume schemes, metric graphs and non-reversible Markov chains</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:7629\">https://doi.org/10.15479/AT:ISTA:7629</a>","chicago":"Forkert, Dominik L. “Gradient Flows in Spaces of Probability Measures for Finite-Volume Schemes, Metric Graphs and Non-Reversible Markov Chains.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:7629\">https://doi.org/10.15479/AT:ISTA:7629</a>.","ista":"Forkert DL. 2020. Gradient flows in spaces of probability measures for finite-volume schemes, metric graphs and non-reversible Markov chains. Institute of Science and Technology Austria.","mla":"Forkert, Dominik L. <i>Gradient Flows in Spaces of Probability Measures for Finite-Volume Schemes, Metric Graphs and Non-Reversible Markov Chains</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7629\">10.15479/AT:ISTA:7629</a>.","short":"D.L. Forkert, Gradient Flows in Spaces of Probability Measures for Finite-Volume Schemes, Metric Graphs and Non-Reversible Markov Chains, Institute of Science and Technology Austria, 2020.","ieee":"D. L. Forkert, “Gradient flows in spaces of probability measures for finite-volume schemes, metric graphs and non-reversible Markov chains,” Institute of Science and Technology Austria, 2020."},"ddc":["510"],"publisher":"Institute of Science and Technology Austria","department":[{"_id":"JaMa"}],"alternative_title":["ISTA Thesis"],"day":"31","oa_version":"Published Version","article_processing_charge":"No","_id":"7629","project":[{"call_identifier":"H2020","name":"Optimal Transport and Stochastic Dynamics","grant_number":"716117","_id":"256E75B8-B435-11E9-9278-68D0E5697425"}],"author":[{"id":"35C79D68-F248-11E8-B48F-1D18A9856A87","full_name":"Forkert, Dominik L","last_name":"Forkert","first_name":"Dominik L"}],"title":"Gradient flows in spaces of probability measures for finite-volume schemes, metric graphs and non-reversible Markov chains","date_created":"2020-04-02T06:40:23Z","date_updated":"2026-04-08T07:22:00Z","abstract":[{"lang":"eng","text":"This thesis is based on three main topics: In the first part, we study convergence of discrete gradient flow structures associated with regular finite-volume discretisations of Fokker-Planck equations. We show evolutionary I convergence of the discrete gradient flows to the L2-Wasserstein gradient flow corresponding to the solution of a Fokker-Planck\r\nequation in arbitrary dimension d >= 1. Along the argument, we prove Mosco- and I-convergence results for discrete energy functionals, which are of independent interest for convergence of equivalent gradient flow structures in Hilbert spaces.\r\nThe second part investigates L2-Wasserstein flows on metric graph. The starting point is a Benamou-Brenier formula for the L2-Wasserstein distance, which is proved via a regularisation scheme for solutions of the continuity equation, adapted to the peculiar geometric structure of metric graphs. Based on those results, we show that the L2-Wasserstein space over a metric graph admits a gradient flow which may be identified as a solution of a Fokker-Planck equation.\r\nIn the third part, we focus again on the discrete gradient flows, already encountered in the first part. We propose a variational structure which extends the gradient flow structure to Markov chains violating the detailed-balance conditions. Using this structure, we characterise contraction estimates for the discrete heat flow in terms of convexity of\r\ncorresponding path-dependent energy functionals. In addition, we use this approach to derive several functional inequalities for said functionals."}],"publication_status":"published","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","file_date_updated":"2020-07-14T12:48:01Z","date_published":"2020-03-31T00:00:00Z","corr_author":"1","OA_place":"publisher","publication_identifier":{"issn":["2663-337X"]},"ec_funded":1,"status":"public","degree_awarded":"PhD","type":"dissertation","month":"03","oa":1,"year":"2020","language":[{"iso":"eng"}],"file":[{"file_id":"7657","creator":"dernst","access_level":"open_access","relation":"main_file","date_created":"2020-04-14T10:47:59Z","file_name":"Thesis_Forkert_PDFA.pdf","date_updated":"2020-07-14T12:48:01Z","file_size":3297129,"content_type":"application/pdf","checksum":"c814a1a6195269ca6fe48b0dca45ae8a"},{"date_updated":"2020-07-14T12:48:01Z","file_name":"Thesis_Forkert_source.zip","checksum":"ceafb53f923d1b5bdf14b2b0f22e4a81","content_type":"application/x-zip-compressed","file_size":1063908,"relation":"source_file","date_created":"2020-04-14T10:47:59Z","creator":"dernst","access_level":"closed","file_id":"7658"}],"has_accepted_license":"1","page":"154","doi":"10.15479/AT:ISTA:7629"},{"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_status":"published","file_date_updated":"2020-07-14T12:48:08Z","date_published":"2020-06-26T00:00:00Z","corr_author":"1","date_created":"2020-06-26T10:00:36Z","title":"Combinatorial width parameters for 3-dimensional manifolds","author":[{"id":"33C26278-F248-11E8-B48F-1D18A9856A87","full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","first_name":"Kristóf","last_name":"Huszár"}],"date_updated":"2026-04-08T07:21:28Z","abstract":[{"text":"Algorithms in computational 3-manifold topology typically take a triangulation as an input and return topological information about the underlying 3-manifold. However, extracting the desired information from a triangulation (e.g., evaluating an invariant) is often computationally very expensive. In recent years this complexity barrier has been successfully tackled in some cases by importing ideas from the theory of parameterized algorithms into the realm of 3-manifolds. Various computationally hard problems were shown to be efficiently solvable for input triangulations that are sufficiently “tree-like.”\r\nIn this thesis we focus on the key combinatorial parameter in the above context: we consider the treewidth of a compact, orientable 3-manifold, i.e., the smallest treewidth of the dual graph of any triangulation thereof. By building on the work of Scharlemann–Thompson and Scharlemann–Schultens–Saito on generalized Heegaard splittings, and on the work of Jaco–Rubinstein on layered triangulations, we establish quantitative relations between the treewidth and classical topological invariants of a 3-manifold. In particular, among other results, we show that the treewidth of a closed, orientable, irreducible, non-Haken 3-manifold is always within a constant factor of its Heegaard genus.","lang":"eng"}],"department":[{"_id":"UlWa"}],"alternative_title":["ISTA Thesis"],"day":"26","_id":"8032","article_processing_charge":"No","oa_version":"Published Version","citation":{"ama":"Huszár K. Combinatorial width parameters for 3-dimensional manifolds. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8032\">10.15479/AT:ISTA:8032</a>","apa":"Huszár, K. (2020). <i>Combinatorial width parameters for 3-dimensional manifolds</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:8032\">https://doi.org/10.15479/AT:ISTA:8032</a>","chicago":"Huszár, Kristóf. “Combinatorial Width Parameters for 3-Dimensional Manifolds.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:8032\">https://doi.org/10.15479/AT:ISTA:8032</a>.","ista":"Huszár K. 2020. Combinatorial width parameters for 3-dimensional manifolds. Institute of Science and Technology Austria.","short":"K. Huszár, Combinatorial Width Parameters for 3-Dimensional Manifolds, Institute of Science and Technology Austria, 2020.","mla":"Huszár, Kristóf. <i>Combinatorial Width Parameters for 3-Dimensional Manifolds</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8032\">10.15479/AT:ISTA:8032</a>.","ieee":"K. Huszár, “Combinatorial width parameters for 3-dimensional manifolds,” Institute of Science and Technology Austria, 2020."},"supervisor":[{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","last_name":"Wagner","first_name":"Uli"},{"last_name":"Spreer","first_name":"Jonathan","full_name":"Spreer, Jonathan"}],"ddc":["514"],"acknowledged_ssus":[{"_id":"E-Lib"},{"_id":"CampIT"}],"publisher":"Institute of Science and Technology Austria","year":"2020","oa":1,"language":[{"iso":"eng"}],"file":[{"file_id":"8034","access_level":"open_access","creator":"khuszar","date_created":"2020-06-26T10:03:58Z","relation":"main_file","date_updated":"2020-07-14T12:48:08Z","file_name":"Kristof_Huszar-Thesis.pdf","file_size":2637562,"checksum":"bd8be6e4f1addc863dfcc0fad29ee9c3","content_type":"application/pdf"},{"file_id":"8035","creator":"khuszar","access_level":"closed","relation":"source_file","date_created":"2020-06-26T10:10:06Z","file_size":7163491,"content_type":"application/x-zip-compressed","checksum":"d5f8456202b32f4a77552ef47a2837d1","date_updated":"2020-07-14T12:48:08Z","file_name":"Kristof_Huszar-Thesis-source.zip"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"doi":"10.15479/AT:ISTA:8032","related_material":{"record":[{"id":"6556","status":"public","relation":"dissertation_contains"},{"relation":"dissertation_contains","status":"public","id":"7093"}]},"has_accepted_license":"1","page":"xviii+120","month":"06","type":"dissertation","degree_awarded":"PhD","OA_place":"publisher","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-006-0"]},"status":"public"},{"file_date_updated":"2021-09-16T12:40:56Z","publication_status":"published","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","corr_author":"1","date_published":"2020-09-09T00:00:00Z","author":[{"last_name":"Steiner","first_name":"Julia","orcid":"0000-0003-0493-3775","id":"3BB67EB0-F248-11E8-B48F-1D18A9856A87","full_name":"Steiner, Julia"}],"title":"Biochemical and structural investigation of the Mrp antiporter, an ancestor of complex I","date_created":"2020-09-09T14:27:01Z","project":[{"_id":"26169496-B435-11E9-9278-68D0E5697425","name":"Revealing the functional mechanism of Mrp antiporter, an ancestor of complex I","grant_number":"24741"}],"abstract":[{"text":"Mrp (Multi resistance and pH adaptation) are broadly distributed secondary active antiporters that catalyze the transport of monovalent ions such as sodium and potassium outside of the cell coupled to the inward translocation of protons. Mrp antiporters are unique in a way that they are composed of seven subunits (MrpABCDEFG) encoded in a single operon, whereas other antiporters catalyzing the same reaction are mostly encoded by a single gene. Mrp exchangers are crucial for intracellular pH homeostasis and Na+ efflux, essential mechanisms for H+ uptake under alkaline environments and for reduction of the intracellular concentration of toxic cations. Mrp displays no homology to any other monovalent Na+(K+)/H+ antiporters but Mrp subunits have primary sequence similarity to essential redox-driven proton pumps, such as respiratory complex I and membrane-bound hydrogenases. This similarity reinforces the hypothesis that these present day redox-driven proton pumps are descended from the Mrp antiporter. The Mrp structure serves as a model to understand the yet obscure coupling mechanism between ion or electron transfer and proton translocation in this large group of proteins. In the thesis, I am presenting the purification, biochemical analysis, cryo-EM analysis and molecular structure of the Mrp complex from Anoxybacillus flavithermus solved by cryo-EM at 3.0 Å resolution. Numerous conditions were screened to purify Mrp to high homogeneity and to obtain an appropriate distribution of single particles on cryo-EM grids covered with a continuous layer of ultrathin carbon. A preferred particle orientation problem was solved by performing a tilted data collection. The activity assays showed the specific pH-dependent\r\nprofile of secondary active antiporters. The molecular structure shows that Mrp is a dimer of seven-subunit protomers with 50 trans-membrane helices each. The dimer interface is built by many short and tilted transmembrane helices, probably causing a thinning of the bacterial membrane. The surface charge distribution shows an extraordinary asymmetry within each monomer, revealing presumable proton and sodium translocation pathways. The two largest\r\nand homologous Mrp subunits MrpA and MrpD probably translocate one proton each into the cell. The sodium ion is likely being translocated in the opposite direction within the small subunits along a ladder of charged and conserved residues. Based on the structure, we propose a mechanism were the antiport activity is accomplished via electrostatic interactions between the charged cations and key charged residues. The flexible key TM helices coordinate these\r\nelectrostatic interactions, while the membrane thinning between the monomers enables the translocation of sodium across the charged membrane. The entire family of redox-driven proton pumps is likely to perform their mechanism in a likewise manner.","lang":"eng"}],"date_updated":"2026-04-08T07:23:36Z","alternative_title":["ISTA Thesis"],"department":[{"_id":"LeSa"}],"article_processing_charge":"No","oa_version":"None","_id":"8353","day":"09","ddc":["572"],"citation":{"short":"J. Steiner, Biochemical and Structural Investigation of the Mrp Antiporter, an Ancestor of Complex I, Institute of Science and Technology Austria, 2020.","mla":"Steiner, Julia. <i>Biochemical and Structural Investigation of the Mrp Antiporter, an Ancestor of Complex I</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8353\">10.15479/AT:ISTA:8353</a>.","ieee":"J. Steiner, “Biochemical and structural investigation of the Mrp antiporter, an ancestor of complex I,” Institute of Science and Technology Austria, 2020.","ista":"Steiner J. 2020. Biochemical and structural investigation of the Mrp antiporter, an ancestor of complex I. Institute of Science and Technology Austria.","chicago":"Steiner, Julia. “Biochemical and Structural Investigation of the Mrp Antiporter, an Ancestor of Complex I.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:8353\">https://doi.org/10.15479/AT:ISTA:8353</a>.","ama":"Steiner J. Biochemical and structural investigation of the Mrp antiporter, an ancestor of complex I. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8353\">10.15479/AT:ISTA:8353</a>","apa":"Steiner, J. (2020). <i>Biochemical and structural investigation of the Mrp antiporter, an ancestor of complex I</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:8353\">https://doi.org/10.15479/AT:ISTA:8353</a>"},"supervisor":[{"last_name":"Sazanov","first_name":"Leonid A","orcid":"0000-0002-0977-7989","full_name":"Sazanov, Leonid A","id":"338D39FE-F248-11E8-B48F-1D18A9856A87"}],"publisher":"Institute of Science and Technology Austria","acknowledged_ssus":[{"_id":"LifeSc"},{"_id":"EM-Fac"},{"_id":"ScienComp"}],"file":[{"date_updated":"2021-09-16T12:40:56Z","file_name":"Thesis_Julia_Steiner_pdfA.pdf","content_type":"application/pdf","checksum":"2388d7e6e7a4d364c096fa89f305c3de","file_size":117547589,"date_created":"2020-09-09T14:22:35Z","relation":"main_file","access_level":"open_access","creator":"jsteiner","file_id":"8354"},{"file_id":"8355","creator":"jsteiner","access_level":"closed","relation":"source_file","date_created":"2020-09-09T14:23:25Z","file_name":"Thesis_Julia_Steiner.docx","date_updated":"2020-09-15T08:48:37Z","file_size":223328668,"content_type":"application/vnd.openxmlformats-officedocument.wordprocessingml.document","checksum":"ba112f957b7145462d0ab79044873ee9"}],"language":[{"iso":"eng"}],"oa":1,"year":"2020","related_material":{"record":[{"status":"public","id":"8284","relation":"part_of_dissertation"}]},"page":"191","has_accepted_license":"1","doi":"10.15479/AT:ISTA:8353","month":"09","acknowledgement":"I acknowledge the scientific service units of the IST Austria for providing resources by the Life Science Facility, the Electron Microscopy Facility and the high-performance computer cluster. Special thanks to the cryo-EM specialists Valentin Hodirnau and Daniel Johann Gütl for spending many hours with me in front of the microscope and for supporting me to collect the data presented here. I also want to thank Professor Masahiro Ito for providing plasmid DNA\r\nencoding Mrp from Anoxybacillus flavithermus WK1. I am a recipient of a DOC Fellowship of the Austrian Academy of Sciences.","degree_awarded":"PhD","type":"dissertation","OA_place":"publisher","status":"public","publication_identifier":{"issn":["2663-337X"]}},{"month":"09","doi":"10.15479/AT:ISTA:8332","page":"120","has_accepted_license":"1","related_material":{"record":[{"id":"8012","status":"public","relation":"part_of_dissertation"},{"id":"8195","status":"public","relation":"part_of_dissertation"},{"status":"public","id":"133","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"160"}]},"language":[{"iso":"eng"}],"file":[{"access_level":"open_access","creator":"bkragl","file_id":"8333","content_type":"application/pdf","checksum":"26fe261550f691280bda4c454bf015c7","file_size":1348815,"date_updated":"2020-09-04T12:17:47Z","file_name":"kragl-thesis.pdf","date_created":"2020-09-04T12:17:47Z","relation":"main_file"},{"relation":"source_file","date_created":"2020-09-04T13:00:17Z","date_updated":"2020-09-04T13:00:17Z","file_name":"kragl-thesis.zip","content_type":"application/zip","checksum":"b9694ce092b7c55557122adba8337ebc","file_size":372312,"file_id":"8335","creator":"bkragl","access_level":"closed"}],"year":"2020","oa":1,"status":"public","publication_identifier":{"issn":["2663-337X"]},"OA_place":"publisher","type":"dissertation","degree_awarded":"PhD","abstract":[{"text":"Designing and verifying concurrent programs is a notoriously challenging, time consuming, and error prone task, even for experts. This is due to the sheer number of possible interleavings of a concurrent program, all of which have to be tracked and accounted for in a formal proof. Inventing an inductive invariant that captures all interleavings of a low-level implementation is theoretically possible, but practically intractable. We develop a refinement-based verification framework that provides mechanisms to simplify proof construction by decomposing the verification task into smaller subtasks.\r\n\r\nIn a first line of work, we present a foundation for refinement reasoning over structured concurrent programs. We introduce layered concurrent programs as a compact notation to represent multi-layer refinement proofs. A layered concurrent program specifies a sequence of connected concurrent programs, from most concrete to most abstract, such that common parts of different programs are written exactly once. Each program in this sequence is expressed as structured concurrent program, i.e., a program over (potentially recursive) procedures, imperative control flow, gated atomic actions, structured parallelism, and asynchronous concurrency. This is in contrast to existing refinement-based verifiers, which represent concurrent systems as flat transition relations. We present a powerful refinement proof rule that decomposes refinement checking over structured programs into modular verification conditions. Refinement checking is supported by a new form of modular, parameterized invariants, called yield invariants, and a linear permission system to enhance local reasoning.\r\n\r\nIn a second line of work, we present two new reduction-based program transformations that target asynchronous programs. These transformations reduce the number of interleavings that need to be considered, thus reducing the complexity of invariants. Synchronization simplifies the verification of asynchronous programs by introducing the fiction, for proof purposes, that asynchronous operations complete synchronously. Synchronization summarizes an asynchronous computation as immediate atomic effect. Inductive sequentialization establishes sequential reductions that captures every behavior of the original program up to reordering of coarse-grained commutative actions. A sequential reduction of a concurrent program is easy to reason about since it corresponds to a simple execution of the program in an idealized synchronous environment, where processes act in a fixed order and at the same speed.\r\n\r\nOur approach is implemented the CIVL verifier, which has been successfully used for the verification of several complex concurrent programs. In our methodology, the overall correctness of a program is established piecemeal by focusing on the invariant required for each refinement step separately. While the programmer does the creative work of specifying the chain of programs and the inductive invariant justifying each link in the chain, the tool automatically constructs the verification conditions underlying each refinement step.","lang":"eng"}],"date_updated":"2026-04-08T07:23:53Z","date_created":"2020-09-04T12:24:12Z","author":[{"orcid":"0000-0001-7745-9117","first_name":"Bernhard","last_name":"Kragl","id":"320FC952-F248-11E8-B48F-1D18A9856A87","full_name":"Kragl, Bernhard"}],"title":"Verifying concurrent programs: Refinement, synchronization, sequentialization","corr_author":"1","date_published":"2020-09-03T00:00:00Z","file_date_updated":"2020-09-04T13:00:17Z","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_status":"published","publisher":"Institute of Science and Technology Austria","ddc":["000"],"citation":{"ista":"Kragl B. 2020. Verifying concurrent programs: Refinement, synchronization, sequentialization. Institute of Science and Technology Austria.","ieee":"B. Kragl, “Verifying concurrent programs: Refinement, synchronization, sequentialization,” Institute of Science and Technology Austria, 2020.","mla":"Kragl, Bernhard. <i>Verifying Concurrent Programs: Refinement, Synchronization, Sequentialization</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8332\">10.15479/AT:ISTA:8332</a>.","short":"B. Kragl, Verifying Concurrent Programs: Refinement, Synchronization, Sequentialization, Institute of Science and Technology Austria, 2020.","apa":"Kragl, B. (2020). <i>Verifying concurrent programs: Refinement, synchronization, sequentialization</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:8332\">https://doi.org/10.15479/AT:ISTA:8332</a>","ama":"Kragl B. Verifying concurrent programs: Refinement, synchronization, sequentialization. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:8332\">10.15479/AT:ISTA:8332</a>","chicago":"Kragl, Bernhard. “Verifying Concurrent Programs: Refinement, Synchronization, Sequentialization.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:8332\">https://doi.org/10.15479/AT:ISTA:8332</a>."},"supervisor":[{"last_name":"Henzinger","first_name":"Thomas A","orcid":"0000-0002-2985-7724","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"}],"_id":"8332","article_processing_charge":"No","oa_version":"Published Version","day":"03","alternative_title":["ISTA Thesis"],"department":[{"_id":"ToHe"}]},{"date_updated":"2026-04-08T07:23:36Z","abstract":[{"text":"Multiple resistance and pH adaptation (Mrp) antiporters are multi-subunit Na+ (or K+)/H+ exchangers representing an ancestor of many essential redox-driven proton pumps, such as respiratory complex I. The mechanism of coupling between ion or electron transfer and proton translocation in this large protein family is unknown. Here, we present the structure of the Mrp complex from Anoxybacillus flavithermus solved by cryo-EM at 3.0 Å resolution. It is a dimer of seven-subunit protomers with 50 trans-membrane helices each. Surface charge distribution within each monomer is remarkably asymmetric, revealing probable proton and sodium translocation pathways. On the basis of the structure we propose a mechanism where the coupling between sodium and proton translocation is facilitated by a series of electrostatic interactions between a cation and key charged residues. This mechanism is likely to be applicable to the entire family of redox proton pumps, where electron transfer to substrates replaces cation movements.","lang":"eng"}],"project":[{"_id":"26169496-B435-11E9-9278-68D0E5697425","grant_number":"24741","name":"Revealing the functional mechanism of Mrp antiporter, an ancestor of complex I"}],"author":[{"full_name":"Steiner, Julia","id":"3BB67EB0-F248-11E8-B48F-1D18A9856A87","last_name":"Steiner","first_name":"Julia","orcid":"0000-0003-0493-3775"},{"first_name":"Leonid A","last_name":"Sazanov","orcid":"0000-0002-0977-7989","id":"338D39FE-F248-11E8-B48F-1D18A9856A87","full_name":"Sazanov, Leonid A"}],"title":"Structure and mechanism of the Mrp complex, an ancient cation/proton antiporter","date_created":"2020-08-24T06:24:04Z","external_id":{"isi":["000562123600001"],"pmid":["32735215"]},"date_published":"2020-07-31T00:00:00Z","article_number":"e59407","pmid":1,"publication_status":"published","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication":"eLife","file_date_updated":"2020-08-24T13:31:53Z","acknowledged_ssus":[{"_id":"EM-Fac"},{"_id":"LifeSc"}],"publisher":"eLife Sciences Publications","citation":{"chicago":"Steiner, Julia, and Leonid A Sazanov. “Structure and Mechanism of the Mrp Complex, an Ancient Cation/Proton Antiporter.” <i>ELife</i>. eLife Sciences Publications, 2020. <a href=\"https://doi.org/10.7554/eLife.59407\">https://doi.org/10.7554/eLife.59407</a>.","ama":"Steiner J, Sazanov LA. Structure and mechanism of the Mrp complex, an ancient cation/proton antiporter. <i>eLife</i>. 2020;9. doi:<a href=\"https://doi.org/10.7554/eLife.59407\">10.7554/eLife.59407</a>","apa":"Steiner, J., &#38; Sazanov, L. A. (2020). Structure and mechanism of the Mrp complex, an ancient cation/proton antiporter. <i>ELife</i>. eLife Sciences Publications. <a href=\"https://doi.org/10.7554/eLife.59407\">https://doi.org/10.7554/eLife.59407</a>","ieee":"J. Steiner and L. A. Sazanov, “Structure and mechanism of the Mrp complex, an ancient cation/proton antiporter,” <i>eLife</i>, vol. 9. eLife Sciences Publications, 2020.","short":"J. Steiner, L.A. Sazanov, ELife 9 (2020).","mla":"Steiner, Julia, and Leonid A. Sazanov. “Structure and Mechanism of the Mrp Complex, an Ancient Cation/Proton Antiporter.” <i>ELife</i>, vol. 9, e59407, eLife Sciences Publications, 2020, doi:<a href=\"https://doi.org/10.7554/eLife.59407\">10.7554/eLife.59407</a>.","ista":"Steiner J, Sazanov LA. 2020. Structure and mechanism of the Mrp complex, an ancient cation/proton antiporter. eLife. 9, e59407."},"quality_controlled":"1","ddc":["570"],"day":"31","article_processing_charge":"No","oa_version":"Published Version","_id":"8284","article_type":"original","scopus_import":"1","department":[{"_id":"LeSa"}],"intvolume":"         9","isi":1,"month":"07","has_accepted_license":"1","related_material":{"link":[{"description":"News on IST Homepage","relation":"press_release","url":"https://ist.ac.at/en/news/mystery-of-giant-proton-pump-solved/"}],"record":[{"id":"8353","status":"public","relation":"dissertation_contains"}]},"doi":"10.7554/eLife.59407","oa":1,"year":"2020","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file":[{"relation":"main_file","date_created":"2020-08-24T13:31:53Z","date_updated":"2020-08-24T13:31:53Z","file_name":"2020_eLife_Steiner.pdf","content_type":"application/pdf","checksum":"b3656d14d5ddbb9d26e3074eea2d0c15","file_size":7320493,"file_id":"8289","creator":"cziletti","success":1,"access_level":"open_access"}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["2050-084X"]},"status":"public","volume":9,"type":"journal_article","acknowledgement":"This research was supported by the Scientific Service Units (SSU) of IST Austria through resources provided by the Electron Microscopy Facility (EMF), the Life Science Facility (LSF) and the IST high-performance computing cluster. We thank Dr Victor-Valentin Hodirnau and Daniel Johann Gütl from IST Austria for assistance with collecting cryo-EM data. We thank Prof. Masahiro Ito (Graduate School of Life Sciences, Toyo University, Japan) for a kind provision of plasmid DNA encoding Mrp from A. flavithermus WK1. JS is a recipient of a DOC Fellowship of the Austrian Academy of Sciences at the Institute of Science and Technology, Austria."},{"publication_identifier":{"issn":["2663-337X"]},"status":"public","OA_place":"publisher","keyword":["shape reconstruction","hole manipulation","ordered complexes","Alpha complex","Wrap complex","computational topology","Bregman geometry"],"type":"dissertation","degree_awarded":"PhD","month":"02","doi":"10.15479/AT:ISTA:7460","page":"155","related_material":{"record":[{"id":"6608","status":"public","relation":"part_of_dissertation"}]},"has_accepted_license":"1","year":"2020","oa":1,"language":[{"iso":"eng"}],"file":[{"date_updated":"2020-07-14T12:47:58Z","file_name":"thesis_ist-final_noack.pdf","checksum":"1df9f8c530b443c0e63a3f2e4fde412e","file_size":76195184,"content_type":"application/pdf","date_created":"2020-02-06T14:43:54Z","relation":"main_file","access_level":"open_access","creator":"koelsboe","file_id":"7461"},{"creator":"koelsboe","access_level":"closed","file_id":"7462","description":"latex source files, figures","date_updated":"2020-07-14T12:47:58Z","file_name":"latex-files.zip","content_type":"application/x-zip-compressed","checksum":"7a52383c812b0be64d3826546509e5a4","file_size":122103715,"relation":"source_file","date_created":"2020-02-06T14:52:45Z"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","image":"/images/cc_by_nc_sa.png","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)","short":"CC BY-NC-SA (4.0)"},"publisher":"Institute of Science and Technology Austria","supervisor":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"}],"citation":{"chicago":"Ölsböck, Katharina. “The Hole System of Triangulated Shapes.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:7460\">https://doi.org/10.15479/AT:ISTA:7460</a>.","ama":"Ölsböck K. The hole system of triangulated shapes. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7460\">10.15479/AT:ISTA:7460</a>","apa":"Ölsböck, K. (2020). <i>The hole system of triangulated shapes</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:7460\">https://doi.org/10.15479/AT:ISTA:7460</a>","short":"K. Ölsböck, The Hole System of Triangulated Shapes, Institute of Science and Technology Austria, 2020.","mla":"Ölsböck, Katharina. <i>The Hole System of Triangulated Shapes</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7460\">10.15479/AT:ISTA:7460</a>.","ieee":"K. Ölsböck, “The hole system of triangulated shapes,” Institute of Science and Technology Austria, 2020.","ista":"Ölsböck K. 2020. The hole system of triangulated shapes. Institute of Science and Technology Austria."},"ddc":["514"],"day":"10","_id":"7460","article_processing_charge":"No","oa_version":"Published Version","alternative_title":["ISTA Thesis"],"department":[{"_id":"HeEd"},{"_id":"GradSch"}],"date_updated":"2026-04-08T07:23:21Z","abstract":[{"text":"Many methods for the reconstruction of shapes from sets of points produce ordered simplicial complexes, which are collections of vertices, edges, triangles, and their higher-dimensional analogues, called simplices, in which every simplex gets assigned a real value measuring its size. This thesis studies ordered simplicial complexes, with a focus on their topology, which reflects the connectedness of the represented shapes and the presence of holes. We are interested both in understanding better the structure of these complexes, as well as in developing algorithms for applications.\r\n\r\nFor the Delaunay triangulation, the most popular measure for a simplex is the radius of the smallest empty circumsphere. Based on it, we revisit Alpha and Wrap complexes and experimentally determine their probabilistic properties for random data. Also, we prove the existence of tri-partitions, propose algorithms to open and close holes, and extend the concepts from Euclidean to Bregman geometries.","lang":"eng"}],"date_created":"2020-02-06T14:56:53Z","title":"The hole system of triangulated shapes","author":[{"orcid":"0000-0002-4672-8297","last_name":"Ölsböck","first_name":"Katharina","full_name":"Ölsböck, Katharina","id":"4D4AA390-F248-11E8-B48F-1D18A9856A87"}],"date_published":"2020-02-10T00:00:00Z","corr_author":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_status":"published","file_date_updated":"2020-07-14T12:47:58Z"},{"publication_identifier":{"isbn":["9783030532871"],"issn":["0302-9743"],"eisbn":["9783030532888"],"eissn":["1611-3349"]},"status":"public","volume":12224,"type":"conference","acknowledgement":"Bernhard Kragl and Thomas A. Henzinger were supported by\r\nthe Austrian Science Fund (FWF) under grant Z211-N23 (Wittgenstein Award).","isi":1,"month":"07","page":"275-298","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"8332"}]},"has_accepted_license":"1","doi":"10.1007/978-3-030-53288-8_14","oa":1,"year":"2020","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file":[{"date_created":"2020-08-06T08:14:54Z","relation":"main_file","file_name":"2020_LNCS_Kragl.pdf","date_updated":"2020-08-06T08:14:54Z","content_type":"application/pdf","file_size":804237,"file_id":"8201","access_level":"open_access","creator":"dernst","success":1}],"language":[{"iso":"eng"}],"publisher":"Springer Nature","quality_controlled":"1","citation":{"chicago":"Kragl, Bernhard, Shaz Qadeer, and Thomas A Henzinger. “Refinement for Structured Concurrent Programs.” In <i>Computer Aided Verification</i>, 12224:275–98. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-53288-8_14\">https://doi.org/10.1007/978-3-030-53288-8_14</a>.","ama":"Kragl B, Qadeer S, Henzinger TA. Refinement for structured concurrent programs. In: <i>Computer Aided Verification</i>. Vol 12224. Springer Nature; 2020:275-298. doi:<a href=\"https://doi.org/10.1007/978-3-030-53288-8_14\">10.1007/978-3-030-53288-8_14</a>","apa":"Kragl, B., Qadeer, S., &#38; Henzinger, T. A. (2020). Refinement for structured concurrent programs. In <i>Computer Aided Verification</i> (Vol. 12224, pp. 275–298). Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-53288-8_14\">https://doi.org/10.1007/978-3-030-53288-8_14</a>","mla":"Kragl, Bernhard, et al. “Refinement for Structured Concurrent Programs.” <i>Computer Aided Verification</i>, vol. 12224, Springer Nature, 2020, pp. 275–98, doi:<a href=\"https://doi.org/10.1007/978-3-030-53288-8_14\">10.1007/978-3-030-53288-8_14</a>.","short":"B. Kragl, S. Qadeer, T.A. Henzinger, in:, Computer Aided Verification, Springer Nature, 2020, pp. 275–298.","ieee":"B. Kragl, S. Qadeer, and T. A. Henzinger, “Refinement for structured concurrent programs,” in <i>Computer Aided Verification</i>, 2020, vol. 12224, pp. 275–298.","ista":"Kragl B, Qadeer S, Henzinger TA. 2020. Refinement for structured concurrent programs. Computer Aided Verification. , LNCS, vol. 12224, 275–298."},"ddc":["000"],"day":"14","article_processing_charge":"No","oa_version":"Published Version","_id":"8195","scopus_import":"1","alternative_title":["LNCS"],"department":[{"_id":"ToHe"}],"intvolume":"     12224","date_updated":"2026-04-08T07:23:52Z","abstract":[{"text":"This paper presents a foundation for refining concurrent programs with structured control flow. The verification problem is decomposed into subproblems that aid interactive program development, proof reuse, and automation. The formalization in this paper is the basis of a new design and implementation of the Civl verifier.","lang":"eng"}],"project":[{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems","call_identifier":"FWF"}],"author":[{"id":"320FC952-F248-11E8-B48F-1D18A9856A87","full_name":"Kragl, Bernhard","orcid":"0000-0001-7745-9117","first_name":"Bernhard","last_name":"Kragl"},{"full_name":"Qadeer, Shaz","first_name":"Shaz","last_name":"Qadeer"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724","first_name":"Thomas A","last_name":"Henzinger"}],"title":"Refinement for structured concurrent programs","external_id":{"isi":["000695276000014"]},"date_created":"2020-08-03T11:45:35Z","date_published":"2020-07-14T00:00:00Z","corr_author":"1","publication_status":"published","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication":"Computer Aided Verification","file_date_updated":"2020-08-06T08:14:54Z"},{"type":"conference","publication_identifier":{"isbn":["9781450376136"]},"status":"public","oa":1,"year":"2020","language":[{"iso":"eng"}],"conference":{"location":"London, United Kingdom","end_date":"2020-06-20","name":"PLDI: Programming Language Design and Implementation","start_date":"2020-06-15"},"page":"227-242","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"8332"}]},"doi":"10.1145/3385412.3385980","month":"06","isi":1,"scopus_import":"1","department":[{"_id":"ToHe"}],"day":"01","oa_version":"Published Version","article_processing_charge":"No","_id":"8012","quality_controlled":"1","citation":{"mla":"Kragl, Bernhard, et al. “Inductive Sequentialization of Asynchronous Programs.” <i>Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation</i>, Association for Computing Machinery, 2020, pp. 227–42, doi:<a href=\"https://doi.org/10.1145/3385412.3385980\">10.1145/3385412.3385980</a>.","short":"B. Kragl, C. Enea, T.A. Henzinger, S.O. Mutluergil, S. Qadeer, in:, Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2020, pp. 227–242.","ieee":"B. Kragl, C. Enea, T. A. Henzinger, S. O. Mutluergil, and S. Qadeer, “Inductive sequentialization of asynchronous programs,” in <i>Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation</i>, London, United Kingdom, 2020, pp. 227–242.","ista":"Kragl B, Enea C, Henzinger TA, Mutluergil SO, Qadeer S. 2020. Inductive sequentialization of asynchronous programs. Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI: Programming Language Design and Implementation, 227–242.","chicago":"Kragl, Bernhard, Constantin Enea, Thomas A Henzinger, Suha Orhun Mutluergil, and Shaz Qadeer. “Inductive Sequentialization of Asynchronous Programs.” In <i>Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation</i>, 227–42. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3385412.3385980\">https://doi.org/10.1145/3385412.3385980</a>.","apa":"Kragl, B., Enea, C., Henzinger, T. A., Mutluergil, S. O., &#38; Qadeer, S. (2020). Inductive sequentialization of asynchronous programs. In <i>Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation</i> (pp. 227–242). London, United Kingdom: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3385412.3385980\">https://doi.org/10.1145/3385412.3385980</a>","ama":"Kragl B, Enea C, Henzinger TA, Mutluergil SO, Qadeer S. Inductive sequentialization of asynchronous programs. In: <i>Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation</i>. Association for Computing Machinery; 2020:227-242. doi:<a href=\"https://doi.org/10.1145/3385412.3385980\">10.1145/3385412.3385980</a>"},"publisher":"Association for Computing Machinery","publication_status":"published","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication":"Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation","date_published":"2020-06-01T00:00:00Z","project":[{"_id":"25F42A32-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z211","name":"Formal methods for the design and analysis of complex systems"}],"author":[{"first_name":"Bernhard","last_name":"Kragl","orcid":"0000-0001-7745-9117","id":"320FC952-F248-11E8-B48F-1D18A9856A87","full_name":"Kragl, Bernhard"},{"first_name":"Constantin","last_name":"Enea","full_name":"Enea, Constantin"},{"orcid":"0000-0002-2985-7724","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","id":"40876CD8-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Mutluergil, Suha Orhun","first_name":"Suha Orhun","last_name":"Mutluergil"},{"first_name":"Shaz","last_name":"Qadeer","full_name":"Qadeer, Shaz"}],"title":"Inductive sequentialization of asynchronous programs","external_id":{"isi":["000614622300016"]},"date_created":"2020-06-25T11:40:16Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1145/3385412.3385980"}],"date_updated":"2026-04-08T07:23:52Z","abstract":[{"lang":"eng","text":"Asynchronous programs are notoriously difficult to reason about because they spawn computation tasks which take effect asynchronously in a nondeterministic way. Devising inductive invariants for such programs requires understanding and stating complex relationships between an unbounded number of computation tasks in arbitrarily long executions. In this paper, we introduce inductive sequentialization, a new proof rule that sidesteps this complexity via a sequential reduction, a sequential program that captures every behavior of the original program up to reordering of coarse-grained commutative actions. A sequential reduction of a concurrent program is easy to reason about since it corresponds to a simple execution of the program in an idealized synchronous environment, where processes act in a fixed order and at the same speed. We have implemented and integrated our proof rule in the CIVL verifier, allowing us to provably derive fine-grained implementations of asynchronous programs. We have successfully applied our proof rule to a diverse set of message-passing protocols, including leader election protocols, two-phase commit, and Paxos."}]},{"oa_version":"Published Version","article_processing_charge":"No","_id":"7896","day":"25","alternative_title":["ISTA Thesis"],"department":[{"_id":"KrPi"}],"publisher":"Institute of Science and Technology Austria","ddc":["000"],"supervisor":[{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"}],"citation":{"ista":"Kamath Hosdurg C. 2020. On the average-case hardness of total search problems. Institute of Science and Technology Austria.","ieee":"C. Kamath Hosdurg, “On the average-case hardness of total search problems,” Institute of Science and Technology Austria, 2020.","mla":"Kamath Hosdurg, Chethan. <i>On the Average-Case Hardness of Total Search Problems</i>. Institute of Science and Technology Austria, 2020, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7896\">10.15479/AT:ISTA:7896</a>.","short":"C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems, Institute of Science and Technology Austria, 2020.","apa":"Kamath Hosdurg, C. (2020). <i>On the average-case hardness of total search problems</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:7896\">https://doi.org/10.15479/AT:ISTA:7896</a>","ama":"Kamath Hosdurg C. On the average-case hardness of total search problems. 2020. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:7896\">10.15479/AT:ISTA:7896</a>","chicago":"Kamath Hosdurg, Chethan. “On the Average-Case Hardness of Total Search Problems.” Institute of Science and Technology Austria, 2020. <a href=\"https://doi.org/10.15479/AT:ISTA:7896\">https://doi.org/10.15479/AT:ISTA:7896</a>."},"corr_author":"1","date_published":"2020-05-25T00:00:00Z","file_date_updated":"2020-07-14T12:48:04Z","publication_status":"published","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","abstract":[{"text":"A search problem lies in the complexity class FNP if a solution to the given instance of the problem can be verified efficiently. The complexity class TFNP consists of all search problems in FNP that are total in the sense that a solution is guaranteed to exist. TFNP contains a host of interesting problems from fields such as algorithmic game theory, computational topology, number theory and combinatorics. Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead, one studies its syntactic subclasses which are defined based on the combinatorial principle used to argue totality. Of particular interest is the subclass PPAD, which contains important problems\r\nlike computing Nash equilibrium for bimatrix games and computational counterparts of several fixed-point theorems as complete. In the thesis, we undertake the study of averagecase hardness of TFNP, and in particular its subclass PPAD.\r\nAlmost nothing was known about average-case hardness of PPAD before a series of recent results showed how to achieve it using a cryptographic primitive called program obfuscation.\r\nHowever, it is currently not known how to construct program obfuscation from standard cryptographic assumptions. Therefore, it is desirable to relax the assumption under which average-case hardness of PPAD can be shown. In the thesis we take a step in this direction. First, we show that assuming the (average-case) hardness of a numbertheoretic\r\nproblem related to factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average in the random-oracle model. Then we strengthen this result to show that the average-case hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform, a well-known technique used to compile a public-coin interactive protocol into a non-interactive one. As a corollary, we obtain average-case hardness for PPAD in the random-oracle model assuming the worst-case hardness of #SAT. Moreover, the above results can all be strengthened to obtain average-case hardness for the class CLS ⊆ PPAD.\r\nOur main technical contribution is constructing incrementally-verifiable procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable, we mean that every intermediate state of the computation includes a proof of its correctness, and the proof can be updated and verified in polynomial time. Previous constructions of such procedures relied on strong, non-standard assumptions. Instead, we introduce a technique called recursive proof-merging to obtain the same from weaker assumptions. ","lang":"eng"}],"date_updated":"2026-04-08T07:24:42Z","author":[{"id":"4BD3F30E-F248-11E8-B48F-1D18A9856A87","full_name":"Kamath Hosdurg, Chethan","orcid":"0009-0006-6812-7317","first_name":"Chethan","last_name":"Kamath Hosdurg"}],"title":"On the average-case hardness of total search problems","date_created":"2020-05-26T14:08:55Z","project":[{"grant_number":"259668","name":"Provable Security for Physical Cryptography","call_identifier":"FP7","_id":"258C570E-B435-11E9-9278-68D0E5697425"},{"_id":"258AA5B2-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"682815","name":"Teaching Old Crypto New Tricks"}],"degree_awarded":"PhD","type":"dissertation","ec_funded":1,"status":"public","publication_identifier":{"issn":["2663-337X"]},"OA_place":"publisher","page":"126","related_material":{"record":[{"relation":"part_of_dissertation","id":"6677","status":"public"}]},"has_accepted_license":"1","doi":"10.15479/AT:ISTA:7896","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"language":[{"iso":"eng"}],"file":[{"file_id":"7897","access_level":"open_access","creator":"dernst","date_created":"2020-05-26T14:08:13Z","relation":"main_file","checksum":"b39e2e1c376f5819b823fb7077491c64","content_type":"application/pdf","file_size":1622742,"date_updated":"2020-07-14T12:48:04Z","file_name":"2020_Thesis_Kamath.pdf"},{"file_id":"7898","creator":"dernst","access_level":"closed","relation":"source_file","date_created":"2020-05-26T14:08:23Z","file_name":"Thesis_Kamath.zip","date_updated":"2020-07-14T12:48:04Z","content_type":"application/x-zip-compressed","checksum":"8b26ba729c1a85ac6bea775f5d73cdc7","file_size":15301529}],"oa":1,"year":"2020","month":"05"}]