Parameterized random complexity
From MaRDI portal
Publication:1946497
DOI10.1007/s00224-011-9381-0zbMath1288.68082OpenAlexW2008237210MaRDI QIDQ1946497
Moritz Müller, Juan Andrés Montoya
Publication date: 15 April 2013
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-011-9381-0
derandomizationuniqueness problemsprobability amplificationparameterized complexity theoryparameterized counting complexityrandom complexity
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20)
Related Items
The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems, Unnamed Item, The challenges of unbounded treewidth in parameterised subgraph counting problems, Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for kernelizations and other preprocessing procedures
- Machine-based methods in parameterized complexity theory
- Parameterized complexity of constraint satisfaction problems
- The parameterized complexity of probability amplification
- NP is as easy as detecting unique solutions
- On generating all maximal independent sets
- Parameterized circuit complexity and the \(W\) hierarchy
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Time bounded random access machines
- On unique satisfiability and the threshold behavior of randomized reductions
- The parameterized complexity of maximality and minimality problems
- The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
- On the structure of parameterized problems in NP
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- Fixed-Parameter Tractability, Definability, and Model-Checking
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- On the unique satisfiability problem
- PP is as Hard as the Polynomial-Time Hierarchy
- Resolution Is Not Automatizable Unless W[P Is Tractable]
- Randomized Approximations of Parameterized Counting Problems
- Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters
- Parameterized Derandomization
- Expander graphs and their applications
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- Pairwise Independence and Derandomization
- Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
- On Approximation Algorithms for # P
- The Complexity of Enumeration and Reliability Problems
- Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
- SAT-Problems and Reductions with Respect to the Number of Variables
- Color-coding
- The Parallel Evaluation of General Arithmetic Expressions
- The Parameterized Complexity of Counting Problems
- On computing Boolean connectives of characteristic functions
- On the parameterized complexity of approximate counting
- Randomness-optimal unique element isolation, with applications to perfect matching and related problems
- Model-Checking Problems as a Basis for Parameterized Intractability
- Computational Complexity
- The Parallel Evaluation of Arithmetic Expressions Without Division
- Computational Complexity
- Randomisation and Derandomisation in Descriptive Complexity Theory
