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.17zbMATH Open1378.68054OpenAlexW2256089709MaRDI QIDQ5363756FDOQ5363756
Authors: Virginia Vassilevska Williams 
Publication date: 29 September 2017
Full work available at URL: https://doi.org/10.4230/LIPIcs.IPEC.2015.17
Recommendations
- scientific article; zbMATH DE number 1560343
- The complexity of constraint satisfaction problems (invited talk)
- An introduction to exponential time exact algorithms for solving NP-hard problems
- Towards hardness of approximation for polynomial time problems
- On the relative complexity of hard problems for complexity classes without complete problems
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Average-case hardness of NP from exponential worst-case hardness assumptions
shortest paths3SUMreductionssatisfiabilityequivalencesstrong exponential time hypothesisfine-grained complexity
Cited In (50)
- Tight conditional lower bounds for longest common increasing subsequence
- Tight conditional lower bounds for longest common increasing subsequence
- Fine-Grained Complexity of Regular Path Queries
- Multivariate analysis of orthogonal range searching and graph distances
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
- Rectilinear link diameter and radius in a rectilinear polygonal domain
- Fine-grained parameterized complexity analysis of graph coloring problems
- Enumeration of minimal tropical connected sets
- Fooling views: a new lower bound technique for distributed computations under congestion
- Worst-Case to Average-Case Reductions for Subclasses of P
- Title not available (Why is that?)
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- Title not available (Why is that?)
- Fine-grained complexity lower bounds for problems in computer aided verification
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- Simple doubly-efficient interactive proof systems for locally-characterizable sets
- Fine-grained parameterized complexity analysis of graph coloring problems
- Subsequences in bounded ranges: matching and analysis problems
- Lower bounds based on the exponential time hypothesis
- Two-dimensional pattern matching against local and regular-like picture languages
- Lengths of words accepted by nondeterministic finite automata
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
- A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
- More consequences of falsifying SETH and the orthogonal vectors conjecture
- Fast approximation of eccentricities and distances in hyperbolic graphs
- On problems equivalent to \((\min,+)\)-convolution
- The complexity of approximate pattern matching on de Bruijn graphs
- Proofs of Work from worst-case assumptions
- Sublinear-time reductions for big data computing
- Title not available (Why is that?)
- Combinatorial algorithms for subsequence matching: a survey
- Fine-Grained Complexity Theory (Tutorial)
- Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- Multivariate analysis of orthogonal range searching and graph distances
- What circuit classes can be learned with non-trivial savings?
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
- On the complexity of closest pair via polar-pair of point-sets
- On the complexity of closest pair via polar-pair of point-sets
- Structural parameterizations of clique coloring
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- On some fine-grained questions in algorithms and complexity
- Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
This page was built for publication: Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363756)
