[{"publication_status":"epub_ahead","project":[{"name":"IST-BRIDGE: International postdoctoral program","call_identifier":"H2020","_id":"fc2ed2f7-9c52-11eb-aca3-c01059dda49c","grant_number":"101034413"},{"grant_number":"101019564","call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","name":"The design and evaluation of modern fully dynamic data structures"}],"citation":{"short":"N. Hahn, M. Henzinger, Z. Stefankovic, Information Processing Letters 195 (2026).","apa":"Hahn, N., Henzinger, M., &#38; Stefankovic, Z. (2026). Tight bounds on the performance of dynamic directed cutset data structures based on OMv. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/j.ipl.2026.106663\">https://doi.org/10.1016/j.ipl.2026.106663</a>","ista":"Hahn N, Henzinger M, Stefankovic Z. 2026. Tight bounds on the performance of dynamic directed cutset data structures based on OMv. Information Processing Letters. 195, 106663.","ieee":"N. Hahn, M. Henzinger, and Z. Stefankovic, “Tight bounds on the performance of dynamic directed cutset data structures based on OMv,” <i>Information Processing Letters</i>, vol. 195. Elsevier, 2026.","ama":"Hahn N, Henzinger M, Stefankovic Z. Tight bounds on the performance of dynamic directed cutset data structures based on OMv. <i>Information Processing Letters</i>. 2026;195. doi:<a href=\"https://doi.org/10.1016/j.ipl.2026.106663\">10.1016/j.ipl.2026.106663</a>","chicago":"Hahn, Niklas, Monika Henzinger, and Zofia Stefankovic. “Tight Bounds on the Performance of Dynamic Directed Cutset Data Structures Based on OMv.” <i>Information Processing Letters</i>. Elsevier, 2026. <a href=\"https://doi.org/10.1016/j.ipl.2026.106663\">https://doi.org/10.1016/j.ipl.2026.106663</a>.","mla":"Hahn, Niklas, et al. “Tight Bounds on the Performance of Dynamic Directed Cutset Data Structures Based on OMv.” <i>Information Processing Letters</i>, vol. 195, 106663, Elsevier, 2026, doi:<a href=\"https://doi.org/10.1016/j.ipl.2026.106663\">10.1016/j.ipl.2026.106663</a>."},"dataavailabilitystatement":"No data was used for the research described in the article.","OA_type":"closed access","type":"journal_article","keyword":["Dynamic algorithms","Graph algorithms","Directed graphs","Lower bounds","Upper bounds"],"author":[{"first_name":"Niklas","full_name":"Hahn, Niklas","id":"0a01c7b2-b823-11ed-9928-cc3f874f9ffd","last_name":"Hahn"},{"full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Zofia","full_name":"Stefankovic, Zofia","last_name":"Stefankovic"}],"article_number":"106663","date_created":"2026-09-06T22:01:55Z","language":[{"iso":"eng"}],"ec_funded":1,"article_processing_charge":"No","abstract":[{"text":"Efficient data structures for computing the cutset of a set of nodes in a graph undergoing dynamic edge insertions/deletions are well-studied in undirected graphs. We study this problem in directed graphs and show a reduction from the Online Boolean Matrix-Vector Multiplication Conjecture (OMv) introduced by Henzinger et al. [STOC’15]. We prove conditional on OMv that a dynamic data structure computing the directed cutset of a set of nodes cannot have an amortized time of both O(n2−ε) for a query operation and O(n1−ε) for an update operation, for any constant ε > 0, even when an adversary’s operations are restricted to the incremental or decremental settings. We further give algorithms to match these lower bounds.","lang":"eng"}],"intvolume":"       195","department":[{"_id":"MoHe"}],"date_published":"2026-08-30T00:00:00Z","scopus_import":"1","status":"public","publication":"Information Processing Letters","oa_version":"None","researchdata_availability":"no","fulldoi":"https://doi.org/10.1016/j.ipl.2026.106663","supplementarymaterial":"no","quality_controlled":"1","publication_identifier":{"issn":["0020-0190"]},"date_updated":"2026-09-09T11:55:47Z","das_tickbox":"1","volume":195,"article_type":"original","month":"08","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","doi":"10.1016/j.ipl.2026.106663","_id":"22812","acknowledgement":"This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 101034413 and from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) Image 1 dummy alt text. Zofia Stefankovic was partially supported by the ISTernship program of the Institute of Science and Technology Austria and OEAD.","publisher":"Elsevier","title":"Tight bounds on the performance of dynamic directed cutset data structures based on OMv","day":"30","year":"2026"},{"ddc":["539"],"has_accepted_license":"1","degree_awarded":"PhD","status":"public","acknowledged_ssus":[{"_id":"ScienComp"}],"abstract":[{"lang":"eng","text":"Can current quantum computers provide a speedup over their classical counterparts for some kinds of problems? In this thesis, with a focus on ground state search/preparation, we address some of the challenges that both quantum annealing and variational quantum algorithms suffer from, hindering any possible practical speedup in comparison to the best classical counterparts. \r\n\r\nIn the first part of the thesis, we study the performance of quantum annealing for solving a particular combinatorial optimization problem called 3-XOR satisfability (3-XORSAT). The classical problem is mapped into a ground state search of a 3-local classical Hamiltonian $H_C$. We consider how modifying the initial problem, by adding more interaction terms to the corresponding Hamiltonian, leads to the emergence of a first-order phase transition during the annealing process. This phenomenon causes the total annealing duration, $T$, required to prepare the ground state of $H_C$ with a high probability to increase exponentially with the size of the problem. Our findings indicate that with the growing complexity of problem instances, the likelihood of encountering first-order phase transitions also increases, making quantum annealing an impractical solution for these types of combinatorial optimization problems.\r\n\r\nIn the second part, we focus on the problem of barren plateaus in generic variational quantum algorithms. Barren plateaus correspond to flat regions in the parameter space where the gradient of the cost function is zero in expectation, and with the variance decaying exponentially with the system size, thus obstructing an efficient parameter optimization.  We propose an algorithm to circumvent Barren Plateaus by monitoring the entanglement entropy of k-local reduced density matrices, alongside a method for estimating entanglement entropy via classical shadow tomography. We illustrate the approach with the paradigmatic example of the variational quantum eigensolver, and show that our algorithm effectively avoids barren plateaus in the initialization as well as during the optimization stage. \r\n\r\nLastly, in the last two Chapters of this thesis, we focus on the quantum approximate optimization algorithm (QAOA), originally introduced as an algorithm for solving generic combinatorial optimization problems in near-term quantum devices. Specifically, we focus on how to develop rigorous initialization strategies with guarantee improvement. Our motivation for this study lies in that for random initialization, the optimization typically leads to local minima with poor performance. Our main result corresponds to the analytical construction of index-1 saddle points or transition states, stationary points with a single direction of descent, as a tool for systematically exploring the QAOA optimization landscape. This leads us to propose a novel greedy parameter initialization strategy that guarantees for the energy to decrease with an increasing number of circuit layers. Furthermore, with precise estimates for the negative Hessian eigenvalue and its eigenvector, we establish a lower bound for energy improvement following a QAOA iteration."}],"department":[{"_id":"GradSch"},{"_id":"MaSe"}],"date_published":"2024-07-09T00:00:00Z","supervisor":[{"first_name":"Maksym","orcid":"0000-0002-2399-5827","full_name":"Serbyn, Maksym","id":"47809E7E-F248-11E8-B48F-1D18A9856A87","last_name":"Serbyn"}],"language":[{"iso":"eng"}],"oa":1,"ec_funded":1,"article_processing_charge":"No","OA_place":"publisher","file_date_updated":"2024-07-17T09:23:24Z","page":"133","date_created":"2024-07-09T09:14:24Z","keyword":["Quantum computing","Variational Quantum Algorithms","Optimization"],"alternative_title":["ISTA Thesis"],"type":"dissertation","author":[{"last_name":"Medina Ramos","id":"CE680B90-D85A-11E9-B684-C920E6697425","full_name":"Medina Ramos, Raimel A","orcid":"0000-0002-5383-2869","first_name":"Raimel A"}],"project":[{"grant_number":"850899","call_identifier":"H2020","_id":"23841C26-32DE-11EA-91FC-C7463DDC885E","name":"Non-Ergodic Quantum Matter: Universality, Dynamics and Control"}],"publication_status":"published","citation":{"short":"R.A. Medina Ramos, Exploring the Optimization Landscape of Variational Quantum Algorithms, Institute of Science and Technology Austria, 2024.","apa":"Medina Ramos, R. A. (2024). <i>Exploring the optimization landscape of variational quantum algorithms</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/at:ista:17208\">https://doi.org/10.15479/at:ista:17208</a>","chicago":"Medina Ramos, Raimel A. “Exploring the Optimization Landscape of Variational Quantum Algorithms.” Institute of Science and Technology Austria, 2024. <a href=\"https://doi.org/10.15479/at:ista:17208\">https://doi.org/10.15479/at:ista:17208</a>.","ieee":"R. A. Medina Ramos, “Exploring the optimization landscape of variational quantum algorithms,” Institute of Science and Technology Austria, 2024.","mla":"Medina Ramos, Raimel A. <i>Exploring the Optimization Landscape of Variational Quantum Algorithms</i>. Institute of Science and Technology Austria, 2024, doi:<a href=\"https://doi.org/10.15479/at:ista:17208\">10.15479/at:ista:17208</a>.","ama":"Medina Ramos RA. Exploring the optimization landscape of variational quantum algorithms. 2024. doi:<a href=\"https://doi.org/10.15479/at:ista:17208\">10.15479/at:ista:17208</a>","ista":"Medina Ramos RA. 2024. Exploring the optimization landscape of variational quantum algorithms. Institute of Science and Technology Austria."},"file":[{"file_name":"Raimel_Thesis-Final.zip","content_type":"application/zip","access_level":"closed","file_size":"14218691","creator":"rmedinar","date_updated":"2024-07-10T11:34:09Z","date_created":"2024-07-09T09:21:44Z","relation":"source_file","checksum":"6f45273d04f4418bc2adc018baed0525","file_id":"17212"},{"date_updated":"2024-07-17T09:23:24Z","checksum":"6724a95bec772dbabc0111b9f08a805e","file_id":"17275","relation":"main_file","date_created":"2024-07-17T09:23:24Z","file_name":"Raimel_Thesis-20_pdfa.pdf","content_type":"application/pdf","file_size":11253627,"access_level":"open_access","success":1,"creator":"rmedinar"}],"doi":"10.15479/at:ista:17208","publisher":"Institute of Science and Technology Austria","_id":"17208","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"10545"},{"status":"public","id":"10067","relation":"part_of_dissertation"},{"id":"17222","relation":"part_of_dissertation","status":"public"},{"id":"13125","relation":"part_of_dissertation","status":"public"},{"status":"public","relation":"part_of_dissertation","id":"11471"}]},"day":"09","year":"2024","corr_author":"1","title":"Exploring the optimization landscape of variational quantum algorithms","month":"07","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publication_identifier":{"issn":["2663-337X"]},"fulldoi":"https://doi.org/10.15479/at:ista:17208","date_updated":"2026-04-07T12:43:22Z","oa_version":"Published Version"},{"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","month":"02","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","_id":"22373","related_material":{"record":[{"status":"public","id":"22281","relation":"dissertation_contains"}]},"acknowledgement":" This project has received funding from the European Research Council (ERC) under\r\nthe European Union’s Horizon 2020 research and innovation programme (grant agreement No.\r\n101019564). This work was further supported by the Austrian Science Fund (FWF) and netIDEE\r\nSCIENCE project P 33775-N, as well as the FWF project I 4800-N (ADVISE)","doi":"10.4230/LIPICS.ITCS.2023.47","title":"Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks","year":"2023","day":"01","editor":[{"last_name":"Tauman Kalai","full_name":"Tauman Kalai, Yael","first_name":"Yael"}],"oa_version":"Published Version","fulldoi":"https://doi.org/10.4230/LIPICS.ITCS.2023.47","quality_controlled":"1","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959772631"]},"date_updated":"2026-07-24T12:48:29Z","volume":251,"article_processing_charge":"No","language":[{"iso":"eng"}],"external_id":{"arxiv":["2211.10151"]},"oa":1,"date_published":"2023-02-01T00:00:00Z","abstract":[{"lang":"eng","text":"Data dissemination is a fundamental task in distributed computing. This paper studies broadcast problems in various innovative models where the communication network connecting n processes is dynamic (e.g., due to mobility or failures) and controlled by an adversary. \r\nIn the first model, the processes transitively communicate their ids in synchronous rounds along a rooted tree given in each round by the adversary whose goal is to maximize the number of rounds until at least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2 lower bound and an O(nlog log n) upper bound. We show the first linear upper bound for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n.\r\nWe extend these results to the setting where the adversary gives in each round k-disjoint forests and their goal is to maximize the number of rounds until there is a set of k ids such that each process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem.\r\nFinally, we study the setting where the adversary gives in each round a directed graph with k roots and their goal is to maximize the number of rounds until there exist k ids that are known by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k upper bound for this problem.\r\nFor the two latter problems no upper or lower bounds were previously known."}],"intvolume":"       251","extern":"1","arxiv":1,"scopus_import":"1","has_accepted_license":"1","ddc":["000"],"status":"public","publication":"14th Innovations in Theoretical Computer Science Conference","publication_status":"published","file":[{"content_type":"application/pdf","file_name":"2023_LIPIcs_El-Hayek.pdf","creator":"cchlebak","access_level":"open_access","success":1,"file_size":1077427,"relation":"main_file","date_created":"2026-07-22T08:04:03Z","checksum":"d7f45fdcbc5fccd61db69f56d775c636","file_id":"22383","date_updated":"2026-07-22T08:04:03Z"}],"citation":{"apa":"El-Hayek, A., Henzinger, M., &#38; Schmid, S. (2023). Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. In Y. Tauman Kalai (Ed.), <i>14th Innovations in Theoretical Computer Science Conference</i> (Vol. 251). Cambridge, Massachusetts, USA: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">https://doi.org/10.4230/LIPICS.ITCS.2023.47</a>","short":"A. El-Hayek, M. Henzinger, S. Schmid, in:, Y. Tauman Kalai (Ed.), 14th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.","ieee":"A. El-Hayek, M. Henzinger, and S. Schmid, “Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks,” in <i>14th Innovations in Theoretical Computer Science Conference</i>, Cambridge, Massachusetts, USA, 2023, vol. 251.","mla":"El-Hayek, Antoine, et al. “Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks.” <i>14th Innovations in Theoretical Computer Science Conference</i>, edited by Yael Tauman Kalai, vol. 251, 47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">10.4230/LIPICS.ITCS.2023.47</a>.","ama":"El-Hayek A, Henzinger M, Schmid S. Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. In: Tauman Kalai Y, ed. <i>14th Innovations in Theoretical Computer Science Conference</i>. Vol 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">10.4230/LIPICS.ITCS.2023.47</a>","chicago":"El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Asymptotically Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks.” In <i>14th Innovations in Theoretical Computer Science Conference</i>, edited by Yael Tauman Kalai, Vol. 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. <a href=\"https://doi.org/10.4230/LIPICS.ITCS.2023.47\">https://doi.org/10.4230/LIPICS.ITCS.2023.47</a>.","ista":"El-Hayek A, Henzinger M, Schmid S. 2023. Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. 14th Innovations in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer Science, LIPIcs, vol. 251, 47."},"conference":{"name":"ITCS: Innovations in Theoretical Computer Science","start_date":"2023-01-10","location":"Cambridge, Massachusetts, USA","end_date":"2023-01-13"},"file_date_updated":"2026-07-22T08:04:03Z","author":[{"last_name":"El-Hayek","id":"888a098e-fcac-11ee-aff7-d347be57b725","orcid":"0000-0003-4268-7368","full_name":"El-Hayek, Antoine","first_name":"Antoine"},{"last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H"},{"last_name":"Schmid","first_name":"Stefan","orcid":"0000-0002-7798-1711","full_name":"Schmid, Stefan"}],"keyword":["broadcast","cover","k-broadcast","dynamic radius","dynamic graphs","oblivious message adversary","time complexity","Theory of computation → Distributed algorithms","Networks → Network algorithms"],"type":"conference","alternative_title":["LIPIcs"],"date_created":"2026-07-20T11:45:04Z","article_number":"47"},{"date_created":"2021-09-12T22:01:25Z","page":"1-13","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","first_name":"Krishnendu","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Doyen","first_name":"Laurent","full_name":"Doyen, Laurent"}],"type":"conference","keyword":["Computer science","Heuristic algorithms","Memory management","Automata","Markov processes","Probability distribution","Complexity theory"],"project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"publication_status":"published","conference":{"location":"Rome, Italy","end_date":"2021-07-02","name":"LICS: Logic in Computer Science","start_date":"2021-06-29"},"citation":{"ama":"Chatterjee K, Doyen L. Stochastic processes with expected stopping time. In: <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>. IEEE; 2021:1-13. doi:<a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">10.1109/LICS52264.2021.9470595</a>","mla":"Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected Stopping Time.” <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, IEEE, 2021, pp. 1–13, doi:<a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">10.1109/LICS52264.2021.9470595</a>.","chicago":"Chatterjee, Krishnendu, and Laurent Doyen. “Stochastic Processes with Expected Stopping Time.” In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, 1–13. IEEE, 2021. <a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">https://doi.org/10.1109/LICS52264.2021.9470595</a>.","ieee":"K. Chatterjee and L. Doyen, “Stochastic processes with expected stopping time,” in <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i>, Rome, Italy, 2021, pp. 1–13.","ista":"Chatterjee K, Doyen L. 2021. Stochastic processes with expected stopping time. Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, 1–13.","apa":"Chatterjee, K., &#38; Doyen, L. (2021). Stochastic processes with expected stopping time. In <i>Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science</i> (pp. 1–13). Rome, Italy: IEEE. <a href=\"https://doi.org/10.1109/LICS52264.2021.9470595\">https://doi.org/10.1109/LICS52264.2021.9470595</a>","short":"K. Chatterjee, L. Doyen, in:, Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2021, pp. 1–13."},"scopus_import":"1","publication":"Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science","status":"public","department":[{"_id":"KrCh"}],"date_published":"2021-07-07T00:00:00Z","abstract":[{"lang":"eng","text":"Markov chains are the de facto finite-state model for stochastic dynamical systems, and Markov decision processes (MDPs) extend Markov chains by incorporating non-deterministic behaviors. Given an MDP and rewards on states, a classical optimization criterion is the maximal expected total reward where the MDP stops after T steps, which can be computed by a simple dynamic programming algorithm. We consider a natural generalization of the problem where the stopping times can be chosen according to a probability distribution, such that the expected stopping time is T, to optimize the expected total reward. Quite surprisingly we establish inter-reducibility of the expected stopping-time problem for Markov chains with the Positivity problem (which is related to the well-known Skolem problem), for which establishing either decidability or undecidability would be a major breakthrough. Given the hardness of the exact problem, we consider the approximate version of the problem: we show that it can be solved in exponential time for Markov chains and in exponential space for MDPs."}],"article_processing_charge":"No","ec_funded":1,"external_id":{"isi":["000947350400036"],"arxiv":["2104.07278"]},"language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2104.07278"}],"arxiv":1,"quality_controlled":"1","publication_identifier":{"eisbn":["978-1-6654-4895-6"],"isbn":["978-1-6654-4896-3"],"issn":["1043-6871"]},"fulldoi":"https://doi.org/10.1109/LICS52264.2021.9470595","date_updated":"2026-08-12T06:39:27Z","oa_version":"Preprint","isi":1,"acknowledgement":"We are grateful to the anonymous reviewers of LICS 2021 and of a previous version of this paper for insightful comments that helped improving the presentation. This research was partially supported by the grant ERC CoG 863818 (ForM-SMArt).","_id":"10004","related_material":{"record":[{"id":"18630","relation":"later_version","status":"public"}]},"publisher":"IEEE","doi":"10.1109/LICS52264.2021.9470595","year":"2021","day":"07","title":"Stochastic processes with expected stopping time","month":"07","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00453-019-00630-4"}],"extern":"1","abstract":[{"lang":"eng","text":"We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm’s past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation ratio of (2+ε) and an amortized update time of O(logn/ε2). Our result can be generalized to give a fully dynamic O(f3)-approximate algorithm with O(f2) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices."}],"intvolume":"        82","date_published":"2020-04-01T00:00:00Z","oa":1,"language":[{"iso":"eng"}],"article_processing_charge":"No","publication":"Algorithmica","status":"public","scopus_import":"1","citation":{"ama":"Bhattacharya S, Chakrabarty D, Henzinger M. Deterministic dynamic matching in O(1) update time. <i>Algorithmica</i>. 2020;82(4):1057-1080. doi:<a href=\"https://doi.org/10.1007/s00453-019-00630-4\">10.1007/s00453-019-00630-4</a>","mla":"Bhattacharya, Sayan, et al. “Deterministic Dynamic Matching in O(1) Update Time.” <i>Algorithmica</i>, vol. 82, no. 4, Springer Nature, 2020, pp. 1057–80, doi:<a href=\"https://doi.org/10.1007/s00453-019-00630-4\">10.1007/s00453-019-00630-4</a>.","chicago":"Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika Henzinger. “Deterministic Dynamic Matching in O(1) Update Time.” <i>Algorithmica</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s00453-019-00630-4\">https://doi.org/10.1007/s00453-019-00630-4</a>.","ieee":"S. Bhattacharya, D. Chakrabarty, and M. Henzinger, “Deterministic dynamic matching in O(1) update time,” <i>Algorithmica</i>, vol. 82, no. 4. Springer Nature, pp. 1057–1080, 2020.","ista":"Bhattacharya S, Chakrabarty D, Henzinger M. 2020. Deterministic dynamic matching in O(1) update time. Algorithmica. 82(4), 1057–1080.","short":"S. Bhattacharya, D. Chakrabarty, M. Henzinger, Algorithmica 82 (2020) 1057–1080.","apa":"Bhattacharya, S., Chakrabarty, D., &#38; Henzinger, M. (2020). Deterministic dynamic matching in O(1) update time. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-019-00630-4\">https://doi.org/10.1007/s00453-019-00630-4</a>"},"publication_status":"published","page":"1057-1080","date_created":"2022-07-27T14:31:06Z","type":"journal_article","keyword":["Dynamic algorithms","Data structures","Graph algorithms","Matching","Vertex cover"],"author":[{"last_name":"Bhattacharya","first_name":"Sayan","full_name":"Bhattacharya, Sayan"},{"full_name":"Chakrabarty, Deeparnab","first_name":"Deeparnab","last_name":"Chakrabarty"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"issue":"4","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"04","article_type":"original","day":"01","year":"2020","title":"Deterministic dynamic matching in O(1) update time","doi":"10.1007/s00453-019-00630-4","_id":"11675","publisher":"Springer Nature","oa_version":"Published Version","volume":82,"date_updated":"2024-11-06T12:07:43Z","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"quality_controlled":"1","fulldoi":"https://doi.org/10.1007/s00453-019-00630-4"},{"oa_version":"Preprint","volume":77,"date_updated":"2024-11-06T12:07:55Z","quality_controlled":"1","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"fulldoi":"https://doi.org/10.1007/s00453-015-0066-y","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"01","article_type":"original","day":"01","year":"2017","title":"Maximizing a submodular function with viability constraints","doi":"10.1007/s00453-015-0066-y","_id":"11676","acknowledgement":"The research leading to these results has received funding from the European Research\r\nCouncil under the European Union’s Seventh Framework Programme (FP/2007-2013)/ERC Grant Agreement No. 340506.","publisher":"Springer Nature","citation":{"short":"W. Dvořák, M. Henzinger, D.P. Williamson, Algorithmica 77 (2017) 152–172.","apa":"Dvořák, W., Henzinger, M., &#38; Williamson, D. P. (2017). Maximizing a submodular function with viability constraints. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-015-0066-y\">https://doi.org/10.1007/s00453-015-0066-y</a>","ista":"Dvořák W, Henzinger M, Williamson DP. 2017. Maximizing a submodular function with viability constraints. Algorithmica. 77(1), 152–172.","chicago":"Dvořák, Wolfgang, Monika Henzinger, and David P. Williamson. “Maximizing a Submodular Function with Viability Constraints.” <i>Algorithmica</i>. Springer Nature, 2017. <a href=\"https://doi.org/10.1007/s00453-015-0066-y\">https://doi.org/10.1007/s00453-015-0066-y</a>.","mla":"Dvořák, Wolfgang, et al. “Maximizing a Submodular Function with Viability Constraints.” <i>Algorithmica</i>, vol. 77, no. 1, Springer Nature, 2017, pp. 152–72, doi:<a href=\"https://doi.org/10.1007/s00453-015-0066-y\">10.1007/s00453-015-0066-y</a>.","ama":"Dvořák W, Henzinger M, Williamson DP. Maximizing a submodular function with viability constraints. <i>Algorithmica</i>. 2017;77(1):152-172. doi:<a href=\"https://doi.org/10.1007/s00453-015-0066-y\">10.1007/s00453-015-0066-y</a>","ieee":"W. Dvořák, M. Henzinger, and D. P. Williamson, “Maximizing a submodular function with viability constraints,” <i>Algorithmica</i>, vol. 77, no. 1. Springer Nature, pp. 152–172, 2017."},"publication_status":"published","page":"152-172","date_created":"2022-07-27T14:37:24Z","keyword":["Approximation algorithms","Submodular functions","Phylogenetic diversity","Viability constraints"],"type":"journal_article","author":[{"last_name":"Dvořák","full_name":"Dvořák, Wolfgang","first_name":"Wolfgang"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530"},{"last_name":"Williamson","first_name":"David P.","full_name":"Williamson, David P."}],"issue":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1611.05753"}],"arxiv":1,"extern":"1","intvolume":"        77","abstract":[{"text":"We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant depth. The goal is to select a subset of k species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithms. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is (1−1e√). This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no (1−1/e+ϵ)-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting.","lang":"eng"}],"date_published":"2017-01-01T00:00:00Z","external_id":{"arxiv":["1611.05753"]},"language":[{"iso":"eng"}],"oa":1,"article_processing_charge":"No","status":"public","publication":"Algorithmica","scopus_import":"1"},{"fulldoi":"https://doi.org/10.1145/2818357","publication_identifier":{"issn":["2167-8375"],"eissn":["2167-8383"]},"quality_controlled":"1","date_updated":"2024-11-06T12:06:41Z","volume":4,"oa_version":"Submitted Version","publisher":"Association for Computing Machinery","_id":"11668","doi":"10.1145/2818357","title":"On multiple keyword sponsored search auctions with budgets","year":"2015","day":"05","article_type":"original","month":"12","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Colini-Baldeschi, Riccardo","first_name":"Riccardo","last_name":"Colini-Baldeschi"},{"first_name":"Stefano","full_name":"Leonardi, Stefano","last_name":"Leonardi"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"last_name":"Starnberger","first_name":"Martin","full_name":"Starnberger, Martin"}],"issue":"1","type":"journal_article","keyword":["Algorithms","Economics","Clinching ascending auction","auctions with budgets","Sponsored search auctions"],"date_created":"2022-07-27T11:54:56Z","article_number":"2","publication_status":"published","citation":{"ama":"Colini-Baldeschi R, Leonardi S, Henzinger M, Starnberger M. On multiple keyword sponsored search auctions with budgets. <i>ACM Transactions on Economics and Computation</i>. 2015;4(1). doi:<a href=\"https://doi.org/10.1145/2818357\">10.1145/2818357</a>","ieee":"R. Colini-Baldeschi, S. Leonardi, M. Henzinger, and M. Starnberger, “On multiple keyword sponsored search auctions with budgets,” <i>ACM Transactions on Economics and Computation</i>, vol. 4, no. 1. Association for Computing Machinery, 2015.","chicago":"Colini-Baldeschi, Riccardo, Stefano Leonardi, Monika Henzinger, and Martin Starnberger. “On Multiple Keyword Sponsored Search Auctions with Budgets.” <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery, 2015. <a href=\"https://doi.org/10.1145/2818357\">https://doi.org/10.1145/2818357</a>.","mla":"Colini-Baldeschi, Riccardo, et al. “On Multiple Keyword Sponsored Search Auctions with Budgets.” <i>ACM Transactions on Economics and Computation</i>, vol. 4, no. 1, 2, Association for Computing Machinery, 2015, doi:<a href=\"https://doi.org/10.1145/2818357\">10.1145/2818357</a>.","ista":"Colini-Baldeschi R, Leonardi S, Henzinger M, Starnberger M. 2015. On multiple keyword sponsored search auctions with budgets. ACM Transactions on Economics and Computation. 4(1), 2.","apa":"Colini-Baldeschi, R., Leonardi, S., Henzinger, M., &#38; Starnberger, M. (2015). On multiple keyword sponsored search auctions with budgets. <i>ACM Transactions on Economics and Computation</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/2818357\">https://doi.org/10.1145/2818357</a>","short":"R. Colini-Baldeschi, S. Leonardi, M. Henzinger, M. Starnberger, ACM Transactions on Economics and Computation 4 (2015)."},"scopus_import":"1","publication":"ACM Transactions on Economics and Computation","status":"public","article_processing_charge":"No","language":[{"iso":"eng"}],"oa":1,"date_published":"2015-12-05T00:00:00Z","intvolume":"         4","abstract":[{"lang":"eng","text":"We study multiple keyword sponsored search auctions with budgets. Each keyword has multiple ad slots with a click-through rate. The bidders have additive valuations, which are linear in the click-through rates, and budgets, which are restricting their overall payments. Additionally, the number of slots per keyword assigned to a bidder is bounded.\r\n\r\nWe show the following results: (1) We give the first mechanism for multiple keywords, where click-through rates differ among slots. Our mechanism is incentive compatible in expectation, individually rational in expectation, and Pareto optimal. (2) We study the combinatorial setting, where each bidder is only interested in a subset of the keywords. We give an incentive compatible, individually rational, Pareto-optimal, and deterministic mechanism for identical click-through rates. (3) We give an impossibility result for incentive compatible, individually rational, Pareto-optimal, and deterministic mechanisms for bidders with diminishing marginal valuations."}],"extern":"1","main_file_link":[{"url":"http://eprints.cs.univie.ac.at/3510/","open_access":"1"}]},{"volume":24,"date_updated":"2024-11-04T11:41:23Z","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"quality_controlled":"1","fulldoi":"https://doi.org/10.1007/pl00009268","oa_version":"None","year":"1999","day":"01","title":"Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology","related_material":{"record":[{"id":"11927","relation":"earlier_version","status":"public"}]},"publisher":"Springer Nature","_id":"11679","doi":"10.1007/pl00009268","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","month":"05","article_type":"original","date_created":"2022-07-27T15:02:28Z","page":"1-13","author":[{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"last_name":"King","first_name":"V.","full_name":"King, V."},{"first_name":"T.","full_name":"Warnow, T.","last_name":"Warnow"}],"keyword":["Algorithms","Data structures","Evolutionary biology","Theory of databases"],"type":"journal_article","citation":{"short":"M. Henzinger, V. King, T. Warnow, Algorithmica 24 (1999) 1–13.","apa":"Henzinger, M., King, V., &#38; Warnow, T. (1999). Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/pl00009268\">https://doi.org/10.1007/pl00009268</a>","mla":"Henzinger, Monika, et al. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” <i>Algorithmica</i>, vol. 24, Springer Nature, 1999, pp. 1–13, doi:<a href=\"https://doi.org/10.1007/pl00009268\">10.1007/pl00009268</a>.","chicago":"Henzinger, Monika, V. King, and T. Warnow. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” <i>Algorithmica</i>. Springer Nature, 1999. <a href=\"https://doi.org/10.1007/pl00009268\">https://doi.org/10.1007/pl00009268</a>.","ieee":"M. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology,” <i>Algorithmica</i>, vol. 24. Springer Nature, pp. 1–13, 1999.","ama":"Henzinger M, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. <i>Algorithmica</i>. 1999;24:1-13. doi:<a href=\"https://doi.org/10.1007/pl00009268\">10.1007/pl00009268</a>","ista":"Henzinger M, King V, Warnow T. 1999. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 24, 1–13."},"publication_status":"published","status":"public","publication":"Algorithmica","scopus_import":"1","extern":"1","date_published":"1999-05-01T00:00:00Z","abstract":[{"lang":"eng","text":"We are given a set T = {T 1 ,T 2 , . . .,T k } of rooted binary trees, each T i leaf-labeled by a subset L(Ti)⊂{1,2,...,n} . If T is a tree on {1,2, . . .,n }, we let T|L denote the minimal subtree of T induced by the nodes of L and all their ancestors. The consensus tree problem asks whether there exists a tree T * such that, for every i , T∗|L(Ti) is homeomorphic to T i .\r\n\r\nWe present algorithms which test if a given set of trees has a consensus tree and if so, construct one. The deterministic algorithm takes time min{O(N n 1/2 ), O(N+ n 2 log n )}, where N=∑i|Ti| , and uses linear space. The randomized algorithm takes time O(N log3 n) and uses linear space. The previous best for this problem was a 1981 O(Nn) algorithm by Aho et al. Our faster deterministic algorithm uses a new efficient algorithm for the following interesting dynamic graph problem: Given a graph G with n nodes and m edges and a sequence of b batches of one or more edge deletions, then, after each batch, either find a new component that has just been created or determine that there is no such component. For this problem, we have a simple algorithm with running time O(n 2 log n + b 0 min{n 2 , m log n }), where b 0 is the number of batches which do not result in a new component. For our particular application, b0≤1 . If all edges are deleted, then the best previously known deterministic algorithm requires time O(mn−−√) to solve this problem. We also present two applications of these consensus tree algorithms which solve other problems in computational evolutionary biology."}],"intvolume":"        24","article_processing_charge":"No","language":[{"iso":"eng"}]}]