## Piyush Srivastavaपीयूष श्रीवास्तव

In August 2014, I submitted my dissertation at UC Berkeley. Since September 2014, I am a postdoctoral scholar at the Center for the Mathematics of Information in the department of Computing and Mathematical Sciences at Caltech. I am broadly interested in randomized algorithms (and especially in connections between phase transitions and the computational complexity of counting and sampling problems). My research advisor at UC Berkeley was Alistair Sinclair.

Before coming to Berkeley, I did my undergraduate studies in computer science at IIT Kanpur.

Email: piyushsr (at) cs (dot) berkeley (dot) edu, piyushs (at) caltech (dot) edu.

### Papers

1. Alistair Sinclair, Piyush Srivastava, Daniel Štefankovič and Yitong Yin. Spatial mixing and the connective constant: Optimal bounds.
• Extended abstract in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015.
• [arXiv version]. The results of this paper subsume and unify the results of the preliminary paper below, and also add new results for the monomer-dimer model.
2. Alistair Sinclair, Piyush Srivastava, and Yitong Yin. Spatial mixing and approximation algorithms for graphs with bounded connective constant.
• Extended abstract in the proceedings of the IEEE Symposium on the Foundations of Computer Science (FOCS), 2013.
• [arXiv version].
3. Alistair Sinclair, Piyush Srivastava. Lee-Yang theorems and the complexity of computing averages.
• Extended abstract in the proceedings of the ACM Symposium on the Theory of Computing (STOC), 2013.
• [arXiv version].
• Comm. Math. Phys. 329 (3), pp. 827-858. August 2014.
4. Narendra M. Dixit, Piyush Srivastava and Nisheeth K. Vishnoi. A finite population model of molecular evolution
• J. Comp. Biol. 19 (10), pp. 1176-1202, October 2012.
5. Alistair Sinclair, Piyush Srivastava, and Marc Thurley. Approximation algorithms for two-state anti-ferromagnetic spin systems.
• Extended abstract in the proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012.
• [arXiv version].
• J. Stat. Phys. 155 (4), pp. 666-686. March 2014.

### 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. The Lee-Yang Theory of Phase Transitions. October 2013.
• An informal companion note for my talk at a workshop on Zeros of Polynomials and their Applications at IEEE FOCS, 2013 which includes a simplified description of Asano's proof of the Lee-Yang Theorem. Parts of the appendix to this note were also incorporated into a survey written by Nisheeth Vishnoi for the same workshop.
3. 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)}$$.

### Teaching

• CS170: Efficient Algorithms and Intractable Problems (Fall 2013, UC Berkeley). Instructor: Satish Rao.
• CS172: Computability and Complexity (Spring 2012, UC Berkeley). Instructor: Koushik Sen.