Regularity in hypergraphs is fine-grained equivalent to the general case for clique detection, enabling a complete classification of k-sparse Boolean CSP optimization complexity by constraint degree: linear for d≤1, clique-equivalent for d=2, and exhaustive-search for d≥3 under 3-uniform hyperclique
Schaefer , editor =
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
verdicts
UNVERDICTED 5roles
background 1polarities
background 1representative citing papers
Sparsity helps for k-independent set only below certain density thresholds, with new algorithms achieving O(min(n^{ωk/3} + m^{k/3}, n^k)) time and conditional lower bounds showing brute-force necessity above thresholds for many binary constraint families.
Gives an approximation algorithm for satisfiable instances of generalized linear equation CSPs over finite groups that is optimal for certain S, while the predicate remains approximation resistant on almost-satisfiable instances.
AutCSPs allow polynomial-time polymorphism verification and extend Schaefer's dichotomy to Boolean domains with tractability decision procedures for automatic polymorphisms on succinct automata representations.
Establishes no-PTAS hardness for interval-restricted assignment and approximation thresholds of 48/47 and 1.5 for 2- and 4-resource restricted scheduling.
citing papers explorer
-
The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
Regularity in hypergraphs is fine-grained equivalent to the general case for clique detection, enabling a complete classification of k-sparse Boolean CSP optimization complexity by constraint degree: linear for d≤1, clique-equivalent for d=2, and exhaustive-search for d≥3 under 3-uniform hyperclique
-
When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
Sparsity helps for k-independent set only below certain density thresholds, with new algorithms achieving O(min(n^{ωk/3} + m^{k/3}, n^k)) time and conditional lower bounds showing brute-force necessity above thresholds for many binary constraint families.
-
Optimal Inapproximability of Generalized Linear Equations over a Finite Group
Gives an approximation algorithm for satisfiable instances of generalized linear equation CSPs over finite groups that is optimal for certain S, while the predicate remains approximation resistant on almost-satisfiable instances.
-
Automatic constraint satisfaction problem
AutCSPs allow polynomial-time polymorphism verification and extend Schaefer's dichotomy to Boolean domains with tractability decision procedures for automatic polymorphisms on succinct automata representations.
-
Inapproximability Results for Scheduling with Interval and Resource Restrictions
Establishes no-PTAS hardness for interval-restricted assignment and approximation thresholds of 48/47 and 1.5 for 2- and 4-resource restricted scheduling.