arXiv preprint ·
Separations between $\#\mathrm{BIS}$ and $\#\mathrm{IS}$
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give complexity-theoretic separations between $\#\mathrm{BIS}$ and $\#\mathrm{IS}$. Given a graph $G$, and a fugacity $λ>0$, the hard-core model is given by $Z_G(λ)=\sum_{I\in\mathcal I(G)}λ^{|I|}$, where $\mathcal I(G)$ denotes the independent sets of $G$. For $F\ge1$, an $F$-factor approximation to $Z_G(λ)$ is an estimate $\widehat Z$ satisfying $F^{-1}Z_G(λ)\le\widehat Z\le FZ_G(λ)$. Let $\mathcal G_Δ$ denote the class of $Δ$-regular graphs and $\mathcal G_{Δ,Δ}$ the class of $Δ$-regular bipartite graphs. We give two separation results. (1) There exist an integer $Δ\ge3$, a sufficiently large fugacity $λ$, and a constant $c>0$ so that the following hold: (a) For every $δ\in(0,1)$, deterministic $(1+δ)$-factor approximation on $\mathcal G_{Δ,Δ}$ is possible in time $\exp(cn)\operatorname{poly}(n,1/δ)$. (b) Under the Gap-Exponential Time Hypothesis, there exists no deterministic algorithm running in time $\exp(2cn)\operatorname{poly}(n)$ on $\mathcal G_Δ$ that gives an $\frac{11}{10}$-factor approximation. (2) For every fixed $Δ\ge3$ and $\varepsilon\in(0,1)$, for all sufficiently large fugacities $λ$, the following hold: (a) There exists an algorithm which outputs a deterministic $(1+\varepsilon)^n$-factor approximation to $Z_G(λ)$ on $\mathcal G_{Δ,Δ}$ in polynomial time. (b) Under the assumption $\mathrm P\ne\mathrm{NP}$, there exists no deterministic polynomial-time algorithm on $\mathcal G_Δ$ that gives a $(1+\varepsilon)^n$-factor approximation. Both our algorithmic results follow from a new spanning-tree encoding of independent sets that enables an efficient representation of large independent sets.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Quantum Query Complexity of Tournament Solutions
Ancilla-free randomized Toffoli gates and the T-count of Boolean oracles
Retrieval Sequencing in a Compact Storage System with Side Access
A Witnessing Duality for ReLU Network Depth
Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.