Prasad Tetali Email: <last name> @ math dot gatech.edu <last name> @ cc dot gatech dot edu Skiles 234 (Math) and Klaus 2132 (CS) Phone: +1 (404) 894 9238 Fax: +1 (404) 894-4409 |
Professor, Georgia Tech 686 Cherry St Atlanta, GA 30332-0160 U.S.A. |
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
Ricci curvature bounds for weakly interacting Markov chains, (with M. Erbar, C. Henderson, G. Menz)
Math Arxiv Preprint, February 2016. Electronic J. Probab. (under revision).
Multidimensional bin packing and related problems: a survey, (with H. Christensen, A. Khan, S. Pokutta)
Computer Science Reviews, to appear 2016.
Concentration Properties of Restricted Measures with Applications to Non-Lipschitz Functions, (with S. Bobkov and P. Nayar)
GAFA Seminar Notes, accepted (2016).
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.
On the Widom-Rowlinson occupancy fraction in regular graphs, (with E. Cohen and W. Perkins)
Combin. Probab. Computing, to appear (2016).
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, to appear (2016)
Kantorovich Duality for General Transport Costs and Applications, (with N. Gozlan, C. Roberto and P-M. Samson)
J. Funct. Analysis (under revision).
2015
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), accepted.
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.
Lattice Path Matroids: Negative Correlation and Fast Mixing, (with E. Cohen and D. Yelliussizov)
Preprint, June 2015.
2014
Discrete curvature and abelian groups, (with B. Klartag, G. Kozma, and P. Ralli)
Canadian J. Math. accepted.
Discrete Curvature Bounds for Bernoulli-Laplace and Random Transposition Models, (with M. Erbar and J. Maas)
Annales Fac. Sci. Toulouse, accepted.
Kruskal's Principle and Collision Time for Monotone Transitive Walks on the Integers, (with R. Montenegro)
Submitted, September 2014.
Inverse Expander Mixing for Hypergraphs, (with E. Cohen, D. Mubayi, and P. Ralli)
Electronic J. Combinatorics, accepted.
Approximate Tensorization of Entropy at High Temperature, (with P. Caputo, G. Menz)
Annales Fac. Sci. Toulouse, accepted.
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, accepted.
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.
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.
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.