[{"file_date_updated":"2020-07-14T12:47:49Z","department":[{"_id":"UlWa"}],"date_updated":"2023-09-07T13:18:26Z","ddc":["514"],"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)"},"article_type":"original","type":"journal_article","status":"public","_id":"7093","volume":10,"issue":"2","related_material":{"record":[{"relation":"earlier_version","id":"285","status":"public"},{"status":"public","id":"8032","relation":"part_of_dissertation"}]},"publication_status":"published","publication_identifier":{"issn":["1920-180X"]},"language":[{"iso":"eng"}],"file":[{"access_level":"open_access","relation":"main_file","content_type":"application/pdf","file_id":"7094","checksum":"c872d590d38d538404782bca20c4c3f5","creator":"khuszar","date_updated":"2020-07-14T12:47:49Z","file_size":857590,"date_created":"2019-11-23T12:35:16Z","file_name":"479-1917-1-PB.pdf"}],"intvolume":" 10","month":"11","abstract":[{"text":"In graph theory, as well as in 3-manifold topology, there exist several width-type parameters to describe how \"simple\" or \"thin\" a given graph or 3-manifold is. These parameters, such as pathwidth or treewidth for graphs, or the concept of thin position for 3-manifolds, play an important role when studying algorithmic problems; in particular, there is a variety of problems in computational 3-manifold topology - some of them known to be computationally hard in general - that become solvable in polynomial time as soon as the dual graph of the input triangulation has bounded treewidth.\r\nIn view of these algorithmic results, it is natural to ask whether every 3-manifold admits a triangulation of bounded treewidth. We show that this is not the case, i.e., that there exists an infinite family of closed 3-manifolds not admitting triangulations of bounded pathwidth or treewidth (the latter implies the former, but we present two separate proofs).\r\nWe derive these results from work of Agol, of Scharlemann and Thompson, and of Scharlemann, Schultens and Saito by exhibiting explicit connections between the topology of a 3-manifold M on the one hand and width-type parameters of the dual graphs of triangulations of M on the other hand, answering a question that had been raised repeatedly by researchers in computational 3-manifold topology. In particular, we show that if a closed, orientable, irreducible, non-Haken 3-manifold M has a triangulation of treewidth (resp. pathwidth) k then the Heegaard genus of M is at most 18(k+1) (resp. 4(3k+1)).","lang":"eng"}],"oa_version":"Published Version","article_processing_charge":"No","external_id":{"arxiv":["1712.00434"]},"author":[{"full_name":"Huszár, Kristóf","orcid":"0000-0002-5445-5057","last_name":"Huszár","first_name":"Kristóf","id":"33C26278-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Jonathan","last_name":"Spreer","full_name":"Spreer, Jonathan"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","last_name":"Wagner"}],"title":"On the treewidth of triangulated 3-manifolds","citation":{"ista":"Huszár K, Spreer J, Wagner U. 2019. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 10(2), 70–98.","chicago":"Huszár, Kristóf, Jonathan Spreer, and Uli Wagner. “On the Treewidth of Triangulated 3-Manifolds.” Journal of Computational Geometry. Computational Geometry Laborartoy, 2019. https://doi.org/10.20382/JOGC.V10I2A5.","apa":"Huszár, K., Spreer, J., & Wagner, U. (2019). On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. Computational Geometry Laborartoy. https://doi.org/10.20382/JOGC.V10I2A5","ama":"Huszár K, Spreer J, Wagner U. On the treewidth of triangulated 3-manifolds. Journal of Computational Geometry. 2019;10(2):70–98. doi:10.20382/JOGC.V10I2A5","short":"K. Huszár, J. Spreer, U. Wagner, Journal of Computational Geometry 10 (2019) 70–98.","ieee":"K. Huszár, J. Spreer, and U. Wagner, “On the treewidth of triangulated 3-manifolds,” Journal of Computational Geometry, vol. 10, no. 2. Computational Geometry Laborartoy, pp. 70–98, 2019.","mla":"Huszár, Kristóf, et al. “On the Treewidth of Triangulated 3-Manifolds.” Journal of Computational Geometry, vol. 10, no. 2, Computational Geometry Laborartoy, 2019, pp. 70–98, doi:10.20382/JOGC.V10I2A5."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","page":"70–98","date_created":"2019-11-23T12:14:09Z","date_published":"2019-11-01T00:00:00Z","doi":"10.20382/JOGC.V10I2A5","year":"2019","has_accepted_license":"1","publication":"Journal of Computational Geometry","day":"01","oa":1,"publisher":"Computational Geometry Laborartoy","quality_controlled":"1"},{"isi":1,"has_accepted_license":"1","year":"2019","day":"17","publication":"Nature Communications","date_published":"2019-12-17T00:00:00Z","doi":"10.1038/s41467-019-13702-4","date_created":"2019-12-20T12:22:57Z","quality_controlled":"1","publisher":"Springer Nature","oa":1,"citation":{"ista":"Dos Santos Caldas PR, Lopez Pelegrin MD, Pearce DJG, Budanur NB, Brugués J, Loose M. 2019. Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA. Nature Communications. 10, 5744.","chicago":"Dos Santos Caldas, Paulo R, Maria D Lopez Pelegrin, Daniel J. G. Pearce, Nazmi B Budanur, Jan Brugués, and Martin Loose. “Cooperative Ordering of Treadmilling Filaments in Cytoskeletal Networks of FtsZ and Its Crosslinker ZapA.” Nature Communications. Springer Nature, 2019. https://doi.org/10.1038/s41467-019-13702-4.","apa":"Dos Santos Caldas, P. R., Lopez Pelegrin, M. D., Pearce, D. J. G., Budanur, N. B., Brugués, J., & Loose, M. (2019). Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA. Nature Communications. Springer Nature. https://doi.org/10.1038/s41467-019-13702-4","ama":"Dos Santos Caldas PR, Lopez Pelegrin MD, Pearce DJG, Budanur NB, Brugués J, Loose M. Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA. Nature Communications. 2019;10. doi:10.1038/s41467-019-13702-4","short":"P.R. Dos Santos Caldas, M.D. Lopez Pelegrin, D.J.G. Pearce, N.B. Budanur, J. Brugués, M. Loose, Nature Communications 10 (2019).","ieee":"P. R. Dos Santos Caldas, M. D. Lopez Pelegrin, D. J. G. Pearce, N. B. Budanur, J. Brugués, and M. Loose, “Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA,” Nature Communications, vol. 10. Springer Nature, 2019.","mla":"Dos Santos Caldas, Paulo R., et al. “Cooperative Ordering of Treadmilling Filaments in Cytoskeletal Networks of FtsZ and Its Crosslinker ZapA.” Nature Communications, vol. 10, 5744, Springer Nature, 2019, doi:10.1038/s41467-019-13702-4."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"full_name":"Dos Santos Caldas, Paulo R","orcid":"0000-0001-6730-4461","last_name":"Dos Santos Caldas","first_name":"Paulo R","id":"38FCDB4C-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Maria D","id":"319AA9CE-F248-11E8-B48F-1D18A9856A87","full_name":"Lopez Pelegrin, Maria D","last_name":"Lopez Pelegrin"},{"first_name":"Daniel J. G.","full_name":"Pearce, Daniel J. G.","last_name":"Pearce"},{"id":"3EA1010E-F248-11E8-B48F-1D18A9856A87","first_name":"Nazmi B","last_name":"Budanur","full_name":"Budanur, Nazmi B","orcid":"0000-0003-0423-5010"},{"full_name":"Brugués, Jan","last_name":"Brugués","first_name":"Jan"},{"id":"462D4284-F248-11E8-B48F-1D18A9856A87","first_name":"Martin","last_name":"Loose","orcid":"0000-0001-7309-9724","full_name":"Loose, Martin"}],"article_processing_charge":"No","external_id":{"isi":["000503009300001"]},"title":"Cooperative ordering of treadmilling filaments in cytoskeletal networks of FtsZ and its crosslinker ZapA","article_number":"5744","project":[{"name":"Self-Organization of the Bacterial Cell","grant_number":"679239","call_identifier":"H2020","_id":"2595697A-B435-11E9-9278-68D0E5697425"},{"_id":"260D98C8-B435-11E9-9278-68D0E5697425","name":"Reconstitution of Bacterial Cell Division Using Purified Components"}],"publication_identifier":{"issn":["2041-1723"]},"publication_status":"published","file":[{"checksum":"a1b44b427ba341383197790d0e8789fa","file_id":"7208","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"2019_NatureComm_Caldas.pdf","date_created":"2019-12-23T07:34:56Z","file_size":8488733,"date_updated":"2020-07-14T12:47:53Z","creator":"dernst"}],"language":[{"iso":"eng"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"8358","status":"public"}]},"volume":10,"ec_funded":1,"abstract":[{"lang":"eng","text":"During bacterial cell division, the tubulin-homolog FtsZ forms a ring-like structure at the center of the cell. This Z-ring not only organizes the division machinery, but treadmilling of FtsZ filaments was also found to play a key role in distributing proteins at the division site. What regulates the architecture, dynamics and stability of the Z-ring is currently unknown, but FtsZ-associated proteins are known to play an important role. Here, using an in vitro reconstitution approach, we studied how the well-conserved protein ZapA affects FtsZ treadmilling and filament organization into large-scale patterns. Using high-resolution fluorescence microscopy and quantitative image analysis, we found that ZapA cooperatively increases the spatial order of the filament network, but binds only transiently to FtsZ filaments and has no effect on filament length and treadmilling velocity. Together, our data provides a model for how FtsZ-associated proteins can increase the precision and stability of the bacterial cell division machinery in a switch-like manner."}],"acknowledged_ssus":[{"_id":"LifeSc"},{"_id":"Bio"}],"oa_version":"Published Version","scopus_import":"1","month":"12","intvolume":" 10","date_updated":"2023-09-07T13:18:51Z","ddc":["570"],"department":[{"_id":"MaLo"},{"_id":"BjHo"}],"file_date_updated":"2020-07-14T12:47:53Z","_id":"7197","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)"},"status":"public"},{"oa":1,"publisher":"Springer Nature","quality_controlled":"1","year":"2019","has_accepted_license":"1","isi":1,"publication":"Communications Biology","day":"23","date_created":"2019-12-23T13:36:50Z","date_published":"2019-04-23T00:00:00Z","doi":"10.1038/s42003-019-0373-y","article_number":"138","project":[{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"},{"_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification"},{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"citation":{"ama":"Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. Population structure determines the tradeoff between fixation probability and fixation time. Communications Biology. 2019;2. doi:10.1038/s42003-019-0373-y","apa":"Tkadlec, J., Pavlogiannis, A., Chatterjee, K., & Nowak, M. A. (2019). Population structure determines the tradeoff between fixation probability and fixation time. Communications Biology. Springer Nature. https://doi.org/10.1038/s42003-019-0373-y","short":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, M.A. Nowak, Communications Biology 2 (2019).","ieee":"J. Tkadlec, A. Pavlogiannis, K. Chatterjee, and M. A. Nowak, “Population structure determines the tradeoff between fixation probability and fixation time,” Communications Biology, vol. 2. Springer Nature, 2019.","mla":"Tkadlec, Josef, et al. “Population Structure Determines the Tradeoff between Fixation Probability and Fixation Time.” Communications Biology, vol. 2, 138, Springer Nature, 2019, doi:10.1038/s42003-019-0373-y.","ista":"Tkadlec J, Pavlogiannis A, Chatterjee K, Nowak MA. 2019. Population structure determines the tradeoff between fixation probability and fixation time. Communications Biology. 2, 138.","chicago":"Tkadlec, Josef, Andreas Pavlogiannis, Krishnendu Chatterjee, and Martin A. Nowak. “Population Structure Determines the Tradeoff between Fixation Probability and Fixation Time.” Communications Biology. Springer Nature, 2019. https://doi.org/10.1038/s42003-019-0373-y."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","external_id":{"isi":["000465425700006"],"pmid":["31044163"]},"article_processing_charge":"No","author":[{"id":"3F24CCC8-F248-11E8-B48F-1D18A9856A87","first_name":"Josef","last_name":"Tkadlec","orcid":"0000-0002-1097-9684","full_name":"Tkadlec, Josef"},{"orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","last_name":"Pavlogiannis","id":"49704004-F248-11E8-B48F-1D18A9856A87","first_name":"Andreas"},{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Nowak, Martin A.","last_name":"Nowak","first_name":"Martin A."}],"title":"Population structure determines the tradeoff between fixation probability and fixation time","abstract":[{"lang":"eng","text":"The rate of biological evolution depends on the fixation probability and on the fixation time of new mutants. Intensive research has focused on identifying population structures that augment the fixation probability of advantageous mutants. But these amplifiers of natural selection typically increase fixation time. Here we study population structures that achieve a tradeoff between fixation probability and time. First, we show that no amplifiers can have an asymptotically lower absorption time than the well-mixed population. Then we design population structures that substantially augment the fixation probability with just a minor increase in fixation time. Finally, we show that those structures enable higher effective rate of evolution than the well-mixed population provided that the rate of generating advantageous mutants is relatively low. Our work sheds light on how population structure affects the rate of evolution. Moreover, our structures could be useful for lab-based, medical, or industrial applications of evolutionary optimization."}],"pmid":1,"oa_version":"Published Version","scopus_import":"1","intvolume":" 2","month":"04","publication_status":"published","publication_identifier":{"issn":["2399-3642"]},"language":[{"iso":"eng"}],"file":[{"file_id":"7211","checksum":"d1a69bfe73767e4246f0a38e4e1554dd","content_type":"application/pdf","relation":"main_file","access_level":"open_access","file_name":"2019_CommBio_Tkadlec.pdf","date_created":"2019-12-23T13:39:30Z","file_size":1670274,"date_updated":"2020-07-14T12:47:53Z","creator":"dernst"}],"ec_funded":1,"related_material":{"record":[{"relation":"part_of_dissertation","id":"7196","status":"public"}]},"volume":2,"_id":"7210","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)"},"article_type":"original","type":"journal_article","status":"public","date_updated":"2023-09-07T13:19:22Z","ddc":["000"],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:47:53Z"},{"date_published":"2019-10-10T00:00:00Z","doi":"10.1145/3360550","date_created":"2021-10-27T14:57:06Z","has_accepted_license":"1","year":"2019","day":"10","publication":"Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications","publisher":"ACM","quality_controlled":"1","oa":1,"acknowledgement":"The authors would also like to thank anonymous referees for their valuable comments and helpful suggestions. This work is supported by the Austrian Science Fund (FWF) NFN grants S11407-N23 (RiSE/SHiNE) and S11402-N23 (RiSE/SHiNE), by the Vienna Science and Technology Fund (WWTF) Project ICT15-003, and by the Austrian Science Fund (FWF) Schrodinger grant J-4220.\r\n","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Pavlogiannis","orcid":"0000-0002-8943-0722","full_name":"Pavlogiannis, Andreas","first_name":"Andreas","id":"49704004-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Toman, Viktor","orcid":"0000-0001-9036-063X","last_name":"Toman","id":"3AF3DA7C-F248-11E8-B48F-1D18A9856A87","first_name":"Viktor"}],"article_processing_charge":"No","external_id":{"arxiv":["1909.00989"]},"title":"Value-centric dynamic partial order reduction","citation":{"apa":"Chatterjee, K., Pavlogiannis, A., & Toman, V. (2019). Value-centric dynamic partial order reduction. In Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications (Vol. 3). Athens, Greece: ACM. https://doi.org/10.1145/3360550","ama":"Chatterjee K, Pavlogiannis A, Toman V. Value-centric dynamic partial order reduction. In: Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications. Vol 3. ACM; 2019. doi:10.1145/3360550","ieee":"K. Chatterjee, A. Pavlogiannis, and V. Toman, “Value-centric dynamic partial order reduction,” in Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications, Athens, Greece, 2019, vol. 3.","short":"K. Chatterjee, A. Pavlogiannis, V. Toman, in:, Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications, ACM, 2019.","mla":"Chatterjee, Krishnendu, et al. “Value-Centric Dynamic Partial Order Reduction.” Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications, vol. 3, 124, ACM, 2019, doi:10.1145/3360550.","ista":"Chatterjee K, Pavlogiannis A, Toman V. 2019. Value-centric dynamic partial order reduction. Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications. OOPSLA: Object-oriented Programming, Systems, Languages and Applications vol. 3, 124.","chicago":"Chatterjee, Krishnendu, Andreas Pavlogiannis, and Viktor Toman. “Value-Centric Dynamic Partial Order Reduction.” In Proceedings of the 34th ACM International Conference on Object-Oriented Programming, Systems, Languages, and Applications, Vol. 3. ACM, 2019. https://doi.org/10.1145/3360550."},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","project":[{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003"},{"name":"Game Theory","grant_number":"S11407","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Moderne Concurrency Paradigms","grant_number":"S11402-N23","_id":"25F5A88A-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"}],"article_number":"124","related_material":{"record":[{"status":"public","id":"10199","relation":"dissertation_contains"}]},"volume":3,"publication_identifier":{"eissn":["2475-1421"]},"publication_status":"published","file":[{"creator":"cchlebak","date_updated":"2021-11-12T11:41:56Z","file_size":570829,"date_created":"2021-11-12T11:41:56Z","file_name":"2019_ACM_Chatterjee.pdf","access_level":"open_access","relation":"main_file","content_type":"application/pdf","checksum":"2149979c46964c4d117af06ccb6c0834","file_id":"10278","success":1}],"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://dl.acm.org/doi/10.1145/3360550"}],"month":"10","intvolume":" 3","abstract":[{"lang":"eng","text":"The verification of concurrent programs remains an open challenge, as thread interaction has to be accounted for, which leads to state-space explosion. Stateless model checking battles this problem by exploring traces rather than states of the program. As there are exponentially many traces, dynamic partial-order reduction (DPOR) techniques are used to partition the trace space into equivalence classes, and explore a few representatives from each class. The standard equivalence that underlies most DPOR techniques is the happens-before equivalence, however recent works have spawned a vivid interest towards coarser equivalences. The efficiency of such approaches is a product of two parameters: (i) the size of the partitioning induced by the equivalence, and (ii) the time spent by the exploration algorithm in each class of the partitioning. In this work, we present a new equivalence, called value-happens-before and show that it has two appealing features. First, value-happens-before is always at least as coarse as the happens-before equivalence, and can be even exponentially coarser. Second, the value-happens-before partitioning is efficiently explorable when the number of threads is bounded. We present an algorithm called value-centric DPOR (VCDPOR), which explores the underlying partitioning using polynomial time per class. Finally, we perform an experimental evaluation of VCDPOR on various benchmarks, and compare it against other state-of-the-art approaches. Our results show that value-happens-before typically induces a significant reduction in the size of the underlying partitioning, which leads to a considerable reduction in the running time for exploring the whole partitioning."}],"oa_version":"Published Version","file_date_updated":"2021-11-12T11:41:56Z","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"date_updated":"2023-09-07T13:30:27Z","ddc":["000"],"type":"conference","conference":{"name":"OOPSLA: Object-oriented Programming, Systems, Languages and Applications","start_date":"2019-10-23","end_date":"2019-10-25","location":"Athens, Greece"},"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)"},"status":"public","keyword":["safety","risk","reliability and quality","software"],"_id":"10190"},{"publication_status":"published","publication_identifier":{"isbn":["9781450361842"]},"language":[{"iso":"eng"}],"ec_funded":1,"related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"10429"}]},"abstract":[{"lang":"eng","text":"Several classic problems in graph processing and computational geometry are solved via incremental algorithms, which split computation into a series of small tasks acting on shared state, which gets updated progressively. While the sequential variant of such algorithms usually specifies a fixed (but sometimes random) order in which the tasks should be performed, a standard approach to parallelizing such algorithms is to relax this constraint to allow for out-of-order parallel execution. This is the case for parallel implementations of Dijkstra's single-source shortest-paths (SSSP) algorithm, and for parallel Delaunay mesh triangulation. While many software frameworks parallelize incremental computation in this way, it is still not well understood whether this relaxed ordering approach can still provide any complexity guarantees. In this paper, we address this problem, and analyze the efficiency guarantees provided by a range of incremental algorithms when parallelized via relaxed schedulers. We show that, for algorithms such as Delaunay mesh triangulation and sorting by insertion, schedulers with a maximum relaxation factor of k in terms of the maximum priority inversion allowed will introduce a maximum amount of wasted work of O(łog n poly(k)), where n is the number of tasks to be executed. For SSSP, we show that the additional work is O(poly(k), dmax / wmin), where dmax is the maximum distance between two nodes, and wmin is the minimum such distance. In practical settings where n >> k, this suggests that the overheads of relaxation will be outweighed by the improved scalability of the relaxed scheduler. On the negative side, we provide lower bounds showing that certain algorithms will inherently incur a non-trivial amount of wasted work due to scheduler relaxation, even for relatively benign relaxed schedulers."}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2003.09363"}],"scopus_import":"1","month":"06","date_updated":"2023-09-07T13:31:39Z","department":[{"_id":"DaAl"}],"_id":"6673","conference":{"start_date":"2019-06-22","end_date":"2019-06-24","location":"Phoenix, AZ, United States","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures"},"type":"conference","status":"public","year":"2019","isi":1,"publication":"31st ACM Symposium on Parallelism in Algorithms and Architectures","day":"01","page":"145-154","date_created":"2019-07-24T08:59:36Z","doi":"10.1145/3323165.3323201","date_published":"2019-06-01T00:00:00Z","oa":1,"quality_controlled":"1","publisher":"ACM Press","citation":{"ista":"Alistarh D-A, Nadiradze G, Koval N. 2019. Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. 31st ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures, 145–154.","chicago":"Alistarh, Dan-Adrian, Giorgi Nadiradze, and Nikita Koval. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” In 31st ACM Symposium on Parallelism in Algorithms and Architectures, 145–54. ACM Press, 2019. https://doi.org/10.1145/3323165.3323201.","short":"D.-A. Alistarh, G. Nadiradze, N. Koval, in:, 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM Press, 2019, pp. 145–154.","ieee":"D.-A. Alistarh, G. Nadiradze, and N. Koval, “Efficiency guarantees for parallel incremental algorithms under relaxed schedulers,” in 31st ACM Symposium on Parallelism in Algorithms and Architectures, Phoenix, AZ, United States, 2019, pp. 145–154.","apa":"Alistarh, D.-A., Nadiradze, G., & Koval, N. (2019). Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In 31st ACM Symposium on Parallelism in Algorithms and Architectures (pp. 145–154). Phoenix, AZ, United States: ACM Press. https://doi.org/10.1145/3323165.3323201","ama":"Alistarh D-A, Nadiradze G, Koval N. Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In: 31st ACM Symposium on Parallelism in Algorithms and Architectures. ACM Press; 2019:145-154. doi:10.1145/3323165.3323201","mla":"Alistarh, Dan-Adrian, et al. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM Press, 2019, pp. 145–54, doi:10.1145/3323165.3323201."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"arxiv":["2003.09363"],"isi":["000507618500018"]},"article_processing_charge":"No","author":[{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","last_name":"Alistarh"},{"id":"3279A00C-F248-11E8-B48F-1D18A9856A87","first_name":"Giorgi","full_name":"Nadiradze, Giorgi","orcid":"0000-0001-5634-0731","last_name":"Nadiradze"},{"id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","first_name":"Nikita","last_name":"Koval","full_name":"Koval, Nikita"}],"title":"Efficiency guarantees for parallel incremental algorithms under relaxed schedulers","project":[{"name":"Elastic Coordination for Scalable Machine Learning","grant_number":"805223","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425"}]}]