Parameterized random complexity
type: Item
instance of: scholarly article
title: Parameterized random complexity
zbMATH Open document ID: 1288.68082
author: J. Andres Montoya
author: Moritz Müller
published in: Theory of Computing Systems
publication date: 2013-04-15T00:00:00Z
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 6153886
zbMATH Keywords: parameterized complexity theory
zbMATH Keywords: random complexity
zbMATH Keywords: probability amplification
zbMATH Keywords: derandomization
zbMATH Keywords: parameterized counting complexity
zbMATH Keywords: uniqueness problems
MaRDI profile type: Publication
full work available at URL: s00224-011-9381-0
OpenAlex ID: W2008237210
cites work: Resolution Is Not Automatizable Unless W[P] Is Tractable
cites work: Color-coding
cites work: Computational Complexity
cites work: Q4427867
cites work: On the unique satisfiability problem
cites work: The Parallel Evaluation of Arithmetic Expressions Without Division
cites work: The Parallel Evaluation of General Arithmetic Expressions
cites work: Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
cites work: On the structure of parameterized problems in NP
cites work: The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
cites work: On computing Boolean connectives of characteristic functions
cites work: On unique satisfiability and the threshold behavior of randomized reductions
cites work: Randomness-optimal unique element isolation, with applications to perfect matching and related problems
cites work: Randomized Disposal of Unknowns and Implicitly Enforced Bounds on Parameters
cites work: Q2934608
cites work: Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
cites work: The parameterized complexity of maximality and minimality problems
cites work: An Isomorphism Between Subexponential and Parameterized Complexity Theory
cites work: Machine-based methods in parameterized complexity theory
cites work: Lower bounds for kernelizations and other preprocessing procedures
cites work: Time bounded random access machines
cites work: Q4503944
cites work: Parameterized circuit complexity and the \(W\) hierarchy
cites work: Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
cites work: Randomisation and Derandomisation in Descriptive Complexity Theory
cites work: Q4279511
cites work: Fixed-parameter tractability, definability, and model-checking
cites work: The Parameterized Complexity of Counting Problems
cites work: Model-Checking Problems as a Basis for Parameterized Intractability
cites work: Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
cites work: SAT-Problems and Reductions with Respect to the Number of Variables
cites work: Q2762493
cites work: Expander graphs and their applications
cites work: Q4798347
cites work: On generating all maximal independent sets
cites work: Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms
cites work: Pairwise Independence and Derandomization
cites work: Parameterized complexity of constraint satisfaction problems
cites work: The parameterized complexity of probability amplification
cites work: On the parameterized complexity of approximate counting
cites work: Randomized Approximations of Parameterized Counting Problems
cites work: Parameterized Derandomization
cites work: Small-Bias Probability Spaces: Efficient Constructions and Applications
cites work: Q4231923
cites work: Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
cites work: Entropy waves, the zig-zag graph product, and new constant-degree expanders
cites work: On Approximation Algorithms for # P
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: The Complexity of Enumeration and Reliability Problems
cites work: NP is as easy as detecting unique solutions
DOI: 10.1007/S00224-011-9381-0
description: scientific article; zbMATH DE number 6153886