BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Piyush Srivastava

Piyush Srivastava appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Discrete MathematicsData Structures and AlgorithmsComputational Complexitycond-mat.stat-mechmath.PRPopulations and Evolutionmath-phmath.MPOther Computer Sciencephysics.soc-phQuantitative MethodsArtificial IntelligenceComputational GeometryMachine Learningmath.COMethodologyNeurons and Cognition

Catalog footprint

What is connected

13works
17topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

13 published item(s)

preprint2022arXiv

Correlation decay and partition function zeros: Algorithms and phase transitions

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 instances, proofs showing that weak spatial mixing on the Bethe lattice (infinite $Δ$-regular tree) implies strong spatial mixing on all graphs of maximum degree $Δ$ can be lifted to the complex plane, establishing the absence of zeros of the associated partition function in a complex neighborhood of the region in parameter space corresponding to strong spatial mixing. This allows us to give unified proofs of several recent results of this kind, including the resolution by Peters and Regts of the Sokal conjecture for the partition function of the hard core lattice gas. It also allows us to prove new results on the location of Lee-Yang zeros of the anti-ferromagnetic Ising model. We show further that our methods extend to the case when weak spatial mixing on the Bethe lattice is not known to be equivalent to strong spatial mixing on all graphs. In particular, we show that results on strong spatial mixing in the anti-ferromagnetic Potts model can be lifted to the complex plane to give new zero-freeness results for the associated partition function. This extension allows us to give the first deterministic FPTAS for counting the number of $q$-colorings of a graph of maximum degree $Δ$ provided only that $q\ge 2Δ$. This matches the natural bound for randomized algorithms obtained by a straightforward application of Markov chain Monte Carlo. We also give an improved version of this result for triangle-free graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the mixing time of coordinate Hit-and-Run

We obtain a polynomial upper bound on the mixing time $T_{CHR}(ε)$ of the coordinate Hit-and-Run random walk on an $n-$dimensional convex body, where $T_{CHR}(ε)$ is the number of steps needed in order to reach within $ε$ of the uniform distribution with respect to the total variation distance, starting from a warm start (i.e., a distribution which has a density with respect to the uniform distribution on the convex body that is bounded above by a constant). Our upper bound is polynomial in $n, R$ and $\frac{1}ε$, where we assume that the convex body contains the unit $\Vert\cdot\Vert_\infty$-unit ball $B_\infty$ and is contained in its $R$-dilation $R\cdot B_\infty$. Whether coordinate Hit-and-Run has a polynomial mixing time has been an open question.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Universal Lower Bound for Learning Causal DAGs with Atomic Interventions

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 a "Markov equivalence class" (MEC). The remaining undirected edges have to be oriented using interventions, which can be very expensive to perform in applications. Thus, the problem of minimizing the number of interventions needed to fully orient the MEC has received a lot of recent attention, and is also the focus of this work. Our first result is a new universal lower bound on the number of single-node interventions that any algorithm (whether active or passive) would need to perform in order to orient a given MEC. Our second result shows that this bound is, in fact, within a factor of two of the size of the smallest set of single-node interventions that can orient the MEC. Our lower bound is provably better than previously known lower bounds. Further, using simulations on synthetic graphs and by giving examples of special graph families, we show that our bound is often significantly better. To prove our lower bound, we develop the notion of clique-block shared-parents (CBSP) orderings, which are topological orderings of DAGs without v-structures and satisfy certain special properties. We also use the techniques developed here to extend our results to the setting of multi-node interventions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

City-Scale Agent-Based Simulators for the Study of Non-Pharmaceutical Interventions in the Context of the COVID-19 Epidemic

We highlight the usefulness of city-scale agent-based simulators in studying various non-pharmaceutical interventions to manage an evolving pandemic. We ground our studies in the context of the COVID-19 pandemic and demonstrate the power of the simulator via several exploratory case studies in two metropolises, Bengaluru and Mumbai. Such tools become common-place in any city administration's tool kit in our march towards digital health.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

COVID-19 Epidemic Study II: Phased Emergence From the Lockdown in Mumbai

The nation-wide lockdown starting 25 March 2020, aimed at suppressing the spread of the COVID-19 disease, was extended until 31 May 2020 in three subsequent orders by the Government of India. The extended lockdown has had significant social and economic consequences and `lockdown fatigue' has likely set in. Phased reopening began from 01 June 2020 onwards. Mumbai, one of the most crowded cities in the world, has witnessed both the largest number of cases and deaths among all the cities in India (41986 positive cases and 1368 deaths as of 02 June 2020). Many tough decisions are going to be made on re-opening in the next few days. In an earlier IISc-TIFR Report, we presented an agent-based city-scale simulator(ABCS) to model the progression and spread of the infection in large metropolises like Mumbai and Bengaluru. As discussed in IISc-TIFR Report 1, ABCS is a useful tool to model interactions of city residents at an individual level and to capture the impact of non-pharmaceutical interventions on the infection spread. In this report we focus on Mumbai. Using our simulator, we consider some plausible scenarios for phased emergence of Mumbai from the lockdown, 01 June 2020 onwards. These include phased and gradual opening of the industry, partial opening of public transportation (modelling of infection spread in suburban trains), impact of containment zones on controlling infections, and the role of compliance with respect to various intervention measures including use of masks, case isolation, home quarantine, etc. The main takeaway of our simulation results is that a phased opening of workplaces, say at a conservative attendance level of 20 to 33\%, is a good way to restart economic activity while ensuring that the city's medical care capacity remains adequate to handle the possible rise in the number of COVID-19 patients in June and July.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The PSPACE-hardness of understanding neural circuits

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 behavior governed by the neural circuit. A similar problem is to determine whether a given small set of neurons may be enough for the behavior to be displayed, even if all other neurons in the circuit are deactivated. Such a subset of neurons forms what is called a degenerate circuit for the behavior being studied. Recent advances in experimental techniques have provided researchers with tools to activate and deactivate subsets of neurons with a very high resolution, even in living animals. The data collected from such experiments may be of the following form: when a given subset of neurons is deactivated, is the behavior under study observed? This setting leads to the algorithmic question of determining the minimal vital or degenerate sets of neurons when one is given as input a description of the neural circuit. The algorithmic problem entails both figuring out which subsets of neurons should be perturbed (activated/deactivated), and then using the data from those perturbations to determine the minimal vital or degenerate sets. Given the large number of possible perturbations, and the recurrent nature of neural circuits, the possibility of a combinatorial explosion in such an approach has been recognized in the biology and the neuroscience literature. In this paper, we prove that the problems of finding minimal or minimum-size degenerate sets, and of finding the set of vital neurons, of a neural circuit given as input, are in fact PSPACE-hard. More importantly, we prove our hardness results by showing that a simpler problem, that of simulating such neural circuits, is itself PSPACE-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Fisher zeros and correlation decay in the Ising model

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 introduction by Fisher in 1965. While the zeros of the partition function as a polynomial in the "field" parameter have been extensively studied since the classical work of Lee and Yang, comparatively little is known about Fisher zeros for general graphs. Our main result shows that the zero-field Ising model has no Fisher zeros in a complex neighborhood of the entire region of parameters where the model exhibits correlation decay. In addition to shedding light on Fisher zeros themselves, this result also establishes a formal connection between two distinct notions of phase transition for the Ising model: the absence of complex zeros (analyticity of the free energy, or the logarithm of the partition function) and decay of correlations with distance. We also discuss the consequences of our result for efficient deterministic approximation of the partition function. Our proof relies heavily on algorithmic techniques, notably Weitz's self-avoiding walk tree, and as such belongs to a growing body of work that uses algorithmic methods to resolve classical questions in statistical physics.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Spatial mixing and approximation algorithms for graphs with bounded connective constant

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|), where lambda > 0 is the vertex activity. We show that there is an intimate connection between the connective constant of a graph and the phenomenon of strong spatial mixing (decay of correlations) for the hard core model; specifically, we prove that the hard core model with vertex activity lambda < lambda_c(Delta + 1) exhibits strong spatial mixing on any graph of connective constant Delta, irrespective of its maximum degree, and hence derive an FPTAS for the partition function of the hard core model on such graphs. Here lambda_c(d) := d^d/(d-1)^(d+1) is the critical activity for the uniqueness of the Gibbs measure of the hard core model on the infinite d-ary tree. As an application, we show that the partition function can be efficiently approximated with high probability on graphs drawn from the random graph model G(n,d/n) for all lambda < e/d, even though the maximum degree of such graphs is unbounded with high probability. We also improve upon Weitz's bounds for strong spatial mixing on bounded degree graphs (Weitz, 2006) by providing a computationally simple method which uses known estimates of the connective constant of a lattice to obtain bounds on the vertex activities lambda for which the hard core model on the lattice exhibits strong spatial mixing. Using this framework, we improve upon these bounds for several lattices including the Cartesian lattice in dimensions 3 and higher. Our techniques also allow us to relate the threshold for the uniqueness of the Gibbs measure on a general tree to its branching factor (Lyons, 1989).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Spatial mixing and the connective constant: Optimal bounds

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 evaluating the partition functions of the monomer-dimer model (which is defined as a weighted sum over all matchings where each matching is given a weight $γ^{|V| - 2 |M|}$ in terms of a fixed parameter gamma called the monomer activity) and the hard core model (which is defined as a weighted sum over all independent sets where an independent set I is given a weight $λ^{|I|}$ in terms of a fixed parameter lambda called the vertex activity). The connective constant is a natural measure of the average degree of a graph which has been studied extensively in combinatorics and mathematical physics, and can be bounded by a constant even for certain unbounded degree graphs such as those sampled from the sparse Erdős-Rényi model $G(n, d/n)$. Our main technical contribution is to prove the best possible rates of decay of correlations in the natural probability distributions induced by both the hard core model and the monomer-dimer model in graphs with a given bound on the connective constant. These results on decay of correlations are obtained using a new framework based on the so-called message approach that has been extensively used recently to prove such results for bounded degree graphs. We then use these optimal decay of correlations results to obtain FPTASs for the two problems on graphs of bounded connective constant. Our techniques also allow us to improve upon known bounds for decay of correlations for the hard core model on various regular lattices, including those obtained by Restrepo, Shin, Vigoda and Tetali (2011) for the special case of Z^2 using sophisticated numerically intensive methods tailored to that special case.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Lee-Yang theorems and the complexity of computing averages

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 dimer count (or average size of a matching) in the monomer-dimer model. By establishing connections between the complexity of computing these averages and the location of the complex zeros of the partition function, we show that these averages are #P-hard to compute. In case of the Ising model, our approach requires us to prove an extension of the famous Lee-Yang Theorem from the 1950s.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Finite Population Model of Molecular Evolution: Theory and Computation

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 attempt to understand such an evolutionary process. Their work has impacted antiviral treatment and vaccine design strategies. Yet, predictions of the quasispecies model are at best viewed as a guideline, primarily because it assumes an infinite population size, whereas realistic population sizes can be quite small. In this paper we consider a population genetics-based model aimed at understanding the evolution of such organisms with finite population sizes and present a rigorous study of the convergence and computational issues that arise therein. Our first result is structural and shows that, at any time during the evolution, as the population size tends to infinity, the distribution of genomes predicted by our model converges to that predicted by the quasispecies model. This justifies the continued use of the quasispecies model to derive guidelines for intervention. While the stationary state in the quasispecies model is readily obtained, due to the explosion of the state space in our model, exact computations are prohibitive. Our second set of results are computational in nature and address this issue. We derive conditions on the parameters of evolution under which our stochastic model mixes rapidly. Further, for a class of widely used fitness landscapes we give a fast deterministic algorithm which computes the stationary distribution of our model. These computational tools are expected to serve as a framework for the modeling of strategies for the deployment of mutagenic drugs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

In a seminal paper (Weitz, 2006), Weitz gave a deterministic fully polynomial approximation scheme for count- ing exponentially weighted independent sets (equivalently, approximating the partition function of the hard-core model from statistical physics) on graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the infinite d-regular tree. More recently Sly (Sly, 2010) showed that this is optimal in the sense that if there is an FPRAS for the hard-core partition function on graphs of maximum degree d for activities larger than the critical activity on the infinite d-regular tree then NP = RP. In this paper, we extend Weitz's approach to derive a deterministic fully polynomial approx- imation scheme for the partition function of the anti-ferromagnetic Ising model with arbitrary field on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing. This in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al (Restrepo et al, 2011) to the case of the anti-ferromagnetic Ising model with arbitrary field. By a standard correspondence, these results translate to arbitrary two-state anti-ferromagnetic spin systems with soft constraints.

0 citations0 reviewsNo code linkedOpen access