---
_id: '11829'
abstract:
- lang: eng
  text: "In recent years it has become popular to study dynamic problems in a sensitivity
    setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity
    model only allows to apply batch updates of small size to the original input data.
    The sensitivity model is particularly appealing since recent strong conditional
    lower bounds ruled out fast algorithms for many dynamic problems, such as shortest
    paths, reachability, or subgraph connectivity.\r\n\r\nIn this paper we prove conditional
    lower bounds for these and additional problems in a sensitivity setting. For example,
    we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial
    algorithms cannot compute the (4/3-\\varepsilon)-approximate diameter of an undirected
    unweighted dense graph with truly subcubic preprocessing time and truly subquadratic
    update/query time. This result is surprising since in the static setting it is
    not clear whether a reduction from BMM to diameter is possible. We further show
    under the BMM conjecture that many problems, such as reachability or approximate
    shortest paths, cannot be solved faster than by recomputation from scratch even
    after only one or two edge insertions. We extend our reduction from BMM to Diameter
    to give a reduction from All Pairs Shortest Paths to Diameter under one deletion
    in weighted graphs. This is intriguing, as in the static setting it is a big open
    problem whether Diameter is as hard as APSP. We further get a nearly tight lower
    bound for shortest paths after two edge deletions based on the APSP conjecture.
    We give more lower bounds under the Strong Exponential Time Hypothesis. Many of
    our lower bounds also hold for static oracle data structures where no sensitivity
    is required.\r\n\r\nFinally, we give the first algorithm for the (1+\\varepsilon)-approximate
    radius, diameter, and eccentricity problems in directed or undirected unweighted
    graphs in case of single edges failures. The algorithm has a truly subcubic running
    time for graphs with a truly subquadratic number of edges; it is tight w.r.t.
    the conditional lower bounds we obtain."
alternative_title:
- LIPIcs
article_number: '26'
article_processing_charge: No
arxiv: 1
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: Andrea
  full_name: Lincoln, Andrea
  last_name: Lincoln
- first_name: Stefan
  full_name: Neumann, Stefan
  last_name: Neumann
- first_name: Virginia
  full_name: Vassilevska Williams, Virginia
  last_name: Vassilevska Williams
citation:
  ama: 'Henzinger MH, Lincoln A, Neumann S, Vassilevska Williams V. Conditional hardness
    for sensitivity problems. In: <i>8th Innovations in Theoretical Computer Science
    Conference</i>. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017.
    doi:<a href="https://doi.org/10.4230/LIPICS.ITCS.2017.26">10.4230/LIPICS.ITCS.2017.26</a>'
  apa: 'Henzinger, M. H., Lincoln, A., Neumann, S., &#38; Vassilevska Williams, V.
    (2017). Conditional hardness for sensitivity problems. In <i>8th Innovations in
    Theoretical Computer Science Conference</i> (Vol. 67). Berkley, CA, United States:
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPICS.ITCS.2017.26">https://doi.org/10.4230/LIPICS.ITCS.2017.26</a>'
  chicago: Henzinger, Monika H, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska
    Williams. “Conditional Hardness for Sensitivity Problems.” In <i>8th Innovations
    in Theoretical Computer Science Conference</i>, Vol. 67. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2017. <a href="https://doi.org/10.4230/LIPICS.ITCS.2017.26">https://doi.org/10.4230/LIPICS.ITCS.2017.26</a>.
  ieee: M. H. Henzinger, A. Lincoln, S. Neumann, and V. Vassilevska Williams, “Conditional
    hardness for sensitivity problems,” in <i>8th Innovations in Theoretical Computer
    Science Conference</i>, Berkley, CA, United States, 2017, vol. 67.
  ista: 'Henzinger MH, Lincoln A, Neumann S, Vassilevska Williams V. 2017. Conditional
    hardness for sensitivity problems. 8th Innovations in Theoretical Computer Science
    Conference. ITCS: Innovations in Theoretical Computer Science Conference, LIPIcs,
    vol. 67, 26.'
  mla: Henzinger, Monika H., et al. “Conditional Hardness for Sensitivity Problems.”
    <i>8th Innovations in Theoretical Computer Science Conference</i>, vol. 67, 26,
    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:<a href="https://doi.org/10.4230/LIPICS.ITCS.2017.26">10.4230/LIPICS.ITCS.2017.26</a>.
  short: M.H. Henzinger, A. Lincoln, S. Neumann, V. Vassilevska Williams, in:, 8th
    Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2017.
conference:
  end_date: 2017-01-11
  location: Berkley, CA, United States
  name: 'ITCS: Innovations in Theoretical Computer Science Conference'
  start_date: 2017-01-09
date_created: 2022-08-12T08:55:33Z
date_published: 2017-11-28T00:00:00Z
date_updated: 2023-02-16T11:49:15Z
day: '28'
doi: 10.4230/LIPICS.ITCS.2017.26
extern: '1'
external_id:
  arxiv:
  - '1703.01638'
intvolume: '        67'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.4230/LIPICS.ITCS.2017.26
month: '11'
oa: 1
oa_version: Published Version
publication: 8th Innovations in Theoretical Computer Science Conference
publication_identifier:
  isbn:
  - '9783959770293'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Conditional hardness for sensitivity problems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 67
year: '2017'
...