PUBLICATIONS

Tight Bounds for Mixing of the Swendsen-Wang Algorithm at the Potts Transition Point
C. Borgs, J. Chayes and P. Tetali

Submitted August, 2008.

Concentration on the Discrete Torus using Transportation
M. Sammer and P. Tetali

Submitted August, 2008.

Parking Functions and Acyclic Orientations on Graphs
Brian Benson and Prasad Tetali

Preprint, January 2008. available on MathArxiv.

A Birthday Paradox for Markov chains, with an optimal bound for collision
in the Pollard's Rho for Discrete Logarithm:
Jeong Han Kim, Ravi Montenegro, Yuval Peres, and Prasad Tetali

Algorithmic Number Theory Symposium (ANTS VIII)
Banff, Canada, May 2008, Springer Lecture Notes in CS, pp. 402-415.

Running Time Predictions for Factoring Algorithms
E. Croot, A. Granville, R. Pemantle, and Prasad Tetali

Algorithmic Number Theory Symposium (ANTS VIII)
Banff, Canada, May 2008, Springer Lecture Notes in CS, pp. 1-36.

A Note on Sumsets using Entropy:
Adam Marcus and Prasad Tetali

Revised April 2008.

The collision time of Pollard's Rho for the discrete logarithm:
Jeong Han Kim, Ravi Montenegro, and Prasad Tetali

FOCS 2007 version (IEEE Proc. of the Foundations of Computer Science (FOCS),
October 2007, Providence, RI, appeared.)

Information Inequalities for Joint Distributions, with Interpretations and Applications :
Mokshay Madiman and Prasad Tetali

IEEE Trans. on Info. Theory (May 2007), submitted pdf file

The Correlation Decay (CD) Tree and Strong Spatial Mixing in Multi-Spin Systems :
Chandra Nair and Prasad Tetali

Preprint pdf file (Under revision)

Simple Deterministic Approximation Algorithms for Counting Matchings :
M. Bayati, D. Gamarnik, D. Katz, C. Nair, and P. Tetali

ACM Symp. on Theory of Computing (STOC, San Diego, 2007, appeared);

journal version submitted pdf file

A Tight Bound for the Lamplighter Problem :
Murali Ganapathy and Prasad Tetali

Submitted pdf file (Under revision)

Sandwich Bounds for Joint Entropy :
Mokshay Madiman and Prasad Tetali

IEEE Symp. on Info. Theory (Nice, France 2007), appeared pdf file

Sharp Transitions in Making Squares:
Ernie Croot, Andrew Granville, and Prasad Tetali

Under Revision pdf file

Already Published (some links under construction...)

Analysis of Top-Swap Shuffling for Genome Rearrangements :
N. Bhatnagar, P. Caputo, P. Tetali, and E. Vigoda

Ann. Appl. Probab. 17(4):1424-1445, 2007; 01_07_version : also available at math.PR/0609171

Mathematical Aspects of Mixing Times in Markov Chains:
Ravi Montenegro and Prasad Tetali

Foundations & Trends in Theoretical Computer Science, (2006)
Now Publishers pdf file (120 pages, 04/18/06)

Mixing Time Bounds via the Spectral Profile:
Sharad Goel, Ravi Montenegro, and Prasad Tetali

Electronic J. Probab. 11 (2006), 1-26. pdf file

On the trade-off between rate and performance of expander codes on AWGN channels:
Souvik Dihidar, Steve W. MacLaughlin and Prasad Tetali

IEEE Symp. On Info. Theory June 27-July 2(Chicago, 2004) word document

On smoothed analysis of dense graphs and formulas:
Michael Krivelevich, Benny Sudakov and Prasad Tetali

Random Struct. & Alg. (to appear) pdf file

Modified Log-Sobolev Inequalities in Discrete Settings:
Sergey Bobkov and Prasad Tetali

Preliminary version appeared in Proc. of the ACM STOC 2003, pages 287-296.
Jour. Theor. Probab. (to appear) Preprint pdf file

The subgaussian constant and concentration inequalities:
Sergey Bobkov, Christian Houdré and Prasad Tetali

Israel J. Math. (appeared) a somewhat condensed version (pdf file)

a fuller version (pdf file)

Slow mixing of the Glauber dynamics for the hard-core model on the Hamming cube:
David Galvin and Prasad Tetali

Proc. of the Annual Symposium on Discrete Algorithms (SODA 2004).
Journal version in Random Struct. & Algorithms (to appear) pdf file

A sharp threshold for random graphs with a monochromatic triangle in every edge coloring:
Ehud Friedgut, Vojtech Rodl, Andrzej Rucinski and Prasad Tetali

Memoires of the AMS (to appear) pdf file

A family of switch equivalent graphs:
B. Guenin, D. Mubayi, P. Tetali

Discrete Math. (to appear) pdf file

The number of linear extensions of the Boolean lattice: Graham Brightwell and Prasad Tetali,
Order Vol. 20 (2003), 333-345 pdf file

Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains:
Mark Jerrum, Jung-Bae Son, Prasad Tetali and Eric Vigoda Ann. Appl. Probab.(2004) ; Isaac Newton Institute Preprint NI03006-CMP

Isoperimetric Constants for Product Markov Chains and Graph Products:

C. Houdré and P. Tetali, Combinatorica Vol. 24 (2004), 359-388 pdf file

On weighted graph homomorphisms:
D. Galvin and P. Tetali

DIMACS-AMS Special Volume Vol. 63 (2004), 97-104 pdf file

On the sampling problem for H-colorings on the hypercubic lattice:
C. Borgs, J. Chayes, M. Dyer, P. Tetali

DIMACS-AMS Special Volume Vol. 63 (2004), 13-28 pdf file

Ramsey games against a one-armed bandit:
Ehud Friedgut, Yoshiharu Kohayakawa, Vojtech Rodl, Andrzej Rucinski and Prasad Tetali

Combin. Probab. & Computing 12 (2003), 515-546 pdf file

On playing golf with two balls:
Ioana Dumitriu, Prasad Tetali, and Peter Winkler

SIAM J. on Discrete Math. 16 (2003) 604-615 ps file

Approximating Min-sum Set Cover:
Uriel Feige, Laszlo Lovasz and Prasad Tetali

APPROX 2002; Algorithmica (2004) (to appear) pdf file

Two-coloring random hypergraphs:
D. Achlioptas, J.H. Kim, M, Krivelevich, and P. Tetali

Random Structures & Algorithms 18 (2002), 249-259 pdf file

On the chromatic number of set systems:
A. Kostochka, D. Mubayi, V. Rödl, P. Tetali

Random Structures & Algorithms 19 (2001), 87-98 pdf file

Minimal completely separating systems of k-sets:
A. Kundgen, D. Mubayi and P. Tetali

J. Comb. Theory (Series A) 93 (2001), 192-198 pdf file

Concentration of Measure for Products of Markov Chains via Functional Inequalities:
C. Houdré and P. Tetali

Combinatorics, Probability & Computing 10 (2001), 1-28 pdf file

Random Sampling of Euler Tours:
P. Tetali and S. Vempala

Algorithmica 30 (2001), 376-385 (Erratum : to be attached ...)
and Lecture Notes in Computer Science No. 1269 (July 1997), 57-66 pdf file

Analyzing Glauber dynamics using comparison of Markov chains:
D. Randall and P. Tetali

J. Math. Physics 41 (2000), 1598-1615 pdf file

\lambda_infty, Vertex isoperimetry and concentration:
S. Bobkov, C. Houdré and P. Tetali

Combinatorica 20 (2000), 153-172 pdf file

Optimal linear arrangements on rectangular grids:
P. Fishburn, P. Winkler, and P. Tetali

Discrete Math. 213 (2000), 123-139 pdf file

Torpid mixing of some MCMC algorithms in statistical physics:
C. Borgs, J. Chayes, A. Frieze, J. H. Kim, P. Tetali, E. Vigoda and V. H. Vu

IEEE Symp. on Foundations of Computer Science (Oct. 1999), New York pdf file

Limits on the efficiency of one-way permutation-based hash functions:
J. H. Kim, D. R. Simon, and P. Tetali

IEEE Symp. on Foundations of Computer Science (Oct. 1999), New York pdf file

A Markov Chain Model for a Shared Optical Memory Packet Switch:
P. Bergstrom, M.A. Ingram, A. Vernon, J. Hughes, and P. Tetali

IEEE Trans. on Communications (Oct. 1999), 1593-1603 pdf file

Design of on-line algorithms using hitting times:
P. Tetali

Proc. of the Symp. on Discrete Algorithms (1994), 402-411; SIAM J. on Computing 28 (1999), 1232-1246 pdf file

Simple Markov chain algorithms for generating bipartite graphs and tournaments:
R. Kannan, P. Tetali, and S. Vempala

Proc. of 8th Annual ACM/SIAM Symposium on Discrete Algorithms Jan. 1997; Random Structures & Algorithms 14 (1999), 293-308 pdf file

On the Mixing Time of the Triangulation Walk and Other Catalan Structures:
L. McShine and P. Tetali

SIAM Conf. on Discrete Math. (1998), Toronto, Canada; DIMACS-AMS volume on Randomization Methods in Algorithm Design 43 (ed. By Pardalos et al.) (1998), 147-160 pdf file

Analyzing Glauber Dynamics Using Comparison of Markov:
D. Randall and P. Tetali

presented at LATIN '98, Campinas, Brazil; also appeared in Lecture Notes in Computer Science 1380 (1998) pdf file

Isoperimetric inequalities for Cartesian products of graphs:
F.R.K. Chung and P. Tetali

Combinatorics, Probability and Computing 7 (1998), 141-148 pdf file

A characterization of UNIQUE Tournaments:
P. Tetali

J. Combinatorial Theory (Series B) 72 (1998), 157-159 pdf file

Score Certificates for Tournaments:
P. Fishburn, J.H. Kim and P. Tetali

Bell Labs Tech. Memo. (May 1994), DIMACS Tech. Report No. 94-30 (1994),
J. Graph Theory 24 (1997), 117-139 pdf file

A note on expected hitting times for birth and death chains:
J. Palacios and P. Tetali
Statistics and Probability Letters 30 (1996), 119-125 pdf file

Covering with Latin Transversals:
N. Alon, J. Spencer, and P. Tetali

Technical Report 91-71, Oct. 1991; also Discrete Applied Math. 57 (1995), 1-10 pdf file

Independence of Solution Sets and Minimal Asymptotic Bases:
P. Erdös, M. Nathanson and P. Tetali

Acta Arithmetica LXIX.3 (1995), 243-258 pdf file

Sidon sets with small gaps:
J. Spencer and P. Tetali

in Discrete Probability and Algorithms, IMA Volumes in Applied Mathematics and its Applications (eds., D. Aldous et al.), Springer-Verlag, New York (1995) pdf file

An Extension of Foster's Network Theorem:
P. Tetali

Combinatorics, Probability & Computing, special issue dedicated to the 80th birthday of Paul Erdös, No. 3 (1994) 421-427 pdf file

Simultaneous Reversible Markov Chains:
P. Tetali and P. Winkler

Combinatorics, Paul Erdös Is Eighty (Vol. 1), Keszthely, Hungary (1993), 433-451 pdf file

Collisions among Random Walks on a Graph:
D. Coppersmith, P. Tetali and P. Winkler

SIAM Journal on Discrete Mathematics 6 (1993), 363-374 pdf file

Communication Complexity and Quasi-Randomness:
F.R.K. Chung and P. Tetali

Journal on Discrete Mathematics 6 (1993), 110-123 pdf file

Random Walks and the Effective Resistance of Networks:
P. Tetali

Journal of Theoretical Probability 4 (1991), 101-109 pdf file

On a Random Walk Problem Arising in Self-Stabilizing Token Management:
P. Tetali and P. Winkler

Proceedings of 10th Annual ACM Symposium on Principles of Distributed Computing Montreal, Canada (1991) pdf file

Representations of Integers as the Sum of k Terms:
P. Erdös and P. Tetali

Random Structures and Algorithms 1 (1990) 245-261 pdf file

Recent Publications

Already Published (some links under construction...)