88 citations · 293 across the 27 of their papers we have counts for
4 papers · 1 filter
Correlation decay and partition function zeros: Algorithms and phase transitions
Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
We explore connections between the phenomenon of correlation decay and the location of Lee-Yang and Fisher zeros for various spin systems. In particular we show that, in many insta…
Lee-Yang theorems and the complexity of computing averages
Alistair Sinclair, Piyush Srivastava
We study the complexity of computing average quantities related to spin systems, such as the mean magnetization and susceptibility in the ferromagnetic Ising model, and the average…
Almost Settling the Hardness of Noncommutative Determinant
Steve Chien, Prahladh Harsha, Alistair Sinclair +1
In this paper, we study the complexity of computing the determinant of a matrix over a non-commutative algebra. In particular, we ask the question, "over which algebras, is the det…
On the Satisfiability Threshold and Clustering of Solutions of Random 3-SAT Formulas
Elitza Maneva, Alistair Sinclair
We study the structure of satisfying assignments of a random 3-SAT formula. In particular, we show that a random formula of density 4.453 or higher almost surely has no non-trivial…