Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
From MaRDI portal
Publication:5363756
DOI10.4230/LIPIcs.IPEC.2015.17zbMath1378.68054OpenAlexW2256089709MaRDI QIDQ5363756
Publication date: 29 September 2017
Full work available at URL: https://doi.org/10.4230/LIPIcs.IPEC.2015.17
shortest pathsreductionssatisfiabilityequivalences3SUMstrong exponential time hypothesisfine-grained complexity
Related Items (44)
Rectilinear link diameter and radius in a rectilinear polygonal domain ⋮ Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems ⋮ On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices ⋮ Structural parameterizations of clique coloring ⋮ What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ On the Complexity of Closest Pair via Polar-Pair of Point-Sets ⋮ Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness ⋮ The complexity of approximate pattern matching on de Bruijn graphs ⋮ A faster diameter problem algorithm for a chordal graph, with a connection to its center problem ⋮ Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False) ⋮ Proofs of Work from worst-case assumptions ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ Enumeration of minimal tropical connected sets ⋮ Unnamed Item ⋮ A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs ⋮ Unnamed Item ⋮ Fine-grained complexity lower bounds for problems in computer aided verification ⋮ Fine-Grained Complexity of Regular Path Queries ⋮ Unnamed Item ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Lengths of words accepted by nondeterministic finite automata ⋮ Unnamed Item ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ Unnamed Item ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ Tight conditional lower bounds for longest common increasing subsequence ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Two-dimensional pattern matching against local and regular-like picture languages ⋮ Unnamed Item ⋮ Sublinear-time reductions for big data computing ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming. ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ Multivariate analysis of orthogonal range searching and graph distances ⋮ On the Complexity of Closest Pair via Polar-Pair of Point-Sets ⋮ Toward Tight Approximation Bounds for Graph Diameter and Eccentricities ⋮ Fine-grained parameterized complexity analysis of graph coloring problems ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates
This page was built for publication: Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
