„Strong Exponential Time Hypothesis“

Suchergebnisse

19 Treffer

• Conditional Lower Bounds for String Matching in Labelled Graphs
  Equi, Massimo 2025 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• On the Optimality of Pseudo-polynomial Algorithms for Integer Programming
  Fomin, Fedor V. ; Panolan, Fahad ; Ramanujan, M. S. ; Saurabh, Saket 2018 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• On the Complexity of String Matching for Graphs
  Equi, Massimo ; Grossi, Roberto ; Mäkinen, Veli ; Tomescu, Alexandru I. 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Structural Parameterizations with Modulator Oblivion
  Jacob, Ashwin ; Panolan, Fahad ; Raman, Venkatesh ; Sahlot, Vibha 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
  Can Esmer, Barış ; Focke, Jacob ; Marx, Dániel ; Rzążewski, Paweł 2024 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Residue Domination in Bounded-Treewidth Graphs
  Greilhuber, Jakob ; Schepper, Philipp ; Wellnitz, Philip 2025 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• A Framework of Quantum Strong Exponential-Time Hypotheses
  Buhrman, Harry ; Patro, Subhasree ; Speelman, Florian 2021 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Structural Parameterizations of Clique Coloring
  Jaffke, Lars ; Lima, Paloma T. ; Philip, Geevarghese 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• On the Quantum Complexity of Closest Pair and Related Problems
  Aaronson, Scott ; Chia, Nai-Hui ; Lin, Han-Hsuan ; Wang, Chunhao ; Zhang, Ruizhe 2020 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth
  van Geffen, Bas A. M. ; Jansen, Bart M. P. ; de Kroon, Arnoud A. W. M. ; Morel, Rolf 2019 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds
  Abboud, Amir ; Rubinstein, Aviad 2018 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Tighter Hard Instances for PPSZ
  Pudlák, Pavel ; Scheder, Dominik ; Talebanfard, Navid 2017 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Conditional Lower Bounds for All-Pairs Max-Flow
  Krauthgamer, Robert ; Trabelsi, Ohad 2017 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Computing Graph Distances Parameterized by Treewidth and Diameter
  Husfeldt, Thore 2017 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Strong ETH Breaks With Merlin and Arthur: Short Non-Interactive Proofs of Batch Evaluation
  Williams, Richard Ryan 2016 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Strong ETH and Resolution via Games and the Multiplicity of Strategies
  Bonacina, Ilario ; Talebanfard, Navid 2015 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
  Vassilevska Williams, Virginia 2015 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Approximability of the Discrete Fréchet Distance
  Bringmann, Karl ; Mulzer, Wolfgang 2015 Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Counting Solutions to Polynomial Systems via Reductions
  Williams, R. Ryan 2018 Schloss Dagstuhl – Leibniz-Zentrum für Informatik