[{"oa_version":"Preprint","month":"07","publication":"IEEE Transactions on Information Theory","keyword":["Computer Science Applications","Information Systems"],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1557-9654"],"issn":["0018-9448"]},"oa":1,"type":"journal_article","date_published":"2023-07-01T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2101.12426"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","article_processing_charge":"No","department":[{"_id":"MaMo"}],"date_created":"2024-01-08T13:04:54Z","publication_status":"published","intvolume":"        69","title":"Zero-error communication over adversarial MACs","scopus_import":"1","_id":"14751","issue":"7","author":[{"id":"2ce5da42-b2ea-11eb-bba5-9f264e9d002c","full_name":"Zhang, Yihan","orcid":"0000-0002-6465-6258","last_name":"Zhang","first_name":"Yihan"}],"publisher":"Institute of Electrical and Electronics Engineers","article_type":"original","quality_controlled":"1","page":"4093-4127","day":"01","arxiv":1,"doi":"10.1109/tit.2023.3257239","abstract":[{"text":"We consider zero-error communication over a two-transmitter deterministic adversarial multiple access channel (MAC) governed by an adversary who has access to the transmissions of both senders (hence called omniscient ) and aims to maliciously corrupt the communication. None of the encoders, jammer and decoder is allowed to randomize using private or public randomness. This enforces a combinatorial nature of the problem. Our model covers a large family of channels studied in the literature, including all deterministic discrete memoryless noisy or noiseless MACs. In this work, given an arbitrary two-transmitter deterministic omniscient adversarial MAC, we characterize when the capacity region: 1) has nonempty interior (in particular, is two-dimensional); 2) consists of two line segments (in particular, has empty interior); 3) consists of one line segment (in particular, is one-dimensional); 4) or only contains (0,0) (in particular, is zero-dimensional). This extends a recent result by Wang et al. (201 9) from the point-to-point setting to the multiple access setting. Indeed, our converse arguments build upon their generalized Plotkin bound and involve delicate case analysis. One of the technical challenges is to take care of both “joint confusability” and “marginal confusability”. In particular, the treatment of marginal confusability does not follow from the point-to-point results by Wang et al. Our achievability results follow from random coding with expurgation.","lang":"eng"}],"citation":{"ieee":"Y. Zhang, “Zero-error communication over adversarial MACs,” <i>IEEE Transactions on Information Theory</i>, vol. 69, no. 7. Institute of Electrical and Electronics Engineers, pp. 4093–4127, 2023.","chicago":"Zhang, Yihan. “Zero-Error Communication over Adversarial MACs.” <i>IEEE Transactions on Information Theory</i>. Institute of Electrical and Electronics Engineers, 2023. <a href=\"https://doi.org/10.1109/tit.2023.3257239\">https://doi.org/10.1109/tit.2023.3257239</a>.","apa":"Zhang, Y. (2023). Zero-error communication over adversarial MACs. <i>IEEE Transactions on Information Theory</i>. Institute of Electrical and Electronics Engineers. <a href=\"https://doi.org/10.1109/tit.2023.3257239\">https://doi.org/10.1109/tit.2023.3257239</a>","ama":"Zhang Y. Zero-error communication over adversarial MACs. <i>IEEE Transactions on Information Theory</i>. 2023;69(7):4093-4127. doi:<a href=\"https://doi.org/10.1109/tit.2023.3257239\">10.1109/tit.2023.3257239</a>","ista":"Zhang Y. 2023. Zero-error communication over adversarial MACs. IEEE Transactions on Information Theory. 69(7), 4093–4127.","short":"Y. Zhang, IEEE Transactions on Information Theory 69 (2023) 4093–4127.","mla":"Zhang, Yihan. “Zero-Error Communication over Adversarial MACs.” <i>IEEE Transactions on Information Theory</i>, vol. 69, no. 7, Institute of Electrical and Electronics Engineers, 2023, pp. 4093–127, doi:<a href=\"https://doi.org/10.1109/tit.2023.3257239\">10.1109/tit.2023.3257239</a>."},"year":"2023","date_updated":"2024-01-09T08:45:24Z","external_id":{"arxiv":["2101.12426"]},"volume":69,"acknowledgement":"The author would like to thank Amitalok J. Budkuley and Sidharth Jaggi for many helpful discussions at the early stage of this work. He would also like to thank Nir Ailon, Qi Cao, and Chandra Nair for discussions on a related problem regarding zero-error binary adder MACs.\r\nThe work of Yihan Zhang was supported by the European Union’s Horizon 2020 Research and Innovation Programme under Grant 682203-ERC-[Inf-Speed-Tradeoff]"},{"oa_version":"Published Version","month":"11","article_number":"16527","publication":"International Journal of Molecular Sciences","has_accepted_license":"1","language":[{"iso":"eng"}],"keyword":["Inorganic Chemistry","Organic Chemistry","Physical and Theoretical Chemistry","Computer Science Applications","Spectroscopy","Molecular Biology","General Medicine","Catalysis"],"publication_identifier":{"issn":["1422-0067"]},"oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"date_published":"2023-11-01T00:00:00Z","type":"journal_article","file":[{"file_name":"2023_IJMS_Teplova.pdf","content_type":"application/pdf","date_updated":"2024-01-10T13:39:42Z","file_size":2637784,"checksum":"4df7d206ba022b7f54eff1f0aec1659a","date_created":"2024-01-10T13:39:42Z","creator":"dernst","file_id":"14791","relation":"main_file","access_level":"open_access","success":1}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","article_processing_charge":"Yes","department":[{"_id":"JiFr"}],"date_created":"2024-01-10T09:24:35Z","title":"Phytaspase Is capable of detaching the endoplasmic reticulum retrieval signal from tobacco calreticulin-3","intvolume":"        24","_id":"14776","pmid":1,"author":[{"id":"e3736151-106c-11ec-b916-c2558e2762c6","full_name":"Teplova, Anastasiia","last_name":"Teplova","first_name":"Anastasiia"},{"last_name":"Pigidanov","first_name":"Artemii A.","full_name":"Pigidanov, Artemii A."},{"full_name":"Serebryakova, Marina V.","first_name":"Marina V.","last_name":"Serebryakova"},{"first_name":"Sergei A.","last_name":"Golyshev","full_name":"Golyshev, Sergei A."},{"full_name":"Galiullina, Raisa A.","last_name":"Galiullina","first_name":"Raisa A."},{"last_name":"Chichkova","first_name":"Nina V.","full_name":"Chichkova, Nina V."},{"full_name":"Vartapetian, Andrey B.","last_name":"Vartapetian","first_name":"Andrey B."}],"issue":"22","publisher":"MDPI","article_type":"original","quality_controlled":"1","file_date_updated":"2024-01-10T13:39:42Z","doi":"10.3390/ijms242216527","day":"01","abstract":[{"text":"Soluble chaperones residing in the endoplasmic reticulum (ER) play vitally important roles in folding and quality control of newly synthesized proteins that transiently pass through the ER en route to their final destinations. These soluble residents of the ER are themselves endowed with an ER retrieval signal that enables the cell to bring the escaped residents back from the Golgi. Here, by using purified proteins, we showed that Nicotiana tabacum phytaspase, a plant aspartate-specific protease, introduces two breaks at the C-terminus of the N. tabacum ER resident calreticulin-3. These cleavages resulted in removal of either a dipeptide or a hexapeptide from the C-terminus of calreticulin-3 encompassing part or all of the ER retrieval signal. Consistently, expression of the calreticulin-3 derivative mimicking the phytaspase cleavage product in Nicotiana benthamiana cells demonstrated loss of the ER accumulation of the protein. Notably, upon its escape from the ER, calreticulin-3 was further processed by an unknown protease(s) to generate the free N-terminal (N) domain of calreticulin-3, which was ultimately secreted into the apoplast. Our study thus identified a specific proteolytic enzyme capable of precise detachment of the ER retrieval signal from a plant ER resident protein, with implications for the further fate of the escaped resident.","lang":"eng"}],"date_updated":"2024-01-10T13:41:10Z","citation":{"apa":"Teplova, A., Pigidanov, A. A., Serebryakova, M. V., Golyshev, S. A., Galiullina, R. A., Chichkova, N. V., &#38; Vartapetian, A. B. (2023). Phytaspase Is capable of detaching the endoplasmic reticulum retrieval signal from tobacco calreticulin-3. <i>International Journal of Molecular Sciences</i>. MDPI. <a href=\"https://doi.org/10.3390/ijms242216527\">https://doi.org/10.3390/ijms242216527</a>","ama":"Teplova A, Pigidanov AA, Serebryakova MV, et al. Phytaspase Is capable of detaching the endoplasmic reticulum retrieval signal from tobacco calreticulin-3. <i>International Journal of Molecular Sciences</i>. 2023;24(22). doi:<a href=\"https://doi.org/10.3390/ijms242216527\">10.3390/ijms242216527</a>","chicago":"Teplova, Anastasiia, Artemii A. Pigidanov, Marina V. Serebryakova, Sergei A. Golyshev, Raisa A. Galiullina, Nina V. Chichkova, and Andrey B. Vartapetian. “Phytaspase Is Capable of Detaching the Endoplasmic Reticulum Retrieval Signal from Tobacco Calreticulin-3.” <i>International Journal of Molecular Sciences</i>. MDPI, 2023. <a href=\"https://doi.org/10.3390/ijms242216527\">https://doi.org/10.3390/ijms242216527</a>.","ieee":"A. Teplova <i>et al.</i>, “Phytaspase Is capable of detaching the endoplasmic reticulum retrieval signal from tobacco calreticulin-3,” <i>International Journal of Molecular Sciences</i>, vol. 24, no. 22. MDPI, 2023.","mla":"Teplova, Anastasiia, et al. “Phytaspase Is Capable of Detaching the Endoplasmic Reticulum Retrieval Signal from Tobacco Calreticulin-3.” <i>International Journal of Molecular Sciences</i>, vol. 24, no. 22, 16527, MDPI, 2023, doi:<a href=\"https://doi.org/10.3390/ijms242216527\">10.3390/ijms242216527</a>.","short":"A. Teplova, A.A. Pigidanov, M.V. Serebryakova, S.A. Golyshev, R.A. Galiullina, N.V. Chichkova, A.B. Vartapetian, International Journal of Molecular Sciences 24 (2023).","ista":"Teplova A, Pigidanov AA, Serebryakova MV, Golyshev SA, Galiullina RA, Chichkova NV, Vartapetian AB. 2023. Phytaspase Is capable of detaching the endoplasmic reticulum retrieval signal from tobacco calreticulin-3. International Journal of Molecular Sciences. 24(22), 16527."},"year":"2023","isi":1,"external_id":{"pmid":["38003717"],"isi":["001113792600001"]},"volume":24,"acknowledgement":"We thank C.U.T. Hellen for critically reading the manuscript. The MALDI MS facility and CLSM became available to us in the framework of Moscow State University Development Programs PNG 5.13 and PNR 5.13.\r\nThis work was funded by the Russian Science Foundation, grant numbers 19-14-00010 and 22-14-00071.","ddc":["580"]},{"file_date_updated":"2024-01-16T08:11:24Z","quality_controlled":"1","ec_funded":1,"article_type":"original","publisher":"Association for Computing Machinery","issue":"2","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu"},{"last_name":"Kafshdar Goharshady","first_name":"Ehsan","full_name":"Kafshdar Goharshady, Ehsan"},{"id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","full_name":"Novotný, Petr","last_name":"Novotný","first_name":"Petr"},{"first_name":"Jiří","last_name":"Zárevúcky","full_name":"Zárevúcky, Jiří"},{"id":"294AA7A6-F248-11E8-B48F-1D18A9856A87","last_name":"Zikelic","first_name":"Dorde","full_name":"Zikelic, Dorde","orcid":"0000-0002-4681-1699"}],"_id":"14778","intvolume":"        35","title":"On lexicographic proof rules for probabilistic termination","article_processing_charge":"Yes (via OA deal)","date_created":"2024-01-10T09:27:43Z","department":[{"_id":"KrCh"}],"publication_status":"published","ddc":["000"],"volume":35,"acknowledgement":"This research was partially supported by the ERC CoG (grant no. 863818; ForM-SMArt), the Czech Science Foundation (grant no. GA21-24711S), and the European Union’s Horizon 2020 research and innovation program under the Marie Skłodowska-Curie Grant Agreement No. 665385.","external_id":{"arxiv":["2108.02188"]},"citation":{"chicago":"Chatterjee, Krishnendu, Ehsan Kafshdar Goharshady, Petr Novotný, Jiří Zárevúcky, and Dorde Zikelic. “On Lexicographic Proof Rules for Probabilistic Termination.” <i>Formal Aspects of Computing</i>. Association for Computing Machinery, 2023. <a href=\"https://doi.org/10.1145/3585391\">https://doi.org/10.1145/3585391</a>.","ieee":"K. Chatterjee, E. Kafshdar Goharshady, P. Novotný, J. Zárevúcky, and D. Zikelic, “On lexicographic proof rules for probabilistic termination,” <i>Formal Aspects of Computing</i>, vol. 35, no. 2. Association for Computing Machinery, 2023.","apa":"Chatterjee, K., Kafshdar Goharshady, E., Novotný, P., Zárevúcky, J., &#38; Zikelic, D. (2023). On lexicographic proof rules for probabilistic termination. <i>Formal Aspects of Computing</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3585391\">https://doi.org/10.1145/3585391</a>","ama":"Chatterjee K, Kafshdar Goharshady E, Novotný P, Zárevúcky J, Zikelic D. On lexicographic proof rules for probabilistic termination. <i>Formal Aspects of Computing</i>. 2023;35(2). doi:<a href=\"https://doi.org/10.1145/3585391\">10.1145/3585391</a>","ista":"Chatterjee K, Kafshdar Goharshady E, Novotný P, Zárevúcky J, Zikelic D. 2023. On lexicographic proof rules for probabilistic termination. Formal Aspects of Computing. 35(2), 11.","short":"K. Chatterjee, E. Kafshdar Goharshady, P. Novotný, J. Zárevúcky, D. Zikelic, Formal Aspects of Computing 35 (2023).","mla":"Chatterjee, Krishnendu, et al. “On Lexicographic Proof Rules for Probabilistic Termination.” <i>Formal Aspects of Computing</i>, vol. 35, no. 2, 11, Association for Computing Machinery, 2023, doi:<a href=\"https://doi.org/10.1145/3585391\">10.1145/3585391</a>."},"year":"2023","date_updated":"2025-07-14T09:10:10Z","abstract":[{"lang":"eng","text":"We consider the almost-sure (a.s.) termination problem for probabilistic programs, which are a stochastic extension of classical imperative programs. Lexicographic ranking functions provide a sound and practical approach for termination of non-probabilistic programs, and their extension to probabilistic programs is achieved via lexicographic ranking supermartingales (LexRSMs). However, LexRSMs introduced in the previous work have a limitation that impedes their automation: all of their components have to be non-negative in all reachable states. This might result in a LexRSM not existing even for simple terminating programs. Our contributions are twofold. First, we introduce a generalization of LexRSMs that allows for some components to be negative. This standard feature of non-probabilistic termination proofs was hitherto not known to be sound in the probabilistic setting, as the soundness proof requires a careful analysis of the underlying stochastic process. Second, we present polynomial-time algorithms using our generalized LexRSMs for proving a.s. termination in broad classes of linear-arithmetic programs."}],"day":"23","doi":"10.1145/3585391","arxiv":1,"keyword":["Theoretical Computer Science","Software"],"language":[{"iso":"eng"}],"has_accepted_license":"1","publication":"Formal Aspects of Computing","article_number":"11","month":"06","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"},{"name":"International IST Doctoral Program","grant_number":"665385","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"}],"oa_version":"Published Version","related_material":{"record":[{"id":"10414","relation":"earlier_version","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","file":[{"success":1,"relation":"main_file","access_level":"open_access","creator":"dernst","file_id":"14804","checksum":"3bb133eeb27ec01649a9a36445d952d9","file_size":502522,"date_created":"2024-01-16T08:11:24Z","content_type":"application/pdf","file_name":"2023_FormalAspectsComputing_Chatterjee.pdf","date_updated":"2024-01-16T08:11:24Z"}],"type":"journal_article","date_published":"2023-06-23T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"publication_identifier":{"issn":["0934-5043"],"eissn":["1433-299X"]}},{"publication_identifier":{"issn":["2169-3536"]},"oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"journal_article","date_published":"2023-08-01T00:00:00Z","file":[{"file_id":"14166","creator":"dernst","access_level":"open_access","success":1,"relation":"main_file","date_updated":"2023-08-22T06:37:48Z","file_name":"2023_IEEEAccess_Neiheiser.pdf","content_type":"application/pdf","date_created":"2023-08-22T06:37:48Z","checksum":"4b80b0ff212edf7e5842fbdd53784432","file_size":1289285}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","month":"08","has_accepted_license":"1","publication":"IEEE Access","keyword":["General Engineering","General Materials Science","General Computer Science","Electrical and Electronic Engineering"],"language":[{"iso":"eng"}],"day":"01","doi":"10.1109/access.2023.3237897","abstract":[{"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.","lang":"eng"}],"year":"2023","citation":{"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>","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>","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.","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."},"date_updated":"2023-12-13T12:14:52Z","external_id":{"isi":["000927831000001"]},"isi":1,"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.","volume":11,"ddc":["000"],"article_processing_charge":"Yes","department":[{"_id":"ElKo"}],"date_created":"2023-08-09T12:09:57Z","publication_status":"published","intvolume":"        11","title":"Practical limitations of Ethereum’s layer-2","scopus_import":"1","_id":"13988","author":[{"orcid":"0000-0001-7227-8309","full_name":"Neiheiser, Ray","first_name":"Ray","last_name":"Neiheiser","id":"f09651b9-fec0-11ec-b5d8-934aff0e52a4"},{"first_name":"Gustavo","last_name":"Inacio","full_name":"Inacio, Gustavo"},{"full_name":"Rech, Luciana","first_name":"Luciana","last_name":"Rech"},{"full_name":"Montez, Carlos","last_name":"Montez","first_name":"Carlos"},{"full_name":"Matos, Miguel","first_name":"Miguel","last_name":"Matos"},{"last_name":"Rodrigues","first_name":"Luis","full_name":"Rodrigues, Luis"}],"publisher":"Institute of Electrical and Electronics Engineers","article_type":"original","quality_controlled":"1","page":"8651-8662","file_date_updated":"2023-08-22T06:37:48Z"},{"publisher":"Springer Nature","article_type":"original","page":"29-43","quality_controlled":"1","publication_status":"published","date_created":"2023-01-12T12:10:08Z","department":[{"_id":"KrPi"}],"article_processing_charge":"No","title":"Long-lived counters with polylogarithmic amortized step complexity","intvolume":"        36","_id":"12164","scopus_import":"1","author":[{"id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","full_name":"Baig, Mirza Ahad","last_name":"Baig","first_name":"Mirza Ahad"},{"full_name":"Hendler, Danny","first_name":"Danny","last_name":"Hendler"},{"first_name":"Alessia","last_name":"Milani","full_name":"Milani, Alessia"},{"full_name":"Travers, Corentin","last_name":"Travers","first_name":"Corentin"}],"volume":36,"acknowledgement":"A preliminary version of this work appeared in DISC’19. Mirza Ahad Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes and FREDDA. Mirza Ahad Baig is supported by UMI Relax. Danny Hendler is supported by the Israel Science Foundation (Grants 380/18 and 1425/22).","doi":"10.1007/s00446-022-00439-5","day":"01","abstract":[{"text":"A shared-memory counter is a widely-used and well-studied concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. In Jayanti et al (SIAM J Comput, 30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read-write registers, of a large class of shared objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity. In this work, we address this gap. We show that n-process, wait-free and linearizable counters can be implemented from read-write registers with O(log2n) amortized step complexity. This is the first counter algorithm from read-write registers that provides sub-linear amortized step complexity in executions of arbitrary length. Since a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations exists, our upper bound is within a logarithmic factor of the optimal. The worst-case step complexity of the construction remains linear, which is optimal. This is obtained thanks to a new max register construction with O(logn) amortized step complexity in executions of arbitrary length in which the value stored in the register does not grow too quickly. We then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel [1] in which we “plug” our max register implementation to show that it remains linearizable while achieving O(log2n) amortized step complexity.","lang":"eng"}],"date_updated":"2023-08-16T08:39:36Z","year":"2023","citation":{"ista":"Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic amortized step complexity. Distributed Computing. 36, 29–43.","mla":"Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023, pp. 29–43, doi:<a href=\"https://doi.org/10.1007/s00446-022-00439-5\">10.1007/s00446-022-00439-5</a>.","short":"M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023) 29–43.","chicago":"Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed Computing</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00446-022-00439-5\">https://doi.org/10.1007/s00446-022-00439-5</a>.","ieee":"M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with polylogarithmic amortized step complexity,” <i>Distributed Computing</i>, vol. 36. Springer Nature, pp. 29–43, 2023.","ama":"Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>. 2023;36:29-43. doi:<a href=\"https://doi.org/10.1007/s00446-022-00439-5\">10.1007/s00446-022-00439-5</a>","apa":"Baig, M. A., Hendler, D., Milani, A., &#38; Travers, C. (2023). Long-lived counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00446-022-00439-5\">https://doi.org/10.1007/s00446-022-00439-5</a>"},"isi":1,"external_id":{"isi":["000890138700001"]},"language":[{"iso":"eng"}],"keyword":["Computational Theory and Mathematics","Computer Networks and Communications","Hardware and Architecture","Theoretical Computer Science"],"oa_version":"Preprint","month":"03","publication":"Distributed Computing","main_file_link":[{"open_access":"1","url":"https://drops.dagstuhl.de/opus/volltexte/2019/11310/"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["0178-2770"],"eissn":["1432-0452"]},"oa":1,"date_published":"2023-03-01T00:00:00Z","type":"journal_article"},{"keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"language":[{"iso":"eng"}],"has_accepted_license":"1","publication":"Discrete & Computational Geometry","month":"01","project":[{"name":"ISTplus - Postdoctoral Fellowships","grant_number":"754411","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425"},{"grant_number":"M03073","name":"Learning and triangulating manifolds via collapses","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2"}],"oa_version":"Published Version","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","file":[{"date_updated":"2023-02-02T11:01:10Z","content_type":"application/pdf","file_name":"2023_DiscreteCompGeometry_Boissonnat.pdf","date_created":"2023-02-02T11:01:10Z","file_size":582850,"checksum":"46352e0ee71e460848f88685ca852681","file_id":"12488","creator":"dernst","access_level":"open_access","success":1,"relation":"main_file"}],"type":"journal_article","date_published":"2023-01-01T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"file_date_updated":"2023-02-02T11:01:10Z","quality_controlled":"1","ec_funded":1,"page":"156-191","article_type":"original","publisher":"Springer Nature","author":[{"full_name":"Boissonnat, Jean-Daniel","last_name":"Boissonnat","first_name":"Jean-Daniel"},{"full_name":"Dyer, Ramsay","last_name":"Dyer","first_name":"Ramsay"},{"full_name":"Ghosh, Arijit","first_name":"Arijit","last_name":"Ghosh"},{"id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","first_name":"Mathijs","full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220"}],"scopus_import":"1","_id":"12287","intvolume":"        69","title":"Local criteria for triangulating general manifolds","department":[{"_id":"HeEd"}],"date_created":"2023-01-16T10:04:06Z","article_processing_charge":"No","publication_status":"published","ddc":["510"],"acknowledgement":"This work has been funded by the European Research Council under the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). Arijit Ghosh is supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015). Part of this work was done when Arijit Ghosh was a Researcher at Max-Planck-Institute for Informatics, Germany, supported by the IndoGerman Max Planck Center for Computer Science (IMPECS). Mathijs Wintraecken also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411 and the Austrian Science Fund (FWF): M-3073. A part of the results described in this paper were presented at SoCG 2018 and in [3]. \r\nOpen access funding provided by the Austrian Science Fund (FWF).","volume":69,"external_id":{"isi":["000862193600001"]},"isi":1,"year":"2023","citation":{"apa":"Boissonnat, J.-D., Dyer, R., Ghosh, A., &#38; Wintraecken, M. (2023). Local criteria for triangulating general manifolds. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00431-7\">https://doi.org/10.1007/s00454-022-00431-7</a>","ama":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. Local criteria for triangulating general manifolds. <i>Discrete &#38; Computational Geometry</i>. 2023;69:156-191. doi:<a href=\"https://doi.org/10.1007/s00454-022-00431-7\">10.1007/s00454-022-00431-7</a>","ieee":"J.-D. Boissonnat, R. Dyer, A. Ghosh, and M. Wintraecken, “Local criteria for triangulating general manifolds,” <i>Discrete &#38; Computational Geometry</i>, vol. 69. Springer Nature, pp. 156–191, 2023.","chicago":"Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken. “Local Criteria for Triangulating General Manifolds.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00454-022-00431-7\">https://doi.org/10.1007/s00454-022-00431-7</a>.","short":"J.-D. Boissonnat, R. Dyer, A. Ghosh, M. Wintraecken, Discrete &#38; Computational Geometry 69 (2023) 156–191.","mla":"Boissonnat, Jean-Daniel, et al. “Local Criteria for Triangulating General Manifolds.” <i>Discrete &#38; Computational Geometry</i>, vol. 69, Springer Nature, 2023, pp. 156–91, doi:<a href=\"https://doi.org/10.1007/s00454-022-00431-7\">10.1007/s00454-022-00431-7</a>.","ista":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. 2023. Local criteria for triangulating general manifolds. Discrete &#38; Computational Geometry. 69, 156–191."},"date_updated":"2023-08-01T12:47:32Z","abstract":[{"text":"We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use.","lang":"eng"}],"day":"01","doi":"10.1007/s00454-022-00431-7"},{"date_published":"2023-01-01T00:00:00Z","type":"journal_article","publication_identifier":{"eissn":["1095-7111"],"issn":["0097-5397"]},"oa":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2003.11351"}],"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication":"SIAM Journal on Computing","oa_version":"Preprint","project":[{"name":"IST-BRIDGE: International postdoctoral program","grant_number":"101034413","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c"}],"month":"01","language":[{"iso":"eng"}],"keyword":["General Mathematics","General Computer Science"],"date_updated":"2023-08-01T13:11:30Z","year":"2023","citation":{"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.","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 &#38; 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.","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 &#38; 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 &#38; Applied Mathematics, pp. 38–79, 2023.","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>","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 &#38; Applied Mathematics. <a href=\"https://doi.org/10.1137/20m1378223\">https://doi.org/10.1137/20m1378223</a>"},"isi":1,"external_id":{"isi":["000955000000001"],"arxiv":["2003.11351"]},"doi":"10.1137/20m1378223","arxiv":1,"day":"01","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."}],"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. ","volume":52,"_id":"12563","scopus_import":"1","author":[{"last_name":"Krokhin","first_name":"Andrei","full_name":"Krokhin, Andrei"},{"id":"ec596741-c539-11ec-b829-c79322a91242","full_name":"Opršal, Jakub","orcid":"0000-0003-1245-3456","last_name":"Opršal","first_name":"Jakub"},{"full_name":"Wrochna, Marcin","last_name":"Wrochna","first_name":"Marcin"},{"full_name":"Živný, Stanislav","first_name":"Stanislav","last_name":"Živný"}],"issue":"1","publication_status":"published","department":[{"_id":"UlWa"}],"article_processing_charge":"No","date_created":"2023-02-16T07:03:52Z","title":"Topology and adjunction in promise constraint satisfaction","intvolume":"        52","page":"38-79","ec_funded":1,"quality_controlled":"1","publisher":"Society for Industrial & Applied Mathematics","article_type":"original"},{"date_updated":"2023-08-03T11:55:06Z","citation":{"ista":"Kalinov A, Osinskiy AI, Matveev SA, Otieno W, Brilliantov NV. 2022. Direct simulation Monte Carlo for new regimes in aggregation-fragmentation kinetics. Journal of Computational Physics. 467, 111439.","short":"A. Kalinov, A.I. Osinskiy, S.A. Matveev, W. Otieno, N.V. Brilliantov, Journal of Computational Physics 467 (2022).","mla":"Kalinov, Aleksei, et al. “Direct Simulation Monte Carlo for New Regimes in Aggregation-Fragmentation Kinetics.” <i>Journal of Computational Physics</i>, vol. 467, 111439, Elsevier, 2022, doi:<a href=\"https://doi.org/10.1016/j.jcp.2022.111439\">10.1016/j.jcp.2022.111439</a>.","chicago":"Kalinov, Aleksei, A.I. Osinskiy, S.A. Matveev, W. Otieno, and N.V. Brilliantov. “Direct Simulation Monte Carlo for New Regimes in Aggregation-Fragmentation Kinetics.” <i>Journal of Computational Physics</i>. Elsevier, 2022. <a href=\"https://doi.org/10.1016/j.jcp.2022.111439\">https://doi.org/10.1016/j.jcp.2022.111439</a>.","ieee":"A. Kalinov, A. I. Osinskiy, S. A. Matveev, W. Otieno, and N. V. Brilliantov, “Direct simulation Monte Carlo for new regimes in aggregation-fragmentation kinetics,” <i>Journal of Computational Physics</i>, vol. 467. Elsevier, 2022.","ama":"Kalinov A, Osinskiy AI, Matveev SA, Otieno W, Brilliantov NV. Direct simulation Monte Carlo for new regimes in aggregation-fragmentation kinetics. <i>Journal of Computational Physics</i>. 2022;467. doi:<a href=\"https://doi.org/10.1016/j.jcp.2022.111439\">10.1016/j.jcp.2022.111439</a>","apa":"Kalinov, A., Osinskiy, A. I., Matveev, S. A., Otieno, W., &#38; Brilliantov, N. V. (2022). Direct simulation Monte Carlo for new regimes in aggregation-fragmentation kinetics. <i>Journal of Computational Physics</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.jcp.2022.111439\">https://doi.org/10.1016/j.jcp.2022.111439</a>"},"year":"2022","isi":1,"external_id":{"isi":["000917225500013"],"arxiv":["2103.09481"]},"arxiv":1,"doi":"10.1016/j.jcp.2022.111439","day":"15","abstract":[{"lang":"eng","text":"We revisit two basic Direct Simulation Monte Carlo Methods to model aggregation kinetics and extend them for aggregation processes with collisional fragmentation (shattering). We test the performance and accuracy of the extended methods and compare their performance with efficient deterministic finite-difference method applied to the same model. We validate the stochastic methods on the test problems and apply them to verify the existence of oscillating regimes in the aggregation-fragmentation kinetics recently detected in deterministic simulations. We confirm the emergence of steady oscillations of densities in such systems and prove the stability of the\r\noscillations with respect to fluctuations and noise."}],"acknowledgement":"Zhores supercomputer of Skolkovo Institute of Science and Technology [68] has been used in the present research. S.A.M. was supported by Moscow Center for Fundamental and Applied Mathematics (the agreement with the Ministry of Education and Science of the Russian Federation No. 075-15-2019-1624). A.I.O. acknowledges RFBR project No. 20-31-90022. N.V.B. acknowledges the support of the Analytical Center (subsidy agreement 000000D730321P5Q0002, Grant No. 70-2021-00145 02.11.2021).","volume":467,"ddc":["518"],"_id":"11556","author":[{"id":"44b7120e-eb97-11eb-a6c2-e1557aa81d02","orcid":"0000-0003-2189-3904","full_name":"Kalinov, Aleksei","first_name":"Aleksei","last_name":"Kalinov"},{"first_name":"A.I.","last_name":"Osinskiy","full_name":"Osinskiy, A.I."},{"last_name":"Matveev","first_name":"S.A.","full_name":"Matveev, S.A."},{"full_name":"Otieno, W.","last_name":"Otieno","first_name":"W."},{"full_name":"Brilliantov, N.V.","first_name":"N.V.","last_name":"Brilliantov"}],"publication_status":"published","date_created":"2022-07-11T12:19:59Z","article_processing_charge":"No","department":[{"_id":"GradSch"},{"_id":"ChWo"}],"title":"Direct simulation Monte Carlo for new regimes in aggregation-fragmentation kinetics","intvolume":"       467","quality_controlled":"1","publisher":"Elsevier","article_type":"original","date_published":"2022-10-15T00:00:00Z","type":"journal_article","publication_identifier":{"issn":["0021-9991"]},"oa":1,"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2103.09481","open_access":"1"}],"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","publication":"Journal of Computational Physics","oa_version":"Preprint","month":"10","article_number":"111439","language":[{"iso":"eng"}],"keyword":["Computer Science Applications","Physics and Astronomy (miscellaneous)","Applied Mathematics","Computational Mathematics","Modeling and Simulation","Numerical Analysis"]},{"project":[{"call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","name":"Game Theory","grant_number":"S11407"}],"oa_version":"Preprint","month":"02","publication":"Mathematics of Operations Research","keyword":["Management Science and Operations Research","General Mathematics","Computer Science Applications"],"language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1526-5471"],"issn":["0364-765X"]},"oa":1,"type":"journal_article","date_published":"2022-02-01T00:00:00Z","main_file_link":[{"url":"https://arxiv.org/abs/1904.13360","open_access":"1"}],"status":"public","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","date_created":"2021-04-08T09:33:31Z","department":[{"_id":"GradSch"},{"_id":"KrCh"}],"article_processing_charge":"No","publication_status":"published","intvolume":"        47","title":"Finite-memory strategies in POMDPs with long-run average objectives","scopus_import":"1","_id":"9311","issue":"1","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Raimundo J","last_name":"Saona Urmeneta","orcid":"0000-0001-5103-038X","full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425"},{"full_name":"Ziliotto, Bruno","first_name":"Bruno","last_name":"Ziliotto"}],"publisher":"Institute for Operations Research and the Management Sciences","article_type":"original","quality_controlled":"1","page":"100-119","day":"01","doi":"10.1287/moor.2020.1116","arxiv":1,"abstract":[{"text":"Partially observable Markov decision processes (POMDPs) are standard models for dynamic systems with probabilistic and nondeterministic behaviour in uncertain environments. We prove that in POMDPs with long-run average objective, the decision maker has approximately optimal strategies with finite memory. This implies notably that approximating the long-run value is recursively enumerable, as well as a weak continuity property of the value with respect to the transition function. ","lang":"eng"}],"citation":{"chicago":"Chatterjee, Krishnendu, Raimundo J Saona Urmeneta, and Bruno Ziliotto. “Finite-Memory Strategies in POMDPs with Long-Run Average Objectives.” <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences, 2022. <a href=\"https://doi.org/10.1287/moor.2020.1116\">https://doi.org/10.1287/moor.2020.1116</a>.","ieee":"K. Chatterjee, R. J. Saona Urmeneta, and B. Ziliotto, “Finite-memory strategies in POMDPs with long-run average objectives,” <i>Mathematics of Operations Research</i>, vol. 47, no. 1. Institute for Operations Research and the Management Sciences, pp. 100–119, 2022.","ama":"Chatterjee K, Saona Urmeneta RJ, Ziliotto B. Finite-memory strategies in POMDPs with long-run average objectives. <i>Mathematics of Operations Research</i>. 2022;47(1):100-119. doi:<a href=\"https://doi.org/10.1287/moor.2020.1116\">10.1287/moor.2020.1116</a>","apa":"Chatterjee, K., Saona Urmeneta, R. J., &#38; Ziliotto, B. (2022). Finite-memory strategies in POMDPs with long-run average objectives. <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences. <a href=\"https://doi.org/10.1287/moor.2020.1116\">https://doi.org/10.1287/moor.2020.1116</a>","ista":"Chatterjee K, Saona Urmeneta RJ, Ziliotto B. 2022. Finite-memory strategies in POMDPs with long-run average objectives. Mathematics of Operations Research. 47(1), 100–119.","mla":"Chatterjee, Krishnendu, et al. “Finite-Memory Strategies in POMDPs with Long-Run Average Objectives.” <i>Mathematics of Operations Research</i>, vol. 47, no. 1, Institute for Operations Research and the Management Sciences, 2022, pp. 100–19, doi:<a href=\"https://doi.org/10.1287/moor.2020.1116\">10.1287/moor.2020.1116</a>.","short":"K. Chatterjee, R.J. Saona Urmeneta, B. Ziliotto, Mathematics of Operations Research 47 (2022) 100–119."},"year":"2022","date_updated":"2023-09-05T13:16:11Z","external_id":{"arxiv":["1904.13360"],"isi":["000731918100001"]},"isi":1,"acknowledgement":"Partially supported by Austrian Science Fund (FWF) NFN Grant No RiSE/SHiNE S11407, by CONICYT Chile through grant PII 20150140, and by ECOS-CONICYT through grant C15E03.\r\n","volume":47},{"quality_controlled":"1","page":"2621–2635","file_date_updated":"2022-12-20T23:30:08Z","publisher":"Springer Nature","article_type":"original","scopus_import":"1","_id":"10208","author":[{"full_name":"Goudarzi, Samira","last_name":"Goudarzi","first_name":"Samira"},{"first_name":"Mohammad","last_name":"Sharif","full_name":"Sharif, Mohammad"},{"id":"2A2BCDC4-CF62-11E9-BE5E-3B1EE6697425","first_name":"Farid","last_name":"Karimipour","orcid":"0000-0001-6746-4174","full_name":"Karimipour, Farid"}],"department":[{"_id":"HeEd"}],"article_processing_charge":"No","date_created":"2021-11-02T09:28:55Z","publication_status":"published","intvolume":"        13","title":"A context-aware dimension reduction framework for trajectory and health signal analyses","volume":13,"acknowledgement":"The third author acknowledges the funding received from the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z 342-N31.","ddc":["000"],"year":"2022","citation":{"short":"S. Goudarzi, M. Sharif, F. Karimipour, Journal of Ambient Intelligence and Humanized Computing 13 (2022) 2621–2635.","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>.","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.","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>","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>","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>.","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."},"date_updated":"2023-08-02T13:31:48Z","external_id":{"isi":["000712198000001"]},"isi":1,"day":"01","doi":"10.1007/s12652-021-03569-z","abstract":[{"lang":"eng","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."}],"keyword":["general computer science"],"language":[{"iso":"eng"}],"has_accepted_license":"1","publication":"Journal of Ambient Intelligence and Humanized Computing","project":[{"call_identifier":"FWF","_id":"268116B8-B435-11E9-9278-68D0E5697425","name":"The Wittgenstein Prize","grant_number":"Z00342"}],"oa_version":"Submitted Version","month":"05","file":[{"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","checksum":"0a8961416a9bb2be5a1cebda65468bcf","file_size":1634958,"embargo":"2022-11-12","date_created":"2021-11-12T19:38:05Z","creator":"fkarimip","file_id":"10279","relation":"main_file","access_level":"open_access"}],"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","type":"journal_article","date_published":"2022-05-01T00:00:00Z","publication_identifier":{"issn":["1868-5137"],"eissn":["1868-5145"]},"oa":1},{"volume":10,"acknowledgement":"J.H. acknowledges partial financial support by the ERC Advanced Grant ‘RMTBeyond’ No. 101020331. Support for publication costs from the Deutsche Forschungsgemeinschaft and the Open Access Publishing Fund of the University of Tübingen is gratefully acknowledged.","ddc":["510"],"day":"18","arxiv":1,"doi":"10.1017/fms.2021.80","abstract":[{"lang":"eng","text":"We prove a generalised super-adiabatic theorem for extended fermionic systems assuming a spectral gap only in the bulk. More precisely, we assume that the infinite system has a unique ground state and that the corresponding Gelfand–Naimark–Segal Hamiltonian has a spectral gap above its eigenvalue zero. Moreover, we show that a similar adiabatic theorem also holds in the bulk of finite systems up to errors that vanish faster than any inverse power of the system size, although the corresponding finite-volume Hamiltonians need not have a spectral gap.\r\n\r\n"}],"year":"2022","citation":{"ista":"Henheik SJ, Teufel S. 2022. Adiabatic theorem in the thermodynamic limit: Systems with a gap in the bulk. Forum of Mathematics, Sigma. 10, e4.","mla":"Henheik, Sven Joscha, and Stefan Teufel. “Adiabatic Theorem in the Thermodynamic Limit: Systems with a Gap in the Bulk.” <i>Forum of Mathematics, Sigma</i>, vol. 10, e4, Cambridge University Press, 2022, doi:<a href=\"https://doi.org/10.1017/fms.2021.80\">10.1017/fms.2021.80</a>.","short":"S.J. Henheik, S. Teufel, Forum of Mathematics, Sigma 10 (2022).","chicago":"Henheik, Sven Joscha, and Stefan Teufel. “Adiabatic Theorem in the Thermodynamic Limit: Systems with a Gap in the Bulk.” <i>Forum of Mathematics, Sigma</i>. Cambridge University Press, 2022. <a href=\"https://doi.org/10.1017/fms.2021.80\">https://doi.org/10.1017/fms.2021.80</a>.","ieee":"S. J. Henheik and S. Teufel, “Adiabatic theorem in the thermodynamic limit: Systems with a gap in the bulk,” <i>Forum of Mathematics, Sigma</i>, vol. 10. Cambridge University Press, 2022.","ama":"Henheik SJ, Teufel S. Adiabatic theorem in the thermodynamic limit: Systems with a gap in the bulk. <i>Forum of Mathematics, Sigma</i>. 2022;10. doi:<a href=\"https://doi.org/10.1017/fms.2021.80\">10.1017/fms.2021.80</a>","apa":"Henheik, S. J., &#38; Teufel, S. (2022). Adiabatic theorem in the thermodynamic limit: Systems with a gap in the bulk. <i>Forum of Mathematics, Sigma</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fms.2021.80\">https://doi.org/10.1017/fms.2021.80</a>"},"date_updated":"2023-08-02T13:53:11Z","external_id":{"arxiv":["2012.15239"],"isi":["000743615000001"]},"isi":1,"publisher":"Cambridge University Press","article_type":"original","quality_controlled":"1","ec_funded":1,"file_date_updated":"2022-01-19T09:27:43Z","date_created":"2022-01-18T16:18:51Z","article_processing_charge":"Yes","department":[{"_id":"GradSch"},{"_id":"LaEr"}],"publication_status":"published","intvolume":"        10","title":"Adiabatic theorem in the thermodynamic limit: Systems with a gap in the bulk","_id":"10643","author":[{"id":"31d731d7-d235-11ea-ad11-b50331c8d7fb","first_name":"Sven Joscha","last_name":"Henheik","orcid":"0000-0003-1106-327X","full_name":"Henheik, Sven Joscha"},{"first_name":"Stefan","last_name":"Teufel","full_name":"Teufel, Stefan"}],"file":[{"date_created":"2022-01-19T09:27:43Z","file_size":705323,"checksum":"87592a755adcef22ea590a99dc728dd3","date_updated":"2022-01-19T09:27:43Z","file_name":"2022_ForumMathSigma_Henheik.pdf","content_type":"application/pdf","relation":"main_file","success":1,"access_level":"open_access","file_id":"10646","creator":"cchlebak"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","publication_identifier":{"eissn":["2050-5094"]},"oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"journal_article","date_published":"2022-01-18T00:00:00Z","keyword":["computational mathematics","discrete mathematics and combinatorics","geometry and topology","mathematical physics","statistics and probability","algebra and number theory","theoretical computer science","analysis"],"language":[{"iso":"eng"}],"project":[{"grant_number":"101020331","name":"Random matrices beyond Wigner-Dyson-Mehta","_id":"62796744-2b32-11ec-9570-940b20777f1d","call_identifier":"H2020"}],"oa_version":"Published Version","article_number":"e4","month":"01","has_accepted_license":"1","publication":"Forum of Mathematics, Sigma"},{"has_accepted_license":"1","publication":"Discrete & Computational Geometry","oa_version":"Published Version","month":"11","keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"language":[{"iso":"eng"}],"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"journal_article","date_published":"2022-11-14T00:00:00Z","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"oa":1,"file":[{"file_size":1747581,"checksum":"307e879d09e52eddf5b225d0aaa9213a","date_created":"2023-01-23T11:10:03Z","file_name":"2022_DiscreteCompGeometry_Wagner.pdf","content_type":"application/pdf","date_updated":"2023-01-23T11:10:03Z","access_level":"open_access","relation":"main_file","success":1,"creator":"dernst","file_id":"12345"}],"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","related_material":{"record":[{"id":"7807","relation":"earlier_version","status":"public"},{"status":"public","relation":"earlier_version","id":"7990"}]},"scopus_import":"1","_id":"12129","issue":"4","author":[{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568"},{"full_name":"Welzl, Emo","last_name":"Welzl","first_name":"Emo"}],"date_created":"2023-01-12T12:02:28Z","article_processing_charge":"No","department":[{"_id":"UlWa"}],"publication_status":"published","intvolume":"        68","title":"Connectivity of triangulation flip graphs in the plane","quality_controlled":"1","page":"1227-1284","file_date_updated":"2023-01-23T11:10:03Z","publisher":"Springer Nature","article_type":"original","year":"2022","citation":{"ista":"Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the plane. Discrete &#38; Computational Geometry. 68(4), 1227–1284.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” <i>Discrete &#38; Computational Geometry</i>, vol. 68, no. 4, Springer Nature, 2022, pp. 1227–84, doi:<a href=\"https://doi.org/10.1007/s00454-022-00436-2\">10.1007/s00454-022-00436-2</a>.","short":"U. Wagner, E. Welzl, Discrete &#38; Computational Geometry 68 (2022) 1227–1284.","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane,” <i>Discrete &#38; Computational Geometry</i>, vol. 68, no. 4. Springer Nature, pp. 1227–1284, 2022.","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s00454-022-00436-2\">https://doi.org/10.1007/s00454-022-00436-2</a>.","apa":"Wagner, U., &#38; Welzl, E. (2022). Connectivity of triangulation flip graphs in the plane. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-022-00436-2\">https://doi.org/10.1007/s00454-022-00436-2</a>","ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane. <i>Discrete &#38; Computational Geometry</i>. 2022;68(4):1227-1284. doi:<a href=\"https://doi.org/10.1007/s00454-022-00436-2\">10.1007/s00454-022-00436-2</a>"},"date_updated":"2023-08-04T08:51:08Z","external_id":{"isi":["000883222200003"]},"isi":1,"day":"14","doi":"10.1007/s00454-022-00436-2","abstract":[{"lang":"eng","text":"Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P′ of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P∖P′ as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is ⌈n/2−2⌉-vertex connected, and the bistellar flip graph is (n−3)-vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where (n−3)-vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski’s Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2−2⌉ (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n−3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n−3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n−3. (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations."}],"volume":68,"acknowledgement":"This is a full and revised version of [38] (on partial triangulations) in Proceedings of the 36th Annual International Symposium on Computational Geometry (SoCG‘20) and of some of the results in [37] (on full triangulations) in Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA‘20).\r\nThis research started at the 11th Gremo’s Workshop on Open Problems (GWOP), Alp Sellamatt, Switzerland, June 24–28, 2013, motivated by a question posed by Filip Mori´c on full triangulations. Research was supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681, and by IST Austria and Berlin Free University during a sabbatical stay of the second author. We thank Michael Joswig, Jesús De Loera, and Francisco Santos for helpful discussions on the topics of this paper, and Daniel Bertschinger and Valentin Stoppiello for carefully reading earlier versions and for many helpful comments.\r\nOpen access funding provided by the Swiss Federal Institute of Technology Zürich","ddc":["510"]},{"month":"10","article_number":"04LT02","oa_version":"Published Version","publication":"Journal of Physics: Complexity","has_accepted_license":"1","language":[{"iso":"eng"}],"keyword":["Artificial Intelligence","Computer Networks and Communications","Computer Science Applications","Information Systems"],"oa":1,"publication_identifier":{"issn":["2632-072X"]},"date_published":"2022-10-25T00:00:00Z","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"date_created":"2023-01-24T07:24:37Z","file_size":1006106,"checksum":"35c5c5cb0eb17ea1b5184755daab9fc9","date_updated":"2023-01-24T07:24:37Z","content_type":"application/pdf","file_name":"2022_JourPhysics_Boerner.pdf","success":1,"relation":"main_file","access_level":"open_access","file_id":"12350","creator":"dernst"}],"title":"Explosive transitions in epidemic dynamics","intvolume":"         3","publication_status":"published","department":[{"_id":"BjHo"}],"date_created":"2023-01-12T12:03:43Z","article_processing_charge":"No","author":[{"full_name":"Börner, Georg","last_name":"Börner","first_name":"Georg"},{"last_name":"Schröder","first_name":"Malte","full_name":"Schröder, Malte"},{"last_name":"Scarselli","first_name":"Davide","full_name":"Scarselli, Davide","orcid":"0000-0001-5227-4271","id":"40315C30-F248-11E8-B48F-1D18A9856A87"},{"orcid":"0000-0003-0423-5010","full_name":"Budanur, Nazmi B","first_name":"Nazmi B","last_name":"Budanur","id":"3EA1010E-F248-11E8-B48F-1D18A9856A87"},{"id":"3A374330-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-2057-2754","full_name":"Hof, Björn","first_name":"Björn","last_name":"Hof"},{"full_name":"Timme, Marc","last_name":"Timme","first_name":"Marc"}],"issue":"4","_id":"12134","scopus_import":"1","article_type":"original","publisher":"IOP Publishing","file_date_updated":"2023-01-24T07:24:37Z","quality_controlled":"1","abstract":[{"text":"Standard epidemic models exhibit one continuous, second order phase transition to macroscopic outbreaks. However, interventions to control outbreaks may fundamentally alter epidemic dynamics. Here we reveal how such interventions modify the type of phase transition. In particular, we uncover three distinct types of explosive phase transitions for epidemic dynamics with capacity-limited interventions. Depending on the capacity limit, interventions may (i) leave the standard second order phase transition unchanged but exponentially suppress the probability of large outbreaks, (ii) induce a first-order discontinuous transition to macroscopic outbreaks, or (iii) cause a secondary explosive yet continuous third-order transition. These insights highlight inherent limitations in predicting and containing epidemic outbreaks. More generally our study offers a cornerstone example of a third-order explosive phase transition in complex systems.","lang":"eng"}],"doi":"10.1088/2632-072x/ac99cd","day":"25","date_updated":"2023-02-13T09:15:13Z","citation":{"apa":"Börner, G., Schröder, M., Scarselli, D., Budanur, N. B., Hof, B., &#38; Timme, M. (2022). Explosive transitions in epidemic dynamics. <i>Journal of Physics: Complexity</i>. IOP Publishing. <a href=\"https://doi.org/10.1088/2632-072x/ac99cd\">https://doi.org/10.1088/2632-072x/ac99cd</a>","ama":"Börner G, Schröder M, Scarselli D, Budanur NB, Hof B, Timme M. Explosive transitions in epidemic dynamics. <i>Journal of Physics: Complexity</i>. 2022;3(4). doi:<a href=\"https://doi.org/10.1088/2632-072x/ac99cd\">10.1088/2632-072x/ac99cd</a>","chicago":"Börner, Georg, Malte Schröder, Davide Scarselli, Nazmi B Budanur, Björn Hof, and Marc Timme. “Explosive Transitions in Epidemic Dynamics.” <i>Journal of Physics: Complexity</i>. IOP Publishing, 2022. <a href=\"https://doi.org/10.1088/2632-072x/ac99cd\">https://doi.org/10.1088/2632-072x/ac99cd</a>.","ieee":"G. Börner, M. Schröder, D. Scarselli, N. B. Budanur, B. Hof, and M. Timme, “Explosive transitions in epidemic dynamics,” <i>Journal of Physics: Complexity</i>, vol. 3, no. 4. IOP Publishing, 2022.","mla":"Börner, Georg, et al. “Explosive Transitions in Epidemic Dynamics.” <i>Journal of Physics: Complexity</i>, vol. 3, no. 4, 04LT02, IOP Publishing, 2022, doi:<a href=\"https://doi.org/10.1088/2632-072x/ac99cd\">10.1088/2632-072x/ac99cd</a>.","short":"G. Börner, M. Schröder, D. Scarselli, N.B. Budanur, B. Hof, M. Timme, Journal of Physics: Complexity 3 (2022).","ista":"Börner G, Schröder M, Scarselli D, Budanur NB, Hof B, Timme M. 2022. Explosive transitions in epidemic dynamics. Journal of Physics: Complexity. 3(4), 04LT02."},"year":"2022","ddc":["530"],"volume":3,"acknowledgement":"We acknowledge support from the Volkswagen Foundation under Grant No. 99720 and the German Federal Ministry for Education and Research (BMBF) under Grant No. 16ICR01. This research was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy—EXC-2068—390729961—Cluster of Excellence Physics of Life of TU Dresden."},{"file_date_updated":"2023-01-24T10:02:40Z","ec_funded":1,"quality_controlled":"1","article_type":"original","publisher":"Cambridge University Press","author":[{"last_name":"Cipolloni","first_name":"Giorgio","full_name":"Cipolloni, Giorgio","orcid":"0000-0002-4901-7992","id":"42198EFA-F248-11E8-B48F-1D18A9856A87"},{"id":"4DBD5372-F248-11E8-B48F-1D18A9856A87","full_name":"Erdös, László","orcid":"0000-0001-5366-9603","last_name":"Erdös","first_name":"László"},{"last_name":"Schröder","first_name":"Dominik J","full_name":"Schröder, Dominik J","orcid":"0000-0002-2904-1856","id":"408ED176-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":"1","_id":"12148","intvolume":"        10","title":"Rank-uniform local law for Wigner matrices","article_processing_charge":"No","date_created":"2023-01-12T12:07:30Z","department":[{"_id":"LaEr"}],"publication_status":"published","ddc":["510"],"acknowledgement":"L.E. acknowledges support by ERC Advanced Grant ‘RMTBeyond’ No. 101020331. D.S. acknowledges the support of Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation.","volume":10,"external_id":{"isi":["000873719200001"]},"isi":1,"year":"2022","citation":{"ista":"Cipolloni G, Erdös L, Schröder DJ. 2022. Rank-uniform local law for Wigner matrices. Forum of Mathematics, Sigma. 10, e96.","mla":"Cipolloni, Giorgio, et al. “Rank-Uniform Local Law for Wigner Matrices.” <i>Forum of Mathematics, Sigma</i>, vol. 10, e96, Cambridge University Press, 2022, doi:<a href=\"https://doi.org/10.1017/fms.2022.86\">10.1017/fms.2022.86</a>.","short":"G. Cipolloni, L. Erdös, D.J. Schröder, Forum of Mathematics, Sigma 10 (2022).","ieee":"G. Cipolloni, L. Erdös, and D. J. Schröder, “Rank-uniform local law for Wigner matrices,” <i>Forum of Mathematics, Sigma</i>, vol. 10. Cambridge University Press, 2022.","chicago":"Cipolloni, Giorgio, László Erdös, and Dominik J Schröder. “Rank-Uniform Local Law for Wigner Matrices.” <i>Forum of Mathematics, Sigma</i>. Cambridge University Press, 2022. <a href=\"https://doi.org/10.1017/fms.2022.86\">https://doi.org/10.1017/fms.2022.86</a>.","ama":"Cipolloni G, Erdös L, Schröder DJ. Rank-uniform local law for Wigner matrices. <i>Forum of Mathematics, Sigma</i>. 2022;10. doi:<a href=\"https://doi.org/10.1017/fms.2022.86\">10.1017/fms.2022.86</a>","apa":"Cipolloni, G., Erdös, L., &#38; Schröder, D. J. (2022). Rank-uniform local law for Wigner matrices. <i>Forum of Mathematics, Sigma</i>. Cambridge University Press. <a href=\"https://doi.org/10.1017/fms.2022.86\">https://doi.org/10.1017/fms.2022.86</a>"},"date_updated":"2023-08-04T09:00:35Z","abstract":[{"text":"We prove a general local law for Wigner matrices that optimally handles observables of arbitrary rank and thus unifies the well-known averaged and isotropic local laws. As an application, we prove a central limit theorem in quantum unique ergodicity (QUE): that is, we show that the quadratic forms of a general deterministic matrix A on the bulk eigenvectors of a Wigner matrix have approximately Gaussian fluctuation. For the bulk spectrum, we thus generalise our previous result [17] as valid for test matrices A of large rank as well as the result of Benigni and Lopatto [7] as valid for specific small-rank observables.","lang":"eng"}],"day":"27","doi":"10.1017/fms.2022.86","keyword":["Computational Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Mathematical Physics","Statistics and Probability","Algebra and Number Theory","Theoretical Computer Science","Analysis"],"language":[{"iso":"eng"}],"has_accepted_license":"1","publication":"Forum of Mathematics, Sigma","article_number":"e96","month":"10","project":[{"grant_number":"101020331","name":"Random matrices beyond Wigner-Dyson-Mehta","call_identifier":"H2020","_id":"62796744-2b32-11ec-9570-940b20777f1d"}],"oa_version":"Published Version","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","file":[{"relation":"main_file","success":1,"access_level":"open_access","creator":"dernst","file_id":"12356","checksum":"94a049aeb1eea5497aa097712a73c400","file_size":817089,"date_created":"2023-01-24T10:02:40Z","file_name":"2022_ForumMath_Cipolloni.pdf","content_type":"application/pdf","date_updated":"2023-01-24T10:02:40Z"}],"type":"journal_article","date_published":"2022-10-27T00:00:00Z","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"publication_identifier":{"issn":["2050-5094"]}},{"oa":1,"publication_identifier":{"issn":["2073-8994"]},"date_published":"2022-10-17T00:00:00Z","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"status":"public","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","file":[{"file_name":"2022_Symmetry_Salsnich.pdf","content_type":"application/pdf","date_updated":"2023-01-24T10:56:12Z","checksum":"9b6bd0e484834dd76d7b26e3c5fba8bd","file_size":843723,"date_created":"2023-01-24T10:56:12Z","creator":"dernst","file_id":"12361","relation":"main_file","success":1,"access_level":"open_access"}],"month":"10","article_number":"2182","oa_version":"Published Version","publication":"Symmetry","has_accepted_license":"1","language":[{"iso":"eng"}],"keyword":["Physics and Astronomy (miscellaneous)","General Mathematics","Chemistry (miscellaneous)","Computer Science (miscellaneous)"],"abstract":[{"text":"We review our theoretical results of the sound propagation in two-dimensional (2D) systems of ultracold fermionic and bosonic atoms. In the superfluid phase, characterized by the spontaneous symmetry breaking of the U(1) symmetry, there is the coexistence of first and second sound. In the case of weakly-interacting repulsive bosons, we model the recent measurements of the sound velocities of 39K atoms in 2D obtained in the weakly-interacting regime and around the Berezinskii–Kosterlitz–Thouless (BKT) superfluid-to-normal transition temperature. In particular, we perform a quite accurate computation of the superfluid density and show that it is reasonably consistent with the experimental results. For superfluid attractive fermions, we calculate the first and second sound velocities across the whole BCS-BEC crossover. In the low-temperature regime, we reproduce the recent measurements of first-sound speed with 6Li atoms. We also predict that there is mixing between sound modes only in the finite-temperature BEC regime.","lang":"eng"}],"doi":"10.3390/sym14102182","day":"17","isi":1,"external_id":{"isi":["000875039200001"]},"date_updated":"2023-08-09T10:13:17Z","citation":{"short":"L. Salasnich, A. Cappellaro, K. Furutani, A. Tononi, G. Bighin, Symmetry 14 (2022).","mla":"Salasnich, Luca, et al. “First and Second Sound in Two-Dimensional Bosonic and Fermionic Superfluids.” <i>Symmetry</i>, vol. 14, no. 10, 2182, MDPI, 2022, doi:<a href=\"https://doi.org/10.3390/sym14102182\">10.3390/sym14102182</a>.","ista":"Salasnich L, Cappellaro A, Furutani K, Tononi A, Bighin G. 2022. First and second sound in two-dimensional bosonic and fermionic superfluids. Symmetry. 14(10), 2182.","apa":"Salasnich, L., Cappellaro, A., Furutani, K., Tononi, A., &#38; Bighin, G. (2022). First and second sound in two-dimensional bosonic and fermionic superfluids. <i>Symmetry</i>. MDPI. <a href=\"https://doi.org/10.3390/sym14102182\">https://doi.org/10.3390/sym14102182</a>","ama":"Salasnich L, Cappellaro A, Furutani K, Tononi A, Bighin G. First and second sound in two-dimensional bosonic and fermionic superfluids. <i>Symmetry</i>. 2022;14(10). doi:<a href=\"https://doi.org/10.3390/sym14102182\">10.3390/sym14102182</a>","chicago":"Salasnich, Luca, Alberto Cappellaro, Koichiro Furutani, Andrea Tononi, and Giacomo Bighin. “First and Second Sound in Two-Dimensional Bosonic and Fermionic Superfluids.” <i>Symmetry</i>. MDPI, 2022. <a href=\"https://doi.org/10.3390/sym14102182\">https://doi.org/10.3390/sym14102182</a>.","ieee":"L. Salasnich, A. Cappellaro, K. Furutani, A. Tononi, and G. Bighin, “First and second sound in two-dimensional bosonic and fermionic superfluids,” <i>Symmetry</i>, vol. 14, no. 10. MDPI, 2022."},"year":"2022","ddc":["530"],"volume":14,"acknowledgement":"This research is partially supported by University of Padova, BIRD grant “Ultracold atoms\r\nin curved geometries”. KF is supported by Fondazione CARIPARO with a PhD fellowship. AT is\r\npartially supported by French National Research Agency ANR Grant Droplets N. ANR-19-CE30-0003-02. LS thanks Herwig Ott and Sandro Wimberger for their kind invitation to the\r\nInternational Workshop “Quantum Transport with ultracold atoms” (2022).","title":"First and second sound in two-dimensional bosonic and fermionic superfluids","intvolume":"        14","publication_status":"published","date_created":"2023-01-12T12:08:31Z","department":[{"_id":"MiLe"}],"article_processing_charge":"Yes","author":[{"full_name":"Salasnich, Luca","last_name":"Salasnich","first_name":"Luca"},{"first_name":"Alberto","last_name":"Cappellaro","orcid":"0000-0001-6110-2359","full_name":"Cappellaro, Alberto","id":"9d13b3cb-30a2-11eb-80dc-f772505e8660"},{"last_name":"Furutani","first_name":"Koichiro","full_name":"Furutani, Koichiro"},{"first_name":"Andrea","last_name":"Tononi","full_name":"Tononi, Andrea"},{"orcid":"0000-0001-8823-9777","full_name":"Bighin, Giacomo","first_name":"Giacomo","last_name":"Bighin","id":"4CA96FD4-F248-11E8-B48F-1D18A9856A87"}],"issue":"10","_id":"12154","scopus_import":"1","article_type":"original","publisher":"MDPI","file_date_updated":"2023-01-24T10:56:12Z","quality_controlled":"1"},{"keyword":["Applied Mathematics","Computer Science Applications","Drug Discovery","General Biochemistry","Genetics and Molecular Biology","Modeling and Simulation"],"language":[{"iso":"eng"}],"project":[{"call_identifier":"FWF","_id":"254E9036-B435-11E9-9278-68D0E5697425","grant_number":"P28844-B27","name":"Biophysics of information processing in gene regulation"}],"oa_version":"Published Version","article_number":"100435","month":"09","has_accepted_license":"1","publication":"Current Opinion in Systems Biology","file":[{"access_level":"open_access","success":1,"relation":"main_file","file_id":"12362","creator":"dernst","date_created":"2023-01-24T12:14:10Z","file_size":2214944,"checksum":"97ef01e0cc60cdc84f45640a0f248fb0","date_updated":"2023-01-24T12:14:10Z","content_type":"application/pdf","file_name":"2022_CurrentBiology_Zoller.pdf"}],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"issn":["2452-3100"]},"oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"journal_article","date_published":"2022-09-01T00:00:00Z","publisher":"Elsevier","article_type":"original","quality_controlled":"1","file_date_updated":"2023-01-24T12:14:10Z","department":[{"_id":"GaTk"}],"date_created":"2023-01-12T12:08:51Z","article_processing_charge":"Yes (via OA deal)","publication_status":"published","intvolume":"        31","title":"Eukaryotic gene regulation at equilibrium, or non?","scopus_import":"1","_id":"12156","issue":"9","author":[{"full_name":"Zoller, Benjamin","last_name":"Zoller","first_name":"Benjamin"},{"full_name":"Gregor, Thomas","last_name":"Gregor","first_name":"Thomas"},{"last_name":"Tkačik","first_name":"Gašper","full_name":"Tkačik, Gašper","orcid":"1","id":"3D494DCA-F248-11E8-B48F-1D18A9856A87"}],"volume":31,"acknowledgement":"This work was supported through the Center for the Physics of Biological Function (PHYe1734030) and by National Institutes of Health Grants R01GM097275 and U01DK127429 (TG). GT acknowledges the support of the Austrian Science Fund grant FWF P28844 and the Human Frontiers Science Program. ","ddc":["570"],"day":"01","doi":"10.1016/j.coisb.2022.100435","abstract":[{"text":"Models of transcriptional regulation that assume equilibrium binding of transcription factors have been less successful at predicting gene expression from sequence in eukaryotes than in bacteria. This could be due to the non-equilibrium nature of eukaryotic regulation. Unfortunately, the space of possible non-equilibrium mechanisms is vast and predominantly uninteresting. The key question is therefore how this space can be navigated efficiently, to focus on mechanisms and models that are biologically relevant. In this review, we advocate for the normative role of theory—theory that prescribes rather than just describes—in providing such a focus. Theory should expand its remit beyond inferring mechanistic models from data, towards identifying non-equilibrium gene regulatory schemes that may have been evolutionarily selected, despite their energy consumption, because they are precise, reliable, fast, or otherwise outperform regulation at equilibrium. We illustrate our reasoning by toy examples for which we provide simulation code.","lang":"eng"}],"citation":{"ista":"Zoller B, Gregor T, Tkačik G. 2022. Eukaryotic gene regulation at equilibrium, or non? Current Opinion in Systems Biology. 31(9), 100435.","mla":"Zoller, Benjamin, et al. “Eukaryotic Gene Regulation at Equilibrium, or Non?” <i>Current Opinion in Systems Biology</i>, vol. 31, no. 9, 100435, Elsevier, 2022, doi:<a href=\"https://doi.org/10.1016/j.coisb.2022.100435\">10.1016/j.coisb.2022.100435</a>.","short":"B. Zoller, T. Gregor, G. Tkačik, Current Opinion in Systems Biology 31 (2022).","chicago":"Zoller, Benjamin, Thomas Gregor, and Gašper Tkačik. “Eukaryotic Gene Regulation at Equilibrium, or Non?” <i>Current Opinion in Systems Biology</i>. Elsevier, 2022. <a href=\"https://doi.org/10.1016/j.coisb.2022.100435\">https://doi.org/10.1016/j.coisb.2022.100435</a>.","ieee":"B. Zoller, T. Gregor, and G. Tkačik, “Eukaryotic gene regulation at equilibrium, or non?,” <i>Current Opinion in Systems Biology</i>, vol. 31, no. 9. Elsevier, 2022.","apa":"Zoller, B., Gregor, T., &#38; Tkačik, G. (2022). Eukaryotic gene regulation at equilibrium, or non? <i>Current Opinion in Systems Biology</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.coisb.2022.100435\">https://doi.org/10.1016/j.coisb.2022.100435</a>","ama":"Zoller B, Gregor T, Tkačik G. Eukaryotic gene regulation at equilibrium, or non? <i>Current Opinion in Systems Biology</i>. 2022;31(9). doi:<a href=\"https://doi.org/10.1016/j.coisb.2022.100435\">10.1016/j.coisb.2022.100435</a>"},"year":"2022","date_updated":"2023-02-13T09:20:34Z"},{"isi":1,"external_id":{"isi":["000876763300001"]},"date_updated":"2023-08-04T10:29:18Z","year":"2022","citation":{"ista":"Cooley O, Kang M, Zalla J. 2022. Loose cores and cycles in random hypergraphs. The Electronic Journal of Combinatorics. 29(4), P4.13.","mla":"Cooley, Oliver, et al. “Loose Cores and Cycles in Random Hypergraphs.” <i>The Electronic Journal of Combinatorics</i>, vol. 29, no. 4, P4.13, The Electronic Journal of Combinatorics, 2022, doi:<a href=\"https://doi.org/10.37236/10794\">10.37236/10794</a>.","short":"O. Cooley, M. Kang, J. Zalla, The Electronic Journal of Combinatorics 29 (2022).","chicago":"Cooley, Oliver, Mihyun Kang, and Julian Zalla. “Loose Cores and Cycles in Random Hypergraphs.” <i>The Electronic Journal of Combinatorics</i>. The Electronic Journal of Combinatorics, 2022. <a href=\"https://doi.org/10.37236/10794\">https://doi.org/10.37236/10794</a>.","ieee":"O. Cooley, M. Kang, and J. Zalla, “Loose cores and cycles in random hypergraphs,” <i>The Electronic Journal of Combinatorics</i>, vol. 29, no. 4. The Electronic Journal of Combinatorics, 2022.","apa":"Cooley, O., Kang, M., &#38; Zalla, J. (2022). Loose cores and cycles in random hypergraphs. <i>The Electronic Journal of Combinatorics</i>. The Electronic Journal of Combinatorics. <a href=\"https://doi.org/10.37236/10794\">https://doi.org/10.37236/10794</a>","ama":"Cooley O, Kang M, Zalla J. Loose cores and cycles in random hypergraphs. <i>The Electronic Journal of Combinatorics</i>. 2022;29(4). doi:<a href=\"https://doi.org/10.37236/10794\">10.37236/10794</a>"},"abstract":[{"text":"Inspired by the study of loose cycles in hypergraphs, we define the loose core in hypergraphs as a structurewhich mirrors the close relationship between cycles and $2$-cores in graphs. We prove that in the $r$-uniform binomial random hypergraph $H^r(n,p)$, the order of the loose core undergoes a phase transition at a certain critical threshold and determine this order, as well as the number of edges, asymptotically in the subcritical and supercritical regimes.&#x0D;\r\nOur main tool is an algorithm called CoreConstruct, which enables us to analyse a peeling process for the loose core. By analysing this algorithm we determine the asymptotic degree distribution of vertices in the loose core and in particular how many vertices and edges the loose core contains. As a corollary we obtain an improved upper bound on the length of the longest loose cycle in $H^r(n,p)$.","lang":"eng"}],"doi":"10.37236/10794","day":"21","ddc":["510"],"volume":29,"acknowledgement":"Supported by Austrian Science Fund (FWF): I3747, W1230.","author":[{"full_name":"Cooley, Oliver","first_name":"Oliver","last_name":"Cooley","id":"43f4ddd0-a46b-11ec-8df6-ef3703bd721d"},{"first_name":"Mihyun","last_name":"Kang","full_name":"Kang, Mihyun"},{"first_name":"Julian","last_name":"Zalla","full_name":"Zalla, Julian"}],"issue":"4","_id":"12286","scopus_import":"1","license":"https://creativecommons.org/licenses/by-nd/4.0/","title":"Loose cores and cycles in random hypergraphs","intvolume":"        29","publication_status":"published","article_processing_charge":"No","date_created":"2023-01-16T10:03:57Z","department":[{"_id":"MaKw"}],"file_date_updated":"2023-01-30T11:45:13Z","quality_controlled":"1","article_type":"original","publisher":"The Electronic Journal of Combinatorics","date_published":"2022-10-21T00:00:00Z","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nd/4.0/legalcode","name":"Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)","image":"/image/cc_by_nd.png","short":"CC BY-ND (4.0)"},"oa":1,"publication_identifier":{"eissn":["1077-8926"]},"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","file":[{"file_id":"12462","creator":"dernst","success":1,"access_level":"open_access","relation":"main_file","date_updated":"2023-01-30T11:45:13Z","content_type":"application/pdf","file_name":"2022_ElecJournCombinatorics_Cooley_Kang_Zalla.pdf","date_created":"2023-01-30T11:45:13Z","file_size":626953,"checksum":"00122b2459f09b5ae43073bfba565e94"}],"publication":"The Electronic Journal of Combinatorics","has_accepted_license":"1","month":"10","article_number":"P4.13","oa_version":"Published Version","language":[{"iso":"eng"}],"keyword":["Computational Theory and Mathematics","Geometry and Topology","Theoretical Computer Science","Applied Mathematics","Discrete Mathematics and Combinatorics"]},{"file_date_updated":"2022-01-26T08:04:50Z","page":"10:1-10:23","quality_controlled":"1","article_type":"original","publisher":"International Federation for Computational Logic","author":[{"full_name":"Aghajohari, Milad","last_name":"Aghajohari","first_name":"Milad"},{"full_name":"Avni, Guy","orcid":"0000-0001-5588-8287","last_name":"Avni","first_name":"Guy","id":"463C8BC2-F248-11E8-B48F-1D18A9856A87"},{"id":"40876CD8-F248-11E8-B48F-1D18A9856A87","last_name":"Henzinger","first_name":"Thomas A","full_name":"Henzinger, Thomas A","orcid":"0000-0002-2985-7724"}],"issue":"1","_id":"10674","scopus_import":"1","title":"Determinacy in discrete-bidding infinite-duration games","intvolume":"        17","publication_status":"published","department":[{"_id":"ToHe"}],"article_processing_charge":"No","date_created":"2022-01-25T16:32:13Z","ddc":["510"],"volume":17,"acknowledgement":"This research was supported in part by the Austrian Science Fund (FWF) under grants S11402-N23 (RiSE/SHiNE), Z211-N23 (Wittgenstein Award), and M 2369-N33 (Meitner fellowship).\r\n","isi":1,"external_id":{"isi":["000658724600010"],"arxiv":["1905.03588"]},"date_updated":"2023-08-17T06:56:42Z","year":"2021","citation":{"short":"M. Aghajohari, G. Avni, T.A. Henzinger, Logical Methods in Computer Science 17 (2021) 10:1-10:23.","mla":"Aghajohari, Milad, et al. “Determinacy in Discrete-Bidding Infinite-Duration Games.” <i>Logical Methods in Computer Science</i>, vol. 17, no. 1, International Federation for Computational Logic, 2021, p. 10:1-10:23, doi:<a href=\"https://doi.org/10.23638/LMCS-17(1:10)2021\">10.23638/LMCS-17(1:10)2021</a>.","ista":"Aghajohari M, Avni G, Henzinger TA. 2021. Determinacy in discrete-bidding infinite-duration games. Logical Methods in Computer Science. 17(1), 10:1-10:23.","apa":"Aghajohari, M., Avni, G., &#38; Henzinger, T. A. (2021). Determinacy in discrete-bidding infinite-duration games. <i>Logical Methods in Computer Science</i>. International Federation for Computational Logic. <a href=\"https://doi.org/10.23638/LMCS-17(1:10)2021\">https://doi.org/10.23638/LMCS-17(1:10)2021</a>","ama":"Aghajohari M, Avni G, Henzinger TA. Determinacy in discrete-bidding infinite-duration games. <i>Logical Methods in Computer Science</i>. 2021;17(1):10:1-10:23. doi:<a href=\"https://doi.org/10.23638/LMCS-17(1:10)2021\">10.23638/LMCS-17(1:10)2021</a>","chicago":"Aghajohari, Milad, Guy Avni, and Thomas A Henzinger. “Determinacy in Discrete-Bidding Infinite-Duration Games.” <i>Logical Methods in Computer Science</i>. International Federation for Computational Logic, 2021. <a href=\"https://doi.org/10.23638/LMCS-17(1:10)2021\">https://doi.org/10.23638/LMCS-17(1:10)2021</a>.","ieee":"M. Aghajohari, G. Avni, and T. A. Henzinger, “Determinacy in discrete-bidding infinite-duration games,” <i>Logical Methods in Computer Science</i>, vol. 17, no. 1. International Federation for Computational Logic, p. 10:1-10:23, 2021."},"abstract":[{"lang":"eng","text":"In two-player games on graphs, the players move a token through a graph to produce an infinite path, which determines the winner of the game. Such games are central in formal methods since they model the interaction between a non-terminating system and its environment. In bidding games the players bid for the right to move the token: in each round, the players simultaneously submit bids, and the higher bidder moves the token and pays the other player. Bidding games are known to have a clean and elegant mathematical structure that relies on the ability of the players to submit arbitrarily small bids. Many applications, however, require a fixed granularity for the bids, which can represent, for example, the monetary value expressed in cents. We study, for the first time, the combination of discrete-bidding and infinite-duration games. Our most important result proves that these games form a large determined subclass of concurrent games, where determinacy is the strong property that there always exists exactly one player who can guarantee winning the game. In particular, we show that, in contrast to non-discrete bidding games, the mechanism with which tied bids are resolved plays an important role in discrete-bidding games. We study several natural tie-breaking mechanisms and show that, while some do not admit determinacy, most natural mechanisms imply determinacy for every pair of initial budgets."}],"arxiv":1,"doi":"10.23638/LMCS-17(1:10)2021","day":"03","language":[{"iso":"eng"}],"keyword":["computer science","computer science and game theory","logic in computer science"],"publication":"Logical Methods in Computer Science","has_accepted_license":"1","month":"02","oa_version":"Published Version","project":[{"call_identifier":"FWF","_id":"264B3912-B435-11E9-9278-68D0E5697425","grant_number":"M02369","name":"Formal Methods meets Algorithmic Game Theory"},{"call_identifier":"FWF","_id":"25F2ACDE-B435-11E9-9278-68D0E5697425","grant_number":"S11402-N23","name":"Rigorous Systems Engineering"},{"grant_number":"Z211","name":"The Wittgenstein Prize","call_identifier":"FWF","_id":"25F42A32-B435-11E9-9278-68D0E5697425"}],"status":"public","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","file":[{"access_level":"open_access","relation":"main_file","success":1,"creator":"alisjak","file_id":"10690","file_size":819878,"checksum":"b35586a50ed1ca8f44767de116d18d81","date_created":"2022-01-26T08:04:50Z","file_name":"2021_LMCS_AGHAJOHAR.pdf","content_type":"application/pdf","date_updated":"2022-01-26T08:04:50Z"}],"date_published":"2021-02-03T00:00:00Z","type":"journal_article","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa":1,"publication_identifier":{"eissn":["1860-5974"]}},{"issue":"1","author":[{"first_name":"Klaus-Tycho","last_name":"Foerster","full_name":"Foerster, Klaus-Tycho"},{"full_name":"Korhonen, Janne","first_name":"Janne","last_name":"Korhonen","id":"C5402D42-15BC-11E9-A202-CA2BE6697425"},{"full_name":"Paz, Ami","first_name":"Ami","last_name":"Paz"},{"id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646","full_name":"Rybicki, Joel","first_name":"Joel","last_name":"Rybicki"},{"last_name":"Schmid","first_name":"Stefan","full_name":"Schmid, Stefan"}],"scopus_import":"1","_id":"10855","intvolume":"         5","title":"Input-dynamic distributed algorithms for communication networks","date_created":"2022-03-18T09:10:27Z","department":[{"_id":"DaAl"}],"article_processing_charge":"No","publication_status":"published","quality_controlled":"1","ec_funded":1,"page":"1-33","article_type":"original","publisher":"Association for Computing Machinery","external_id":{"arxiv":["2005.07637"]},"year":"2021","citation":{"ista":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. 2021. Input-dynamic distributed algorithms for communication networks. Proceedings of the ACM on Measurement and Analysis of Computing Systems. 5(1), 1–33.","short":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, S. Schmid, Proceedings of the ACM on Measurement and Analysis of Computing Systems 5 (2021) 1–33.","mla":"Foerster, Klaus-Tycho, et al. “Input-Dynamic Distributed Algorithms for Communication Networks.” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>, vol. 5, no. 1, Association for Computing Machinery, 2021, pp. 1–33, doi:<a href=\"https://doi.org/10.1145/3447384\">10.1145/3447384</a>.","ieee":"K.-T. Foerster, J. Korhonen, A. Paz, J. Rybicki, and S. Schmid, “Input-dynamic distributed algorithms for communication networks,” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>, vol. 5, no. 1. Association for Computing Machinery, pp. 1–33, 2021.","chicago":"Foerster, Klaus-Tycho, Janne Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid. “Input-Dynamic Distributed Algorithms for Communication Networks.” <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3447384\">https://doi.org/10.1145/3447384</a>.","ama":"Foerster K-T, Korhonen J, Paz A, Rybicki J, Schmid S. Input-dynamic distributed algorithms for communication networks. <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. 2021;5(1):1-33. doi:<a href=\"https://doi.org/10.1145/3447384\">10.1145/3447384</a>","apa":"Foerster, K.-T., Korhonen, J., Paz, A., Rybicki, J., &#38; Schmid, S. (2021). Input-dynamic distributed algorithms for communication networks. <i>Proceedings of the ACM on Measurement and Analysis of Computing Systems</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3447384\">https://doi.org/10.1145/3447384</a>"},"date_updated":"2023-09-26T10:40:55Z","abstract":[{"text":"Consider a distributed task where the communication network is fixed but the local inputs given to the nodes of the distributed system may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic \\congest model in which we are given a bandwidth-limited communication network and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of α edge label changes arrive, \\beginitemize \\item how much time as a function of α we need to update an existing solution, and \\item how much information the nodes have to keep in local memory between batches in order to update the solution quickly. \\enditemize Our work lays the foundations for the theory of input-dynamic distributed network algorithms. We give a general picture of the complexity landscape in this model, design both universal algorithms and algorithms for concrete problems, and present a general framework for lower bounds. In particular, we derive non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques.","lang":"eng"}],"day":"01","doi":"10.1145/3447384","arxiv":1,"volume":5,"acknowledgement":"We thank Jukka Suomela for discussions. We also thank our shepherd Mohammad Hajiesmaili\r\nand the reviewers for their time and suggestions on how to improve the paper. This project\r\nhas received funding from the European Research Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation programme (grant agreement No 805223 ScaleML), from the European Union’s Horizon 2020 research and innovation programme under the Marie\r\nSk lodowska–Curie grant agreement No. 840605, from the Vienna Science and Technology Fund (WWTF) project WHATIF, ICT19-045, 2020-2024, and from the Austrian Science Fund (FWF) and netIDEE SCIENCE project P 33775-N.","publication":"Proceedings of the ACM on Measurement and Analysis of Computing Systems","month":"03","project":[{"name":"Coordination in constrained and natural distributed systems","grant_number":"840605","_id":"26A5D39A-B435-11E9-9278-68D0E5697425","call_identifier":"H2020"},{"call_identifier":"H2020","_id":"268A44D6-B435-11E9-9278-68D0E5697425","grant_number":"805223","name":"Elastic Coordination for Scalable Machine Learning"}],"oa_version":"Preprint","keyword":["Computer Networks and Communications","Hardware and Architecture","Safety","Risk","Reliability and Quality","Computer Science (miscellaneous)"],"language":[{"iso":"eng"}],"type":"journal_article","date_published":"2021-03-01T00:00:00Z","oa":1,"publication_identifier":{"issn":["2476-1249"]},"status":"public","related_material":{"record":[{"id":"10854","relation":"shorter_version","status":"public"}]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2005.07637"}]},{"author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","full_name":"Avvakumov, Sergey","last_name":"Avvakumov","first_name":"Sergey"},{"id":"ecf01965-d252-11ea-95a5-8ada5f6c6a67","last_name":"Kudrya","first_name":"Sergey","full_name":"Kudrya, Sergey"}],"issue":"3","_id":"11446","scopus_import":"1","title":"Vanishing of all equivariant obstructions and the mapping degree","intvolume":"        66","publication_status":"published","article_processing_charge":"No","date_created":"2022-06-17T08:45:15Z","page":"1202-1216","quality_controlled":"1","article_type":"original","publisher":"Springer Nature","external_id":{"arxiv":["1910.12628"]},"date_updated":"2023-02-23T13:26:41Z","year":"2021","citation":{"apa":"Avvakumov, S., &#38; Kudrya, S. (2021). Vanishing of all equivariant obstructions and the mapping degree. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-021-00299-z\">https://doi.org/10.1007/s00454-021-00299-z</a>","ama":"Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping degree. <i>Discrete &#38; Computational Geometry</i>. 2021;66(3):1202-1216. doi:<a href=\"https://doi.org/10.1007/s00454-021-00299-z\">10.1007/s00454-021-00299-z</a>","chicago":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s00454-021-00299-z\">https://doi.org/10.1007/s00454-021-00299-z</a>.","ieee":"S. Avvakumov and S. Kudrya, “Vanishing of all equivariant obstructions and the mapping degree,” <i>Discrete &#38; Computational Geometry</i>, vol. 66, no. 3. Springer Nature, pp. 1202–1216, 2021.","short":"S. Avvakumov, S. Kudrya, Discrete &#38; Computational Geometry 66 (2021) 1202–1216.","mla":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” <i>Discrete &#38; Computational Geometry</i>, vol. 66, no. 3, Springer Nature, 2021, pp. 1202–16, doi:<a href=\"https://doi.org/10.1007/s00454-021-00299-z\">10.1007/s00454-021-00299-z</a>.","ista":"Avvakumov S, Kudrya S. 2021. Vanishing of all equivariant obstructions and the mapping degree. Discrete &#38; Computational Geometry. 66(3), 1202–1216."},"abstract":[{"text":"Suppose that n is not a prime power and not twice a prime power. We prove that for any Hausdorff compactum X with a free action of the symmetric group Sn, there exists an Sn-equivariant map X→Rn whose image avoids the diagonal {(x,x,…,x)∈Rn∣x∈R}. Previously, the special cases of this statement for certain X were usually proved using the equivartiant obstruction theory. Such calculations are difficult and may become infeasible past the first (primary) obstruction. We take a different approach which allows us to prove the vanishing of all obstructions simultaneously. The essential step in the proof is classifying the possible degrees of Sn-equivariant maps from the boundary ∂Δn−1 of (n−1)-simplex to itself. Existence of equivariant maps between spaces is important for many questions arising from discrete mathematics and geometry, such as Kneser’s conjecture, the Square Peg conjecture, the Splitting Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate the utility of our result applying it to one such question, a specific instance of envy-free division problem.","lang":"eng"}],"doi":"10.1007/s00454-021-00299-z","arxiv":1,"day":"01","extern":"1","volume":66,"acknowledgement":"S. Avvakumov has received funding from the European Research Council under the European Union’s Seventh Framework Programme ERC Grant agreement ERC StG 716424–CASe. S. Kudrya was supported by the Austrian Academic Exchange Service (OeAD), ICM-2019-13577.","publication":"Discrete & Computational Geometry","month":"10","oa_version":"Preprint","language":[{"iso":"eng"}],"keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"date_published":"2021-10-01T00:00:00Z","type":"journal_article","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"record":[{"id":"8182","relation":"earlier_version","status":"public"}]},"status":"public"}]