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.
Which problems have strongly exponential complexity? J
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
representative citing papers
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.
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
-
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.
-
Minimum Stable Cut and Treewidth
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.
-
Parallel Algorithms for Group Isomorphism via Code Equivalence
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.
-
Equilibria in Multiplayer Graph Games: An Algorithmic Study
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.