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

Alistair
Sinclair, Leonard
Schulman and Piyush Srivastava. Symbolic integration
and the complexity of computing averages.
 Extended abstract to appear in the proceedings of the
IEEE Symposium on Foundations of Computer Science (FOCS),
2015.

Alistair
Sinclair, Piyush Srivastava,
Daniel
Štefankovič
and Yitong Yin.
Spatial mixing and the connective constant: Optimal
bounds.
 Extended abstract in the proceedings of the ACMSIAM
Symposium on Discrete Algorithms (SODA), 2015.
 [arXiv
version]. The results of this paper subsume and
unify the results of the FOCS 2013 paper below, and also add
new results for the monomerdimer model.

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].

Alistair
Sinclair, Piyush Srivastava. LeeYang 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. 827858. August 2014.

Narendra
M. Dixit, Piyush Srivastava
and Nisheeth
K. Vishnoi. A finite population model of molecular
evolution
 J. Comp. Biol. 19 (10), pp. 11761202,
October 2012.

Alistair
Sinclair, Piyush Srivastava,
and Marc
Thurley. Approximation algorithms for twostate
antiferromagnetic spin systems.
 Extended abstract in the proceedings of the ACMSIAM
Symposium on Discrete Algorithms (SODA), 2012.
 [arXiv
version].
 J. Stat. Phys. 155 (4),
pp. 666686. March 2014.
Dissertation
Notes
 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.
 The LeeYang Theory of Phase
Transitions. October 2013.
 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)}\).
Older Manuscripts
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.