Parameterized random complexity (Q1946497): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00224-011-9381-0
+Normal rank
@@ Property / OpenAlex ID @@
+W2008237210
@@ Property / OpenAlex ID: W2008237210 / rank @@
+Normal rank
@@ Property / cites work @@
+Resolution Is Not Automatizable Unless W[P] Is Tractable
+Normal rank
@@ Property / cites work @@
+Color-coding
@@ Property / cites work: Color-coding / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Q4427867
@@ Property / cites work: Q4427867 / rank @@
+Normal rank
@@ Property / cites work @@
+On the unique satisfiability problem
@@ Property / cites work: On the unique satisfiability problem / rank @@
+Normal rank
@@ Property / cites work @@
+The Parallel Evaluation of Arithmetic Expressions Without Division
+Normal rank
@@ Property / cites work @@
+The Parallel Evaluation of General Arithmetic Expressions
+Normal rank
@@ Property / cites work @@
+Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
+Normal rank
@@ Property / cites work @@
+On the structure of parameterized problems in NP
@@ Property / cites work: On the structure of parameterized problems in NP / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
+Normal rank
@@ Property / cites work @@
+On computing Boolean connectives of characteristic functions
+Normal rank
@@ Property / cites work @@
+On unique satisfiability and the threshold behavior of randomized reductions
+Normal rank
@@ Property / cites work @@
+Randomness-optimal unique element isolation, with applications to perfect matching and related problems
+Normal rank
@@ Property / cites work @@
+Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters
+Normal rank
@@ Property / cites work @@
+Q2934608
@@ Property / cites work: Q2934608 / rank @@
+Normal rank
@@ Property / cites work @@
+Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
+Normal rank
@@ Property / cites work @@
+The parameterized complexity of maximality and minimality problems
+Normal rank
@@ Property / cites work @@
+An Isomorphism Between Subexponential and Parameterized Complexity Theory
+Normal rank
@@ Property / cites work @@
+Machine-based methods in parameterized complexity theory
+Normal rank
@@ Property / cites work @@
+Lower bounds for kernelizations and other preprocessing procedures
+Normal rank
@@ Property / cites work @@
+Time bounded random access machines
@@ Property / cites work: Time bounded random access machines / rank @@
+Normal rank
@@ Property / cites work @@
+Q4503944
@@ Property / cites work: Q4503944 / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized circuit complexity and the \(W\) hierarchy
+Normal rank
@@ Property / cites work @@
+Q2843923
@@ Property / cites work: Q2843923 / rank @@
+Normal rank
@@ Property / cites work @@
+Randomisation and Derandomisation in Descriptive Complexity Theory
+Normal rank
@@ Property / cites work @@
+Q4279511
@@ Property / cites work: Q4279511 / rank @@
+Normal rank
@@ Property / cites work @@
+Fixed-Parameter Tractability, Definability, and Model-Checking
+Normal rank
@@ Property / cites work @@
+The Parameterized Complexity of Counting Problems
@@ Property / cites work: The Parameterized Complexity of Counting Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Model-Checking Problems as a Basis for Parameterized Intractability
+Normal rank
@@ Property / cites work @@
+Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+SAT-Problems and Reductions with Respect to the Number of  Variables
+Normal rank
@@ Property / cites work @@
+Q2762493
@@ Property / cites work: Q2762493 / rank @@
+Normal rank
@@ Property / cites work @@
+Expander graphs and their applications
@@ Property / cites work: Expander graphs and their applications / rank @@
+Normal rank
@@ Property / cites work @@
+Q4798347
@@ Property / cites work: Q4798347 / rank @@
+Normal rank
@@ Property / cites work @@
+On generating all maximal independent sets
@@ Property / cites work: On generating all maximal independent sets / rank @@
+Normal rank
@@ Property / cites work @@
+Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
+Normal rank
@@ Property / cites work @@
+Pairwise Independence and Derandomization
@@ Property / cites work: Pairwise Independence and Derandomization / rank @@
+Normal rank
@@ Property / cites work @@
+Parameterized complexity of constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+The parameterized complexity of probability amplification
+Normal rank
@@ Property / cites work @@
+On the parameterized complexity of approximate counting
+Normal rank
@@ Property / cites work @@
+Randomized Approximations of Parameterized Counting Problems
+Normal rank
@@ Property / cites work @@
+Parameterized Derandomization
@@ Property / cites work: Parameterized Derandomization / rank @@
+Normal rank
@@ Property / cites work @@
+Small-Bias Probability Spaces: Efficient Constructions and Applications
+Normal rank
@@ Property / cites work @@
+Q4231923
@@ Property / cites work: Q4231923 / rank @@
+Normal rank
@@ Property / cites work @@
+Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
+Normal rank
@@ Property / cites work @@
+Entropy waves, the zig-zag graph product, and new constant-degree expanders
+Normal rank
@@ Property / cites work @@
+On Approximation Algorithms for # P
@@ Property / cites work: On Approximation Algorithms for # P / rank @@
+Normal rank
@@ Property / cites work @@
+PP is as Hard as the Polynomial-Time Hierarchy
@@ Property / cites work: PP is as Hard as the Polynomial-Time Hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+The Complexity of Enumeration and Reliability Problems
+Normal rank
@@ Property / cites work @@
+NP is as easy as detecting unique solutions
@@ Property / cites work: NP is as easy as detecting unique solutions / rank @@
+Normal rank