Publications (site will be revised soon)

• Reconstruction threshold for the hardcore model
     Nayantara Bhatnagar, Allan Sly and Prasad Tetali
  
      Proc. of RANDOM (2010), Barcelona, Spain

• Randomizing two derandomized greedy algorithms
     Kevin Costello, Asaf Shapira, Prasad Tetali
  
     to appear in Proc. of the ACM-SIAM SODA (2011), San Francisco, CA.

• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
     Mohsen Bayati, David Gamarnik, and Prasad Tetali

      (Arxiv version, Dec. 2009) Submitted to journal.
  
     Proc. of the ACM STOC (2010), Cambridge, MA.

• Approximations for Isoperimetric and Spectral Profile of Graphs and Eigenvalues of Diagonally-Dominant Matrices
     Prasad Raghavendra, David Steurer, and Prasad Tetali
  
     Proc. of the ACM STOC (2010), Cambridge, MA.

• Near-optimal sublinear time bounds for distributed random walks
      Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, and Prasad Tetali

      (Arxiv Version, Nov. 2009) PODC (2010), Zurich.

• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
      Prasad Tetali, Juan Verga, Eric Vigoda, and Linji Yang

      Conference Version (ACM-SIAM Proc. of SODA) Jan. 2010, Austin, TX.

• How long does it take to catch a wild kangaroo? --
      Ravi Montenegro and Prasad Tetali

      Conference Version (Proc. of the ACM STOC) 2009, Maryland.

• Reconstruction and Clustering in Random Constraint Satisfaction Problems --
      Andrea Montanari, Ricardo Restrepo and Prasad Tetali

      Revised version Submitted (December 2009).

• The finite-state hardcore model on a regular tree --
      David Galvin, Fabio Martinelli, Kavita Ramanan and Prasad Tetali

      journal version SIAM J. on Disc. Math. (to appear).

• Meander  Graphs: Christine Heitsch and Prasad Tetali

      Revised Version Submitted (December 2009).

• On the entropy of sums and cardinalities of compound sets:
      Mokshay Madiman, Adam Marcus and Prasad Tetali

      under revision for Random. Struct. & Alg

• Matchings and Independent Sets of a fixed size in Regular Graphs:
      Teena Carroll, David Galvin and Prasad Tetali

      JCTA (2009).

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

      in revision 2009.

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

      Combinatorics, Probability & Computing 18(2009), 835-860.

• G-Parking Functions, Acyclic Orientations and Spanning Trees
      Brian Benson, Deeparnab Chakrabarty and Prasad Tetali

      Discrete Math. (to appear).

• 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. Ann. Appl. Probab. (to appear)

    Ann. Appl. Probab. (to appear)


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

• 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 (submitted May 2007), revised (August 2009)   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

    draft   pdf file (Under RECONSTRUCTION -- Lemma 6 is wrong, which leaves a major gap in the main theorem!)

• 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

    Submitted (October 2008)   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;   `final' version :

• 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

• 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