[{"related_material":{"record":[{"relation":"part_of_dissertation","id":"7435","status":"deleted"},{"relation":"part_of_dissertation","status":"public","id":"7481"},{"status":"public","id":"9416","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","status":"public","id":"7479"}]},"language":[{"iso":"eng"}],"file":[{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"9419","checksum":"4f0abe64114cfed264f9d36e8d1197e3","success":1,"date_updated":"2021-05-24T11:22:29Z","file_size":2673905,"creator":"bphuong","date_created":"2021-05-24T11:22:29Z","file_name":"mph-thesis-v519-pdfimages.pdf"},{"access_level":"closed","relation":"source_file","content_type":"application/zip","checksum":"f5699e876bc770a9b0df8345a77720a2","file_id":"9420","creator":"bphuong","date_updated":"2021-05-24T11:56:02Z","file_size":92995100,"date_created":"2021-05-24T11:56:02Z","file_name":"thesis.zip"}],"publication_status":"published","degree_awarded":"PhD","publication_identifier":{"issn":["2663-337X"]},"month":"05","alternative_title":["ISTA Thesis"],"oa_version":"Published Version","acknowledged_ssus":[{"_id":"ScienComp"},{"_id":"CampIT"},{"_id":"E-Lib"}],"abstract":[{"text":"Deep learning is best known for its empirical success across a wide range of applications\r\nspanning computer vision, natural language processing and speech. Of equal significance,\r\nthough perhaps less known, are its ramifications for learning theory: deep networks have\r\nbeen observed to perform surprisingly well in the high-capacity regime, aka the overfitting\r\nor underspecified regime. Classically, this regime on the far right of the bias-variance curve\r\nis associated with poor generalisation; however, recent experiments with deep networks\r\nchallenge this view.\r\n\r\nThis thesis is devoted to investigating various aspects of underspecification in deep learning.\r\nFirst, we argue that deep learning models are underspecified on two levels: a) any given\r\ntraining dataset can be fit by many different functions, and b) any given function can be\r\nexpressed by many different parameter configurations. We refer to the second kind of\r\nunderspecification as parameterisation redundancy and we precisely characterise its extent.\r\nSecond, we characterise the implicit criteria (the inductive bias) that guide learning in the\r\nunderspecified regime. Specifically, we consider a nonlinear but tractable classification\r\nsetting, and show that given the choice, neural networks learn classifiers with a large margin.\r\nThird, we consider learning scenarios where the inductive bias is not by itself sufficient to\r\ndeal with underspecification. We then study different ways of ‘tightening the specification’: i)\r\nIn the setting of representation learning with variational autoencoders, we propose a hand-\r\ncrafted regulariser based on mutual information. ii) In the setting of binary classification, we\r\nconsider soft-label (real-valued) supervision. We derive a generalisation bound for linear\r\nnetworks supervised in this way and verify that soft labels facilitate fast learning. Finally, we\r\nexplore an application of soft-label supervision to the training of multi-exit models.","lang":"eng"}],"file_date_updated":"2021-05-24T11:56:02Z","department":[{"_id":"GradSch"},{"_id":"ChLa"}],"ddc":["000"],"date_updated":"2023-09-08T11:11:12Z","supervisor":[{"first_name":"Christoph","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8622-7887","full_name":"Lampert, Christoph","last_name":"Lampert"}],"status":"public","type":"dissertation","_id":"9418","date_created":"2021-05-24T13:06:23Z","date_published":"2021-05-30T00:00:00Z","doi":"10.15479/AT:ISTA:9418","page":"125","day":"30","year":"2021","has_accepted_license":"1","oa":1,"publisher":"Institute of Science and Technology Austria","title":"Underspecification in deep learning","article_processing_charge":"No","author":[{"first_name":"Phuong","id":"3EC6EE64-F248-11E8-B48F-1D18A9856A87","full_name":"Bui Thi Mai, Phuong","last_name":"Bui Thi Mai"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Phuong M. 2021. Underspecification in deep learning. Institute of Science and Technology Austria.","chicago":"Phuong, Mary. “Underspecification in Deep Learning.” Institute of Science and Technology Austria, 2021. https://doi.org/10.15479/AT:ISTA:9418.","ieee":"M. Phuong, “Underspecification in deep learning,” Institute of Science and Technology Austria, 2021.","short":"M. Phuong, Underspecification in Deep Learning, Institute of Science and Technology Austria, 2021.","ama":"Phuong M. Underspecification in deep learning. 2021. doi:10.15479/AT:ISTA:9418","apa":"Phuong, M. (2021). Underspecification in deep learning. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:9418","mla":"Phuong, Mary. Underspecification in Deep Learning. Institute of Science and Technology Austria, 2021, doi:10.15479/AT:ISTA:9418."}},{"_id":"14278","article_number":"2111.12171","type":"preprint","status":"public","date_updated":"2023-09-15T06:44:00Z","citation":{"apa":"Koval, I. (n.d.). Local strong Birkhoff conjecture and local spectral rigidity of almost every ellipse. arXiv. https://doi.org/10.48550/ARXIV.2111.12171","ama":"Koval I. Local strong Birkhoff conjecture and local spectral rigidity of almost every ellipse. arXiv. doi:10.48550/ARXIV.2111.12171","ieee":"I. Koval, “Local strong Birkhoff conjecture and local spectral rigidity of almost every ellipse,” arXiv. .","short":"I. Koval, ArXiv (n.d.).","mla":"Koval, Illya. “Local Strong Birkhoff Conjecture and Local Spectral Rigidity of Almost Every Ellipse.” ArXiv, 2111.12171, doi:10.48550/ARXIV.2111.12171.","ista":"Koval I. Local strong Birkhoff conjecture and local spectral rigidity of almost every ellipse. arXiv, 2111.12171.","chicago":"Koval, Illya. “Local Strong Birkhoff Conjecture and Local Spectral Rigidity of Almost Every Ellipse.” ArXiv, n.d. https://doi.org/10.48550/ARXIV.2111.12171."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","external_id":{"arxiv":["2111.12171"]},"article_processing_charge":"No","author":[{"id":"2eed1f3b-896a-11ed-bdf8-93c7c4bf159e","first_name":"Illya","full_name":"Koval, Illya","last_name":"Koval"}],"department":[{"_id":"GradSch"}],"title":"Local strong Birkhoff conjecture and local spectral rigidity of almost every ellipse","abstract":[{"lang":"eng","text":"The Birkhoff conjecture says that the boundary of a strictly convex integrable billiard table is necessarily an ellipse. In this article, we consider a stronger notion of integrability, namely, integrability close to the boundary, and prove a local version of this conjecture: a small perturbation of almost every ellipse that preserves integrability near the boundary, is itself an ellipse. We apply this result to study local spectral rigidity of ellipses using the connection between the wave trace of the Laplacian and the dynamics near the boundary and establish rigidity for almost all of them."}],"oa_version":"Preprint","oa":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2111.12171","open_access":"1"}],"month":"11","publication_status":"submitted","year":"2021","language":[{"iso":"eng"}],"publication":"arXiv","day":"23","date_created":"2023-09-06T08:35:43Z","doi":"10.48550/ARXIV.2111.12171","date_published":"2021-11-23T00:00:00Z"},{"date_updated":"2023-09-19T09:59:54Z","supervisor":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"}],"ddc":["000"],"department":[{"_id":"GradSch"},{"_id":"KrCh"}],"file_date_updated":"2021-11-09T09:00:50Z","_id":"10199","type":"dissertation","keyword":["concurrency","verification","model checking"],"status":"public","publication_status":"published","degree_awarded":"PhD","publication_identifier":{"issn":["2663-337X"]},"language":[{"iso":"eng"}],"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"4f412a1ee60952221b499a4b1268df35","file_id":"10225","creator":"vtoman","date_updated":"2021-11-08T14:12:22Z","file_size":2915234,"date_created":"2021-11-08T14:12:22Z","file_name":"toman_th_final.pdf"},{"access_level":"closed","relation":"source_file","content_type":"application/zip","checksum":"9584943f99127be2dd2963f6784c37d4","file_id":"10226","creator":"vtoman","date_updated":"2021-11-09T09:00:50Z","file_size":8616056,"date_created":"2021-11-08T14:12:46Z","file_name":"toman_thesis.zip"}],"ec_funded":1,"related_material":{"record":[{"relation":"part_of_dissertation","id":"10190","status":"public"},{"relation":"part_of_dissertation","id":"10191","status":"public"},{"id":"9987","status":"public","relation":"part_of_dissertation"},{"relation":"part_of_dissertation","id":"141","status":"public"}]},"abstract":[{"text":"The design and verification of concurrent systems remains an open challenge due to the non-determinism that arises from the inter-process communication. In particular, concurrent programs are notoriously difficult both to be written correctly and to be analyzed formally, as complex thread interaction has to be accounted for. The difficulties are further exacerbated when concurrent programs get executed on modern-day hardware, which contains various buffering and caching mechanisms for efficiency reasons. This causes further subtle non-determinism, which can often produce very unintuitive behavior of the concurrent programs. Model checking is at the forefront of tackling the verification problem, where the task is to decide, given as input a concurrent system and a desired property, whether the system satisfies the property. The inherent state-space explosion problem in model checking of concurrent systems causes naïve explicit methods not to scale, thus more inventive methods are required. One such method is stateless model checking (SMC), which explores in memory-efficient manner the program executions rather than the states of the program. State-of-the-art SMC is typically coupled with partial order reduction (POR) techniques, which argue that certain executions provably produce identical system behavior, thus limiting the amount of executions one needs to explore in order to cover all possible behaviors. Another method to tackle the state-space explosion is symbolic model checking, where the considered techniques operate on a succinct implicit representation of the input system rather than explicitly accessing the system. In this thesis we present new techniques for verification of concurrent systems. We present several novel POR methods for SMC of concurrent programs under various models of semantics, some of which account for write-buffering mechanisms. Additionally, we present novel algorithms for symbolic model checking of finite-state concurrent systems, where the desired property of the systems is to ensure a formally defined notion of fairness.","lang":"eng"}],"acknowledged_ssus":[{"_id":"SSU"}],"oa_version":"Published Version","alternative_title":["ISTA Thesis"],"month":"10","citation":{"ista":"Toman V. 2021. Improved verification techniques for concurrent systems. Institute of Science and Technology Austria.","chicago":"Toman, Viktor. “Improved Verification Techniques for Concurrent Systems.” Institute of Science and Technology Austria, 2021. https://doi.org/10.15479/at:ista:10199.","ieee":"V. Toman, “Improved verification techniques for concurrent systems,” Institute of Science and Technology Austria, 2021.","short":"V. Toman, Improved Verification Techniques for Concurrent Systems, Institute of Science and Technology Austria, 2021.","apa":"Toman, V. (2021). Improved verification techniques for concurrent systems. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:10199","ama":"Toman V. Improved verification techniques for concurrent systems. 2021. doi:10.15479/at:ista:10199","mla":"Toman, Viktor. Improved Verification Techniques for Concurrent Systems. Institute of Science and Technology Austria, 2021, doi:10.15479/at:ista:10199."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","article_processing_charge":"No","author":[{"full_name":"Toman, Viktor","orcid":"0000-0001-9036-063X","last_name":"Toman","id":"3AF3DA7C-F248-11E8-B48F-1D18A9856A87","first_name":"Viktor"}],"title":"Improved verification techniques for concurrent systems","project":[{"call_identifier":"H2020","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","grant_number":"665385","name":"International IST Doctoral Program"},{"_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S11402-N23"},{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"},{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}],"year":"2021","has_accepted_license":"1","day":"31","page":"166","date_created":"2021-10-29T20:09:01Z","doi":"10.15479/at:ista:10199","date_published":"2021-10-31T00:00:00Z","oa":1,"publisher":"Institute of Science and Technology Austria"},{"article_number":"6972","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"mla":"Patxot, Marion, et al. “Probabilistic Inference of the Genetic Architecture Underlying Functional Enrichment of Complex Traits.” Nature Communications, vol. 12, no. 1, 6972, Springer Nature, 2021, doi:10.1038/s41467-021-27258-9.","apa":"Patxot, M., Trejo Banos, D., Kousathanas, A., Orliac, E. J., Ojavee, S. E., Moser, G., … Robinson, M. R. (2021). Probabilistic inference of the genetic architecture underlying functional enrichment of complex traits. Nature Communications. Springer Nature. https://doi.org/10.1038/s41467-021-27258-9","ama":"Patxot M, Trejo Banos D, Kousathanas A, et al. Probabilistic inference of the genetic architecture underlying functional enrichment of complex traits. Nature Communications. 2021;12(1). doi:10.1038/s41467-021-27258-9","short":"M. Patxot, D. Trejo Banos, A. Kousathanas, E.J. Orliac, S.E. Ojavee, G. Moser, J. Sidorenko, Z. Kutalik, R. Magi, P.M. Visscher, L. Ronnegard, M.R. Robinson, Nature Communications 12 (2021).","ieee":"M. Patxot et al., “Probabilistic inference of the genetic architecture underlying functional enrichment of complex traits,” Nature Communications, vol. 12, no. 1. Springer Nature, 2021.","chicago":"Patxot, Marion, Daniel Trejo Banos, Athanasios Kousathanas, Etienne J Orliac, Sven E Ojavee, Gerhard Moser, Julia Sidorenko, et al. “Probabilistic Inference of the Genetic Architecture Underlying Functional Enrichment of Complex Traits.” Nature Communications. Springer Nature, 2021. https://doi.org/10.1038/s41467-021-27258-9.","ista":"Patxot M, Trejo Banos D, Kousathanas A, Orliac EJ, Ojavee SE, Moser G, Sidorenko J, Kutalik Z, Magi R, Visscher PM, Ronnegard L, Robinson MR. 2021. Probabilistic inference of the genetic architecture underlying functional enrichment of complex traits. Nature Communications. 12(1), 6972."},"title":"Probabilistic inference of the genetic architecture underlying functional enrichment of complex traits","author":[{"first_name":"Marion","last_name":"Patxot","full_name":"Patxot, Marion"},{"full_name":"Trejo Banos, Daniel","last_name":"Trejo Banos","first_name":"Daniel"},{"first_name":"Athanasios","last_name":"Kousathanas","full_name":"Kousathanas, Athanasios"},{"first_name":"Etienne J","full_name":"Orliac, Etienne J","last_name":"Orliac"},{"first_name":"Sven E","last_name":"Ojavee","full_name":"Ojavee, Sven E"},{"first_name":"Gerhard","full_name":"Moser, Gerhard","last_name":"Moser"},{"last_name":"Sidorenko","full_name":"Sidorenko, Julia","first_name":"Julia"},{"full_name":"Kutalik, Zoltan","last_name":"Kutalik","first_name":"Zoltan"},{"full_name":"Magi, Reedik","last_name":"Magi","first_name":"Reedik"},{"first_name":"Peter M","last_name":"Visscher","full_name":"Visscher, Peter M"},{"first_name":"Lars","full_name":"Ronnegard, Lars","last_name":"Ronnegard"},{"id":"E5D42276-F5DA-11E9-8E24-6303E6697425","first_name":"Matthew Richard","last_name":"Robinson","full_name":"Robinson, Matthew Richard","orcid":"0000-0001-8982-8813"}],"external_id":{"isi":["000724450600023"]},"article_processing_charge":"No","acknowledgement":"This project was funded by an SNSF Eccellenza Grant to MRR (PCEGP3-181181), and by core funding from the Institute of Science and Technology Austria. We would like to thank the participants of the cohort studies, and the Ecole Polytechnique Federal Lausanne (EPFL) SCITAS for their excellent compute resources, their generosity with their time and the kindness of their support. P.M.V. acknowledges funding from the Australian National Health and Medical Research Council (1113400) and the Australian Research Council (FL180100072). L.R. acknowledges funding from the Kjell & Märta Beijer Foundation (Stockholm, Sweden). We also would like to acknowledge Simone Rubinacci, Oliver Delanau, Alexander Terenin, Eleonora Porcu, and Mike Goddard for their useful comments and suggestions.","quality_controlled":"1","publisher":"Springer Nature","oa":1,"day":"30","publication":"Nature Communications","isi":1,"has_accepted_license":"1","year":"2021","date_published":"2021-11-30T00:00:00Z","doi":"10.1038/s41467-021-27258-9","date_created":"2020-09-17T10:52:38Z","_id":"8429","status":"public","type":"journal_article","article_type":"original","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"ddc":["610"],"date_updated":"2023-09-26T10:36:14Z","department":[{"_id":"MaRo"}],"file_date_updated":"2021-12-06T07:47:11Z","oa_version":"Published Version","abstract":[{"text":"We develop a Bayesian model (BayesRR-RC) that provides robust SNP-heritability estimation, an alternative to marker discovery, and accurate genomic prediction, taking 22 seconds per iteration to estimate 8.4 million SNP-effects and 78 SNP-heritability parameters in the UK Biobank. We find that only ≤10% of the genetic variation captured for height, body mass index, cardiovascular disease, and type 2 diabetes is attributable to proximal regulatory regions within 10kb upstream of genes, while 12-25% is attributed to coding regions, 32–44% to introns, and 22-28% to distal 10-500kb upstream regions. Up to 24% of all cis and coding regions of each chromosome are associated with each trait, with over 3,100 independent exonic and intronic regions and over 5,400 independent regulatory regions having ≥95% probability of contributing ≥0.001% to the genetic variance of these four traits. Our open-source software (GMRM) provides a scalable alternative to current approaches for biobank data.","lang":"eng"}],"month":"11","intvolume":" 12","scopus_import":"1","file":[{"date_created":"2021-12-06T07:47:11Z","file_name":"2021_NatComm_Paxtot.pdf","date_updated":"2021-12-06T07:47:11Z","file_size":6519771,"creator":"cchlebak","file_id":"10419","checksum":"384681be17aff902c149a48f52d13d4f","success":1,"content_type":"application/pdf","access_level":"open_access","relation":"main_file"}],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["2041-1723"]},"publication_status":"published","related_material":{"record":[{"id":"13063","status":"public","relation":"research_data"}]},"volume":12,"issue":"1"},{"project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"},{"_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"840605","name":"Coordination in constrained and natural distributed systems"}],"external_id":{"arxiv":["2005.07637"]},"article_processing_charge":"No","author":[{"first_name":"Klaus-Tycho","last_name":"Foerster","full_name":"Foerster, Klaus-Tycho"},{"id":"C5402D42-15BC-11E9-A202-CA2BE6697425","first_name":"Janne","full_name":"Korhonen, Janne","last_name":"Korhonen"},{"first_name":"Ami","last_name":"Paz","full_name":"Paz, Ami"},{"full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","last_name":"Rybicki","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"}],"title":"Input-dynamic distributed algorithms for communication networks","citation":{"ista":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic distributed algorithms for communication networks. Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. SIGMETRICS: International Conference on Measurement and Modeling of Computer Systems, 71–72.","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” In Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, 71–72. Association for Computing Machinery, 2021. https://doi.org/10.1145/3410220.3453923.","ama":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed algorithms for communication networks. In: Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. Association for Computing Machinery; 2021:71-72. doi:10.1145/3410220.3453923","apa":"Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., & Schmid, S. (2021). Input-dynamic distributed algorithms for communication networks. In Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems (pp. 71–72). Virtual, Online: Association for Computing Machinery. https://doi.org/10.1145/3410220.3453923","short":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, in:, Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery, 2021, pp. 71–72.","ieee":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic distributed algorithms for communication networks,” in Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Virtual, Online, 2021, pp. 71–72.","mla":"Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication Networks.” Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery, 2021, pp. 71–72, doi:10.1145/3410220.3453923."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"quality_controlled":"1","publisher":"Association for Computing Machinery","acknowledgement":"We thank Jukka Suomela for discussions. We also thank our shepherd Mohammad Hajiesmaili and the reviewers for their time and suggestions on how to improve the paper. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML), from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie grant agreement No. 840605, from the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024, and from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N.","page":"71-72","date_created":"2022-03-18T08:48:41Z","date_published":"2021-05-01T00:00:00Z","doi":"10.1145/3410220.3453923","year":"2021","publication":"Abstract Proceedings of the 2021 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems","day":"01","conference":{"end_date":"2021-06-18","location":"Virtual, Online","start_date":"2021-06-14","name":"SIGMETRICS: International Conference on Measurement and Modeling of Computer Systems"},"type":"conference","status":"public","_id":"10854","department":[{"_id":"DaAl"}],"date_updated":"2023-09-26T10:40:55Z","main_file_link":[{"url":"https://arxiv.org/abs/2005.07637","open_access":"1"}],"scopus_import":"1","month":"05","abstract":[{"lang":"eng","text":"Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner?\r\nTo address this question, we define the batch dynamic CONGEST model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labelled graph under batch changes. We investigate, when a batch of alpha edge label changes arrive, - how much time as a function of alpha we need to update an existing solution, and - how much information the nodes have to keep in local memory between batches in order to update the solution quickly.\r\nOur work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. The diverse time complexity of our model spans from constant time, through time polynomial in alpha, and to alpha time, which we show to be enough for any task."}],"oa_version":"Preprint","ec_funded":1,"related_material":{"record":[{"id":"10855","status":"public","relation":"extended_version"}]},"publication_status":"published","publication_identifier":{"isbn":["9781450380720"]},"language":[{"iso":"eng"}]}]