Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
From MaRDI portal
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
Cited in
(65)- Proofs of Work from worst-case assumptions
- Two-dimensional pattern matching against local and regular-like picture languages
- Fine-grained parameterized complexity analysis of graph coloring problems
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- The complexity of approximate pattern matching on de Bruijn graphs
- Lengths of words accepted by nondeterministic finite automata
- Fooling views: a new lower bound technique for distributed computations under congestion
- Tight conditional lower bounds for longest common increasing subsequence
- A faster diameter problem algorithm for a chordal graph, with a connection to its center problem
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On the complexity of closest pair via polar-pair of point-sets
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- On problems equivalent to \((\min,+)\)-convolution
- What circuit classes can be learned with non-trivial savings?
- Lower bounds based on the exponential time hypothesis
- Fast approximation of eccentricities and distances in hyperbolic graphs
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
- Simple doubly-efficient interactive proof systems for locally-characterizable sets
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- Multivariate analysis of orthogonal range searching and graph distances
- Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
- Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices
- scientific article; zbMATH DE number 7559420 (Why is no real title available?)
- A \#SAT algorithm for small constant-depth circuits with PTF gates
- Fine-Grained Complexity Theory (Tutorial)
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
- scientific article; zbMATH DE number 7561744 (Why is no real title available?)
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
- Worst-Case to Average-Case Reductions for Subclasses of P
- Tight conditional lower bounds for longest common increasing subsequence
- On the complexity of closest pair via polar-pair of point-sets
- On some fine-grained questions in algorithms and complexity
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- More consequences of falsifying SETH and the orthogonal vectors conjecture
- Fine-grained parameterized complexity analysis of graph coloring problems
- Recognizing picture languages by reductions to string languages
- Sublinear-time reductions for big data computing
- Enumeration of minimal tropical connected sets
- A Range Space with Constant VC Dimension for All-pairs Shortest Paths in Graphs
- Fine-grained complexity lower bounds for problems in computer aided verification
- Fine-Grained Complexity of Regular Path Queries
- Subsequences in bounded ranges: matching and analysis problems
- Combinatorial algorithms for subsequence matching: a survey
- Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
- Universally Wheeler languages
- On counting t-cliques mod 2
- Direct access for answers to conjunctive queries with aggregation
- Polynomial formulations as a barrier for reduction-based hardness proofs
- How packed is it, really?
- On exponential-time hypotheses, derandomization, and circuit lower bounds
- Algorithms and hardness for multidimensional range updates and queries
- Fine-grained complexity of regular path queries
- On connections between k-coloring and Euclidean k-means
- Can you link up with treewidth?
- Fine-grained equivalence for problems related to integer linear programming
- Towards free lunch derandomization from necessary assumptions (and OWFs)
- Can you link up with treewidth?
- QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more
- The four corners problem over larger alphabets
- Multivariate analysis of orthogonal range searching and graph distances
- Rectilinear link diameter and radius in a rectilinear polygonal domain
- Structural parameterizations of clique coloring
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)
