Parameterized random complexity
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 1688350 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 503190 (Why is no real title available?)
- scientific article; zbMATH DE number 1979521 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 1885142 (Why is no real title available?)
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- Color-coding
- Computational Complexity
- Computational Complexity
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Expander graphs and their applications
- Fixed-parameter tractability, definability, and model-checking
- Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
- Improved algorithms for path, matching, and packing problems
- Lower bounds for kernelizations and other preprocessing procedures
- Machine-based methods in parameterized complexity theory
- Model-Checking Problems as a Basis for Parameterized Intractability
- NP is as easy as detecting unique solutions
- On Approximation Algorithms for # P
- On computing Boolean connectives of characteristic functions
- On generating all maximal independent sets
- On the parameterized complexity of approximate counting
- On the structure of parameterized problems in NP
- On the unique satisfiability problem
- On unique satisfiability and the threshold behavior of randomized reductions
- PP is as Hard as the Polynomial-Time Hierarchy
- Pairwise Independence and Derandomization
- Parameterized Derandomization
- Parameterized circuit complexity and the \(W\) hierarchy
- Parameterized complexity of constraint satisfaction problems
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Randomisation and derandomisation in descriptive complexity theory
- Randomized Approximations of Parameterized Counting Problems
- Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters
- Randomness-optimal unique element isolation, with applications to perfect matching and related problems
- Resolution Is Not Automatizable Unless W[P] Is Tractable
- SAT-Problems and Reductions with Respect to the Number of Variables
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
- The Complexity of Enumeration and Reliability Problems
- The Parallel Evaluation of Arithmetic Expressions Without Division
- The Parallel Evaluation of General Arithmetic Expressions
- The Parameterized Complexity of Counting Problems
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- The parameterized complexity of maximality and minimality problems
- The parameterized complexity of probability amplification
- Time bounded random access machines
Cited in
(10)- Parameterized Derandomization
- Randomized Approximations of Parameterized Counting Problems
- The parity of set systems under random restrictions with applications to exponential time problems
- The parameterized space complexity of model-checking bounded variable first-order logic
- Relativization and interactive proof systems in parameterized complexity theory
- Machine-based methods in parameterized complexity theory
- The randomized complexity of initial value problems
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- Parameterized analogues of probabilistic computation
- Probabilistic parameterized polynomial time
This page was built for publication: Parameterized random complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1946497)
