Publication:5417690
From MaRDI portal
zbMath1288.68135MaRDI QIDQ5417690
Mihai Pǎtraşcu, R. Ryan Williams
Publication date: 22 May 2014
68Q25: Analysis of algorithms and problem complexity
03D15: Complexity of computation (including implicit computational complexity)
03B05: Classical propositional logic
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False), Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection, Hardness Results for Seeding Complex Contagion with Neighborhoods, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds, Efficient and Adaptive Parameterized Algorithms on Modular Decompositions, On Geometric Set Cover for Orthants, Counting Answers to Existential Questions, Fine-Grained Reductions and Quantum Speedups for Dynamic Programming., A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties, A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem, Algorithms and lower bounds for de morgan formulas of low-communication leaf gates, On Multidimensional and Monotone k-SUM, Exact Weight Subgraphs and the k-Sum Conjecture, Unnamed Item, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, A note on hardness of computing recursive teaching dimension, Interweaving real-time jobs with energy harvesting to maximize throughput, On the parameterized complexity of compact set packing, 3SUM, 3XOR, triangles, Separating OR, SUM, and XOR circuits, Efficiently approximating color-spanning balls, The relative exponential time complexity of approximate counting satisfying assignments, Towards NP-P via proof complexity and search, Solving the 2-disjoint connected subgraphs problem faster than \(2^n\), Scheduling partially ordered jobs faster than \(2^n\), Into the square: on the complexity of some quadratic-time solvable problems, Parameterized and subexponential-time complexity of satisfiability problems and applications, On the optimality of exact and approximation algorithms for scheduling problems, Problems on finite automata and the exponential time hypothesis, Hardness of RNA folding problem with four symbols, An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses, The fine-grained complexity of multi-dimensional ordering properties, CNF satisfiability in a subspace and related problems, Some aspects of the database resilience, Faster exponential-time algorithms in graphs of bounded average degree, Extending the kernel for planar Steiner tree to the number of Steiner vertices, Subquadratic algorithms for succinct stable matching, A note on the complexity of computing the number of reachable vertices in a digraph, Computing a Nonnegative Matrix Factorization---Provably, Parameterized Complexity and Subexponential-Time Computability, What’s Next? Future Directions in Parameterized Complexity, Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications, On the Equivalence among Problems of Bounded Width, Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams
