37 citations · 121 across the 18 of their papers we have counts for
20 papers
Entropy Objectives in Markov Decision Processes
S. Akshay, Raghav Goyal, Aditya Neeraje +1
We consider the problem of synthesizing control policies that enforce a concentration property on the state distributions of a stochastic system. We present a formalization of this…
The Rate-Immediacy Barrier in Explicit Tree Code Constructions
Gil Cohen, Leonard J. Schulman, Piyush Srivastava
Since the introduction of tree codes by Schulman (STOC 1993), explicit construction of asymptotically good tree codes has remained a notorious challenge. A work by Cohen, Haeupler…
Deterministically approximating the volume of a Kostka polytope
Hariharan Narayanan, Piyush Srivastava
Polynomial-time deterministic approximation of volumes of polytopes, up to an approximation factor that grows at most sub-exponentially with the dimension, remains an open problem.…
Sampling from convex sets with a cold start using multiscale decompositions
Hariharan Narayanan, Amit Rajaraman, Piyush Srivastava
Running a random walk in a convex body is a standard approach to sample approximately uniformly from the body. The requirement is that from a suitable init…
On complex roots of the independence polynomial
Ferenc Bencs, Péter Csikvári, Piyush Srivastava +1
It is known from the work of Shearer (1985) (and also Scott and Sokal (2005)) that the independence polynomial of a graph of maximum degree at most does not vani…
Universal Lower Bound for Learning Causal DAGs with Atomic Interventions
Vibhor Porwal, Piyush Srivastava, Gaurav Sinha
A well-studied challenge that arises in the structure learning problem of causal directed acyclic graphs (DAG) is that using observational data, one can only learn the graph up to…
On the mixing time of coordinate Hit-and-Run
Hariharan Narayanan, Piyush Srivastava
We obtain a polynomial upper bound on the mixing time of the coordinate Hit-and-Run random walk on an dimensional convex body, where is the number of…
The PSPACE-hardness of understanding neural circuits
Vidya Sagar Sharma, Piyush Srivastava
In neuroscience, an important aspect of understanding the function of a neural circuit is to determine which, if any, of the neurons in the circuit are vital for the biological beh…
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…
Fisher zeros and correlation decay in the Ising model
Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
We study the complex zeros of the partition function of the Ising model, viewed as a polynomial in the "interaction parameter"; these are known as Fisher zeros in light of their in…
Online codes for analog signals
Leonard J. Schulman, Piyush Srivastava
This paper revisits a classical scenario in communication theory: a waveform sampled at regular intervals is to be encoded so as to minimize distortion in its reconstruction, despi…
The Ising Partition Function: Zeros and Deterministic Approximation
Jingcheng Liu, Alistair Sinclair, Piyush Srivastava
We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (a…
Exact recovery in the Ising blockmodel
Quentin Berthet, Philippe Rigollet, Piyush Srivastava
We consider the problem associated to recovering the block structure of an Ising model given independent observations on the binary hypercube. This new model, called the Ising bloc…
Computing the Independence Polynomial: from the Tree Threshold down to the Roots
Nicholas J. A. Harvey, Piyush Srivastava, Jan Vondrák
We study an algorithm for approximating the multivariate independence polynomial , with negative and complex arguments, an object that has strong connections to comb…
Spatial mixing and the connective constant: Optimal bounds
Alistair Sinclair, Piyush Srivastava, Daniel Štefankovič +1
We study the problem of deterministic approximate counting of matchings and independent sets in graphs of bounded connective constant. More generally, we consider the problem of ev…
A simplified proof of a Lee-Yang type theorem
Piyush Srivastava, Mario Szegedy
In this short note, we give a simple proof of a Lee-Yang type theorem which appeared in "Lee-Yang theorems and the complexity of computing averages" by Alistair Sinclair and Piyush…
Spatial mixing and approximation algorithms for graphs with bounded connective constant
Alistair Sinclair, Piyush Srivastava, Yitong Yin
The hard core model in statistical physics is a probability distribution on independent sets in a graph in which the weight of any independent set I is proportional to lambda^(|I|)…
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…
A Finite Population Model of Molecular Evolution: Theory and Computation
Narendra M. Dixit, Piyush Srivastava, Nisheeth K. Vishnoi
This paper is concerned with the evolution of haploid organisms that reproduce asexually. In a seminal piece of work, Eigen and coauthors proposed the quasispecies model in an atte…
Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
Alistair Sinclair, Piyush Srivastava, Marc Thurley
In a seminal paper (Weitz, 2006), Weitz gave a deterministic fully polynomial approximation scheme for count- ing exponentially weighted independent sets (equivalently, approximati…