The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems

DOI10.1007/978-3-662-47672-7_19zbMath1441.68065OpenAlexW2112624678MaRDI QIDQ3448788

Andreas Björklund, Thore Husfeldt, Holger Dell

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-47672-7_19

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (4)

Counting induced subgraphs: an algebraic approach to \(\#\)W[1-hardness] ⋮ Parameterised and fine-grained subgraph counting, modulo 2 ⋮ Unnamed Item ⋮ Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.

Cites Work

• Unnamed Item
• NP is as easy as detecting unique solutions
• Matching is as easy as matrix inversion
• Isolating and odd number of elements and applications in complexity theory
• Parameterized random complexity
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• Parametrized complexity theory.
• Computing the permanent modulo a prime power
• PP is as Hard as the Polynomial-Time Hierarchy
• The Time Complexity of Constraint Satisfaction
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• On Problems as Hard as CNF-SAT
• Computational Complexity
• Finding Four-Node Subgraphs in Triangle Time
• Determinant Sums for Undirected Hamiltonicity

This page was built for publication: The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems