11 Search Results for "Guo, Heng"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.54
On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n,d/n)

Authors: Charilaos Efthymiou and Weiming Feng

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We study the single-site Glauber dynamics for the fugacity λ, Hard-Core model on the random graph G(n, d/n). We show that for the typical instances of the random graph G(n,d/n) and for fugacity λ < {d^d} / {(d-1)^(d+1)}, the mixing time of Glauber dynamics is n^{1 + O(1/log log n)}. Our result improves on the recent elegant algorithm in [Bezáková, Galanis, Goldberg and Štefankovič; ICALP'22]. The algorithm there is an MCMC-based sampling algorithm, but it is not the Glauber dynamics. Our algorithm here is simpler, as we use the classic Glauber dynamics. Furthermore, the bounds on mixing time we prove are smaller than those in Bezáková et al. paper, hence our algorithm is also faster. The main challenge in our proof is handling vertices with unbounded degrees. We provide stronger results with regard the spectral independence via branching values and show that the our Gibbs distributions satisfy the approximate tensorisation of the entropy. We conjecture that the bounds we have here are optimal for G(n,d/n). As corollary of our analysis for the Hard-Core model, we also get bounds on the mixing time of the Glauber dynamics for the Monomer-Dimer model on G(n,d/n). The bounds we get for this model are slightly better than those we have for the Hard-Core model
Cite as

Charilaos Efthymiou and Weiming Feng. On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n,d/n). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{efthymiou_et_al:LIPIcs.ICALP.2023.54,
  author =	{Efthymiou, Charilaos and Feng, Weiming},
  title =	{{On the Mixing Time of Glauber Dynamics for the Hard-Core and Related Models on G(n,d/n)}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{54:1--54:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.54},
  URN =		{urn:nbn:de:0030-drops-181064},
  doi =		{10.4230/LIPIcs.ICALP.2023.54},
  annote =	{Keywords: spin-system, spin-glass, sparse random (hyper)graph, approximate sampling, efficient algorithm}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.72
Parameter Estimation for Gibbs Distributions

Authors: David G. Harris and Vladimir Kolmogorov

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
A central problem in computational statistics is to convert a procedure for sampling combinatorial objects into a procedure for counting those objects, and vice versa. We will consider sampling problems which come from Gibbs distributions, which are families of probability distributions over a discrete space Ω with probability mass function of the form μ^Ω_β(ω) ∝ e^{β H(ω)} for β in an interval [β_min, β_max] and H(ω) ∈ {0} ∪ [1, n]. The partition function is the normalization factor Z(β) = ∑_{ω ∈ Ω} e^{β H(ω)}, and the log partition ratio is defined as q = (log Z(β_max))/Z(β_min) We develop a number of algorithms to estimate the counts c_x using roughly Õ(q/ε²) samples for general Gibbs distributions and Õ(n²/ε²) samples for integer-valued distributions (ignoring some second-order terms and parameters), We show this is optimal up to logarithmic factors. We illustrate with improved algorithms for counting connected subgraphs and perfect matchings in a graph.
Cite as

David G. Harris and Vladimir Kolmogorov. Parameter Estimation for Gibbs Distributions. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 72:1-72:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{harris_et_al:LIPIcs.ICALP.2023.72,
  author =	{Harris, David G. and Kolmogorov, Vladimir},
  title =	{{Parameter Estimation for Gibbs Distributions}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{72:1--72:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.72},
  URN =		{urn:nbn:de:0030-drops-181246},
  doi =		{10.4230/LIPIcs.ICALP.2023.72},
  annote =	{Keywords: Gibbs distribution, sampling}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.25
Improved Bounds for Randomly Colouring Simple Hypergraphs

Authors: Weiming Feng, Heng Guo, and Jiaheng Wang

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
We study the problem of sampling almost uniform proper q-colourings in k-uniform simple hypergraphs with maximum degree Δ. For any δ > 0, if k ≥ 20(1+δ)/δ and q ≥ 100Δ^({2+δ}/{k-4/δ-4}), the running time of our algorithm is Õ(poly(Δ k)⋅ n^1.01), where n is the number of vertices. Our result requires fewer colours than previous results for general hypergraphs (Jain, Pham, and Vuong, 2021; He, Sun, and Wu, 2021), and does not require Ω(log n) colours unlike the work of Frieze and Anastos (2017).
Cite as

Weiming Feng, Heng Guo, and Jiaheng Wang. Improved Bounds for Randomly Colouring Simple Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{feng_et_al:LIPIcs.APPROX/RANDOM.2022.25,
  author =	{Feng, Weiming and Guo, Heng and Wang, Jiaheng},
  title =	{{Improved Bounds for Randomly Colouring Simple Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.25},
  URN =		{urn:nbn:de:0030-drops-171477},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.25},
  annote =	{Keywords: Approximate counting, Markov chain, Mixing time, Hypergraph colouring}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.53
Counting Solutions to Random CNF Formulas

Authors: Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Kuan Yang

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We give the first efficient algorithm to approximately count the number of solutions in the random k-SAT model when the density of the formula scales exponentially with k. The best previous counting algorithm was due to Montanari and Shah and was based on the correlation decay method, which works up to densities (1+o_k(1))(2log k)/k, the Gibbs uniqueness threshold for the model. Instead, our algorithm harnesses a recent technique by Moitra to work for random formulas with much higher densities. The main challenge in our setting is to account for the presence of high-degree variables whose marginal distributions are hard to control and which cause significant correlations within the formula.
Cite as

Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Kuan Yang. Counting Solutions to Random CNF Formulas. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 53:1-53:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{galanis_et_al:LIPIcs.ICALP.2020.53,
  author =	{Galanis, Andreas and Goldberg, Leslie Ann and Guo, Heng and Yang, Kuan},
  title =	{{Counting Solutions to Random CNF Formulas}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{53:1--53:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.53},
  URN =		{urn:nbn:de:0030-drops-124603},
  doi =		{10.4230/LIPIcs.ICALP.2020.53},
  annote =	{Keywords: random CNF formulas, approximate counting}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.68
A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability

Authors: Heng Guo and Mark Jerrum

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that, in a undirected graph, assuming each edge fails independently, the remaining graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak (Random Struct. Algorithms, 2014), that the expected running time of the "cluster-popping" algorithm in bi-directed graphs is bounded by a polynomial in the size of the input.
Cite as

Heng Guo and Mark Jerrum. A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 68:1-68:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.ICALP.2018.68,
  author =	{Guo, Heng and Jerrum, Mark},
  title =	{{A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{68:1--68:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.68},
  URN =		{urn:nbn:de:0030-drops-90727},
  doi =		{10.4230/LIPIcs.ICALP.2018.68},
  annote =	{Keywords: Approximate counting, Network Reliability, Sampling, Markov chains}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.69
Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling

Authors: Heng Guo and Mark Jerrum

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We present a perfect simulation of the hard disks model via the partial rejection sampling method. Provided the density of disks is not too high, the method produces exact samples in O(log n) rounds, where n is the expected number of disks. The method extends easily to the hard spheres model in d>2 dimensions. In order to apply the partial rejection method to this continuous setting, we provide an alternative perspective of its correctness and run-time analysis that is valid for general state spaces.
Cite as

Heng Guo and Mark Jerrum. Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 69:1-69:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.ICALP.2018.69,
  author =	{Guo, Heng and Jerrum, Mark},
  title =	{{Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{69:1--69:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.69},
  URN =		{urn:nbn:de:0030-drops-90739},
  doi =		{10.4230/LIPIcs.ICALP.2018.69},
  annote =	{Keywords: Hard disks model, Sampling, Markov chains}
}
Document
DOI: 10.4230/DFU.Vol7.15301.159
On the Complexity of Holant Problems

Authors: Heng Guo and Pinyan Lu

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)

Abstract
In this article we survey recent developments on the complexity of Holant problems. We discuss three different aspects of Holant problems: the decision version, exact counting, and approximate counting.
Cite as

Heng Guo and Pinyan Lu. On the Complexity of Holant Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 159-177, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InCollection{guo_et_al:DFU.Vol7.15301.159,
  author =	{Guo, Heng and Lu, Pinyan},
  title =	{{On the Complexity of Holant Problems}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{159--177},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.159},
  URN =		{urn:nbn:de:0030-drops-69630},
  doi =		{10.4230/DFU.Vol7.15301.159},
  annote =	{Keywords: Computational complexity, Counting complexity, Dichotomy theorems, Approximate counting, Holant problems}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.31
Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems

Authors: Heng Guo and Pinyan Lu

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
For anti-ferromagnetic 2-spin systems, a beautiful connection has been established, namely that the following three notions align perfectly: the uniqueness in infinite regular trees, the decay of correlations (also known as spatial mixing), and the approximability of the partition function. The uniqueness condition implies spatial mixing, and an FPTAS for the partition function exists based on spatial mixing. On the other hand, non-uniqueness implies some long range correlation, based on which NP-hardness reductions are built. These connections for ferromagnetic 2-spin systems are much less clear, despite their similarities to anti-ferromagnetic systems. The celebrated Jerrum-Sinclair Markov chain [JS93] works even if spatial mixing or uniqueness fails. We provide some partial answers. We use (β,γ) to denote the (+,+) and (−,−) edge interactions and λ the external field, where βγ>1. If all fields satisfy λ<λ_c (assuming β≤γ), where λ_c=(γ/β)^{(Δ_c+1)/2} and Δ_c=(\sqrt{βγ}+1)/(\sqrt{βγ}−1), then a weaker version of spatial mixing holds in all trees. Moreover, if β≤1, then λ<λ_c is sufficient to guarantee strong spatial mixing and FPTAS. This improves the previous best algorithm, which is an FPRAS based on Markov chains and works for λ<γ/β [LLZ14a]. The bound λ_c is almost optimal. When β≤1, uniqueness holds in all infinite regular trees, if and only if λ≤λ^int_c, where λ^int_c=(γ/β)(⌈Δc⌉+1)/2. If we allow fields λ>λ^int′_c, where λ^int′_c=(γ/β)(⌊Δc⌋+2)/2, then approximating the partition function is #BIS-hard.
Cite as

Heng Guo and Pinyan Lu. Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 31:1-31:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.APPROX-RANDOM.2016.31,
  author =	{Guo, Heng and Lu, Pinyan},
  title =	{{Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{31:1--31:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.31},
  URN =		{urn:nbn:de:0030-drops-66547},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.31},
  annote =	{Keywords: Approximate counting; Ising model; Spin systems; Correlation decay}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.45
Approximation via Correlation Decay When Strong Spatial Mixing Fails

Authors: Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Stefankovic

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the computational phase transition that arises in the approximation of the partition function of anti-ferromagnetic two-spin models. Previous analyses of correlation-decay algorithms implicitly depended on the occurrence of strong spatial mixing. This, roughly, means that one uses worst-case analysis of the recursive procedure that creates the sub-instances. In this paper, we develop a new analysis method that is more refined than the worst-case analysis. We take the shape of instances in the computation tree into consideration and we amortise against certain "bad" instances that are created as the recursion proceeds. This enables us to show correlation decay and to obtain an FPTAS even when strong spatial mixing fails. We apply our technique to the problem of approximately counting independent sets in hypergraphs with degree upper-bound Delta and with a lower bound k on the arity of hyperedges. Liu and Lin gave an FPTAS for k >= 2 and Delta <= 5 (lack of strong spatial mixing was the obstacle preventing this algorithm from being generalised to Delta = 6). Our technique gives a tight result for Delta = 6, showing that there is an FPTAS for k >= 3 and Delta <= 6. The best previously-known approximation scheme for Delta = 6 is the Markov-chain simulation based FPRAS of Bordewich, Dyer and Karpinski, which only works for k >= 8. Our technique also applies for larger values of k, giving an FPTAS for k >= 1.66 Delta. This bound is not as strong as existing randomised results, for technical reasons that are discussed in the paper. Nevertheless, it gives the first deterministic approximation schemes in this regime. We further demonstrate that in the hypergraph independent set model, approximating the partition function is NP-hard even within the uniqueness regime.
Cite as

Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Stefankovic. Approximation via Correlation Decay When Strong Spatial Mixing Fails. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bezakova_et_al:LIPIcs.ICALP.2016.45,
  author =	{Bez\'{a}kov\'{a}, Ivona and Galanis, Andreas and Goldberg, Leslie Ann and Guo, Heng and Stefankovic, Daniel},
  title =	{{Approximation via Correlation Decay When Strong Spatial Mixing Fails}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{45:1--45:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.45},
  URN =		{urn:nbn:de:0030-drops-63257},
  doi =		{10.4230/LIPIcs.ICALP.2016.45},
  annote =	{Keywords: approximate counting, independent sets in hypergraphs, correlation decay}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.582
#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region

Authors: Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, and Eric Vigoda

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #SAT to approximate. We study #BIS in the general framework of two-state spin systems in bipartite graphs. Such a system is parameterized by three numbers (beta,gamma,lambda), where beta (respectively gamma) represents the weight of an edge (or "interaction strength") whose endpoints are of the same 0 (respectively 1) spin, and lambda is the weight of a 1 vertex, also known as an "external field". By convention, the edge weight with unequal 0/1 end points and the vertex weight with spin 0 are both normalized to 1. The partition function of the special case beta=1, gamma=0, and lambda=1 counts the number of independent sets. We define two notions, nearly-independent phase-correlated spins and symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any two-spin system on bipartite graphs supporting these two notions. As a consequence, we show that #BIS on graphs of degree at most 6 is as hard to approximate as #BIS~without degree bound. The degree bound 6 is the best possible as Weitz presented an FPTAS to count independent sets on graphs of maximum degree 5. This result extends to the hard-core model and to other anti-ferromagnetic two-spin models. In particular, for all antiferromagnetic two-spin systems, namely those satisfying beta*gamma<1, we prove that when the infinite (Delta-1)-ary tree lies in the non-uniqueness region then it is #BIS-hard to approximate the partition function on bipartite graphs of maximum degree Delta, except for the case beta=gamma and lambda=1. The exceptional case is precisely the antiferromagnetic Ising model without an external field, and we show that it has an FPRAS on bipartite graphs. Our inapproximability results match the approximability results of Li et al., who presented an FPTAS for general graphs of maximum degree Delta when the parameters lie in the uniqueness region.
Cite as

Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, and Eric Vigoda. #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 582-595, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{cai_et_al:LIPIcs.APPROX-RANDOM.2014.582,
  author =	{Cai, Jin-Yi and Galanis, Andreas and Goldberg, Leslie Ann and Guo, Heng and Jerrum, Mark and Stefankovic, Daniel and Vigoda, Eric},
  title =	{{#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{582--595},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.582},
  URN =		{urn:nbn:de:0030-drops-47235},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.582},
  annote =	{Keywords: Spin systems, approximate counting, complexity, #BIS-hardness, phase transition}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.249
The Complexity of Weighted Boolean #CSP Modulo k

Authors: Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k for any positive integer $k>1$. This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k.
Cite as

Heng Guo, Sangxia Huang, Pinyan Lu, and Mingji Xia. The Complexity of Weighted Boolean #CSP Modulo k. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 249-260, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{guo_et_al:LIPIcs.STACS.2011.249,
  author =	{Guo, Heng and Huang, Sangxia and Lu, Pinyan and Xia, Mingji},
  title =	{{The Complexity of Weighted Boolean #CSP Modulo k}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{249--260},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.249},
  URN =		{urn:nbn:de:0030-drops-30158},
  doi =		{10.4230/LIPIcs.STACS.2011.249},
  annote =	{Keywords: #CSP, dichotomy theorem, counting problems, computational complexity}
}
  • Refine by Author
  • 9 Guo, Heng
  • 3 Galanis, Andreas
  • 3 Goldberg, Leslie Ann
  • 3 Jerrum, Mark
  • 3 Lu, Pinyan
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Randomness, geometry and discrete structures
  • 2 Mathematics of computing → Discrete mathematics
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Applied computing → Physics
  • 1 Mathematics of computing → Probabilistic algorithms
  • Show More...

  • Refine by Keyword
  • 3 Approximate counting
  • 3 approximate counting
  • 2 Markov chains
  • 2 Sampling
  • 1 #BIS-hardness
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 2 2016
  • 2 2018
  • 2 2023
  • 1 2011
  • 1 2014
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact