Polynomial-Time Approximation of Zero-Free Partition Functions

• URL: http://arxiv.org/abs/2201.12772v1
• Date: Sun, 30 Jan 2022 09:54:45 GMT
• Title: Polynomial-Time Approximation of Zero-Free Partition Functions
• Authors: Penghui Yao, Yitong Yin, Xinyuan Zhang
• Abstract summary: We give an algorithm-time algorithm for estimating classical and quantum partition functions specified by local Hamiltonians. Our result is based on a new abstract framework that extends and generalizes the approach of Patel and Regts.
• Score: 9.153066211741356
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Zero-free based algorithm is a major technique for deterministic approximate counting. In Barvinok's original framework[Bar17], by calculating truncated Taylor expansions, a quasi-polynomial time algorithm was given for estimating zero-free partition functions. Patel and Regts[PR17] later gave a refinement of Barvinok's framework, which gave a polynomial-time algorithm for a class of zero-free graph polynomials that can be expressed as counting induced subgraphs in bounded-degree graphs. In this paper, we give a polynomial-time algorithm for estimating classical and quantum partition functions specified by local Hamiltonians with bounded maximum degree, assuming a zero-free property for the temperature. Consequently, when the inverse temperature is close enough to zero by a constant gap, we have polynomial-time approximation algorithm for all such partition functions. Our result is based on a new abstract framework that extends and generalizes the approach of Patel and Regts.

Related papers

• On Uniform Weighted Deep Polynomial approximation [0.0]
  We introduce and analyze a class of weighted deep approximants tailored for functions with asymmetric behavior-growing on one side and decaying on the other.<n>We show numerically that this framework outperforms Taylor, Chebyshev, and standard deep approximants, even when all use the same number of parameters.
  arXiv  Detail & Related papers  (2025-06-26T14:25:32Z)
• The Cost of Consistency: Submodular Maximization with Constant Recourse [30.724711970113777]
  In particular, we seek on the best-possible approximation ratio that is attainable when the algorithm is allowed to make at most a constant number of updates per step. We show a tight information-theoretic bound of $tfrac23$ for general submodular functions, and an improved (also tight) bound of $tfrac34$ for coverage functions.
  arXiv  Detail & Related papers  (2024-12-03T15:06:07Z)
• Private graphon estimation via sum-of-squares [10.00024942014117]
  We develop the first pure node-differentially private algorithms for learning block models and for graphon estimation with constant running time for any number of blocks. The statistical utility guarantees match those of the previous best information-theoretic (expon-time) node-private mechanisms for these problems.
  arXiv  Detail & Related papers  (2024-03-18T19:54:59Z)
• Approximate Integer Solution Counts over Linear Arithmetic Constraints [2.28438857884398]
  We propose a new framework to approximate the lattice counts inside a polytope with a new random-walk sampling method. Our algorithm could solve polytopes with dozens of dimensions, which significantly outperforms state-of-the-art counters.
  arXiv  Detail & Related papers  (2023-12-14T09:53:54Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• Complexity of Inexact Proximal Point Algorithm for minimizing convex functions with Holderian Growth [1.9643748953805935]
  We derive nonasymptotic complexity of exact and inexact PPA to minimize convex functions under $gamma-$Holderian growth. Our numerical tests show improvements over existing restarting versions of the Subgradient Method.
  arXiv  Detail & Related papers  (2021-08-10T07:15:07Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• A quantum version of Pollard's Rho of which Shor's Algorithm is a particular case [0.0]
  Pollard's Rho is a method for solving the integer factorization problem. We show that Pollard's Rho is a generalization of Shor's algorithm.
  arXiv  Detail & Related papers  (2020-11-10T19:11:37Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. Our algorithm learns the true halfspace within any accuracy $epsilon$.
  arXiv  Detail & Related papers  (2020-10-04T22:19:06Z)
• Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
  We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime. We show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. We prove that the Overlap Gap Property (OGP) holds in a significant part of the hard regime.
  arXiv  Detail & Related papers  (2020-06-18T17:18:02Z)
• Submodular Maximization in Clean Linear Time [42.51873363778082]
  We provide the first deterministic algorithm that achieves the tight $1-1/e$ approximation guarantee for submodularimation under a cardinality (size) constraint. We show that when the cardinality allowed for a solution is constant, no algorithm making a sub-linear number of function evaluations can guarantee any constant ratio. We extensively evaluate our algorithms on multiple real-life machine learning applications, including movie recommendation, location summarization, twitter text summarization and video summarization.
  arXiv  Detail & Related papers  (2020-06-16T17:06:45Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.