---
OA_type: closed access
_id: '22812'
abstract:
- lang: eng
  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.
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.
article_number: '106663'
article_processing_charge: No
article_type: original
author:
- first_name: Niklas
  full_name: Hahn, Niklas
  id: 0a01c7b2-b823-11ed-9928-cc3f874f9ffd
  last_name: Hahn
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Zofia
  full_name: Stefankovic, Zofia
  last_name: Stefankovic
citation:
  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>
  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>
  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>.
  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.
  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.
  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>.
  short: N. Hahn, M. Henzinger, Z. Stefankovic, Information Processing Letters 195
    (2026).
das_tickbox: '1'
dataavailabilitystatement: No data was used for the research described in the article.
date_created: 2026-09-06T22:01:55Z
date_published: 2026-08-30T00:00:00Z
date_updated: 2026-09-09T11:55:47Z
day: '30'
department:
- _id: MoHe
doi: 10.1016/j.ipl.2026.106663
ec_funded: 1
fulldoi: https://doi.org/10.1016/j.ipl.2026.106663
intvolume: '       195'
keyword:
- Dynamic algorithms
- Graph algorithms
- Directed graphs
- Lower bounds
- Upper bounds
language:
- iso: eng
month: '08'
oa_version: None
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
publication: Information Processing Letters
publication_identifier:
  issn:
  - 0020-0190
publication_status: epub_ahead
publisher: Elsevier
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Tight bounds on the performance of dynamic directed cutset data structures
  based on OMv
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 195
year: '2026'
...
---
OA_place: publisher
_id: '17208'
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."
acknowledged_ssus:
- _id: ScienComp
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Raimel A
  full_name: Medina Ramos, Raimel A
  id: CE680B90-D85A-11E9-B684-C920E6697425
  last_name: Medina Ramos
  orcid: 0000-0002-5383-2869
citation:
  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>
  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.
  ista: Medina Ramos RA. 2024. Exploring the optimization landscape of variational
    quantum algorithms. Institute of Science and Technology Austria.
  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>.
  short: R.A. Medina Ramos, Exploring the Optimization Landscape of Variational Quantum
    Algorithms, Institute of Science and Technology Austria, 2024.
corr_author: '1'
date_created: 2024-07-09T09:14:24Z
date_published: 2024-07-09T00:00:00Z
date_updated: 2026-04-07T12:43:22Z
day: '09'
ddc:
- '539'
degree_awarded: PhD
department:
- _id: GradSch
- _id: MaSe
doi: 10.15479/at:ista:17208
ec_funded: 1
file:
- access_level: closed
  checksum: 6f45273d04f4418bc2adc018baed0525
  content_type: application/zip
  creator: rmedinar
  date_created: 2024-07-09T09:21:44Z
  date_updated: 2024-07-10T11:34:09Z
  file_id: '17212'
  file_name: Raimel_Thesis-Final.zip
  file_size: '14218691'
  relation: source_file
- access_level: open_access
  checksum: 6724a95bec772dbabc0111b9f08a805e
  content_type: application/pdf
  creator: rmedinar
  date_created: 2024-07-17T09:23:24Z
  date_updated: 2024-07-17T09:23:24Z
  file_id: '17275'
  file_name: Raimel_Thesis-20_pdfa.pdf
  file_size: 11253627
  relation: main_file
  success: 1
file_date_updated: 2024-07-17T09:23:24Z
fulldoi: https://doi.org/10.15479/at:ista:17208
has_accepted_license: '1'
keyword:
- Quantum computing
- Variational Quantum Algorithms
- Optimization
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '133'
project:
- _id: 23841C26-32DE-11EA-91FC-C7463DDC885E
  call_identifier: H2020
  grant_number: '850899'
  name: 'Non-Ergodic Quantum Matter: Universality, Dynamics and Control'
publication_identifier:
  issn:
  - 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
  record:
  - id: '10545'
    relation: part_of_dissertation
    status: public
  - id: '10067'
    relation: part_of_dissertation
    status: public
  - id: '17222'
    relation: part_of_dissertation
    status: public
  - id: '13125'
    relation: part_of_dissertation
    status: public
  - id: '11471'
    relation: part_of_dissertation
    status: public
status: public
supervisor:
- first_name: Maksym
  full_name: Serbyn, Maksym
  id: 47809E7E-F248-11E8-B48F-1D18A9856A87
  last_name: Serbyn
  orcid: 0000-0002-2399-5827
title: Exploring the optimization landscape of variational quantum algorithms
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2024'
...
---
_id: '22373'
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."
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)"
alternative_title:
- LIPIcs
article_number: '47'
article_processing_charge: No
arxiv: 1
author:
- first_name: Antoine
  full_name: El-Hayek, Antoine
  id: 888a098e-fcac-11ee-aff7-d347be57b725
  last_name: El-Hayek
  orcid: 0000-0003-4268-7368
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
  orcid: 0000-0002-7798-1711
citation:
  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>'
  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>'
  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>.
  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.
  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.'
  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>.
  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.
conference:
  end_date: 2023-01-13
  location: Cambridge, Massachusetts, USA
  name: 'ITCS: Innovations in Theoretical Computer Science'
  start_date: 2023-01-10
date_created: 2026-07-20T11:45:04Z
date_published: 2023-02-01T00:00:00Z
date_updated: 2026-07-24T12:48:29Z
day: '01'
ddc:
- '000'
doi: 10.4230/LIPICS.ITCS.2023.47
editor:
- first_name: Yael
  full_name: Tauman Kalai, Yael
  last_name: Tauman Kalai
extern: '1'
external_id:
  arxiv:
  - '2211.10151'
file:
- access_level: open_access
  checksum: d7f45fdcbc5fccd61db69f56d775c636
  content_type: application/pdf
  creator: cchlebak
  date_created: 2026-07-22T08:04:03Z
  date_updated: 2026-07-22T08:04:03Z
  file_id: '22383'
  file_name: 2023_LIPIcs_El-Hayek.pdf
  file_size: 1077427
  relation: main_file
  success: 1
file_date_updated: 2026-07-22T08:04:03Z
fulldoi: https://doi.org/10.4230/LIPICS.ITCS.2023.47
has_accepted_license: '1'
intvolume: '       251'
keyword:
- broadcast
- cover
- k-broadcast
- dynamic radius
- dynamic graphs
- oblivious message adversary
- time complexity
- Theory of computation → Distributed algorithms
- Networks → Network algorithms
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
publication: 14th Innovations in Theoretical Computer Science Conference
publication_identifier:
  isbn:
  - '9783959772631'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
  record:
  - id: '22281'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Asymptotically tight bounds on the time complexity of broadcast and its variants
  in dynamic networks
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 251
year: '2023'
...
---
_id: '10004'
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.'
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).
article_processing_charge: No
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Laurent
  full_name: Doyen, Laurent
  last_name: Doyen
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>'
  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>'
  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.'
  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>.
  short: K. Chatterjee, L. Doyen, in:, Proceedings of the 36th Annual ACM/IEEE Symposium
    on Logic in Computer Science, IEEE, 2021, pp. 1–13.
conference:
  end_date: 2021-07-02
  location: Rome, Italy
  name: 'LICS: Logic in Computer Science'
  start_date: 2021-06-29
date_created: 2021-09-12T22:01:25Z
date_published: 2021-07-07T00:00:00Z
date_updated: 2026-08-12T06:39:27Z
day: '07'
department:
- _id: KrCh
doi: 10.1109/LICS52264.2021.9470595
ec_funded: 1
external_id:
  arxiv:
  - '2104.07278'
  isi:
  - '000947350400036'
fulldoi: https://doi.org/10.1109/LICS52264.2021.9470595
isi: 1
keyword:
- Computer science
- Heuristic algorithms
- Memory management
- Automata
- Markov processes
- Probability distribution
- Complexity theory
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/2104.07278
month: '07'
oa: 1
oa_version: Preprint
page: 1-13
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer
  Science
publication_identifier:
  eisbn:
  - 978-1-6654-4895-6
  isbn:
  - 978-1-6654-4896-3
  issn:
  - 1043-6871
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
  record:
  - id: '18630'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Stochastic processes with expected stopping time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '11675'
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.'
article_processing_charge: No
article_type: original
author:
- first_name: Sayan
  full_name: Bhattacharya, Sayan
  last_name: Bhattacharya
- first_name: Deeparnab
  full_name: Chakrabarty, Deeparnab
  last_name: Chakrabarty
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
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>
  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>
  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.
  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>.
  short: S. Bhattacharya, D. Chakrabarty, M. Henzinger, Algorithmica 82 (2020) 1057–1080.
date_created: 2022-07-27T14:31:06Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2024-11-06T12:07:43Z
day: '01'
doi: 10.1007/s00453-019-00630-4
extern: '1'
fulldoi: https://doi.org/10.1007/s00453-019-00630-4
intvolume: '        82'
issue: '4'
keyword:
- Dynamic algorithms
- Data structures
- Graph algorithms
- Matching
- Vertex cover
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1007/s00453-019-00630-4
month: '04'
oa: 1
oa_version: Published Version
page: 1057-1080
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic dynamic matching in O(1) update time
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 82
year: '2020'
...
---
_id: '11676'
abstract:
- lang: eng
  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.
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."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Wolfgang
  full_name: Dvořák, Wolfgang
  last_name: Dvořák
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: David P.
  full_name: Williamson, David P.
  last_name: Williamson
citation:
  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>
  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>
  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>.
  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.
  ista: Dvořák W, Henzinger M, Williamson DP. 2017. Maximizing a submodular function
    with viability constraints. Algorithmica. 77(1), 152–172.
  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>.
  short: W. Dvořák, M. Henzinger, D.P. Williamson, Algorithmica 77 (2017) 152–172.
date_created: 2022-07-27T14:37:24Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2024-11-06T12:07:55Z
day: '01'
doi: 10.1007/s00453-015-0066-y
extern: '1'
external_id:
  arxiv:
  - '1611.05753'
fulldoi: https://doi.org/10.1007/s00453-015-0066-y
intvolume: '        77'
issue: '1'
keyword:
- Approximation algorithms
- Submodular functions
- Phylogenetic diversity
- Viability constraints
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1611.05753
month: '01'
oa: 1
oa_version: Preprint
page: 152-172
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Maximizing a submodular function with viability constraints
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 77
year: '2017'
...
---
_id: '11668'
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."
article_number: '2'
article_processing_charge: No
article_type: original
author:
- first_name: Riccardo
  full_name: Colini-Baldeschi, Riccardo
  last_name: Colini-Baldeschi
- first_name: Stefano
  full_name: Leonardi, Stefano
  last_name: Leonardi
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Martin
  full_name: Starnberger, Martin
  last_name: Starnberger
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>
  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>
  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>.
  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.
  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.
  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>.
  short: R. Colini-Baldeschi, S. Leonardi, M. Henzinger, M. Starnberger, ACM Transactions
    on Economics and Computation 4 (2015).
date_created: 2022-07-27T11:54:56Z
date_published: 2015-12-05T00:00:00Z
date_updated: 2024-11-06T12:06:41Z
day: '05'
doi: 10.1145/2818357
extern: '1'
fulldoi: https://doi.org/10.1145/2818357
intvolume: '         4'
issue: '1'
keyword:
- Algorithms
- Economics
- Clinching ascending auction
- auctions with budgets
- Sponsored search auctions
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://eprints.cs.univie.ac.at/3510/
month: '12'
oa: 1
oa_version: Submitted Version
publication: ACM Transactions on Economics and Computation
publication_identifier:
  eissn:
  - 2167-8383
  issn:
  - 2167-8375
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: On multiple keyword sponsored search auctions with budgets
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2015'
...
---
_id: '11679'
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."
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: V.
  full_name: King, V.
  last_name: King
- first_name: T.
  full_name: Warnow, T.
  last_name: Warnow
citation:
  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>
  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>
  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.
  ista: Henzinger M, King V, Warnow T. 1999. Constructing a tree from homeomorphic
    subtrees, with applications to computational evolutionary biology. Algorithmica.
    24, 1–13.
  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>.
  short: M. Henzinger, V. King, T. Warnow, Algorithmica 24 (1999) 1–13.
date_created: 2022-07-27T15:02:28Z
date_published: 1999-05-01T00:00:00Z
date_updated: 2024-11-04T11:41:23Z
day: '01'
doi: 10.1007/pl00009268
extern: '1'
fulldoi: https://doi.org/10.1007/pl00009268
intvolume: '        24'
keyword:
- Algorithms
- Data structures
- Evolutionary biology
- Theory of databases
language:
- iso: eng
month: '05'
oa_version: None
page: 1-13
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11927'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Constructing a tree from homeomorphic subtrees, with applications to computational
  evolutionary biology
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '1999'
...