Deciding circuit width w(f) ≤ k for degree-3 polynomials with no constant term is NP-complete, with 49/48-ε inapproximability, ETH lower bounds, and FPT algorithms.
Which problems have strongly exponential complexity? J
9 Pith papers cite this work. Polarity classification is still indexing.
9
Pith papers citing it
representative citing papers
Counting induced k-vertex subgraphs with automorphism group exactly Q is #W[1]-hard for every finite group Q, via clique-scaffold reductions from k-clique.
Establishes a tight double-exponential lower bound for high-multiplicity bin packing parameterized by number of distinct item types d, showing no |I|^{2^{o(d)}} algorithm exists unless ETH fails, via a novel 3-SAT reduction to an ILP with O(log n) variables.
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
The paper gives tight ETH-based lower bounds and matching algorithms for Minimum Stable Cut parameterized by treewidth and degree, plus an FPT approximation scheme for almost-stable cuts.
Strengthens the conditional running-time lower bound for Global Label Min-Cut under ETH to (np)^{o(log n / log log n)} via a deterministic reduction.
An O(4^{k + k log k} n + n m^2)-time algorithm for TREE CONTAINMENT parameterized by scanwidth k of a given tree-extension, with a matching ETH lower bound of no 2^{o(c log c)} n^{O(1)} algorithm for directed cutwidth c even on binary inputs.
AC³ isomorphism tests for coprime Abelian extensions and central-radical groups with elementary Abelian radical, plus an AC circuit bound for arbitrary central-radical groups.
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.
citing papers explorer
-
On the Complexity of the Circuit Width Problem
Deciding circuit width w(f) ≤ k for degree-3 polynomials with no constant term is NP-complete, with 49/48-ε inapproximability, ETH lower bounds, and FPT algorithms.
-
Counting Small Induced Subgraphs: Hardness of Symmetry-Based Properties
Counting induced k-vertex subgraphs with automorphism group exactly Q is #W[1]-hard for every finite group Q, via clique-scaffold reductions from k-clique.
-
A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
Establishes a tight double-exponential lower bound for high-multiplicity bin packing parameterized by number of distinct item types d, showing no |I|^{2^{o(d)}} algorithm exists unless ETH fails, via a novel 3-SAT reduction to an ILP with O(log n) variables.
-
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
-
A Stronger Conditional Running-Time Lower Bound for Global Label Min-Cut
Strengthens the conditional running-time lower bound for Global Label Min-Cut under ETH to (np)^{o(log n / log log n)} via a deterministic reduction.
-
Tree Containment Parameterized by Scanwidth
An O(4^{k + k log k} n + n m^2)-time algorithm for TREE CONTAINMENT parameterized by scanwidth k of a given tree-extension, with a matching ETH lower bound of no 2^{o(c log c)} n^{O(1)} algorithm for directed cutwidth c even on binary inputs.
-
Equilibria in Multiplayer Graph Games: An Algorithmic Study
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.