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 resultmore »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.« 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 allmore »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.« less
3. Deconstructing effective non-Hermitian dynamics in quadratic bosonic Hamiltonians

   https://doi.org/10.1088/1367-2630/ab9e87  

   Flynn, Vincent P. ; Cobanera, Emilio ; Viola, Lorenza ( August 2020 , New Journal of Physics)

   Unlike their fermionic counterparts, the dynamics of Hermitian quadratic bosonic Hamiltonians are governed by a generally non-Hermitian Bogoliubov-de Gennes effective Hamiltonian. This underlying non-Hermiticity gives rise to adynamically stableregime, whereby all observables undergo bounded evolution in time, and adynamically unstableone, whereby evolution is unbounded for at least some observables. We show that stability-to-instability transitions may be classified in terms of a suitablygeneralized$\mathcal{P}\mathcal{T}$symmetry, which can be broken when diagonalizability is lost at exceptional points in parameter space, but also when degenerate real eigenvalues split off the real axis while the system remains diagonalizable. By leveraging tools from Krein stability theory in indefinite inner-product spaces, we introduce an indicator of stability phase transitions, which naturally extends the notion of phase rigidity from non-Hermitian quantum mechanics to the bosonic setting. As a paradigmatic example, we fully characterize the stability phase diagram of a bosonic analogue to the Kitaev–Majorana chain under a wide class of boundary conditions. In particular, we establish a connection between phase-dependent transport properties and the onset of instability, and argue that stable regions in parameter space become of measure zero in the thermodynamic limit. Our analysis also reveals that boundary conditions that supportmore »Majorana zero modes in the fermionic Kitaev chain are precisely the same that support stability in the bosonic chain.

   « less
4. 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)

   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.
5. Finite-state parameter space maps for pruning partitions in modularity-based community detection

   https://doi.org/10.1038/s41598-022-20142-6  

   Gibson, Ryan A. ; Mucha, Peter J. ( September 2022 , Scientific Reports)

   Partitioning networks into communities of densely connected nodes is an important tool used widely across different applications, with numerous methods and software packages available for community detection. Modularity-based methods require parameters to be selected (or assume defaults) to control the resolution and, in multilayer networks, interlayer coupling. Meanwhile, most useful algorithms are heuristics yielding different near-optimal results upon repeated runs (even at the same parameters). To address these difficulties, we combine recent developments into a simple-to-use framework for pruning a set of partitions to a subset that are self-consistent by an equivalence with the objective function for inference of a degree-corrected planted partition stochastic block model (SBM). Importantly, this combined framework reduces some of the problems associated with the stochasticity that is inherent in the use of heuristics for optimizing modularity. In our examples, the pruning typically highlights only a small number of partitions that are fixed points of the corresponding map on the set of somewhere-optimal partitions in the parameter space. We also derive resolution parameter upper bounds for fitting a constrained SBM ofKblocks and demonstrate that these bounds hold in practice, further guiding parameter space regions to consider. With publicly available code (http://github.com/ragibson/ModularityPruning), our pruningmore »procedure provides a new baseline for using modularity-based community detection in practice.

   « less