[{"keyword":["General Computer Science","Theoretical Computer Science"],"file":[{"checksum":"efd5b7e738bf845312ba53889a3e13e4","file_size":603570,"file_id":"17263","relation":"main_file","creator":"dernst","access_level":"open_access","date_updated":"2024-07-16T12:02:25Z","file_name":"2024_TheorComputerScience_Schmid.pdf","content_type":"application/pdf","date_created":"2024-07-16T12:02:25Z","success":1}],"oa":1,"type":"journal_article","abstract":[{"lang":"eng","text":"We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e.g., finds applications in cryptocurrency networks. The capacity of a link (u, v) is determined by how many nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given (u, v) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link (u, v) decreases by x. Correspondingly, v's capacity on \r\n increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of (1+E) . (1+3)  for some arbitrary E>0."}],"date_created":"2024-01-16T13:40:41Z","quality_controlled":"1","status":"public","corr_author":"1","article_number":"114353","article_type":"original","author":[{"full_name":"Schmid, Stefan","last_name":"Schmid","first_name":"Stefan"},{"first_name":"Jakub","last_name":"Svoboda","orcid":"0000-0002-1419-3267","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","full_name":"Svoboda, Jakub"},{"last_name":"Yeo","first_name":"Michelle X","orcid":"0009-0001-3676-4809","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","full_name":"Yeo, Michelle X"}],"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020"}],"year":"2024","doi":"10.1016/j.tcs.2023.114353","day":"21","scopus_import":"1","month":"03","title":"Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation","ddc":["000"],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"19985"}]},"acknowledgement":"We thank Mahsa Bastankhah and Mohammad Ali Maddah-Ali for fruitful discussions about different variants of the problem. This work is supported by the European Research Council (ERC) Consolidator Project 864228 (AdjustNet), 2020-2025, the ERC CoG 863818 (ForM-SMArt), and the German Research Foundation (DFG) grant 470029389 (FlexNets), 2021-2024.","isi":1,"tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"publication":"Theoretical Computer Science","intvolume":"       989","file_date_updated":"2024-07-16T12:02:25Z","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","ec_funded":1,"oa_version":"Published Version","volume":989,"date_published":"2024-03-21T00:00:00Z","publication_status":"published","publisher":"Elsevier","language":[{"iso":"eng"}],"has_accepted_license":"1","external_id":{"isi":["001168211400001"]},"publication_identifier":{"issn":["0304-3975"]},"citation":{"apa":"Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2024). Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">https://doi.org/10.1016/j.tcs.2023.114353</a>","mla":"Schmid, Stefan, et al. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>Theoretical Computer Science</i>, vol. 989, 114353, Elsevier, 2024, doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>.","ama":"Schmid S, Svoboda J, Yeo MX. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. <i>Theoretical Computer Science</i>. 2024;989. doi:<a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">10.1016/j.tcs.2023.114353</a>","short":"S. Schmid, J. Svoboda, M.X. Yeo, Theoretical Computer Science 989 (2024).","ista":"Schmid S, Svoboda J, Yeo MX. 2024. Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation. Theoretical Computer Science. 989, 114353.","chicago":"Schmid, Stefan, Jakub Svoboda, and Michelle X Yeo. “Weighted Packet Selection for Rechargeable Links in Cryptocurrency Networks: Complexity and Approximation.” <i>Theoretical Computer Science</i>. Elsevier, 2024. <a href=\"https://doi.org/10.1016/j.tcs.2023.114353\">https://doi.org/10.1016/j.tcs.2023.114353</a>.","ieee":"S. Schmid, J. Svoboda, and M. X. Yeo, “Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation,” <i>Theoretical Computer Science</i>, vol. 989. Elsevier, 2024."},"department":[{"_id":"KrCh"},{"_id":"KrPi"}],"date_updated":"2025-12-02T14:02:37Z","article_processing_charge":"Yes (via OA deal)","_id":"14820"},{"abstract":[{"lang":"eng","text":"Most permissionless blockchains inherently suffer from throughput limitations. Layer-2 systems, such as side-chains or Rollups, have been proposed as a possible strategy to overcome this limitation. Layer-2 systems interact with the main-chain in two ways. First, users can move funds from/to the main-chain to/from the layer-2. Second, layer-2 systems periodically synchronize with the main-chain to keep some form of log of their activity on the main-chain - this log is key for security. Due to this interaction with the main-chain, which is necessary and recurrent, layer-2 systems impose some load on the main-chain. The impact of such load on the main-chain has been, so far, poorly understood. In addition to that, layer-2 approaches typically sacrifice decentralization and security in favor of higher throughput. This paper presents an experimental study that analyzes the current state of Ethereum layer-2 projects. Our goal is to assess the load they impose on Ethereum and to understand their scalability potential in the long-run. Our analysis shows that the impact of any given layer-2 on the main-chain is the result of both technical aspects (how state is logged on the main-chain) and user behavior (how often users decide to transfer funds between the layer-2 and the main-chain). Based on our observations, we infer that without efficient mechanisms that allow users to transfer funds in a secure and fast manner directly from one layer-2 project to another, current layer-2 systems will not be able to scale Ethereum effectively, regardless of their technical solutions. Furthermore, from our results, we conclude that the layer-2 systems that offer similar security guarantees as Ethereum have limited scalability potential, while approaches that offer better performance, sacrifice security and lead to an increase in centralization which runs against the end-goals of permissionless blockchains."}],"date_created":"2023-08-09T12:09:57Z","keyword":["General Engineering","General Materials Science","General Computer Science","Electrical and Electronic Engineering"],"file":[{"file_name":"2023_IEEEAccess_Neiheiser.pdf","date_created":"2023-08-22T06:37:48Z","content_type":"application/pdf","success":1,"relation":"main_file","access_level":"open_access","creator":"dernst","date_updated":"2023-08-22T06:37:48Z","checksum":"4b80b0ff212edf7e5842fbdd53784432","file_size":1289285,"file_id":"14166"}],"oa":1,"type":"journal_article","corr_author":"1","quality_controlled":"1","status":"public","author":[{"last_name":"Neiheiser","first_name":"Ray","orcid":"0000-0001-7227-8309","id":"f09651b9-fec0-11ec-b5d8-934aff0e52a4","full_name":"Neiheiser, Ray"},{"full_name":"Inacio, Gustavo","first_name":"Gustavo","last_name":"Inacio"},{"last_name":"Rech","first_name":"Luciana","full_name":"Rech, Luciana"},{"full_name":"Montez, Carlos","last_name":"Montez","first_name":"Carlos"},{"first_name":"Miguel","last_name":"Matos","full_name":"Matos, Miguel"},{"last_name":"Rodrigues","first_name":"Luis","full_name":"Rodrigues, Luis"}],"year":"2023","doi":"10.1109/access.2023.3237897","day":"01","scopus_import":"1","page":"8651-8662","article_type":"original","ddc":["000"],"month":"08","title":"Practical limitations of Ethereum’s layer-2","publication":"IEEE Access","file_date_updated":"2023-08-22T06:37:48Z","intvolume":"        11","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"This work was supported in part by the Coordenação de Aperfeiçoamento de Pessoal de Nivel Superior (CAPES)—Brazil (CAPES), in part by the Fundação para a Ciência e Tecnologia (FCT) under Project UIDB/50021/2020 and Grant 2020.05270.BD, in part by the Project COSMOS (via the Orçamento de Estado (OE) with ref. PTDC/EEI-COM/29271/2017 and via the ‘‘Programa Operacional Regional de Lisboa na sua componente Fundo Europeu de Desenvolvimento Regional (FEDER)’’ with ref. Lisboa-01-0145-FEDER-029271), and in part by the project Angainor with reference LISBOA-01-0145-FEDER-031456 as well as supported by Meta Platforms for the project key Transparency at Scale.","isi":1,"tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"publication_status":"published","publisher":"Institute of Electrical and Electronics Engineers","oa_version":"Published Version","date_published":"2023-08-01T00:00:00Z","volume":11,"external_id":{"isi":["000927831000001"]},"publication_identifier":{"issn":["2169-3536"]},"citation":{"chicago":"Neiheiser, Ray, Gustavo Inacio, Luciana Rech, Carlos Montez, Miguel Matos, and Luis Rodrigues. “Practical Limitations of Ethereum’s Layer-2.” <i>IEEE Access</i>. Institute of Electrical and Electronics Engineers, 2023. <a href=\"https://doi.org/10.1109/access.2023.3237897\">https://doi.org/10.1109/access.2023.3237897</a>.","ieee":"R. Neiheiser, G. Inacio, L. Rech, C. Montez, M. Matos, and L. Rodrigues, “Practical limitations of Ethereum’s layer-2,” <i>IEEE Access</i>, vol. 11. Institute of Electrical and Electronics Engineers, pp. 8651–8662, 2023.","ama":"Neiheiser R, Inacio G, Rech L, Montez C, Matos M, Rodrigues L. Practical limitations of Ethereum’s layer-2. <i>IEEE Access</i>. 2023;11:8651-8662. doi:<a href=\"https://doi.org/10.1109/access.2023.3237897\">10.1109/access.2023.3237897</a>","mla":"Neiheiser, Ray, et al. “Practical Limitations of Ethereum’s Layer-2.” <i>IEEE Access</i>, vol. 11, Institute of Electrical and Electronics Engineers, 2023, pp. 8651–62, doi:<a href=\"https://doi.org/10.1109/access.2023.3237897\">10.1109/access.2023.3237897</a>.","short":"R. Neiheiser, G. Inacio, L. Rech, C. Montez, M. Matos, L. Rodrigues, IEEE Access 11 (2023) 8651–8662.","ista":"Neiheiser R, Inacio G, Rech L, Montez C, Matos M, Rodrigues L. 2023. Practical limitations of Ethereum’s layer-2. IEEE Access. 11, 8651–8662.","apa":"Neiheiser, R., Inacio, G., Rech, L., Montez, C., Matos, M., &#38; Rodrigues, L. (2023). Practical limitations of Ethereum’s layer-2. <i>IEEE Access</i>. Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/access.2023.3237897\">https://doi.org/10.1109/access.2023.3237897</a>"},"department":[{"_id":"ElKo"}],"language":[{"iso":"eng"}],"has_accepted_license":"1","date_updated":"2024-10-09T21:06:38Z","article_processing_charge":"Yes","_id":"13988"},{"type":"journal_article","keyword":["General Mathematics","General Computer Science"],"oa":1,"date_created":"2023-02-16T07:03:52Z","abstract":[{"lang":"eng","text":"he approximate graph coloring problem, whose complexity is unresolved in most cases, concerns finding a c-coloring of a graph that is promised to be k-colorable, where c≥k. This problem naturally generalizes to promise graph homomorphism problems and further to promise constraint satisfaction problems. The complexity of these problems has recently been studied through an algebraic approach. In this paper, we introduce two new techniques to analyze the complexity of promise CSPs: one is based on topology and the other on adjunction. We apply these techniques, together with the previously introduced algebraic approach, to obtain new unconditional NP-hardness results for a significant class of approximate graph coloring and promise graph homomorphism problems."}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2003.11351"}],"status":"public","arxiv":1,"quality_controlled":"1","article_type":"original","day":"01","scopus_import":"1","page":"38-79","author":[{"full_name":"Krokhin, Andrei","first_name":"Andrei","last_name":"Krokhin"},{"id":"ec596741-c539-11ec-b829-c79322a91242","full_name":"Opršal, Jakub","orcid":"0000-0003-1245-3456","last_name":"Opršal","first_name":"Jakub"},{"first_name":"Marcin","last_name":"Wrochna","full_name":"Wrochna, Marcin"},{"full_name":"Živný, Stanislav","last_name":"Živný","first_name":"Stanislav"}],"project":[{"name":"IST-BRIDGE: International postdoctoral program","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413","call_identifier":"H2020"}],"doi":"10.1137/20m1378223","year":"2023","title":"Topology and adjunction in promise constraint satisfaction","month":"01","acknowledgement":"Andrei Krokhin and Jakub Opršal were supported by the UK EPSRC grant EP/R034516/1. Jakub Opršal has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No 101034413. Stanislav Živný was supported by a Royal Society University Research Fellowship. 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 714532). The paper re\u001eects only the authors’ views and not the views of the ERC or the European Commission. ","isi":1,"intvolume":"        52","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication":"SIAM Journal on Computing","volume":52,"date_published":"2023-01-01T00:00:00Z","ec_funded":1,"oa_version":"Preprint","publication_status":"published","publisher":"Society for Industrial and Applied Mathematics","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"citation":{"chicago":"Krokhin, Andrei, Jakub Opršal, Marcin Wrochna, and Stanislav Živný. “Topology and Adjunction in Promise Constraint Satisfaction.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2023. <a href=\"https://doi.org/10.1137/20m1378223\">https://doi.org/10.1137/20m1378223</a>.","ieee":"A. Krokhin, J. Opršal, M. Wrochna, and S. Živný, “Topology and adjunction in promise constraint satisfaction,” <i>SIAM Journal on Computing</i>, vol. 52, no. 1. Society for Industrial and Applied Mathematics, pp. 38–79, 2023.","apa":"Krokhin, A., Opršal, J., Wrochna, M., &#38; Živný, S. (2023). Topology and adjunction in promise constraint satisfaction. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20m1378223\">https://doi.org/10.1137/20m1378223</a>","ama":"Krokhin A, Opršal J, Wrochna M, Živný S. Topology and adjunction in promise constraint satisfaction. <i>SIAM Journal on Computing</i>. 2023;52(1):38-79. doi:<a href=\"https://doi.org/10.1137/20m1378223\">10.1137/20m1378223</a>","mla":"Krokhin, Andrei, et al. “Topology and Adjunction in Promise Constraint Satisfaction.” <i>SIAM Journal on Computing</i>, vol. 52, no. 1, Society for Industrial and Applied Mathematics, 2023, pp. 38–79, doi:<a href=\"https://doi.org/10.1137/20m1378223\">10.1137/20m1378223</a>.","short":"A. Krokhin, J. Opršal, M. Wrochna, S. Živný, SIAM Journal on Computing 52 (2023) 38–79.","ista":"Krokhin A, Opršal J, Wrochna M, Živný S. 2023. Topology and adjunction in promise constraint satisfaction. SIAM Journal on Computing. 52(1), 38–79."},"department":[{"_id":"UlWa"}],"external_id":{"isi":["000955000000001"],"arxiv":["2003.11351"]},"_id":"12563","date_updated":"2025-05-14T10:51:32Z","article_processing_charge":"No","issue":"1"},{"publication_status":"published","publisher":"Springer Nature","volume":13,"date_published":"2022-05-01T00:00:00Z","oa_version":"Submitted Version","file_date_updated":"2022-12-20T23:30:08Z","intvolume":"        13","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication":"Journal of Ambient Intelligence and Humanized Computing","acknowledgement":"The third author acknowledges the funding received from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.","isi":1,"_id":"10208","date_updated":"2025-04-15T07:16:55Z","article_processing_charge":"No","publication_identifier":{"eissn":["1868-5145"],"issn":["1868-5137"]},"citation":{"ista":"Goudarzi S, Sharif M, Karimipour F. 2022. A context-aware dimension reduction framework for trajectory and health signal analyses. Journal of Ambient Intelligence and Humanized Computing. 13, 2621–2635.","short":"S. Goudarzi, M. Sharif, F. Karimipour, Journal of Ambient Intelligence and Humanized Computing 13 (2022) 2621–2635.","ama":"Goudarzi S, Sharif M, Karimipour F. A context-aware dimension reduction framework for trajectory and health signal analyses. <i>Journal of Ambient Intelligence and Humanized Computing</i>. 2022;13:2621–2635. doi:<a href=\"https://doi.org/10.1007/s12652-021-03569-z\">10.1007/s12652-021-03569-z</a>","mla":"Goudarzi, Samira, et al. “A Context-Aware Dimension Reduction Framework for Trajectory and Health Signal Analyses.” <i>Journal of Ambient Intelligence and Humanized Computing</i>, vol. 13, Springer Nature, 2022, pp. 2621–2635, doi:<a href=\"https://doi.org/10.1007/s12652-021-03569-z\">10.1007/s12652-021-03569-z</a>.","apa":"Goudarzi, S., Sharif, M., &#38; Karimipour, F. (2022). A context-aware dimension reduction framework for trajectory and health signal analyses. <i>Journal of Ambient Intelligence and Humanized Computing</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s12652-021-03569-z\">https://doi.org/10.1007/s12652-021-03569-z</a>","ieee":"S. Goudarzi, M. Sharif, and F. Karimipour, “A context-aware dimension reduction framework for trajectory and health signal analyses,” <i>Journal of Ambient Intelligence and Humanized Computing</i>, vol. 13. Springer Nature, pp. 2621–2635, 2022.","chicago":"Goudarzi, Samira, Mohammad Sharif, and Farid Karimipour. “A Context-Aware Dimension Reduction Framework for Trajectory and Health Signal Analyses.” <i>Journal of Ambient Intelligence and Humanized Computing</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s12652-021-03569-z\">https://doi.org/10.1007/s12652-021-03569-z</a>."},"department":[{"_id":"HeEd"}],"external_id":{"isi":["000712198000001"]},"language":[{"iso":"eng"}],"has_accepted_license":"1","status":"public","quality_controlled":"1","date_created":"2021-11-02T09:28:55Z","abstract":[{"text":"It is practical to collect a huge amount of movement data and environmental context information along with the health signals of individuals because there is the emergence of new generations of positioning and tracking technologies and rapid advancements of health sensors. The study of the relations between these datasets and their sequence similarity analysis is of interest to many applications such as health monitoring and recommender systems. However, entering all movement parameters and health signals can lead to the complexity of the problem and an increase in its computational load. In this situation, dimension reduction techniques can be used to avoid consideration of simultaneous dependent parameters in the process of similarity measurement of the trajectories. The present study provides a framework, named CaDRAW, to use spatial–temporal data and movement parameters along with independent context information in the process of measuring the similarity of trajectories. In this regard, the omission of dependent movement characteristic signals is conducted by using an unsupervised feature selection dimension reduction technique. To evaluate the effectiveness of the proposed framework, it was applied to a real contextualized movement and related health signal datasets of individuals. The results indicated the capability of the proposed framework in measuring the similarity and in decreasing the characteristic signals in such a way that the similarity results -before and after reduction of dependent characteristic signals- have small differences. The mean differences between the obtained results before and after reducing the dimension were 0.029 and 0.023 for the round path, respectively.","lang":"eng"}],"type":"journal_article","keyword":["general computer science"],"file":[{"embargo":"2022-11-12","date_created":"2021-11-12T19:38:05Z","content_type":"application/pdf","file_name":"A Context‑aware Dimension Reduction Framework - Journal of Ambient Intelligence 2021 (Preprint version).pdf","date_updated":"2022-12-20T23:30:08Z","creator":"fkarimip","access_level":"open_access","relation":"main_file","file_id":"10279","file_size":1634958,"checksum":"0a8961416a9bb2be5a1cebda65468bcf"}],"oa":1,"ddc":["000"],"title":"A context-aware dimension reduction framework for trajectory and health signal analyses","month":"05","day":"01","scopus_import":"1","page":"2621–2635","project":[{"_id":"268116B8-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"Z00342","name":"Mathematics, Computer Science"}],"author":[{"full_name":"Goudarzi, Samira","last_name":"Goudarzi","first_name":"Samira"},{"first_name":"Mohammad","last_name":"Sharif","full_name":"Sharif, Mohammad"},{"last_name":"Karimipour","first_name":"Farid","orcid":"0000-0001-6746-4174","id":"2A2BCDC4-CF62-11E9-BE5E-3B1EE6697425","full_name":"Karimipour, Farid"}],"doi":"10.1007/s12652-021-03569-z","year":"2022","article_type":"original"},{"title":"Simple, deterministic, constant-round coloring in congested clique and MPC","month":"01","day":"01","scopus_import":"1","page":"1603-1626","author":[{"full_name":"Czumaj, Artur","first_name":"Artur","last_name":"Czumaj"},{"last_name":"Davies","first_name":"Peter","orcid":"0000-0002-5646-9524","full_name":"Davies, Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425"},{"full_name":"Parter, Merav","last_name":"Parter","first_name":"Merav"}],"project":[{"grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships"}],"doi":"10.1137/20m1366502","year":"2021","article_type":"original","status":"public","quality_controlled":"1","date_created":"2024-04-03T07:53:22Z","abstract":[{"text":"We settle the complexity of the (∆ + 1)-coloring and (∆ + 1)-list coloring problems intheCONGESTED CLIQUEmodel by presenting a simpledeterministicalgorithm for both problemsrunning in a constant number of rounds.  This matches the complexity of the recent breakthroughrandomizedconstant-round (∆ + 1)-list coloring algorithm due to Chang et al.  [Proceedings of the38th  ACM  Symposium  on  Principles  of  Distributed  Computing,  2019]  and  significantly  improvesupon the state-of-the-artO(log ∆)-round deterministic (∆ + 1)-coloring bound of Parter [Proceed-ings of the 45th Annual International Colloquium on Automata, Languages and Programming].  Aremarkable property of our algorithm is its simplicity.  Whereas the state-of-the-artrandomizedal-gorithms for this problem are based on the quite involved local coloring algorithm of Chang, Li, andPettie [Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018],our algorithm can be described in just a few lines.  At a high level, it applies a careful derandomiza-tion of a recursive procedure which partitions the nodes and their respective palettes into separatebins.  We show that afterO(1) recursion steps, the remaining uncolored subgraph within each bin haslinear size and thus can be solved locally by collecting it to a single node.  This algorithm can alsobe implemented in the massively parallel computation (MPC) model provided that each machine haslinear (inn, the number of nodes in the input graph) space.  We also show an extension of our algo-rithm to theMPCregime, in which machines havesublinearspace:  we present the first deterministic(∆ + 1)-list coloring algorithm designed for sublinear-spaceMPC, which runs inO(log ∆ + log logn)rounds.","lang":"eng"}],"type":"journal_article","keyword":["General Mathematics","General Computer Science"],"issue":"5","_id":"15271","date_updated":"2025-09-10T10:14:11Z","article_processing_charge":"No","publication_identifier":{"issn":["0097-5397"],"eissn":["1095-7111"]},"citation":{"ieee":"A. Czumaj, P. Davies, and M. Parter, “Simple, deterministic, constant-round coloring in congested clique and MPC,” <i>SIAM Journal on Computing</i>, vol. 50, no. 5. Society for Industrial and Applied Mathematics, pp. 1603–1626, 2021.","chicago":"Czumaj, Artur, Peter Davies, and Merav Parter. “Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.” <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics, 2021. <a href=\"https://doi.org/10.1137/20m1366502\">https://doi.org/10.1137/20m1366502</a>.","short":"A. Czumaj, P. Davies, M. Parter, SIAM Journal on Computing 50 (2021) 1603–1626.","ista":"Czumaj A, Davies P, Parter M. 2021. Simple, deterministic, constant-round coloring in congested clique and MPC. SIAM Journal on Computing. 50(5), 1603–1626.","ama":"Czumaj A, Davies P, Parter M. Simple, deterministic, constant-round coloring in congested clique and MPC. <i>SIAM Journal on Computing</i>. 2021;50(5):1603-1626. doi:<a href=\"https://doi.org/10.1137/20m1366502\">10.1137/20m1366502</a>","mla":"Czumaj, Artur, et al. “Simple, Deterministic, Constant-Round Coloring in Congested Clique and MPC.” <i>SIAM Journal on Computing</i>, vol. 50, no. 5, Society for Industrial and Applied Mathematics, 2021, pp. 1603–26, doi:<a href=\"https://doi.org/10.1137/20m1366502\">10.1137/20m1366502</a>.","apa":"Czumaj, A., Davies, P., &#38; Parter, M. (2021). Simple, deterministic, constant-round coloring in congested clique and MPC. <i>SIAM Journal on Computing</i>. Society for Industrial and Applied Mathematics. <a href=\"https://doi.org/10.1137/20m1366502\">https://doi.org/10.1137/20m1366502</a>"},"department":[{"_id":"DaAl"}],"external_id":{"isi":["000713008600004"]},"language":[{"iso":"eng"}],"publication_status":"published","publisher":"Society for Industrial and Applied Mathematics","date_published":"2021-01-01T00:00:00Z","volume":50,"ec_funded":1,"oa_version":"None","intvolume":"        50","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication":"SIAM Journal on Computing","acknowledgement":"The  first  author  was  partially  supported  by  the  Centre  for  Discrete  Mathematics and its Applications, by the IBM Faculty Award, and by the EPSRC award EP/N011163/1.  The second author was partially supported by the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement 754411.  The first and third authors were partially supported by a Weizmann-UK Making Connections grant.","isi":1}]