The C-3PO Framework: Algorithms for # BIS-Hard Problems on Graphs with Low Threshold Rank or High Girth
cs.DS, cs.DM
Submitted: 2026-10-30
Updated: 2026-10-30
Terminology
Sources
- Algorithms for the ferromagnetic Potts model on expanders
- Efficient algorithms for the Potts model on small-set expanders
- Approximately counting independent sets in dense bipartite graphs via subspace enumeration
- #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region
- Fast algorithms at low temperatures via Markov chains
- Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region
- Pirogov--Sinai Theory Beyond Lattices
- Active Regression via Linear-Sample Sparsification
- An approximation trichotomy for Boolean #CSP
- Cluster expansion for abstract polymer models. New bounds from an old approach
- Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
- Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
- Algorithmic Pirogov-Sinai theory
- Algorithms for #BIS-hard problems on expander graphs
- Approximately counting independent sets in bipartite graphs via graph containers
- Spectral Algorithms for Unique Games
- Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
- On the hardness of sampling independent sets beyond the tree threshold
- Separations between # BIS and # IS
- The Hard-Core Model on Bipartite Spectral Expanders: Counting and Sampling at All Fugacities
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles