Home Research Teaching Contact

Research

Papers by topic

Click here for a chronological list.

Probability and algorithms

1. [Preprint] A unified law of robustness for Bregman divergence losses. [arXiv].
    with Santanu Das (first author) and Jatin Batra.

2. Sampling from convex sets with a cold start using multiscale decompositions. [arXiv]. [Preprint].
    with Hariharan Narayanan and Amit Rajaraman.

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

3. On the mixing time of coordinate Hit-and-Run. [arXiv].
    with Hariharan Narayanan.

   • Combinatorics, Probability and Computing. August 2021.

4. Online codes for analong signals. [arXiv].
    with Leonard J. Schulman.

   • IEEE Trans. Inf. Theory, 65 (10), pp. 6633–6649. May 2019.

Phase transitions and correlation decay

1. On complex roots of the independence polynomial. [arXiv].
    with Ferenc Bencs, Péter Csikvári, and Jan Vondrák.

   • In proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023.

2. Correlation decay and partition function zeros: Algorithms and phase transitions. [arXiv].
    with Jingcheng Liu and Alistair Sinclair.

   • SIAM J. Comput. (FOCS 2019 special issue).

   • Extended abstract in proceedings of the IEEE Symposium on the Foundations of Computer Science (FOCS), 2019.

3. Fisher zeros and correlation decay in the Ising model. [arXiv].
    with Jingcheng Liu and Alistair Sinclair.

   • J. Math. Phys., 20 (103304), 2019.

   • Extended abstract in proceedings of the Innovations in Theoretical Computer Science (ITCS) conference, 2019.

4. Computing the independence polynomial: from the tree threshold down to the roots. [arXiv].
    with Nicholas J. A. Harvey and Jan Vondrák.

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

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

   • Ann. Stat. 47 (4), pp. 1805–1834. May 2019.

6. The Ising Partition Function: Zeros and Deterministic Approximation. [arXiv].
    with Jingcheng Liu and Alistair Sinclair.

   • Journal of Statistical Physics. Online December 2018.

   • Extended abstract in proceedings of the IEEE Symposium on the Foundations of Computer Science (FOCS), 2017.

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

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

   • Extended abstract in proceedings of the IEEE Symposium on the Foundations of Computer Science (FOCS), 2013.

9. 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 proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012.

Causal inference

1. Universal lower bound for learning causal DAGs with atomic interventions. [arXiv].
    with Vibhor Porwal (first author) and Gaurav Sinha.

   • Extended abstract in proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), 2022 (oral presentation section).

   • Extended version (May 2022) of AISTATS 2022 paper which appeared in the proceedings under the title “Almost universal lower bound for learning causal DAGs with atomic interventions”.

2. Condition number bounds for causal inference.
    with Spencer Gordon, Vinayak Kumar, and Leonard J. Schulman.

   • In proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), 2021.

3. Stability of causal inference. [Conference version] (Erratum for conference version).
    with Leonard J. Schulman.

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

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

   • J. Comp. Biol. 19 (10), pp. 1176–1202. October 2012.

Advertisement: Working at STCS

If you are a student of computer science/mathematics/statistics or a related area and are interested in questions related to the above, you can contact me for possibilities of conducting research at TIFR.

Students who have already graduated with a B.Tech/M.Sc./M.Tech. degree may be eligible for temporary research fellowship (JRF/SRF) positions based on TIFR guidelines. Undergraduate students may also consider applying to the Visiting Students’ Research (VSRP) programme at TIFR.

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. July, 2014. [arXiv].

3. 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 K. Vishnoi for the same workshop.

4. Inferring graphical structures. 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)}\).

Acknowledgments Site generated by Hakyll