[{"language":[{"iso":"eng"}],"publication":"Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing","scopus_import":"1","ec_funded":1,"project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"citation":{"apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2020). Simple, deterministic, constant-round coloring in the congested clique. In <i>Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing</i> (pp. 309–318). Salerno, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3382734.3405751\">https://doi.org/10.1145/3382734.3405751</a>","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Simple, Deterministic, Constant-Round Coloring in the Congested Clique.” In <i>Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing</i>, 309–18. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3382734.3405751\">https://doi.org/10.1145/3382734.3405751</a>.","ieee":"A. Czumaj, P. Davies, and M. Parter, “Simple, deterministic, constant-round coloring in the congested clique,” in <i>Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing</i>, Salerno, Italy, 2020, pp. 309–318.","short":"A. Czumaj, P. Davies, M. Parter, in:, Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 309–318.","ista":"Czumaj A, Davies P, Parter M. 2020. Simple, deterministic, constant-round coloring in the congested clique. Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 309–318.","mla":"Czumaj, Artur, et al. “Simple, Deterministic, Constant-Round Coloring in the Congested Clique.” <i>Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2020, pp. 309–18, doi:<a href=\"https://doi.org/10.1145/3382734.3405751\">10.1145/3382734.3405751</a>.","ama":"Czumaj A, Davies P, Parter M. Simple, deterministic, constant-round coloring in the congested clique. In: <i>Proceedings of the 2020 ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2020:309-318. doi:<a href=\"https://doi.org/10.1145/3382734.3405751\">10.1145/3382734.3405751</a>"},"page":"309-318","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2025-09-10T10:18:18Z","_id":"7803","title":"Simple, deterministic, constant-round coloring in the congested clique","date_created":"2020-05-06T09:02:14Z","author":[{"last_name":"Czumaj","first_name":"Artur","full_name":"Czumaj, Artur","orcid":"0000-0002-5646-9524"},{"full_name":"Davies, Peter","orcid":"0000-0002-5646-9524","id":"11396234-BB50-11E9-B24C-90FCE5697425","first_name":"Peter","last_name":"Davies"},{"first_name":"Merav","last_name":"Parter","full_name":"Parter, Merav"}],"status":"public","type":"conference","oa_version":"Submitted Version","abstract":[{"text":"We settle the complexity of the (Δ+1)-coloring and (Δ+1)-list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. This matches the complexity of the recent breakthrough randomized constant-round (Δ+1)-list coloring algorithm due to Chang et al. (PODC'19), and significantly improves upon the state-of-the-art O(logΔ)-round deterministic (Δ+1)-coloring bound of Parter (ICALP'18).\r\nA remarkable property of our algorithm is its simplicity. Whereas the state-of-the-art randomized algorithms for this problem are based on the quite involved local coloring algorithm of Chang et al. (STOC'18), our algorithm can be described in just a few lines. At a high level, it applies a careful derandomization of a recursive procedure which partitions the nodes and their respective palettes into separate bins. We show that after O(1) recursion steps, the remaining uncolored subgraph within each bin has linear size, and thus can be solved locally by collecting it to a single node. This algorithm can also be implemented in the Massively Parallel Computation (MPC) model provided that each machine has linear (in n, the number of nodes in the input graph) space.\r\nWe also show an extension of our algorithm to the MPC regime in which machines have sublinear space: we present the first deterministic (Δ+1)-list coloring algorithm designed for sublinear-space MPC, which runs in O(logΔ+loglogn) rounds.","lang":"eng"}],"isi":1,"file":[{"checksum":"46fe4fc58a64eb04068115573f631d4c","date_created":"2020-10-08T08:17:36Z","success":1,"creator":"pdavies","relation":"main_file","access_level":"open_access","file_id":"8624","file_size":520051,"content_type":"application/pdf","date_updated":"2020-10-08T08:17:36Z","file_name":"ColoringArxiv.pdf"}],"doi":"10.1145/3382734.3405751","day":"01","oa":1,"external_id":{"isi":["001436693500042"],"arxiv":["2009.06043"]},"month":"07","department":[{"_id":"DaAl"}],"publisher":"Association for Computing Machinery","file_date_updated":"2020-10-08T08:17:36Z","date_published":"2020-07-01T00:00:00Z","conference":{"start_date":"2020-08-03","end_date":"2020-08-07","name":"PODC: Symposium on Principles of Distributed Computing","location":"Salerno, Italy"},"has_accepted_license":"1","article_processing_charge":"No","fulldoi":"https://doi.org/10.1145/3382734.3405751","arxiv":1,"ddc":["000"],"quality_controlled":"1","year":"2020","publication_status":"published"},{"oa_version":"None","type":"conference","abstract":[{"lang":"eng","text":"There has been a significant amount of research on hardware and software support for efficient concurrent data structures; yet, the question of how to build correct, simple, and scalable data structures has not yet been definitively settled. In this paper, we revisit this question from a minimalist perspective, and ask: what is the smallest amount of synchronization required for correct and efficient concurrent search data structures, and how could this minimal synchronization support be provided in hardware?\r\n\r\nTo address these questions, we introduce memory tagging, a simple hardware mechanism which enables the programmer to \"tag\" a dynamic set of memory locations, at cache-line granularity, and later validate whether the memory has been concurrently modified, with the possibility of updating one of the underlying locations atomically if validation succeeds. We provide several examples showing that this mechanism can enable fast and arguably simple concurrent data structure designs, such as lists, binary search trees, balanced search trees, range queries, and Software Transactional Memory (STM) implementations. We provide an implementation of memory tags in the Graphite multi-core simulator, showing that the mechanism can be implemented entirely at the level of L1 cache, and that it can enable non-trivial speedups versus existing implementations of the above data structures."}],"_id":"8191","title":"Memory tagging: Minimalist synchronization for scalable concurrent data structures","author":[{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Brown, Trevor A","first_name":"Trevor A","last_name":"Brown","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Singhal","first_name":"Nandini","full_name":"Singhal, Nandini"}],"date_created":"2020-08-02T22:00:58Z","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2024-02-28T12:56:32Z","page":"37-49","citation":{"ama":"Alistarh D-A, Brown TA, Singhal N. Memory tagging: Minimalist synchronization for scalable concurrent data structures. In: <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>. Association for Computing Machinery; 2020:37-49. doi:<a href=\"https://doi.org/10.1145/3350755.3400213\">10.1145/3350755.3400213</a>","mla":"Alistarh, Dan-Adrian, et al. “Memory Tagging: Minimalist Synchronization for Scalable Concurrent Data Structures.” <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>, no. 7, Association for Computing Machinery, 2020, pp. 37–49, doi:<a href=\"https://doi.org/10.1145/3350755.3400213\">10.1145/3350755.3400213</a>.","short":"D.-A. Alistarh, T.A. Brown, N. Singhal, in:, Annual ACM Symposium on Parallelism in Algorithms and Architectures, Association for Computing Machinery, 2020, pp. 37–49.","ista":"Alistarh D-A, Brown TA, Singhal N. 2020. Memory tagging: Minimalist synchronization for scalable concurrent data structures. Annual ACM Symposium on Parallelism in Algorithms and Architectures. SPAA: Symposium on Parallelism in Algorithms and Architectures, 37–49.","ieee":"D.-A. Alistarh, T. A. Brown, and N. Singhal, “Memory tagging: Minimalist synchronization for scalable concurrent data structures,” in <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>, Virtual Event, United States, 2020, no. 7, pp. 37–49.","chicago":"Alistarh, Dan-Adrian, Trevor A Brown, and Nandini Singhal. “Memory Tagging: Minimalist Synchronization for Scalable Concurrent Data Structures.” In <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i>, 37–49. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3350755.3400213\">https://doi.org/10.1145/3350755.3400213</a>.","apa":"Alistarh, D.-A., Brown, T. A., &#38; Singhal, N. (2020). Memory tagging: Minimalist synchronization for scalable concurrent data structures. In <i>Annual ACM Symposium on Parallelism in Algorithms and Architectures</i> (pp. 37–49). Virtual Event, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3350755.3400213\">https://doi.org/10.1145/3350755.3400213</a>"},"publication_identifier":{"isbn":["9781450369350"]},"publication":"Annual ACM Symposium on Parallelism in Algorithms and Architectures","issue":"7","scopus_import":"1","language":[{"iso":"eng"}],"quality_controlled":"1","year":"2020","publication_status":"published","fulldoi":"https://doi.org/10.1145/3350755.3400213","date_published":"2020-07-06T00:00:00Z","conference":{"location":"Virtual Event, United States","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures","end_date":"2020-07-17","start_date":"2020-07-15"},"article_processing_charge":"No","external_id":{"isi":["000744436200004"]},"month":"07","department":[{"_id":"DaAl"}],"publisher":"Association for Computing Machinery","day":"06","doi":"10.1145/3350755.3400213","isi":1},{"fulldoi":"https://doi.org/10.1109/TSP.2020.3010355","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1802.04907"}],"arxiv":1,"date_published":"2020-07-20T00:00:00Z","article_processing_charge":"No","publication_status":"published","year":"2020","quality_controlled":"1","intvolume":"        68","volume":68,"doi":"10.1109/TSP.2020.3010355","isi":1,"external_id":{"arxiv":["1802.04907"],"isi":["000562044500001"]},"publisher":"IEEE","month":"07","department":[{"_id":"DaAl"}],"day":"20","oa":1,"date_updated":"2025-07-10T11:55:10Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"apa":"Gurel, N. M., Kara, K., Stojanov, A., Smith, T., Lemmin, T., Alistarh, D.-A., … Zhang, C. (2020). Compressive sensing using iterative hard thresholding with low precision data representation: Theory and applications. <i>IEEE Transactions on Signal Processing</i>. IEEE. <a href=\"https://doi.org/10.1109/TSP.2020.3010355\">https://doi.org/10.1109/TSP.2020.3010355</a>","chicago":"Gurel, Nezihe Merve, Kaan Kara, Alen Stojanov, Tyler Smith, Thomas Lemmin, Dan-Adrian Alistarh, Markus Puschel, and Ce Zhang. “Compressive Sensing Using Iterative Hard Thresholding with Low Precision Data Representation: Theory and Applications.” <i>IEEE Transactions on Signal Processing</i>. IEEE, 2020. <a href=\"https://doi.org/10.1109/TSP.2020.3010355\">https://doi.org/10.1109/TSP.2020.3010355</a>.","short":"N.M. Gurel, K. Kara, A. Stojanov, T. Smith, T. Lemmin, D.-A. Alistarh, M. Puschel, C. Zhang, IEEE Transactions on Signal Processing 68 (2020) 4268–4282.","ieee":"N. M. Gurel <i>et al.</i>, “Compressive sensing using iterative hard thresholding with low precision data representation: Theory and applications,” <i>IEEE Transactions on Signal Processing</i>, vol. 68. IEEE, pp. 4268–4282, 2020.","ista":"Gurel NM, Kara K, Stojanov A, Smith T, Lemmin T, Alistarh D-A, Puschel M, Zhang C. 2020. Compressive sensing using iterative hard thresholding with low precision data representation: Theory and applications. IEEE Transactions on Signal Processing. 68, 4268–4282.","mla":"Gurel, Nezihe Merve, et al. “Compressive Sensing Using Iterative Hard Thresholding with Low Precision Data Representation: Theory and Applications.” <i>IEEE Transactions on Signal Processing</i>, vol. 68, IEEE, 2020, pp. 4268–82, doi:<a href=\"https://doi.org/10.1109/TSP.2020.3010355\">10.1109/TSP.2020.3010355</a>.","ama":"Gurel NM, Kara K, Stojanov A, et al. Compressive sensing using iterative hard thresholding with low precision data representation: Theory and applications. <i>IEEE Transactions on Signal Processing</i>. 2020;68:4268-4282. doi:<a href=\"https://doi.org/10.1109/TSP.2020.3010355\">10.1109/TSP.2020.3010355</a>"},"page":"4268-4282","type":"journal_article","oa_version":"Preprint","article_type":"original","abstract":[{"lang":"eng","text":"Modern scientific instruments produce vast amounts of data, which can overwhelm the processing ability of computer systems. Lossy compression of data is an intriguing solution, but comes with its own drawbacks, such as potential signal loss, and the need for careful optimization of the compression ratio. In this work, we focus on a setting where this problem is especially acute: compressive sensing frameworks for interferometry and medical imaging. We ask the following question: can the precision of the data representation be lowered for all inputs, with recovery guarantees and practical performance Our first contribution is a theoretical analysis of the normalized Iterative Hard Thresholding (IHT) algorithm when all input data, meaning both the measurement matrix and the observation vector are quantized aggressively. We present a variant of low precision normalized IHT that, under mild conditions, can still provide recovery guarantees. The second contribution is the application of our quantization framework to radio astronomy and magnetic resonance imaging. We show that lowering the precision of the data can significantly accelerate image recovery. We evaluate our approach on telescope data and samples of brain images using CPU and FPGA implementations achieving up to a 9x speedup with negligible loss of recovery quality."}],"title":"Compressive sensing using iterative hard thresholding with low precision data representation: Theory and applications","_id":"8268","status":"public","author":[{"first_name":"Nezihe Merve","last_name":"Gurel","full_name":"Gurel, Nezihe Merve"},{"last_name":"Kara","first_name":"Kaan","full_name":"Kara, Kaan"},{"full_name":"Stojanov, Alen","last_name":"Stojanov","first_name":"Alen"},{"full_name":"Smith, Tyler","first_name":"Tyler","last_name":"Smith"},{"full_name":"Lemmin, Thomas","first_name":"Thomas","last_name":"Lemmin"},{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh"},{"full_name":"Puschel, Markus","first_name":"Markus","last_name":"Puschel"},{"full_name":"Zhang, Ce","last_name":"Zhang","first_name":"Ce"}],"date_created":"2020-08-16T22:00:56Z","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1941-0476"],"issn":["1053-587X"]},"acknowledgement":"The authors would like to thank Dr. Michiel Brentjens at the Netherlands Institute for Radio Astronomy (ASTRON) for providing radio interferometer data and Dr. Josip Marjanovic and Dr. Franciszek Hennel at the Magnetic Resonance Technology of ETH Zurich for providing their insights on the experiments. CZ and the DS3Lab gratefully acknowledge the support from the Swiss Data Science Center, Alibaba, Google Focused Research Awards, Huawei, MeteoSwiss, Oracle Labs, Swisscom, Zurich Insurance, Chinese Scholarship Council, and the Department of Computer Science at ETH Zurich.","publication":"IEEE Transactions on Signal Processing","scopus_import":"1"},{"date_created":"2020-09-13T22:01:18Z","status":"public","author":[{"full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh"},{"first_name":"James","last_name":"Aspnes","full_name":"Aspnes, James"},{"full_name":"Ellen, Faith","first_name":"Faith","last_name":"Ellen"},{"full_name":"Gelashvili, Rati","last_name":"Gelashvili","first_name":"Rati"},{"first_name":"Leqi","last_name":"Zhu","full_name":"Zhu, Leqi"}],"title":"Brief Announcement: Why Extension-Based Proofs Fail","_id":"8383","abstract":[{"text":"We introduce extension-based proofs, a class of impossibility proofs that includes valency arguments. They are modelled as an interaction between a prover and a protocol. Using proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We explain why this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power.","lang":"eng"}],"type":"conference","publication_status":"published","oa_version":"None","year":"2020","quality_controlled":"1","article_processing_charge":"No","citation":{"ama":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Brief Announcement: Why Extension-Based Proofs Fail. In: <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2020:54-56. doi:<a href=\"https://doi.org/10.1145/3382734.3405743\">10.1145/3382734.3405743</a>","mla":"Alistarh, Dan-Adrian, et al. “Brief Announcement: Why Extension-Based Proofs Fail.” <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2020, pp. 54–56, doi:<a href=\"https://doi.org/10.1145/3382734.3405743\">10.1145/3382734.3405743</a>.","short":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings of the 39th Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 54–56.","ista":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2020. Brief Announcement: Why Extension-Based Proofs Fail. Proceedings of the 39th Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 54–56.","ieee":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Brief Announcement: Why Extension-Based Proofs Fail,” in <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2020, pp. 54–56.","chicago":"Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Brief Announcement: Why Extension-Based Proofs Fail.” In <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, 54–56. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3382734.3405743\">https://doi.org/10.1145/3382734.3405743</a>.","apa":"Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., &#38; Zhu, L. (2020). Brief Announcement: Why Extension-Based Proofs Fail. In <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i> (pp. 54–56). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3382734.3405743\">https://doi.org/10.1145/3382734.3405743</a>"},"page":"54-56","conference":{"end_date":"2020-08-07","start_date":"2020-08-03","name":"PODC: Principles of Distributed Computing","location":"Virtual, Italy"},"date_published":"2020-07-31T00:00:00Z","date_updated":"2025-09-10T10:26:32Z","fulldoi":"https://doi.org/10.1145/3382734.3405743","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","scopus_import":"1","day":"31","publication":"Proceedings of the 39th Symposium on Principles of Distributed Computing","publisher":"Association for Computing Machinery","month":"07","department":[{"_id":"DaAl"}],"publication_identifier":{"isbn":["9781450375825"]},"external_id":{"isi":["001436693500007"]},"isi":1,"doi":"10.1145/3382734.3405743","language":[{"iso":"eng"}]},{"conference":{"name":"PPoPP: Sympopsium on Principles and Practice of Parallel Programming","end_date":"2020-02-26","start_date":"2020-02-22","location":"San Diego, CA, United States"},"date_published":"2020-02-01T00:00:00Z","article_processing_charge":"No","fulldoi":"https://doi.org/10.1145/3332466.3374528","main_file_link":[{"url":"https://arxiv.org/abs/1908.04207","open_access":"1"}],"arxiv":1,"publication_status":"published","year":"2020","quality_controlled":"1","isi":1,"doi":"10.1145/3332466.3374528","day":"01","oa":1,"external_id":{"isi":["000564476500004"],"arxiv":["1908.04207"]},"publisher":"Association for Computing Machinery","department":[{"_id":"DaAl"}],"month":"02","citation":{"ama":"Li S, Tal Ben-Nun TB-N, Girolamo SD, Alistarh D-A, Hoefler T. Taming unbalanced training workloads in deep learning with partial collective operations. In: <i>Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. Association for Computing Machinery; 2020:45-61. doi:<a href=\"https://doi.org/10.1145/3332466.3374528\">10.1145/3332466.3374528</a>","mla":"Li, Shigang, et al. “Taming Unbalanced Training Workloads in Deep Learning with Partial Collective Operations.” <i>Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Association for Computing Machinery, 2020, pp. 45–61, doi:<a href=\"https://doi.org/10.1145/3332466.3374528\">10.1145/3332466.3374528</a>.","short":"S. Li, T.B.-N. Tal Ben-Nun, S.D. Girolamo, D.-A. Alistarh, T. Hoefler, in:, Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery, 2020, pp. 45–61.","ieee":"S. Li, T. B.-N. Tal Ben-Nun, S. D. Girolamo, D.-A. Alistarh, and T. Hoefler, “Taming unbalanced training workloads in deep learning with partial collective operations,” in <i>Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, San Diego, CA, United States, 2020, pp. 45–61.","ista":"Li S, Tal Ben-Nun TB-N, Girolamo SD, Alistarh D-A, Hoefler T. 2020. Taming unbalanced training workloads in deep learning with partial collective operations. Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPoPP: Sympopsium on Principles and Practice of Parallel Programming, 45–61.","chicago":"Li, Shigang, Tal Ben-Nun Tal Ben-Nun, Salvatore Di Girolamo, Dan-Adrian Alistarh, and Torsten Hoefler. “Taming Unbalanced Training Workloads in Deep Learning with Partial Collective Operations.” In <i>Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, 45–61. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3332466.3374528\">https://doi.org/10.1145/3332466.3374528</a>.","apa":"Li, S., Tal Ben-Nun, T. B.-N., Girolamo, S. D., Alistarh, D.-A., &#38; Hoefler, T. (2020). Taming unbalanced training workloads in deep learning with partial collective operations. In <i>Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp. 45–61). San Diego, CA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3332466.3374528\">https://doi.org/10.1145/3332466.3374528</a>"},"page":"45-61","project":[{"call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"}],"date_updated":"2025-04-14T07:49:12Z","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","title":"Taming unbalanced training workloads in deep learning with partial collective operations","_id":"8722","date_created":"2020-11-05T15:25:30Z","author":[{"last_name":"Li","first_name":"Shigang","full_name":"Li, Shigang"},{"last_name":"Tal Ben-Nun","first_name":"Tal Ben-Nun","full_name":"Tal Ben-Nun, Tal Ben-Nun"},{"full_name":"Girolamo, Salvatore Di","last_name":"Girolamo","first_name":"Salvatore Di"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"full_name":"Hoefler, Torsten","first_name":"Torsten","last_name":"Hoefler"}],"status":"public","type":"conference","oa_version":"Preprint","abstract":[{"lang":"eng","text":"Load imbalance pervasively exists in distributed deep learning training systems, either caused by the inherent imbalance in learned tasks or by the system itself. Traditional synchronous Stochastic Gradient Descent (SGD)\r\nachieves good accuracy for a wide variety of tasks, but relies on global synchronization to accumulate the gradients at every training step. In this paper, we propose eager-SGD, which relaxes the global synchronization for\r\ndecentralized accumulation. To implement eager-SGD, we propose to use two partial collectives: solo and majority. With solo allreduce, the faster processes contribute their gradients eagerly without waiting for the slower processes, whereas with majority allreduce, at least half of the participants must contribute gradients before continuing, all without using a central parameter server. We theoretically prove the convergence of the algorithms and describe the partial collectives in detail. Experimental results on load-imbalanced environments (CIFAR-10, ImageNet, and UCF101 datasets) show\r\nthat eager-SGD achieves 1.27x speedup over the state-of-the-art synchronous SGD, without losing accuracy."}],"language":[{"iso":"eng"}],"publication":"Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","scopus_import":"1","ec_funded":1},{"_id":"8724","title":"On the sample complexity of adversarial multi-source PAC learning","status":"public","date_created":"2020-11-05T15:25:58Z","author":[{"full_name":"Konstantinov, Nikola H","orcid":"0009-0009-5204-7621","id":"4B9D76E4-F248-11E8-B48F-1D18A9856A87","last_name":"Konstantinov","first_name":"Nikola H"},{"full_name":"Frantar, Elias","first_name":"Elias","last_name":"Frantar","id":"09a8f98d-ec99-11ea-ae11-c063a7b7fe5f"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"full_name":"Lampert, Christoph","orcid":"0000-0001-8622-7887","id":"40C20FD2-F248-11E8-B48F-1D18A9856A87","last_name":"Lampert","first_name":"Christoph"}],"oa_version":"Published Version","type":"conference","abstract":[{"lang":"eng","text":"We study the problem of learning from multiple untrusted data sources, a scenario of increasing practical relevance given the recent emergence of crowdsourcing and collaborative learning paradigms. Specifically, we analyze the situation in which a learning system obtains datasets from multiple sources, some of which might be biased or even adversarially perturbed. It is\r\nknown that in the single-source case, an adversary with the power to corrupt a fixed fraction of the training data can prevent PAC-learnability, that is, even in the limit of infinitely much training data, no learning system can approach the optimal test error. In this work we show that, surprisingly, the same is not true in the multi-source setting, where the adversary can arbitrarily\r\ncorrupt a fixed fraction of the data sources. Our main results are a generalization bound that provides finite-sample guarantees for this learning setting, as well as corresponding lower bounds. Besides establishing PAC-learnability our results also show that in a cooperative learning setting sharing data with other parties has provable benefits, even if some\r\nparticipants are malicious. "}],"related_material":{"link":[{"url":"http://proceedings.mlr.press/v119/konstantinov20a/konstantinov20a-supp.pdf","relation":"supplementary_material"}],"record":[{"id":"10799","relation":"dissertation_contains","status":"public"}]},"project":[{"_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","grant_number":"805223"}],"page":"5416-5425","citation":{"short":"N.H. Konstantinov, E. Frantar, D.-A. Alistarh, C. Lampert, in:, Proceedings of the 37th International Conference on Machine Learning, ML Research Press, 2020, pp. 5416–5425.","ista":"Konstantinov NH, Frantar E, Alistarh D-A, Lampert C. 2020. On the sample complexity of adversarial multi-source PAC learning. Proceedings of the 37th International Conference on Machine Learning. ICML: International Conference on Machine Learning vol. 119, 5416–5425.","ieee":"N. H. Konstantinov, E. Frantar, D.-A. Alistarh, and C. Lampert, “On the sample complexity of adversarial multi-source PAC learning,” in <i>Proceedings of the 37th International Conference on Machine Learning</i>, Online, 2020, vol. 119, pp. 5416–5425.","mla":"Konstantinov, Nikola H., et al. “On the Sample Complexity of Adversarial Multi-Source PAC Learning.” <i>Proceedings of the 37th International Conference on Machine Learning</i>, vol. 119, ML Research Press, 2020, pp. 5416–25.","ama":"Konstantinov NH, Frantar E, Alistarh D-A, Lampert C. On the sample complexity of adversarial multi-source PAC learning. In: <i>Proceedings of the 37th International Conference on Machine Learning</i>. Vol 119. ML Research Press; 2020:5416-5425.","apa":"Konstantinov, N. H., Frantar, E., Alistarh, D.-A., &#38; Lampert, C. (2020). On the sample complexity of adversarial multi-source PAC learning. In <i>Proceedings of the 37th International Conference on Machine Learning</i> (Vol. 119, pp. 5416–5425). Online: ML Research Press.","chicago":"Konstantinov, Nikola H, Elias Frantar, Dan-Adrian Alistarh, and Christoph Lampert. “On the Sample Complexity of Adversarial Multi-Source PAC Learning.” In <i>Proceedings of the 37th International Conference on Machine Learning</i>, 119:5416–25. ML Research Press, 2020."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-04-07T14:19:48Z","publication":"Proceedings of the 37th International Conference on Machine Learning","scopus_import":"1","ec_funded":1,"publication_identifier":{"issn":["2640-3498"]},"acknowledgement":"Dan Alistarh is supported in part by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML). This research was supported by the Scientific Service Units (SSU) of IST Austria through resources provided by Scientific Computing (SciComp).","language":[{"iso":"eng"}],"ddc":["000"],"quality_controlled":"1","year":"2020","publication_status":"published","intvolume":"       119","date_published":"2020-07-12T00:00:00Z","file_date_updated":"2021-02-15T09:00:01Z","has_accepted_license":"1","conference":{"end_date":"2020-07-18","start_date":"2020-07-12","name":"ICML: International Conference on Machine Learning","location":"Online"},"article_processing_charge":"No","arxiv":1,"acknowledged_ssus":[{"_id":"ScienComp"}],"day":"12","corr_author":"1","oa":1,"external_id":{"arxiv":["2002.10384"]},"department":[{"_id":"DaAl"},{"_id":"ChLa"}],"month":"07","publisher":"ML Research Press","volume":119,"file":[{"date_updated":"2021-02-15T09:00:01Z","content_type":"application/pdf","file_name":"2020_PMLR_Konstantinov.pdf","file_size":281286,"file_id":"9120","access_level":"open_access","relation":"main_file","creator":"dernst","success":1,"date_created":"2021-02-15T09:00:01Z","checksum":"cc755d0054bc4b2be778ea7aa7884d2f"}]},{"page":"3:1-3:18","citation":{"ama":"Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. The splay-list: A distribution-adaptive concurrent skip-list. In: <i>34th International Symposium on Distributed Computing</i>. Vol 179. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:3:1-3:18. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">10.4230/LIPIcs.DISC.2020.3</a>","mla":"Aksenov, Vitaly, et al. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” <i>34th International Symposium on Distributed Computing</i>, vol. 179, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 3:1-3:18, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">10.4230/LIPIcs.DISC.2020.3</a>.","short":"V. Aksenov, D.-A. Alistarh, A. Drozdova, A. Mohtashami, in:, 34th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 3:1-3:18.","ieee":"V. Aksenov, D.-A. Alistarh, A. Drozdova, and A. Mohtashami, “The splay-list: A distribution-adaptive concurrent skip-list,” in <i>34th International Symposium on Distributed Computing</i>, Freiburg, Germany, 2020, vol. 179, p. 3:1-3:18.","ista":"Aksenov V, Alistarh D-A, Drozdova A, Mohtashami A. 2020. The splay-list: A distribution-adaptive concurrent skip-list. 34th International Symposium on Distributed Computing. DISC: Symposium on Distributed ComputingLIPIcs vol. 179, 3:1-3:18.","chicago":"Aksenov, Vitaly, Dan-Adrian Alistarh, Alexandra Drozdova, and Amirkeivan Mohtashami. “The Splay-List: A Distribution-Adaptive Concurrent Skip-List.” In <i>34th International Symposium on Distributed Computing</i>, 179:3:1-3:18. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">https://doi.org/10.4230/LIPIcs.DISC.2020.3</a>.","apa":"Aksenov, V., Alistarh, D.-A., Drozdova, A., &#38; Mohtashami, A. (2020). The splay-list: A distribution-adaptive concurrent skip-list. In <i>34th International Symposium on Distributed Computing</i> (Vol. 179, p. 3:1-3:18). Freiburg, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.3\">https://doi.org/10.4230/LIPIcs.DISC.2020.3</a>"},"project":[{"name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"}],"license":"https://creativecommons.org/licenses/by/3.0/","date_updated":"2025-04-14T07:49:12Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","date_created":"2020-11-05T15:26:17Z","author":[{"full_name":"Aksenov, Vitaly","last_name":"Aksenov","first_name":"Vitaly"},{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Drozdova, Alexandra","last_name":"Drozdova","first_name":"Alexandra"},{"first_name":"Amirkeivan","last_name":"Mohtashami","full_name":"Mohtashami, Amirkeivan"}],"title":"The splay-list: A distribution-adaptive concurrent skip-list","_id":"8725","abstract":[{"text":"The design and implementation of efficient concurrent data structures have\r\nseen significant attention. However, most of this work has focused on\r\nconcurrent data structures providing good \\emph{worst-case} guarantees. In real\r\nworkloads, objects are often accessed at different rates, since access\r\ndistributions may be non-uniform. Efficient distribution-adaptive data\r\nstructures are known in the sequential case, e.g. the splay-trees; however,\r\nthey often are hard to translate efficiently in the concurrent case.\r\n  In this paper, we investigate distribution-adaptive concurrent data\r\nstructures and propose a new design called the splay-list. At a high level, the\r\nsplay-list is similar to a standard skip-list, with the key distinction that\r\nthe height of each element adapts dynamically to its access rate: popular\r\nelements ``move up,'' whereas rarely-accessed elements decrease in height. We\r\nshow that the splay-list provides order-optimal amortized complexity bounds for\r\na subset of operations while being amenable to efficient concurrent\r\nimplementation. Experimental results show that the splay-list can leverage\r\ndistribution-adaptivity to improve on the performance of classic concurrent\r\ndesigns, and can outperform the only previously-known distribution-adaptive\r\ndesign in certain settings.","lang":"eng"}],"type":"conference","oa_version":"Published Version","language":[{"iso":"eng"}],"scopus_import":"1","publication":"34th International Symposium on Distributed Computing","acknowledgement":"Vitaly Aksenov: Government of Russian Federation (Grant 08-08).\r\nDan Alistarh: ERC Starting Grant 805223 ScaleML.","ec_funded":1,"publication_identifier":{"isbn":["9783959771689"],"issn":["1868-8969"]},"article_processing_charge":"No","has_accepted_license":"1","conference":{"start_date":"2020-10-12","end_date":"2020-10-16","name":"DISC: Symposium on Distributed Computing","location":"Freiburg, Germany"},"file_date_updated":"2021-03-11T12:33:35Z","date_published":"2020-08-03T00:00:00Z","arxiv":1,"fulldoi":"https://doi.org/10.4230/LIPIcs.DISC.2020.3","tmp":{"image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"ddc":["000"],"intvolume":"       179","publication_status":"published","year":"2020","quality_controlled":"1","series_title":"LIPIcs","doi":"10.4230/LIPIcs.DISC.2020.3","file":[{"creator":"dernst","relation":"main_file","access_level":"open_access","checksum":"a626a9c47df52b6f6d97edd910dae4ba","date_created":"2021-03-11T12:33:35Z","success":1,"file_size":740358,"date_updated":"2021-03-11T12:33:35Z","content_type":"application/pdf","file_name":"2020_LIPIcs_Aksenov.pdf","file_id":"9237"}],"volume":179,"oa":1,"day":"03","publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","month":"08","department":[{"_id":"DaAl"}],"external_id":{"arxiv":["2008.01009"]}},{"language":[{"iso":"eng"}],"scopus_import":"1","publication_identifier":{"issn":["1049-5258"],"isbn":["9781713829546"]},"ec_funded":1,"acknowledgement":"We thank Marco Mondelli for discussions related to LDPC decoding, and Giorgi Nadiradze for discussions on analysis of relaxed schedulers. This project has received funding from the European Research Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML).","project":[{"grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020"}],"citation":{"apa":"Aksenov, V., Alistarh, D.-A., &#38; Korhonen, J. (2020). Scalable belief propagation via relaxed scheduling (Vol. 33, pp. 22361–22372). Presented at the NeurIPS: Conference on Neural Information Processing Systems, Vancouver, Canada: Neural Information Processing Systems Foundation.","chicago":"Aksenov, Vitaly, Dan-Adrian Alistarh, and Janne Korhonen. “Scalable Belief Propagation via Relaxed Scheduling,” 33:22361–72. Neural Information Processing Systems Foundation, 2020.","short":"V. Aksenov, D.-A. Alistarh, J. Korhonen, in:, Neural Information Processing Systems Foundation, 2020, pp. 22361–22372.","ieee":"V. Aksenov, D.-A. Alistarh, and J. Korhonen, “Scalable belief propagation via relaxed scheduling,” presented at the NeurIPS: Conference on Neural Information Processing Systems, Vancouver, Canada, 2020, vol. 33, pp. 22361–22372.","ista":"Aksenov V, Alistarh D-A, Korhonen J. 2020. Scalable belief propagation via relaxed scheduling. NeurIPS: Conference on Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 33, 22361–22372.","mla":"Aksenov, Vitaly, et al. <i>Scalable Belief Propagation via Relaxed Scheduling</i>. Vol. 33, Neural Information Processing Systems Foundation, 2020, pp. 22361–72.","ama":"Aksenov V, Alistarh D-A, Korhonen J. Scalable belief propagation via relaxed scheduling. In: Vol 33. Neural Information Processing Systems Foundation; 2020:22361-22372."},"page":"22361-22372","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-06-18T19:54:53Z","date_created":"2021-07-04T22:01:26Z","status":"public","author":[{"full_name":"Aksenov, Vitaly","first_name":"Vitaly","last_name":"Aksenov"},{"first_name":"Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"},{"first_name":"Janne","last_name":"Korhonen","id":"C5402D42-15BC-11E9-A202-CA2BE6697425","full_name":"Korhonen, Janne"}],"_id":"9631","title":"Scalable belief propagation via relaxed scheduling","abstract":[{"lang":"eng","text":"The ability to leverage large-scale hardware parallelism has been one of the key enablers of the accelerated recent progress in machine learning. Consequently, there has been considerable effort invested into developing efficient parallel variants of classic machine learning algorithms. However, despite the wealth of knowledge on parallelization, some classic machine learning algorithms often prove hard to parallelize efficiently while maintaining convergence. In this paper, we focus on efficient parallel algorithms for the key machine learning task of inference on graphical models, in particular on the fundamental belief propagation algorithm. We address the challenge of efficiently parallelizing this classic paradigm by showing how to leverage scalable relaxed schedulers in this context. We present an extensive empirical study, showing that our approach outperforms previous parallel belief propagation implementations both in terms of scalability and in terms of wall-clock convergence time, on a range of practical applications."}],"oa_version":"Published Version","type":"conference","volume":33,"corr_author":"1","oa":1,"day":"06","month":"12","department":[{"_id":"DaAl"}],"publisher":"Neural Information Processing Systems Foundation","external_id":{"arxiv":["2002.11505"]},"article_processing_charge":"No","alternative_title":["Advances in Neural Information Processing Systems"],"date_published":"2020-12-06T00:00:00Z","conference":{"end_date":"2020-12-12","start_date":"2020-12-06","name":"NeurIPS: Conference on Neural Information Processing Systems","location":"Vancouver, Canada"},"arxiv":1,"main_file_link":[{"open_access":"1","url":"https://proceedings.neurips.cc/paper/2020/hash/fdb2c3bab9d0701c4a050a4d8d782c7f-Abstract.html"}],"ddc":["000"],"intvolume":"        33","quality_controlled":"1","year":"2020","publication_status":"published"},{"scopus_import":"1","ec_funded":1,"publication_identifier":{"issn":["1049-5258"],"isbn":["9781713829546"]},"acknowledgement":"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). Also, we would like to thank Alexander Shevchenko, Alexandra Peste, and other members of the group for fruitful discussions.","language":[{"iso":"eng"}],"_id":"9632","title":"WoodFisher: Efficient second-order approximation for neural network compression","date_created":"2021-07-04T22:01:26Z","status":"public","author":[{"last_name":"Singh","first_name":"Sidak Pal","id":"DD138E24-D89D-11E9-9DC0-DEF6E5697425","full_name":"Singh, Sidak Pal"},{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","first_name":"Dan-Adrian","last_name":"Alistarh","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87"}],"type":"conference","oa_version":"Published Version","abstract":[{"lang":"eng","text":"Second-order information, in the form of Hessian- or Inverse-Hessian-vector products, is a fundamental tool for solving optimization problems. Recently, there has been significant interest in utilizing this information in the context of deep\r\nneural networks; however, relatively little is known about the quality of existing approximations in this context. Our work examines this question, identifies issues with existing approaches, and proposes a method called WoodFisher to compute a faithful and efficient estimate of the inverse Hessian. Our main application is to neural network compression, where we build on the classic Optimal Brain Damage/Surgeon framework. We demonstrate that WoodFisher significantly outperforms popular state-of-the-art methods for oneshot pruning. Further, even when iterative, gradual pruning is allowed, our method results in a gain in test accuracy over the state-of-the-art approaches, for standard image classification datasets such as ImageNet ILSVRC. We examine how our method can be extended to take into account first-order information, as well as\r\nillustrate its ability to automatically set layer-wise pruning thresholds and perform compression in the limited-data regime. The code is available at the following link, https://github.com/IST-DASLab/WoodFisher."}],"project":[{"call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"}],"page":"18098-18109","citation":{"apa":"Singh, S. P., &#38; Alistarh, D.-A. (2020). WoodFisher: Efficient second-order approximation for neural network compression (Vol. 33, pp. 18098–18109). Presented at the NeurIPS: Conference on Neural Information Processing Systems, Vancouver, Canada: Neural Information Processing Systems Foundation.","chicago":"Singh, Sidak Pal, and Dan-Adrian Alistarh. “WoodFisher: Efficient Second-Order Approximation for Neural Network Compression,” 33:18098–109. Neural Information Processing Systems Foundation, 2020.","ieee":"S. P. Singh and D.-A. Alistarh, “WoodFisher: Efficient second-order approximation for neural network compression,” presented at the NeurIPS: Conference on Neural Information Processing Systems, Vancouver, Canada, 2020, vol. 33, pp. 18098–18109.","ista":"Singh SP, Alistarh D-A. 2020. WoodFisher: Efficient second-order approximation for neural network compression. NeurIPS: Conference on Neural Information Processing Systems, Advances in Neural Information Processing Systems, vol. 33, 18098–18109.","short":"S.P. Singh, D.-A. Alistarh, in:, Neural Information Processing Systems Foundation, 2020, pp. 18098–18109.","ama":"Singh SP, Alistarh D-A. WoodFisher: Efficient second-order approximation for neural network compression. In: Vol 33. Neural Information Processing Systems Foundation; 2020:18098-18109.","mla":"Singh, Sidak Pal, and Dan-Adrian Alistarh. <i>WoodFisher: Efficient Second-Order Approximation for Neural Network Compression</i>. Vol. 33, Neural Information Processing Systems Foundation, 2020, pp. 18098–109."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-06-18T19:55:12Z","day":"06","corr_author":"1","oa":1,"external_id":{"arxiv":["2004.14340"]},"month":"12","department":[{"_id":"DaAl"},{"_id":"ToHe"}],"publisher":"Neural Information Processing Systems Foundation","volume":33,"ddc":["000"],"year":"2020","quality_controlled":"1","publication_status":"published","intvolume":"        33","alternative_title":["Advances in Neural Information Processing Systems"],"date_published":"2020-12-06T00:00:00Z","conference":{"location":"Vancouver, Canada","name":"NeurIPS: Conference on Neural Information Processing Systems","start_date":"2020-12-06","end_date":"2020-12-12"},"article_processing_charge":"No","arxiv":1,"main_file_link":[{"open_access":"1","url":"https://proceedings.neurips.cc/paper/2020/hash/d1ff1ec86b62cd5f3903ff19c3a326b2-Abstract.html"}]},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-07-10T11:54:23Z","project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"citation":{"apa":"Bhatia, S., Chatterjee, B., Nathani, D., &#38; Kaul, M. (2020). A persistent homology perspective to the link prediction problem. In <i>Complex Networks and their applications VIII</i> (Vol. 881, pp. 27–39). Lisbon, Portugal: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-36687-2_3\">https://doi.org/10.1007/978-3-030-36687-2_3</a>","chicago":"Bhatia, Sumit, Bapi Chatterjee, Deepak Nathani, and Manohar Kaul. “A Persistent Homology Perspective to the Link Prediction Problem.” In <i>Complex Networks and Their Applications VIII</i>, 881:27–39. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/978-3-030-36687-2_3\">https://doi.org/10.1007/978-3-030-36687-2_3</a>.","short":"S. Bhatia, B. Chatterjee, D. Nathani, M. Kaul, in:, Complex Networks and Their Applications VIII, Springer Nature, 2020, pp. 27–39.","ista":"Bhatia S, Chatterjee B, Nathani D, Kaul M. 2020. A persistent homology perspective to the link prediction problem. Complex Networks and their applications VIII. COMPLEX: International Conference on Complex Networks and their Applications, SCI, vol. 881, 27–39.","ieee":"S. Bhatia, B. Chatterjee, D. Nathani, and M. Kaul, “A persistent homology perspective to the link prediction problem,” in <i>Complex Networks and their applications VIII</i>, Lisbon, Portugal, 2020, vol. 881, pp. 27–39.","mla":"Bhatia, Sumit, et al. “A Persistent Homology Perspective to the Link Prediction Problem.” <i>Complex Networks and Their Applications VIII</i>, vol. 881, Springer Nature, 2020, pp. 27–39, doi:<a href=\"https://doi.org/10.1007/978-3-030-36687-2_3\">10.1007/978-3-030-36687-2_3</a>.","ama":"Bhatia S, Chatterjee B, Nathani D, Kaul M. A persistent homology perspective to the link prediction problem. In: <i>Complex Networks and Their Applications VIII</i>. Vol 881. Springer Nature; 2020:27-39. doi:<a href=\"https://doi.org/10.1007/978-3-030-36687-2_3\">10.1007/978-3-030-36687-2_3</a>"},"page":"27-39","abstract":[{"lang":"eng","text":"Persistent homology is a powerful tool in Topological Data Analysis (TDA) to capture the topological properties of data succinctly at different spatial resolutions. For graphical data, the shape, and structure of the neighborhood of individual data items (nodes) are an essential means of characterizing their properties. We propose the use of persistent homology methods to capture structural and topological properties of graphs and use it to address the problem of link prediction. We achieve encouraging results on nine different real-world datasets that attest to the potential of persistent homology-based methods for network analysis."}],"type":"conference","oa_version":"Submitted Version","author":[{"full_name":"Bhatia, Sumit","first_name":"Sumit","last_name":"Bhatia"},{"first_name":"Bapi","last_name":"Chatterjee","id":"3C41A08A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2742-4028","full_name":"Chatterjee, Bapi"},{"full_name":"Nathani, Deepak","last_name":"Nathani","first_name":"Deepak"},{"full_name":"Kaul, Manohar","last_name":"Kaul","first_name":"Manohar"}],"status":"public","date_created":"2019-12-29T23:00:45Z","_id":"7213","title":"A persistent homology perspective to the link prediction problem","language":[{"iso":"eng"}],"ec_funded":1,"publication_identifier":{"eissn":["1860-9503"],"isbn":["9783030366865"],"issn":["1860-949X"]},"scopus_import":"1","publication":"Complex Networks and their applications VIII","fulldoi":"https://doi.org/10.1007/978-3-030-36687-2_3","article_processing_charge":"No","alternative_title":["SCI"],"file_date_updated":"2020-10-08T08:16:48Z","date_published":"2020-01-01T00:00:00Z","has_accepted_license":"1","conference":{"location":"Lisbon, Portugal","end_date":"2019-12-12","start_date":"2019-12-10","name":"COMPLEX: International Conference on Complex Networks and their Applications"},"intvolume":"       881","year":"2020","quality_controlled":"1","publication_status":"published","ddc":["004"],"file":[{"file_id":"8625","file_name":"main.pdf","content_type":"application/pdf","date_updated":"2020-10-08T08:16:48Z","file_size":310598,"success":1,"checksum":"8951f094c8c7dae9ff8db885199bc296","date_created":"2020-10-08T08:16:48Z","access_level":"open_access","creator":"bchatter","relation":"main_file"}],"doi":"10.1007/978-3-030-36687-2_3","volume":881,"isi":1,"month":"01","department":[{"_id":"DaAl"}],"publisher":"Springer Nature","external_id":{"isi":["000843927300003"]},"oa":1,"day":"01"},{"date_created":"2020-01-04T11:04:30Z","status":"public","author":[{"full_name":"Rybicki, Joel","orcid":"0000-0002-6432-6646","first_name":"Joel","last_name":"Rybicki","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Abrego","first_name":"Nerea","full_name":"Abrego, Nerea"},{"first_name":"Otso","last_name":"Ovaskainen","full_name":"Ovaskainen, Otso"}],"title":"Habitat fragmentation and species diversity in competitive communities","_id":"7224","abstract":[{"lang":"eng","text":"Habitat loss is one of the key drivers of the ongoing decline of biodiversity. However, ecologists still argue about how fragmentation of habitat (independent of habitat loss) affects species richness. The recently proposed habitat amount hypothesis posits that species richness only depends on the total amount of habitat in a local landscape. In contrast, empirical studies report contrasting patterns: some find positive and others negative effects of fragmentation per se on species richness. To explain this apparent disparity, we devise a stochastic, spatially explicit model of competitive species communities in heterogeneous habitats. The model shows that habitat loss and fragmentation have complex effects on species diversity in competitive communities. When the total amount of habitat is large, fragmentation per se tends to increase species diversity, but if the total amount of habitat is small, the situation is reversed: fragmentation per se decreases species diversity."}],"oa_version":"Published Version","type":"journal_article","article_type":"original","page":"506-517","citation":{"chicago":"Rybicki, Joel, Nerea Abrego, and Otso Ovaskainen. “Habitat Fragmentation and Species Diversity in Competitive Communities.” <i>Ecology Letters</i>. Wiley, 2020. <a href=\"https://doi.org/10.1111/ele.13450\">https://doi.org/10.1111/ele.13450</a>.","apa":"Rybicki, J., Abrego, N., &#38; Ovaskainen, O. (2020). Habitat fragmentation and species diversity in competitive communities. <i>Ecology Letters</i>. Wiley. <a href=\"https://doi.org/10.1111/ele.13450\">https://doi.org/10.1111/ele.13450</a>","ama":"Rybicki J, Abrego N, Ovaskainen O. Habitat fragmentation and species diversity in competitive communities. <i>Ecology Letters</i>. 2020;23(3):506-517. doi:<a href=\"https://doi.org/10.1111/ele.13450\">10.1111/ele.13450</a>","mla":"Rybicki, Joel, et al. “Habitat Fragmentation and Species Diversity in Competitive Communities.” <i>Ecology Letters</i>, vol. 23, no. 3, Wiley, 2020, pp. 506–17, doi:<a href=\"https://doi.org/10.1111/ele.13450\">10.1111/ele.13450</a>.","short":"J. Rybicki, N. Abrego, O. Ovaskainen, Ecology Letters 23 (2020) 506–517.","ieee":"J. Rybicki, N. Abrego, and O. Ovaskainen, “Habitat fragmentation and species diversity in competitive communities,” <i>Ecology Letters</i>, vol. 23, no. 3. Wiley, pp. 506–517, 2020.","ista":"Rybicki J, Abrego N, Ovaskainen O. 2020. Habitat fragmentation and species diversity in competitive communities. Ecology Letters. 23(3), 506–517."},"project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships"},{"grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","name":"Coordination in constrained and natural distributed systems","call_identifier":"H2020"}],"license":"https://creativecommons.org/licenses/by/4.0/","date_updated":"2025-06-12T07:28:52Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","issue":"3","publication":"Ecology Letters","ec_funded":1,"publication_identifier":{"issn":["1461-023X"],"eissn":["1461-0248"]},"language":[{"iso":"eng"}],"tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["000"],"intvolume":"        23","publication_status":"published","year":"2020","quality_controlled":"1","pmid":1,"article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","date_published":"2020-03-01T00:00:00Z","file_date_updated":"2020-07-14T12:47:54Z","fulldoi":"https://doi.org/10.1111/ele.13450","corr_author":"1","oa":1,"day":"01","publisher":"Wiley","department":[{"_id":"DaAl"}],"month":"03","external_id":{"pmid":["31863571"],"isi":["000503625200001"]},"isi":1,"doi":"10.1111/ele.13450","file":[{"file_size":3005474,"content_type":"application/pdf","date_updated":"2020-07-14T12:47:54Z","file_name":"2020_EcologyLetters_Rybicki.pdf","file_id":"7486","creator":"dernst","relation":"main_file","access_level":"open_access","date_created":"2020-02-14T12:02:50Z","checksum":"372f67f2744f4b6049e9778364766c22"}],"volume":23},{"page":"295-306","article_processing_charge":"No","citation":{"mla":"Arbel-Raviv, Maya, et al. “Getting to the Root of Concurrent Binary Search Tree Performance.” <i>Proceedings of the 2018 USENIX Annual Technical Conference</i>, USENIX Association, 2020, pp. 295–306.","ama":"Arbel-Raviv M, Brown TA, Morrison A. Getting to the root of concurrent binary search tree performance. In: <i>Proceedings of the 2018 USENIX Annual Technical Conference</i>. USENIX Association; 2020:295-306.","ista":"Arbel-Raviv M, Brown TA, Morrison A. 2020. Getting to the root of concurrent binary search tree performance. Proceedings of the 2018 USENIX Annual Technical Conference. USENIX: Annual Technical Conference, 295–306.","ieee":"M. Arbel-Raviv, T. A. Brown, and A. Morrison, “Getting to the root of concurrent binary search tree performance,” in <i>Proceedings of the 2018 USENIX Annual Technical Conference</i>, Boston, MA, United States, 2020, pp. 295–306.","short":"M. Arbel-Raviv, T.A. Brown, A. Morrison, in:, Proceedings of the 2018 USENIX Annual Technical Conference, USENIX Association, 2020, pp. 295–306.","chicago":"Arbel-Raviv, Maya, Trevor A Brown, and Adam Morrison. “Getting to the Root of Concurrent Binary Search Tree Performance.” In <i>Proceedings of the 2018 USENIX Annual Technical Conference</i>, 295–306. USENIX Association, 2020.","apa":"Arbel-Raviv, M., Brown, T. A., &#38; Morrison, A. (2020). Getting to the root of concurrent binary search tree performance. In <i>Proceedings of the 2018 USENIX Annual Technical Conference</i> (pp. 295–306). Boston, MA, United States: USENIX Association."},"project":[{"_id":"26450934-B435-11E9-9278-68D0E5697425","name":"NSERC Postdoctoral fellowship"}],"conference":{"name":"USENIX: Annual Technical Conference","end_date":"2018-07-13","start_date":"2018-07-11","location":"Boston, MA, United States"},"date_published":"2020-01-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://www.usenix.org/system/files/conference/atc18/atc18-arbel-raviv.pdf"}],"date_updated":"2025-04-15T07:40:57Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["000"],"date_created":"2020-01-14T07:27:08Z","status":"public","author":[{"last_name":"Arbel-Raviv","first_name":"Maya","full_name":"Arbel-Raviv, Maya"},{"last_name":"Brown","first_name":"Trevor A","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87","full_name":"Brown, Trevor A"},{"last_name":"Morrison","first_name":"Adam","full_name":"Morrison, Adam"}],"title":"Getting to the root of concurrent binary search tree performance","_id":"7272","abstract":[{"lang":"eng","text":"Many systems rely on optimistic concurrent search trees for multi-core scalability. In principle, optimistic trees have a simple performance story: searches are read-only and so run in parallel, with writes to shared memory occurring only when modifying the data structure. However, this paper shows that in practice, obtaining the full performance benefits of optimistic search trees is not so simple.\r\n\r\nWe focus on optimistic binary search trees (BSTs) and perform a detailed performance analysis of 10 state-of-the-art BSTs on large scale x86-64 hardware, using both microbenchmarks and an in-memory database system. We find and explain significant unexpected performance differences between BSTs with similar tree structure and search implementations, which we trace to subtle performance-degrading interactions of BSTs with systems software and hardware subsystems. We further derive a prescriptive approach to avoid this performance degradation, as well as algorithmic insights on optimistic BST design. Our work underlines the gap between the theory and practice of multi-core performance, and calls for further research to help bridge this gap."}],"type":"conference","publication_status":"published","oa_version":"Published Version","year":"2020","quality_controlled":"1","language":[{"iso":"eng"}],"scopus_import":"1","oa":1,"day":"01","publication":"Proceedings of the 2018 USENIX Annual Technical Conference","publisher":"USENIX Association","month":"01","department":[{"_id":"DaAl"}],"publication_identifier":{"isbn":["9781939133021"]}},{"article_number":"40","volume":179,"doi":"10.4230/LIPIcs.DISC.2020.40","file":[{"creator":"dernst","relation":"main_file","access_level":"open_access","checksum":"23e2d9321aef53092dc1e24a8ab82d72","date_created":"2024-03-05T07:08:27Z","success":1,"file_size":303529,"file_name":"2020_LIPIcs_Brandt.pdf","date_updated":"2024-03-05T07:08:27Z","content_type":"application/pdf","file_id":"15075"}],"day":"07","oa":1,"corr_author":"1","external_id":{"arxiv":["2005.07761"]},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","department":[{"_id":"DaAl"}],"month":"10","has_accepted_license":"1","conference":{"end_date":"2020-10-16","start_date":"2020-10-12","name":"DISC: Symposium on Distributed Computing","location":"Virtual"},"date_published":"2020-10-07T00:00:00Z","alternative_title":["LIPIcs"],"file_date_updated":"2024-03-05T07:08:27Z","article_processing_charge":"No","fulldoi":"https://doi.org/10.4230/LIPIcs.DISC.2020.40","arxiv":1,"tmp":{"image":"/images/cc_by.png","short":"CC BY (3.0)","name":"Creative Commons Attribution 3.0 Unported (CC BY 3.0)","legal_code_url":"https://creativecommons.org/licenses/by/3.0/legalcode"},"ddc":["000"],"publication_status":"published","year":"2020","quality_controlled":"1","intvolume":"       179","language":[{"iso":"eng"}],"publication":"34th International Symposium on Distributed Computing","scopus_import":"1","related_material":{"record":[{"status":"public","id":"9678","relation":"later_version"}]},"citation":{"ieee":"S. Brandt, B. Keller, J. Rybicki, J. Suomela, and J. Uitto, “Brief announcement: Efficient load-balancing through distributed token dropping,” in <i>34th International Symposium on Distributed Computing</i>, Virtual, 2020, vol. 179.","ista":"Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. 2020. Brief announcement: Efficient load-balancing through distributed token dropping. 34th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 179, 40.","short":"S. Brandt, B. Keller, J. Rybicki, J. Suomela, J. Uitto, in:, 34th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.","ama":"Brandt S, Keller B, Rybicki J, Suomela J, Uitto J. Brief announcement: Efficient load-balancing through distributed token dropping. In: <i>34th International Symposium on Distributed Computing</i>. Vol 179. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020. doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.40\">10.4230/LIPIcs.DISC.2020.40</a>","mla":"Brandt, Sebastian, et al. “Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping.” <i>34th International Symposium on Distributed Computing</i>, vol. 179, 40, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:<a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.40\">10.4230/LIPIcs.DISC.2020.40</a>.","apa":"Brandt, S., Keller, B., Rybicki, J., Suomela, J., &#38; Uitto, J. (2020). Brief announcement: Efficient load-balancing through distributed token dropping. In <i>34th International Symposium on Distributed Computing</i> (Vol. 179). Virtual: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.40\">https://doi.org/10.4230/LIPIcs.DISC.2020.40</a>","chicago":"Brandt, Sebastian, Barbara Keller, Joel Rybicki, Jukka Suomela, and Jara Uitto. “Brief Announcement: Efficient Load-Balancing through Distributed Token Dropping.” In <i>34th International Symposium on Distributed Computing</i>, Vol. 179. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href=\"https://doi.org/10.4230/LIPIcs.DISC.2020.40\">https://doi.org/10.4230/LIPIcs.DISC.2020.40</a>."},"date_updated":"2026-07-07T06:21:32Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","title":"Brief announcement: Efficient load-balancing through distributed token dropping","_id":"15074","status":"public","date_created":"2024-03-05T07:09:12Z","author":[{"first_name":"Sebastian","last_name":"Brandt","full_name":"Brandt, Sebastian"},{"full_name":"Keller, Barbara","last_name":"Keller","first_name":"Barbara"},{"last_name":"Rybicki","first_name":"Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel"},{"first_name":"Jukka","last_name":"Suomela","full_name":"Suomela, Jukka"},{"first_name":"Jara","last_name":"Uitto","full_name":"Uitto, Jara"}],"type":"conference","oa_version":"Published Version","abstract":[{"lang":"eng","text":"We introduce a new graph problem, the token dropping game, and we show how to solve it efficiently in a distributed setting. We use the token dropping game as a tool to design an efficient distributed algorithm for the stable orientation problem, which is a special case of the more general locally optimal semi-matching problem. The prior work by Czygrinow et al. (DISC 2012) finds a locally optimal semi-matching in O(Δ⁵) rounds in graphs of maximum degree Δ, which directly implies an algorithm with the same runtime for stable orientations. We improve the runtime to O(Δ⁴) for stable orientations and prove a lower bound of Ω(Δ) rounds."}]},{"das_tickbox":"1","article_processing_charge":"No","date_published":"2020-07-12T00:00:00Z","file_date_updated":"2021-05-25T09:51:36Z","conference":{"location":"Online","start_date":"2020-07-12","end_date":"2020-07-18","name":"ICML: International Conference on Machine Learning"},"has_accepted_license":"1","intvolume":"       119","year":"2020","quality_controlled":"1","ddc":["000"],"file":[{"file_name":"2020_PMLR_Kurtz.pdf","date_updated":"2021-05-25T09:51:36Z","content_type":"application/pdf","file_size":741899,"file_id":"9421","access_level":"open_access","relation":"main_file","creator":"kschuh","success":1,"checksum":"2aaaa7d7226e49161311d91627cf783b","date_created":"2021-05-25T09:51:36Z"}],"volume":119,"month":"07","department":[{"_id":"DaAl"}],"oa":1,"day":"12","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-07-07T13:42:32Z","citation":{"mla":"Kurtz, Mark, et al. “Inducing and Exploiting Activation Sparsity for Fast Neural Network Inference.” <i>37th International Conference on Machine Learning</i>, vol. 119, 2020, pp. 5533–43.","ama":"Kurtz M, Kopinsky J, Gelashvili R, et al. Inducing and exploiting activation sparsity for fast neural network inference. In: <i>37th International Conference on Machine Learning</i>. Vol 119. ; 2020:5533-5543.","short":"M. Kurtz, J. Kopinsky, R. Gelashvili, A. Matveev, J. Carr, M. Goin, W. Leiserson, S. Moore, B. Nell, N. Shavit, D.-A. Alistarh, in:, 37th International Conference on Machine Learning, 2020, pp. 5533–5543.","ista":"Kurtz M, Kopinsky J, Gelashvili R, Matveev A, Carr J, Goin M, Leiserson W, Moore S, Nell B, Shavit N, Alistarh D-A. 2020. Inducing and exploiting activation sparsity for fast neural network inference. 37th International Conference on Machine Learning. ICML: International Conference on Machine Learning vol. 119, 5533–5543.","ieee":"M. Kurtz <i>et al.</i>, “Inducing and exploiting activation sparsity for fast neural network inference,” in <i>37th International Conference on Machine Learning</i>, Online, 2020, vol. 119, pp. 5533–5543.","chicago":"Kurtz, Mark, Justin Kopinsky, Rati Gelashvili, Alexander Matveev, John Carr, Michael Goin, William Leiserson, et al. “Inducing and Exploiting Activation Sparsity for Fast Neural Network Inference.” In <i>37th International Conference on Machine Learning</i>, 119:5533–43, 2020.","apa":"Kurtz, M., Kopinsky, J., Gelashvili, R., Matveev, A., Carr, J., Goin, M., … Alistarh, D.-A. (2020). Inducing and exploiting activation sparsity for fast neural network inference. In <i>37th International Conference on Machine Learning</i> (Vol. 119, pp. 5533–5543). Online."},"page":"5533-5543","abstract":[{"lang":"eng","text":"Optimizing convolutional neural networks for fast inference has recently become an extremely active area of research. One of the go-to solutions in this context is weight pruning, which aims to reduce computational and memory footprint by removing large subsets of the connections in a neural network. Surprisingly, much less attention has been given to exploiting sparsity in the activation maps, which tend to be naturally sparse in many settings thanks to the structure of rectified linear (ReLU) activation functions. In this paper, we present an in-depth analysis of methods for maximizing the sparsity of the activations in a trained neural network, and show that, when coupled with an efficient sparse-input convolution algorithm, we can leverage this sparsity for significant performance gains. To induce highly sparse activation maps without accuracy loss, we introduce a new regularization technique, coupled with a new threshold-based sparsification method based on a parameterized activation function called Forced-Activation-Threshold Rectified Linear Unit (FATReLU). We examine the impact of our methods on popular image classification models, showing that most architectures can adapt to significantly sparser activation maps without any accuracy loss. Our second contribution is showing that these these compression gains can be translated into inference speedups: we provide a new algorithm to enable fast convolution operations over networks with sparse activations, and show that it can enable significant speedups for end-to-end inference on a range of popular models on the large-scale ImageNet image classification task on modern Intel CPUs, with little or no retraining cost. "}],"type":"conference","oa_version":"Published Version","date_created":"2021-05-23T22:01:45Z","author":[{"last_name":"Kurtz","first_name":"Mark","full_name":"Kurtz, Mark"},{"full_name":"Kopinsky, Justin","last_name":"Kopinsky","first_name":"Justin"},{"first_name":"Rati","last_name":"Gelashvili","full_name":"Gelashvili, Rati"},{"last_name":"Matveev","first_name":"Alexander","full_name":"Matveev, Alexander"},{"first_name":"John","last_name":"Carr","full_name":"Carr, John"},{"full_name":"Goin, Michael","last_name":"Goin","first_name":"Michael"},{"full_name":"Leiserson, William","first_name":"William","last_name":"Leiserson"},{"first_name":"Sage","last_name":"Moore","full_name":"Moore, Sage"},{"full_name":"Nell, Bill","last_name":"Nell","first_name":"Bill"},{"full_name":"Shavit, Nir","last_name":"Shavit","first_name":"Nir"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh","orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian"}],"status":"public","_id":"9415","title":"Inducing and exploiting activation sparsity for fast neural network inference","language":[{"iso":"eng"}],"publication_identifier":{"issn":["2640-3498"]},"scopus_import":"1","publication":"37th International Conference on Machine Learning"},{"publication":"Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming","scopus_import":"1","ec_funded":1,"publication_identifier":{"isbn":["9781450368186"]},"acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union Horizon 2020 research and innovation program, grant agreement No 805223, ERC Starting Grant ScaleML. We acknowledge the support of the Natural Sciences and\r\nEngineering Research Council of Canada (NSERC). ","OA_type":"free access","OA_place":"publisher","language":[{"iso":"eng"}],"_id":"7636","title":"Non-blocking interpolation search trees with doubly-logarithmic running time","author":[{"full_name":"Brown, Trevor A","last_name":"Brown","first_name":"Trevor A","id":"3569F0A0-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Aleksandar","last_name":"Prokopec","full_name":"Prokopec, Aleksandar"},{"id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian","full_name":"Alistarh, Dan-Adrian","orcid":"0000-0003-3650-940X"}],"date_created":"2020-04-05T22:00:49Z","status":"public","oa_version":"Published Version","type":"conference","abstract":[{"lang":"eng","text":"Balanced search trees typically use key comparisons to guide their operations, and achieve logarithmic running time. By relying on numerical properties of the keys, interpolation search achieves lower search complexity and better performance. Although interpolation-based data structures were investigated in the past, their non-blocking concurrent variants have received very little attention so far.\r\nIn this paper, we propose the first non-blocking implementation of the classic interpolation search tree (IST) data structure. For arbitrary key distributions, the data structure ensures worst-case O(log n + p) amortized time for search, insertion and deletion traversals. When the input key distributions are smooth, lookups run in expected O(log log n + p) time, and insertion and deletion run in expected amortized O(log log n + p) time, where p is a bound on the number of threads. To improve the scalability of concurrent insertion and deletion, we propose a novel parallel rebuilding technique, which should be of independent interest.\r\nWe evaluate whether the theoretical improvements translate to practice by implementing the concurrent interpolation search tree, and benchmarking it on uniform and nonuniform key distributions, for dataset sizes in the millions to billions of keys. Relative to the state-of-the-art concurrent data structures, the concurrent interpolation search tree achieves performance improvements of up to 15% under high update rates, and of up to 50% under moderate update rates. Further, ISTs exhibit up to 2X less cache-misses, and consume 1.2 -- 2.6X less memory compared to the next best alternative on typical dataset sizes. We find that the results are surprisingly robust to distributional skew, which suggests that our data structure can be a promising alternative to classic concurrent search structures."}],"project":[{"grant_number":"805223","_id":"268A44D6-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","name":"Elastic Coordination for Scalable Machine Learning"}],"citation":{"chicago":"Brown, Trevor A, Aleksandar Prokopec, and Dan-Adrian Alistarh. “Non-Blocking Interpolation Search Trees with Doubly-Logarithmic Running Time.” In <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, 276–91. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3332466.3374542\">https://doi.org/10.1145/3332466.3374542</a>.","apa":"Brown, T. A., Prokopec, A., &#38; Alistarh, D.-A. (2020). Non-blocking interpolation search trees with doubly-logarithmic running time. In <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i> (pp. 276–291). San Diego, CA, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3332466.3374542\">https://doi.org/10.1145/3332466.3374542</a>","ama":"Brown TA, Prokopec A, Alistarh D-A. Non-blocking interpolation search trees with doubly-logarithmic running time. In: <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>. Association for Computing Machinery; 2020:276-291. doi:<a href=\"https://doi.org/10.1145/3332466.3374542\">10.1145/3332466.3374542</a>","mla":"Brown, Trevor A., et al. “Non-Blocking Interpolation Search Trees with Doubly-Logarithmic Running Time.” <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, Association for Computing Machinery, 2020, pp. 276–91, doi:<a href=\"https://doi.org/10.1145/3332466.3374542\">10.1145/3332466.3374542</a>.","short":"T.A. Brown, A. Prokopec, D.-A. Alistarh, in:, Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery, 2020, pp. 276–291.","ista":"Brown TA, Prokopec A, Alistarh D-A. 2020. Non-blocking interpolation search trees with doubly-logarithmic running time. Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. PPOPP: Principles and Practice of Parallel Programming, 276–291.","ieee":"T. A. Brown, A. Prokopec, and D.-A. Alistarh, “Non-blocking interpolation search trees with doubly-logarithmic running time,” in <i>Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming</i>, San Diego, CA, United States, 2020, pp. 276–291."},"page":"276-291","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-07-28T12:49:59Z","day":"19","oa":1,"external_id":{"isi":["000564476500020"]},"department":[{"_id":"DaAl"}],"month":"02","publisher":"Association for Computing Machinery","isi":1,"doi":"10.1145/3332466.3374542","ddc":["000"],"quality_controlled":"1","year":"2020","publication_status":"published","date_published":"2020-02-19T00:00:00Z","conference":{"start_date":"2020-02-22","end_date":"2020-02-26","name":"PPOPP: Principles and Practice of Parallel Programming","location":"San Diego, CA, United States"},"article_processing_charge":"No","fulldoi":"https://doi.org/10.1145/3332466.3374542","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1145/3332466.3374542"}]},{"volume":119,"file":[{"creator":"dernst","relation":"main_file","access_level":"open_access","date_created":"2021-03-02T15:38:14Z","checksum":"f042c8d4316bd87c6361aa76f1fbdbbe","success":1,"file_size":5336380,"date_updated":"2021-03-02T15:38:14Z","content_type":"application/pdf","file_name":"2020_PMLR_Shevchenko.pdf","file_id":"9217"}],"external_id":{"arxiv":["1912.10095"]},"department":[{"_id":"MaMo"},{"_id":"DaAl"}],"month":"07","publisher":"ML Research Press","day":"13","oa":1,"arxiv":1,"file_date_updated":"2021-03-02T15:38:14Z","date_published":"2020-07-13T00:00:00Z","has_accepted_license":"1","article_processing_charge":"No","year":"2020","quality_controlled":"1","publication_status":"published","intvolume":"       119","ddc":["000"],"language":[{"iso":"eng"}],"acknowledgement":"M. Mondelli was partially supported by the 2019 LopezLoreta Prize. The authors thank Phan-Minh Nguyen for helpful discussions and the IST Distributed Algorithms and Systems Lab for providing computational resources.","publication":"Proceedings of the 37th International Conference on Machine Learning","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","date_updated":"2026-10-22T22:31:18Z","related_material":{"record":[{"id":"17465","relation":"dissertation_contains","status":"public"}]},"project":[{"name":"Prix Lopez-Loretta 2019 - Marco Mondelli","_id":"059876FA-7A3F-11EA-A408-12923DDC885E"}],"citation":{"apa":"Shevchenko, A., &#38; Mondelli, M. (2020). Landscape connectivity and dropout stability of SGD solutions for over-parameterized neural networks. In <i>Proceedings of the 37th International Conference on Machine Learning</i> (Vol. 119, pp. 8773–8784). ML Research Press.","chicago":"Shevchenko, Aleksandr, and Marco Mondelli. “Landscape Connectivity and Dropout Stability of SGD Solutions for Over-Parameterized Neural Networks.” In <i>Proceedings of the 37th International Conference on Machine Learning</i>, 119:8773–84. ML Research Press, 2020.","ieee":"A. Shevchenko and M. Mondelli, “Landscape connectivity and dropout stability of SGD solutions for over-parameterized neural networks,” in <i>Proceedings of the 37th International Conference on Machine Learning</i>, 2020, vol. 119, pp. 8773–8784.","ista":"Shevchenko A, Mondelli M. 2020. Landscape connectivity and dropout stability of SGD solutions for over-parameterized neural networks. Proceedings of the 37th International Conference on Machine Learning. vol. 119, 8773–8784.","short":"A. Shevchenko, M. Mondelli, in:, Proceedings of the 37th International Conference on Machine Learning, ML Research Press, 2020, pp. 8773–8784.","ama":"Shevchenko A, Mondelli M. Landscape connectivity and dropout stability of SGD solutions for over-parameterized neural networks. In: <i>Proceedings of the 37th International Conference on Machine Learning</i>. Vol 119. ML Research Press; 2020:8773-8784.","mla":"Shevchenko, Aleksandr, and Marco Mondelli. “Landscape Connectivity and Dropout Stability of SGD Solutions for Over-Parameterized Neural Networks.” <i>Proceedings of the 37th International Conference on Machine Learning</i>, vol. 119, ML Research Press, 2020, pp. 8773–84."},"page":"8773-8784","oa_version":"Published Version","type":"conference","abstract":[{"lang":"eng","text":"The optimization of multilayer neural networks typically leads to a solution\r\nwith zero training error, yet the landscape can exhibit spurious local minima\r\nand the minima can be disconnected. In this paper, we shed light on this\r\nphenomenon: we show that the combination of stochastic gradient descent (SGD)\r\nand over-parameterization makes the landscape of multilayer neural networks\r\napproximately connected and thus more favorable to optimization. More\r\nspecifically, we prove that SGD solutions are connected via a piecewise linear\r\npath, and the increase in loss along this path vanishes as the number of\r\nneurons grows large. This result is a consequence of the fact that the\r\nparameters found by SGD are increasingly dropout stable as the network becomes\r\nwider. We show that, if we remove part of the neurons (and suitably rescale the\r\nremaining ones), the change in loss is independent of the total number of\r\nneurons, and it depends only on how many neurons are left. Our results exhibit\r\na mild dependence on the input dimension: they are dimension-free for two-layer\r\nnetworks and depend linearly on the dimension for multilayer networks. We\r\nvalidate our theoretical findings with numerical experiments for different\r\narchitectures and classification tasks."}],"_id":"9198","title":"Landscape connectivity and dropout stability of SGD solutions for over-parameterized neural networks","date_created":"2021-02-25T09:36:22Z","author":[{"id":"F2B06EC2-C99E-11E9-89F0-752EE6697425","first_name":"Aleksandr","last_name":"Shevchenko","full_name":"Shevchenko, Aleksandr"},{"full_name":"Mondelli, Marco","orcid":"0000-0002-3242-7020","first_name":"Marco","last_name":"Mondelli","id":"27EB676C-8706-11E9-9510-7717E6697425"}],"status":"public"},{"publication_status":"published","oa_version":"None","type":"conference_poster","quality_controlled":"1","year":"2019","abstract":[{"text":"Traditional concurrent programming involves manipulating shared mutable state. Alternatives to this programming style are communicating sequential processes (CSP) [1] and actor [2] models, which share data via explicit communication. Rendezvous channelis the common abstraction for communication between several processes, where senders and receivers perform a rendezvous handshake as a part of their protocol (senders wait for receivers and vice versa). Additionally to this, channels support the select expression. In this work, we present the first efficient lock-free channel algorithm, and compare it against Go [3] and Kotlin [4] baseline implementations.","lang":"eng"}],"title":"Lock-free channels for programming via communicating sequential processes","_id":"6485","date_created":"2019-05-24T10:09:12Z","status":"public","author":[{"id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87","last_name":"Koval","first_name":"Nikita","full_name":"Koval, Nikita"},{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh"},{"full_name":"Elizarov, Roman","last_name":"Elizarov","first_name":"Roman"}],"date_updated":"2024-12-11T11:42:22Z","fulldoi":"https://doi.org/10.1145/3293883.3297000","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Washington, NY, United States","start_date":"2019-02-16","end_date":"2019-02-20","name":"PPoPP: Principles and Practice of Parallel Programming"},"date_published":"2019-02-01T00:00:00Z","article_processing_charge":"No","citation":{"chicago":"Koval, Nikita, Dan-Adrian Alistarh, and Roman Elizarov. <i>Lock-Free Channels for Programming via Communicating Sequential Processes</i>. <i>Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming</i>. ACM, 2019. <a href=\"https://doi.org/10.1145/3293883.3297000\">https://doi.org/10.1145/3293883.3297000</a>.","apa":"Koval, N., Alistarh, D.-A., &#38; Elizarov, R. (2019). <i>Lock-free channels for programming via communicating sequential processes</i>. <i>Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming</i> (pp. 417–418). Washington, NY, United States: ACM. <a href=\"https://doi.org/10.1145/3293883.3297000\">https://doi.org/10.1145/3293883.3297000</a>","ama":"Koval N, Alistarh D-A, Elizarov R. <i>Lock-Free Channels for Programming via Communicating Sequential Processes</i>. ACM; 2019:417-418. doi:<a href=\"https://doi.org/10.1145/3293883.3297000\">10.1145/3293883.3297000</a>","mla":"Koval, Nikita, et al. “Lock-Free Channels for Programming via Communicating Sequential Processes.” <i>Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming</i>, ACM, 2019, pp. 417–18, doi:<a href=\"https://doi.org/10.1145/3293883.3297000\">10.1145/3293883.3297000</a>.","ieee":"N. Koval, D.-A. Alistarh, and R. Elizarov, <i>Lock-free channels for programming via communicating sequential processes</i>. ACM, 2019, pp. 417–418.","short":"N. Koval, D.-A. Alistarh, R. Elizarov, Lock-Free Channels for Programming via Communicating Sequential Processes, ACM, 2019.","ista":"Koval N, Alistarh D-A, Elizarov R. 2019. Lock-free channels for programming via communicating sequential processes, ACM,p."},"page":"417-418","external_id":{"isi":["000587604600044"]},"publisher":"ACM","publication_identifier":{"isbn":["9781450362252"]},"department":[{"_id":"DaAl"}],"month":"02","publication":"Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming","day":"01","language":[{"iso":"eng"}],"doi":"10.1145/3293883.3297000","isi":1},{"language":[{"iso":"eng"}],"scopus_import":"1","publication":"31st ACM Symposium on Parallelism in Algorithms and Architectures","ec_funded":1,"publication_identifier":{"isbn":["9781450361842"]},"project":[{"name":"Elastic Coordination for Scalable Machine Learning","call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223"}],"page":"145-154","citation":{"short":"D.-A. Alistarh, G. Nadiradze, N. Koval, in:, 31st ACM Symposium on Parallelism in Algorithms and Architectures, ACM, 2019, pp. 145–154.","ieee":"D.-A. Alistarh, G. Nadiradze, and N. Koval, “Efficiency guarantees for parallel incremental algorithms under relaxed schedulers,” in <i>31st ACM Symposium on Parallelism in Algorithms and Architectures</i>, Phoenix, AZ, United States, 2019, pp. 145–154.","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.","mla":"Alistarh, Dan-Adrian, et al. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” <i>31st ACM Symposium on Parallelism in Algorithms and Architectures</i>, ACM, 2019, pp. 145–54, doi:<a href=\"https://doi.org/10.1145/3323165.3323201\">10.1145/3323165.3323201</a>.","ama":"Alistarh D-A, Nadiradze G, Koval N. Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In: <i>31st ACM Symposium on Parallelism in Algorithms and Architectures</i>. ACM; 2019:145-154. doi:<a href=\"https://doi.org/10.1145/3323165.3323201\">10.1145/3323165.3323201</a>","apa":"Alistarh, D.-A., Nadiradze, G., &#38; Koval, N. (2019). Efficiency guarantees for parallel incremental algorithms under relaxed schedulers. In <i>31st ACM Symposium on Parallelism in Algorithms and Architectures</i> (pp. 145–154). Phoenix, AZ, United States: ACM. <a href=\"https://doi.org/10.1145/3323165.3323201\">https://doi.org/10.1145/3323165.3323201</a>","chicago":"Alistarh, Dan-Adrian, Giorgi Nadiradze, and Nikita Koval. “Efficiency Guarantees for Parallel Incremental Algorithms under Relaxed Schedulers.” In <i>31st ACM Symposium on Parallelism in Algorithms and Architectures</i>, 145–54. ACM, 2019. <a href=\"https://doi.org/10.1145/3323165.3323201\">https://doi.org/10.1145/3323165.3323201</a>."},"related_material":{"record":[{"relation":"dissertation_contains","id":"10429","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-04-08T07:00:45Z","status":"public","author":[{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","last_name":"Alistarh","first_name":"Dan-Adrian"},{"id":"3279A00C-F248-11E8-B48F-1D18A9856A87","last_name":"Nadiradze","first_name":"Giorgi","orcid":"0000-0001-5634-0731","full_name":"Nadiradze, Giorgi"},{"full_name":"Koval, Nikita","first_name":"Nikita","last_name":"Koval","id":"2F4DB10C-F248-11E8-B48F-1D18A9856A87"}],"date_created":"2019-07-24T08:59:36Z","_id":"6673","title":"Efficiency guarantees for parallel incremental algorithms under relaxed schedulers","abstract":[{"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.","lang":"eng"}],"oa_version":"Preprint","type":"conference","isi":1,"doi":"10.1145/3323165.3323201","oa":1,"day":"01","month":"06","department":[{"_id":"DaAl"}],"publisher":"ACM","external_id":{"arxiv":["2003.09363"],"isi":["000507618500018"]},"article_processing_charge":"No","date_published":"2019-06-01T00:00:00Z","conference":{"start_date":"2019-06-22","end_date":"2019-06-24","name":"SPAA: Symposium on Parallelism in Algorithms and Architectures","location":"Phoenix, AZ, United States"},"arxiv":1,"main_file_link":[{"url":"https://arxiv.org/abs/2003.09363","open_access":"1"}],"fulldoi":"https://doi.org/10.1145/3323165.3323201","quality_controlled":"1","year":"2019","publication_status":"published"},{"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781450367059"]},"scopus_import":"1","publication":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing","date_updated":"2025-05-14T11:26:07Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"ama":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. Why extension-based proofs fail. In: <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>. ACM; 2019:986-996. doi:<a href=\"https://doi.org/10.1145/3313276.3316407\">10.1145/3313276.3316407</a>","mla":"Alistarh, Dan-Adrian, et al. “Why Extension-Based Proofs Fail.” <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, ACM, 2019, pp. 986–96, doi:<a href=\"https://doi.org/10.1145/3313276.3316407\">10.1145/3313276.3316407</a>.","ista":"Alistarh D-A, Aspnes J, Ellen F, Gelashvili R, Zhu L. 2019. Why extension-based proofs fail. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. STOC: Symposium on Theory of Computing, 986–996.","ieee":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, and L. Zhu, “Why extension-based proofs fail,” in <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, Phoenix, AZ, United States, 2019, pp. 986–996.","short":"D.-A. Alistarh, J. Aspnes, F. Ellen, R. Gelashvili, L. Zhu, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2019, pp. 986–996.","chicago":"Alistarh, Dan-Adrian, James Aspnes, Faith Ellen, Rati Gelashvili, and Leqi Zhu. “Why Extension-Based Proofs Fail.” In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, 986–96. ACM, 2019. <a href=\"https://doi.org/10.1145/3313276.3316407\">https://doi.org/10.1145/3313276.3316407</a>.","apa":"Alistarh, D.-A., Aspnes, J., Ellen, F., Gelashvili, R., &#38; Zhu, L. (2019). Why extension-based proofs fail. In <i>Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i> (pp. 986–996). Phoenix, AZ, United States: ACM. <a href=\"https://doi.org/10.1145/3313276.3316407\">https://doi.org/10.1145/3313276.3316407</a>"},"page":"986-996","related_material":{"record":[{"relation":"later_version","id":"14364","status":"public"}]},"abstract":[{"lang":"eng","text":"It is impossible to deterministically solve wait-free consensus in an asynchronous system. The classic proof uses a valency argument, which constructs an infinite execution by repeatedly extending a finite execution. We introduce extension-based proofs, a class of impossibility proofs that are modelled as an interaction between a prover and a protocol and that include valency arguments.\r\n\r\nUsing proofs based on combinatorial topology, it has been shown that it is impossible to deterministically solve k-set agreement among n > k ≥ 2 processes in a wait-free manner. However, it was unknown whether proofs based on simpler techniques were possible. We show that this impossibility result cannot be obtained by an extension-based proof and, hence, extension-based proofs are limited in power."}],"oa_version":"Preprint","type":"conference","status":"public","author":[{"orcid":"0000-0003-3650-940X","full_name":"Alistarh, Dan-Adrian","id":"4A899BFC-F248-11E8-B48F-1D18A9856A87","first_name":"Dan-Adrian","last_name":"Alistarh"},{"first_name":"James","last_name":"Aspnes","full_name":"Aspnes, James"},{"full_name":"Ellen, Faith","last_name":"Ellen","first_name":"Faith"},{"first_name":"Rati","last_name":"Gelashvili","full_name":"Gelashvili, Rati"},{"last_name":"Zhu","first_name":"Leqi","full_name":"Zhu, Leqi"}],"date_created":"2019-07-24T09:13:05Z","title":"Why extension-based proofs fail","_id":"6676","doi":"10.1145/3313276.3316407","isi":1,"publisher":"ACM","month":"06","department":[{"_id":"DaAl"}],"external_id":{"arxiv":["1811.01421"],"isi":["000523199100089"]},"oa":1,"day":"01","main_file_link":[{"url":"https://arxiv.org/abs/1811.01421","open_access":"1"}],"arxiv":1,"fulldoi":"https://doi.org/10.1145/3313276.3316407","article_processing_charge":"No","conference":{"location":"Phoenix, AZ, United States","end_date":"2019-06-26","start_date":"2019-06-23","name":"STOC: Symposium on Theory of Computing"},"date_published":"2019-06-01T00:00:00Z","publication_status":"published","quality_controlled":"1","year":"2019"},{"month":"07","department":[{"_id":"DaAl"}],"publisher":"Electronic Journal of Combinatorics","external_id":{"arxiv":["1808.04148"]},"oa":1,"corr_author":"1","day":"19","file":[{"creator":"dernst","relation":"main_file","access_level":"open_access","date_created":"2019-08-05T06:46:55Z","checksum":"20fc366fc6683ef0b074a019b73a663a","file_size":533697,"date_updated":"2020-07-14T12:47:39Z","content_type":"application/pdf","file_name":"2019_eJourCombinatorics_Jelinek.pdf","file_id":"6764"}],"doi":"10.37236/8096","volume":26,"article_number":"P3.17","intvolume":"        26","quality_controlled":"1","year":"2019","publication_status":"published","tmp":{"image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"ddc":["510"],"arxiv":1,"fulldoi":"https://doi.org/10.37236/8096","article_processing_charge":"Yes","file_date_updated":"2020-07-14T12:47:39Z","date_published":"2019-07-19T00:00:00Z","has_accepted_license":"1","publication_identifier":{"eissn":["1077-8926"]},"ec_funded":1,"issue":"3","scopus_import":"1","publication":"Electronic Journal of Combinatorics","language":[{"iso":"eng"}],"OA_place":"publisher","OA_type":"gold","abstract":[{"text":"We consider the graph class Grounded-L corresponding to graphs that admit an intersection representation by L-shaped curves, where additionally the topmost points of each curve are assumed to belong to a common horizontal line. We prove that Grounded-L graphs admit an equivalent characterisation in terms of vertex ordering with forbidden patterns. \r\nWe also compare this class to related intersection classes, such as the grounded segment graphs, the monotone L-graphs (a.k.a. max point-tolerance graphs), or the outer-1-string graphs. We give constructions showing that these classes are all distinct and satisfy only trivial or previously known inclusions.","lang":"eng"}],"article_type":"original","oa_version":"Published Version","type":"journal_article","status":"public","author":[{"full_name":"Jelínek, Vít","last_name":"Jelínek","first_name":"Vít"},{"id":"4B865388-F248-11E8-B48F-1D18A9856A87","last_name":"Töpfer","first_name":"Martin","full_name":"Töpfer, Martin"}],"date_created":"2019-08-04T21:59:20Z","_id":"6759","title":"On grounded L-graphs and their relatives","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2025-06-26T12:25:39Z","project":[{"grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","name":"International IST Doctoral Program","call_identifier":"H2020"}],"citation":{"apa":"Jelínek, V., &#38; Töpfer, M. (2019). On grounded L-graphs and their relatives. <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics. <a href=\"https://doi.org/10.37236/8096\">https://doi.org/10.37236/8096</a>","chicago":"Jelínek, Vít, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.” <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics, 2019. <a href=\"https://doi.org/10.37236/8096\">https://doi.org/10.37236/8096</a>.","short":"V. Jelínek, M. Töpfer, Electronic Journal of Combinatorics 26 (2019).","ieee":"V. Jelínek and M. Töpfer, “On grounded L-graphs and their relatives,” <i>Electronic Journal of Combinatorics</i>, vol. 26, no. 3. Electronic Journal of Combinatorics, 2019.","ista":"Jelínek V, Töpfer M. 2019. On grounded L-graphs and their relatives. Electronic Journal of Combinatorics. 26(3), P3.17.","mla":"Jelínek, Vít, and Martin Töpfer. “On Grounded L-Graphs and Their Relatives.” <i>Electronic Journal of Combinatorics</i>, vol. 26, no. 3, P3.17, Electronic Journal of Combinatorics, 2019, doi:<a href=\"https://doi.org/10.37236/8096\">10.37236/8096</a>.","ama":"Jelínek V, Töpfer M. On grounded L-graphs and their relatives. <i>Electronic Journal of Combinatorics</i>. 2019;26(3). doi:<a href=\"https://doi.org/10.37236/8096\">10.37236/8096</a>"},"DOAJ_listed":"1"}]