Prasad Tetali Publications

Bio

Books

Recent Trends in Combinatorics, (Editors: A. Beveridge, J.R. Griggs, L. Hogben, G. Musiker and P. Tetali)

IMA Volumes in Mathematics and its Applications, Springer, 2016.

Mathematical Aspects of Mixing Times of Markov chains, (R. Montengro and P. Tetali)

Foundations and Trends in Theoretical Computer Science, NOW Publishers, 2006.

Recent Papers ( DBLP, Google Scholar)

2021

The Traveling Firefighter Problem, (with Majid Farhadi and Alejandro Toriello)

Math Arxiv, July 2021, Proc. of SIAM ACDA 2021.

Hardness and Approximation of Submodular Minimum Linear Ordering Problems, (with Majid Farhadi, Swati Gupta, Shengding Sun, Michael Wigal)

Math Arxiv, August 2021.

Improved approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover, (with Nikhil Bansal, Majid Farhadi, Jatin Batra)

Math Arxiv, July 2020; Proc. of ACM-SIAM SODA 2021.

2020

Toppleable Permutations, Excedances and Acyclic Orientations, (with Arvind Ayyer and Daniel Hathcock)

Math Arxiv, October 2020.

On the Bipartiteness Constant and Expansion of Cayley Graphs, (with Nina Moorman and Peter Ralli)

Math Arxiv, August 2020.

Improved approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover, (with Nikhil Bansal, Majid Farhadi, Jatin Batra)

Math Arxiv, July 2020; Proc. of ACM-SIAM SODA 2021 (to appear).

Markov Chain-based Sampling for Exploring RNA Secondary Structure under the Nearest Neighbor Thermodynamic Model,
(with Anna Kirkpatrick, Kalen Patton, Cassie Mitchell) Math. and Comput. Applns 2020, to appear.

On the Complexity of $\lambda_\infty$, Vertex Expansion, and Spread Constant of Trees, (with Majid Farhadi and Anand Louis)

Math Arxiv, March (revised July) 2020.

On the number of independent sets in uniform, regular, linear hypergraphs, (with Emma Cohen, Will Perkins and Michail Sarantis)

Math Arxiv, February 2020.

2019

Efficient sampling and counting algorithms for the Potts model on Z^d at all temperatures, (with C. Borgs, J. Chayes, T. Helmuth and W. Perkins)

Math Arxiv, September 2019. Conf. version in Proc. of ACM STOC 2020 (to appear).

Transport Proofs of Some Discrete Variants of the Prekopa-Leindler Inequality, (with N. Gozlan, C. Roberto, P-M. Samson)

Math Arxiv (May 2019); Annali della Scuola Normale Superiore di Pisa, Classe di Scienze, accepted (April 2020).

Volume Growth, Curvature, and Buser-type inequalities in graphs, (with B. Benson and P. Ralli)

Int'l Math. Res. Notices (IMRN) 2019, rnz305, https://doi.org/10.1093/imrn/rnz305

2018

Finding Cliques with Few Probes, (with U. Feige, D. Gamarnik, J. Neeman and M. Racz)

Math Arxiv, September 2018; Random Struct. Alg. (to appear).

2017

Algebraic connectivity under site percolation in finite weighted graphs, (with S. Bahmani and J. Romberg)

IEEE Trans. on Network Science and Engineering, PP(99), Sept. 2017.

Kantorovich Duality for General Transport Costs and Applications, (with N. Gozlan, C. Roberto and P-M. Samson)

J. Funct. Analysis, 273 (2017), no. 11, 3327-3405.

Characterization of a class of weak transport-entropy inequalities on the line, (with N. Gozlan, C. Roberto, P-M. Samson and Y. Shu)

Annales de l'Institut Henri Poincare (B) Probabilites et Statistiques, to appear.

Ricci curvature bounds for weakly interacting Markov chains, (with M. Erbar, C. Henderson, G. Menz)

Electron. J. Probab. 22 (2017), Paper no. 40, 23 pp.

Multidimensional bin packing and related problems: a survey, (with H. Christensen, A. Khan, S. Pokutta)

Computer Science Reviews, January (2017).

The game of survival: Sexual evolution in dynamic environments, (with R. Mehta, I. Panageas, G. Piliouras and V. Vazirani)

Proc. of the Innovations in Theor. Computer Sc. (ITCS), 2017.

On the Widom-Rowlinson occupancy fraction in regular graphs, (with E. Cohen and W. Perkins)

Combin. Probab. Computing, 26 (2017), 183--194.

The Widom-Rowlinson model, the Hard-core model and and the Extremality of the Compete graph, (with E. Cohen, P. Csikvari and W. Perkins)

Euro. J. Combinatorics, 62 (2017), 70-76.

Concentration Properties of Restricted Measures with Applications to Non-Lipschitz Functions, (with S. Bobkov and P. Nayar)

Geometric Aspects of Functional Analysis, Lecture Notes in Math. 2169 (2017), 25--53.

2016

Discrete curvature and abelian groups, (with B. Klartag, G. Kozma, and P. Ralli)

Canadian J. Math. 68 (2016), 655--674.

Decay of Correlations for the Hardcore Model on the d-regular Random Graph, (with N. Bhatnagar, A. Sly)

Electronic J. Probab. 21 (2016), 1--42.

Inverse Expander Mixing for Hypergraphs, (with E. Cohen, D. Mubayi, and P. Ralli)

Electronic J. Combinatorics, 23 (2016), 2--20.

Convergence to Global Equilibrium in Fokker-Planck Equations on a Graph and Talagrand-type Inequalities, (with R. Che, W. Huang, Y. Li)

J. Differential Equations, 261 (2016), 2552--2583.

2015

Discrete Curvature Bounds for Bernoulli-Laplace and Random Transposition Models, (with M. Erbar and J. Maas)

Annales Fac. Sci. Toulouse, 24 (2015), 691--716.

Approximate Tensorization of Entropy at High Temperature, (with P. Caputo, G. Menz)

Annales Fac. Sci. Toulouse, 24 (2015), 781--800.

Lattice Path Matroids: Negative Correlation and Fast Mixing, (with E. Cohen and D. Yelliussizov)

Preprint, June 2015.

2014

Displacement Convexity of Entropy and Related Inequalities on Graphs, (with N. Gozlan, C. Roberto, P-M. Samson)

Prob. Th. Rel. Fields (Online, August 2013), 160 (2014), 47--94.

Kruskal's Principle and Collision Time for Monotone Transitive Walks on the Integers, (with R. Montenegro)

Submitted, September 2014.

2013

Support-Theoretic Subgraph Preconditioners for Large-Scale SLAM, (with Y-D Jian, D.C. Balcan, I. Panageas, and F. Dellaert)

Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2013, November, Tokyo, Japan.

Phase Coexistence and Slow Mixing for the Hard-Core Model on $Z^2$, (with A. Blanca, D. Galvin, D. Randall)

RANDOM 2013; August 2013, Berkeley, CA.

Distributed Random Walks (with A. Das Sarma, D. Nangonkai, G. Pandurangan)

J. of ACM, 60(1): 2 (2013).

Counting Antichains and Linear Extensions in Generalizations of the Boolean Lattice (with T. Carroll and J. Cooper)

Preprint.

The distribution of second degrees in the Buckley-Osthus random graph model (with A. Kupavskii, L. Ostroumova, D. Shabanov)

Internet Mathematics 9 (2013), 297--335.

Combinatorial Approach to the Interpolation Method and Scaling Limits in Sparse Random Graphs (with M. Bayati and D. Gamarnik)

Annals of Probability 41(2013), 4080-4115. Conference version in Proc. of the ACM Symp. on Theory of Computing (STOC) 2010 (May) Boston, MA.

2012

Approximating (Sub/Supermodular) Minimum Linear Ordering Problems (with S. Iwata and P. Tripathi)

Proc. of APPROX 2012 (August), Cambridge-MIT, MA.

On Sharp Transitions in Making Squares (with E. Croot, A. Granville, and R. Pemantle)

Annals of Mathematics, 175 (2012), 1507-1550.

Mixing Times of Markov Chains on 3-Orientations of Planar Triangulations (with S. Miracle, A. Pascoe Streib, D. Randall)

Proc. of Analysis of Algorithms 2012 (Journal version in SIAM J. Discrete Math, accepted).

Stochastic Matching with Commitments (with K.P. Costello and P. Tripathi)

Proc. of ICALP 2012 (July), Durham, U.K.

Many Sparse Cuts via Higher Eigenvalues (with A. Louis, P. Raghavendra, and S. Vempala)

Journal version submitted. Proc. of Symp. on Theory of Computing (STOC) 2012 (May), New York, NY

Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets (with R. Restrepo, J. Shin, E. Vigoda, and L. Yang)

Probab. Th . Rel. Fields (online version : 24 March 2012); Proc. of IEEE Found. of Computer Science (FOCS) 2011 (October), Palm Springs, CA.

Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees (with J. Vera, E. Vigoda and L. Yang)

Ann. Appl. Probab. 22 (2012), 2210-2239. Conference version in Proc. of the ACM-SIAM Symp. on Discrete Algorithms (SODA) 2010 (January), Austin, TX.

Tight Bounds for Mixing of the Swendsen-Wang Algorithm at the Potts Transition Point (with C. Borgs and J. Chayes)

Probab. Th. Rel. Fields 152 (2012), 509-557. (online version, November 2010).

Entropy and Set Cardinality Inequalities for Partition-determined Functions and Application to Sumsets (with M. Madiman and A. Marcus)

Random Structures & Algorithms 40 (2012), 399-424.

2011

Meander Graphs (with C. Heitsch)

Proc. of Formal Power Series and Algebraic Combinatorics (FPSAC) 2011.

Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions (with A. Louis, P. Raghavendra, and S. Vempala)

Proc. of APPROX 2011 (August), Princeton, NJ.

Medium Access Using Queues (with D. Shah and J. Shin)

Proc. of IEEE Found. of Computer Science (FOCS) 2011 (October), Palm Springs, CA. Journal version submitted to Ann. Appl. Probab.

Reconstruction and Clustering in Random Constraint Satisfaction Problems (with A. Montanari and R. Restrepo)

special issue on CSPs and Message Passing: SIAM J. on Discrete Math. 25 (2011), 771-808.

The Finite-state Hardcore Model on a Regular Tree (with D. Galvin, F. Martinelli, and K. Ramanan)

special issue on CSPs and Message Passing: SIAM J. on Discrete Math. 25 (2011), 894-915.

2010

On Randomizing Two Derandomized Greedy Algorithms (with K. Costello and A. Shapira)

Journal of Combinatorics 1 (2010), 265-283. Conference version in ACM-SIAM Symp. on Discrete Algorithms (SODA) 2011 (January) 647-655, San Francisco, CA.

Reconstruction Threshold for the Hardcore Model (with N. Bhatnagar and A. Sly)

Proc. of RANDOM 2010 (September), Barcelona, Spain.

Improved Sublinear Bounds for Distributed Random Walks (with A. Satish Das Sarma, D. Nanongkai, and G. Pandurangan)

Proc. of the IEEE Principles of Distributed Computing (PODC) 2010 (July), Zurich, Switzerland.

Approximation Algorithms for the Isoperimetric and Spectral Profile of Graphs and for Restricted Eigenvalues of Diagonally-Dominant Matrices (with P. Raghavendra, and D. Steurer)

Proc. of Symp. on Theory of Computing (STOC) 2010 (May), Cambridge, MA.

G-Parking Functions, Acyclic Orientations and Spanning Trees (with B. Benson and D. Chakrabarty)

Discrete Math. 310 (2010), 1340-1353.

A Birthday Paradox for Markov Chains with an Optimal Bound for Collision in the Pollard's Rho for Discrete Logarithm (with J.H. Kim, R. Montenegro and Y. Peres)

Ann. Appl. Probab. 20 (2010), 495-521.

Information Inequalities for Joint Distributions, with Interpretations and Applications (with M. Madiman)

IEEE Trans. on Information Theory 56 (2010), 2699-2713.