# Research

## Papers by topic

### Phase transitions and correlation decay

1. Exact recovery in the Ising blockmodel. [arXiv].
with Quentin Berthet and Philippe Rigollet.

• To appear in the Annals of Statistics.
2. The Ising Partition Function: Zeros and Deterministic Approximation. [arXiv].
with Jingcheng Liu and Alistair Sinclair.

• Extended abstract to appear in the proceedings of the IEEE Symposium on the Foundations of Computer Science (FOCS), 2017.
3. Spatial mixing and the connective constant: Optimal bounds. [arXiv].
with Alistair Sinclair, Daniel Štefankovič and Yitong Yin.

• Probability Theory & Related Fields. Online July 2016.

• Extended abstract in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.

• This paper subsumes the results of our FOCS 2013 paper listed below and also adds new results for the monomer-dimer model.

4. Spatial mixing and approximation algorithms for graphs with bounded connective constant. [arXiv].
with Alistair Sinclair and Yitong Yin.

• Extended abstract in the proceedings of the IEEE Symposium on the Foundations of Computer Science (FOCS), 2013.
5. Approximation algorithms for two-state anti-ferromagnetic spin systems. [arXiv].
with Alistair Sinclair and Marc Thurley.

• J. Stat. Phys. 155 (4), pp. 666–686. March 2014.

• Extended abstract in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012.

### Causal inference

1. Stability of causal inference. [Preprint].
with Leonard J. Schulman.

• Extended abstract in the proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), 2016.

• Recipient of the Best paper award.

### Counting complexity in statistical physics

1. Symbolic integration and the complexity of computing averages. [Preprint].
with Leonard J. Schulman and Alistair Sinclair.

• Extended abstract in the proceedings of the IEEE Symposium on the Foundations of Computer Science (FOCS), 2015.
2. Lee-Yang theorems and the complexity of computing averages. [arXiv].
with Alistair Sinclair.

• Comm. Math. Phys. 329 (3), pp. 827–858. August 2014.

• Extended abstract in the proceedings of the ACM Symposium on the Theory of Computing (STOC), 2013.

• See our FOCS 2015 paper for improved versions of the complexity theoretic results in this paper, and this note for a different proof of our extension of the Lee-Yang theorem.

### Mathematical models of evolution

1. Evolutionary dynamics in finite populations mix rapidly. [Preprint].
with Ioannis Panageas and Nisheeth K. Vishnoi.

• Extended abstract in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016.
2. A finite population model of molecular evolution.
with Narendra M. Dixit and Nisheeth K. Vishnoi.

## Notes

1. Approximating the hard core partition function with negative activities. April, 2015.
• This note shows that a simple modification of the analysis of Weitz’s algorithm for approximating the partition function of the hard core model can be used to show that the hard core model with negative activities also admits an FPTAS as long as all the vertex activities satisfy Shearer’s condition.
2. A simplified proof of a Lee-Yang type theorem, with Mario Szegedy. July, 2014. [arXiv].

3. The Lee-Yang theory of phase transitions. October, 2013.
4. Inferring graphical structures, with Di Wang. May, 2013.
• The main content of this note is the observation that the sample complexity of learning the hard core model on $$\mathcal{G}(n, d/n)$$ is $$n^{\Theta(1/\log\log n)}$$.