More Like this

1. The Complexity of Approximating the Matching Polynomial in the Complex Plane

   https://doi.org/10.1145/3448645  

   Bezáková, Ivona ; Galanis, Andreas ; Goldberg, Leslie Ann ; Štefankovič, Daniel ( June 2021 , ACM Transactions on Computation Theory)

   We study the problem of approximating the value of the matching polynomial on graphs with edge parameter γ, where γ takes arbitrary values in the complex plane. When γ is a positive real, Jerrum and Sinclair showed that the problem admits an FPRAS on general graphs. For general complex values of γ, Patel and Regts, building on methods developed by Barvinok, showed that the problem admits an FPTAS on graphs of maximum degree Δ as long as γ is not a negative real number less than or equal to −1/(4(Δ −1)). Our first main result completes the picture for the approximability of the matching polynomial on bounded degree graphs. We show that for all Δ ≥ 3 and all real γ less than −1/(4(Δ −1)), the problem of approximating the value of the matching polynomial on graphs of maximum degree Δ with edge parameter γ is #P-hard. We then explore whether the maximum degree parameter can be replaced by the connective constant. Sinclair et al. showed that for positive real γ, it is possible to approximate the value of the matching polynomial using a correlation decay algorithm on graphs with bounded connective constant (and potentially unbounded maximum degree). We first show that this result does not extend in general in the complex plane; in particular, the problem is #P-hard on graphs with bounded connective constant for a dense set of γ values on the negative real axis. Nevertheless, we show that the result does extend for any complex value γ that does not lie on the negative real axis. Our analysis accounts for complex values of γ using geodesic distances in the complex plane in the metric defined by an appropriate density function. 

   more » « less
2. Counting Independent Sets in Unbalanced Bipartite Graphs

   https://doi.org/10.1137/1.9781611975994.88  

   Cannon, Sarah ; Perkins, Will ( January 2020 , Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms)

   Chawla, Shuchi (Ed.)

   Understanding the complexity of approximately counting the number of weighted or unweighted independent sets in a bipartite graph (#BIS) is a central open problem in the field of approximate counting. Here we consider a subclass of this problem and give an FPTAS for approximating the partition function of the hard-core model for bipartite graphs when there is sufficient imbalance in the degrees or fugacities between the sides (L, R) of the bipartition. This includes, among others, the biregular case when λ = 1 (approximating the number of independent sets of G) and Delta_R >= 7 Delta_L log(Delta_L). Our approximation algorithm is based on truncating the cluster expansion of a polymer model partition function that expresses the hard-core partition function in terms of deviations from independent sets that are empty on one side of the bipartition. Further consequences of this method for unbalanced bipartite graphs include an efficient sampling algorithm for the hard-core model and zero-freeness results for the partition function with complex fugacities. By utilizing connections between the cluster expansion and joint cumulants of certain random variables, we go beyond previous algorithmic applications of the cluster expansion to prove that the hard-core model exhibits exponential decay of correlations for all graphs and fugacities satisfying our conditions. This illustrates the applicability of statistical mechanics tools to algorithmic problems and refines our understanding of the connections between different methods of approximate counting. 

   more » « less
3. Capacity-Achieving Polar-Based Codes With Sparsity Constraints on the Generator Matrices

   https://doi.org/10.1109/TCOMM.2023.3282603  

   Pang, James Chin-Jen ; Mahdavifar, Hessam ; Pradhan, S. Sandeep ( September 2023 , IEEE Transactions on Communications)

   In general, the generator matrix sparsity is a critical factor in determining the encoding complexity of a linear code. Further, certain applications, e.g., distributed crowdsourcing schemes utilizing linear codes, require most or even all the columns of the generator matrix to have some degree of sparsity. In this paper, we leverage polar codes and the well-established channel polarization to design capacity-achieving codes with a certain constraint on the weights of all the columns in the generator matrix (GM) while having a low-complexity decoding algorithm. We first show that given a binary-input memoryless symmetric (BMS) channel $W$ and a constant $s \in (0, 1]$ , there exists a polarization kernel such that the corresponding polar code is capacity-achieving with the rate of polarization $s/2$ , and the GM column weights being bounded from above by $N^{s}$ . To improve the sparsity versus error rate trade-off, we devise a column-splitting algorithm and two coding schemes for BEC and then for general BMS channels. The polar-based codes generated by the two schemes inherit several fundamental properties of polar codes with the original $2 \times 2$ kernel including the decay in error probability, decoding complexity, and the capacity-achieving property. Furthermore, they demonstrate the additional property that their GM column weights are bounded from above sublinearly in $N$ , while the original polar codes have some column weights that are linear in $N$ . In particular, for any BEC and $\beta < 0.5$ , the existence of a sequence of capacity-achieving polar-based codes where all the GM column weights are bounded from above by $N^{\lambda} $ with $\lambda \approx 0.585$ , and with the error probability bounded by ${\mathcal {O}}(2^{-N^{\beta }})$ under a decoder with complexity ${\mathcal {O}}(N\log N)$ , is shown. The existence of similar capacity-achieving polar-based codes with the same decoding complexity is shown for any BMS channel and $\beta < 0.5$ with $\lambda \approx 0.631$ . 

   more » « less
4. Correlation decay and the absence of zeros property of partition functions

   https://doi.org/10.1002/rsa.21083  

   Gamarnik, David ( March 2022 , Random Structures & Algorithms)

   Absence of (complex) zeros property is at the heart of the interpolation method developed by Barvinok for designing deterministic approximation algorithms for various graph counting and related problems. An earlier method used for the same problem is one based on the correlation decay property. Remarkably, the classes of graphs for which the two methods apply often coincide or nearly coincide. In this article we show that this is not a coincidence. We establish that if the interpolation method is valid for a family of graphs, then this family exhibits a form of the correlation decay property which is asymptotic strong spatial mixing at superlogarithmic distances. Our proof is based on a certain graph polynomial representation of the associated partition function. This representation is at the heart of the design of the polynomial time algorithms underlying the interpolation method itself. We conjecture that our result holds for all, and not just amenable graphs. Indeed this conjecture was recently confirmed by Regts. See the body of the article for details.

    

   more » « less
5. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems

   https://doi.org/10.1145/3357713.3384322  

   Harrow, Aram W. ; Mehraban, Saeed ; Soleimanifar, Mehdi ( June 2020 , STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing)

   null (Ed.)

   We present a quasi-polynomial time classical algorithm that estimates the partition function of quantum many-body systems at temperatures above the thermal phase transition point. It is known that in the worst case, the same problem is NP-hard below this point. Together with our work, this shows that the transition in the phase of a quantum system is also accompanied by a transition in the hardness of approximation. We also show that in a system of n particles above the phase transition point, the correlation between two observables whose distance is at least Ω(logn) decays exponentially. We can improve the factor of logn to a constant when the Hamiltonian has commuting terms or is on a 1D chain. The key to our results is a characterization of the phase transition and the critical behavior of the system in terms of the complex zeros of the partition function. Our work extends a seminal work of Dobrushin and Shlosman on the equivalence between the decay of correlations and the analyticity of the free energy in classical spin models. On the algorithmic side, our result extends the scope of a recent approach due to Barvinok for solving classical counting problems to quantum many-body systems. 

   more » « less