scientific article; zbMATH DE number 6297769

zbMath1288.68135MaRDI QIDQ5417690

Mihai Pǎtraşcu, R. Ryan Williams

Publication date: 22 May 2014

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Some aspects of the database resilience, Separating OR, SUM, and XOR circuits, Matching Triangles and Basing Hardness on an Extremely Popular Conjecture, On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection, Efficiently approximating color-spanning balls, Hardness Results for Seeding Complex Contagion with Neighborhoods, A note on the complexity of computing the number of reachable vertices in a digraph, On the optimality of exact and approximation algorithms for scheduling problems, On the Equivalence among Problems of Bounded Width, Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams, The relative exponential time complexity of approximate counting satisfying assignments, Parameterized Complexity and Subexponential-Time Computability, What’s Next? Future Directions in Parameterized Complexity, Problems on finite automata and the exponential time hypothesis, Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False), Exact Weight Subgraphs and the k-Sum Conjecture, Extending the kernel for planar Steiner tree to the number of Steiner vertices, Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications, Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle, Subquadratic algorithms for succinct stable matching, Unnamed Item, 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, Towards NP-P via proof complexity and search, Parameterized and subexponential-time complexity of satisfiability problems and applications, Unnamed Item, Unnamed Item, Unnamed Item, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Unnamed Item, Hardness of RNA folding problem with four symbols, Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds, Solving the 2-disjoint connected subgraphs problem faster than \(2^n\), Efficient and Adaptive Parameterized Algorithms on Modular Decompositions, Scheduling partially ordered jobs faster than \(2^n\), Unnamed Item, Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, Into the square: on the complexity of some quadratic-time solvable problems, On Geometric Set Cover for Orthants, An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses, Computing a Nonnegative Matrix Factorization---Provably, Unnamed Item, Unnamed Item, 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, Unnamed Item, On Multidimensional and Monotone k-SUM, The fine-grained complexity of multi-dimensional ordering properties, CNF satisfiability in a subspace and related problems, Faster exponential-time algorithms in graphs of bounded average degree, 3SUM, 3XOR, triangles