Parameterized random complexity

DOI10.1007/s00224-011-9381-0zbMath1288.68082MaRDI QIDQ1946497

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

zbMATH Keywords

derandomization; uniqueness problems; probability amplification; parameterized complexity theory; parameterized counting complexity; random complexity

Mathematics Subject Classification ID

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

68W20: Randomized algorithms

Related Items

Unnamed Item, Unnamed Item, The challenges of unbounded treewidth in parameterised subgraph counting problems, The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems

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