Near-Optimal Sublinear Time Bounds for Distributed Random Walks (2009)
Sarma, Atish Das, Nanongkai, Danupon, Pandurangan, Gopal, Tetali, Prasad
We focus on the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk...
Sharp Transitions in Making Squares (2009)
Ernie Croot, Andrew Granville, Robin Pemantle, Prasad Tetali
Supported by an NSF grant.
Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees (2009)
Tetali, Prasad, Vera, Juan C., Vigoda, Eric, Yang, Linji
We prove that the mixing time of the Glauber dynamics for random $k$-colorings of the complete tree with branching factor $b$ undergoes a phase transition at $k=b(1+o_b(1))/\ln{b}$. Our main result...
Sharp Transitions in Making Squares (2009)
Ernie Croot, Andrew Granville, Robin Pemantle, Prasad Tetali
2 Partiellement soutenu par une bourse de la Conseil de recherches en sciences naturelles et en génie du Canada. 3
Reconstruction and Clustering in Random Constraint Satisfaction Problems (2009)
Montanari, Andrea, Restrepo, Ricardo, Tetali, Prasad
Random instances of Constraint Satisfaction Problems (CSP's) appear to be hard for all known algorithms, when the number of constraints per variable lies in a certain interval. Contributing to the...
Prasad Tetali, Dr. Kay Jamison
This is an example of front matter. Note the different type style, and how the text is vertically centered on the page.
Information Inequalities for Joint Distributions, with Interpretations and Applications (2008)
Madiman, Mokshay, Tetali, Prasad
Upper and lower bounds are obtained for the joint entropy of a collection of random variables in terms of an arbitrary collection of subset joint entropies. These inequalities generalize Shannon's...
Madiman, Mokshay, Marcus, Adam, Tetali, Prasad
A new notion of partition-determined functions is introduced, and several basic new inequalities are presented for the entropy of such functions of independent random variables, as well as for...
Abstract. This paper deals with the construction of a correlation decay tree (hypertree) for interacting systems modeled using graphs (hypergraphs) that can be used to compute the marginal...
How long does it take to catch a wild kangaroo? (2008)
Montenegro, Ravi, Tetali, Prasad
The discrete logarithm problem asks to solve for the exponent $x$, given the generator $g$ of a cyclic group $G$ and an element $h\in G$ such that $g^x=h$. We give the first rigorous proof that...
RAMSEY GAMES AGAINST A ONE-ARMED BANDIT EHUD FRIEDGUT, YOSHIHARU KOHAYAKAWA, VOJTĚCH RÖDL, (2008)
Andrzej Ruciński, Prasad Tetali
Abstract. We study the following one-person game against a random graph: the Player’s goal is to 2-colour a random sequence of edges e1, e2,... of a complete graph on n vertices, avoiding a...
Sharp Transitions in Making Squares (2008)
Croot, Ernie, Granville, Andrew, Pemantle, Robin, Tetali, Prasad
In many integer factoring algorithms, one produces a sequence of integers (created in a pseudo-random way), and wishes to rapidly determine a subsequence whose product is a square (which we call a...
Consider a graph on the set of triangulations of a convex polygon with n sides, wherein two triangulations are considered adjacent if (and only if) one can be obtained from the other by \ ipping...
Analysis of Top-Swap Shuffling for Genome Rearrangements (2008)
Nayantara Bhatnagar, Pietro Caputo, Prasad Tetali, Eric Vigoda
Abstract: We study Markov chains which model genome rearrangements. These models are useful for studying the equilibrium distribution of chromosomal lengths, and are used in methods for estimating...
A FAMILY OF SWITCH EQUIVALENT GRAPHS (2008)
Bertrand Guenin, Dhruv Mubayi, Prasad Tetali
ABSTRACT. Let 2G be the graph consisting of two disjoint copies of G. We prove that every graph of the form 2H can be transformed to every other graph of the form 2K using the following operations:...
Michael Krivelevich, Benny Sudakov, Prasad Tetali
smoothed analysis in dense graphs and formulas
Communication Complexity and Quasi-randomness 1 (2008)
Many problems arising in interactive and distributive computation share the general frame-work that a number of processors wish to collaboratively evaluate a Boolean function while each processor has...
RAMSEY GAMES AGAINST A ONE-ARMED BANDIT EHUD FRIEDGUT, YOSHIHARU KOHAYAKAWA, VOJTĚCH RÖDL, (2008)
Andrzej Ruciński, Prasad Tetali
Abstract. We study the following one-person game against a random graph: the Player’s goal is to 2-colour a random sequence of edges e1, e2,... of a complete graph on n vertices, avoiding a...
Limits on the Efficiency of One-Way Permutation-Based Hash Functions (2008)
Jeong Han, Kim Daniel, R. Simon, Prasad Tetali
Naor and Yung show that a one-bit-compressing universal one-way hash function (UOWHF) can be constructed based on a one-way permutation. This construction can be iterated to build a UOWHF which...
On smoothed analysis in dense graphs and formulas (2008)
Abstract We study a model of random graphs, where a random instance is obtained by adding random edges to a large graph of a given density. The research on this model has been started by Bohman et...
On smoothed analysis in dense graphs and formulas (2008)
Michael Krivelevich, Benny Sudakov, Prasad Tetali
ABSTRACT: We study a model of random graphs, where a random instance is obtained by adding random edges to a large graph of a given density. The research on this model has been started by Bohman and...
Parking Functions and Acyclic Orientations of Graphs (2008)
Benson, Brian A., Tetali, Prasad
Given an undirected graph $G=(V,E)$, and a designated vertex $q\in V$, the notion of a $G$-parking function (with respect to $q$) has recently been developed and studied by various authors. This...
Tight Bounds for Mixing of the Swendsen-Wang Algorithm at the Potts Transition Point (2008)
Christian Borgs, Jennifer T. Chayes, Prasad Tetali
We study two widely used algorithms for the Potts model on rectangular subsets of the hypercubic lattice Z d – heat bath dynamics and the Swendsen-Wang algorithm – and prove that, under certain...
Running time predictions for factoring algorithms (2008)
Ernie Croot, Andrew Granville, Robin Pemantle, Prasad Tetali
Partiellement soutenu par une bourse de la Conseil de recherches en sciences naturelles et en génie du Canada. 3 Supported in part by NSF Grant DMS-01-03635. In 1994, Carl Pomerance proposed the...
Matchings and Independent Sets of a Fixed Size in Regular Graphs (2008)
Teena Carroll, David Galvin, Prasad Tetali
We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size ℓ in a d-regular graph on N vertices. For 2ℓ N bounded away from 0...
A Note on Sumsets using Entropy (2008)
Gyarmati, Matolcsi, and Ruzsa recently noted [2] that Han-type inequalities can be applied to sumsets in much the same way that they can be applied to characteristic functions of sets of random...
Kim, Jeong Han, Montenegro, Ravi, Peres, Yuval, Tetali, Prasad
We show a Birthday Paradox for self-intersections of Markov chains with uniform stationary distribution. As an application, we analyze Pollard's Rho algorithm for finding the discrete logarithm in a...
Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, Prasad Tetali, Eric Vigoda, Van Ha Vu
We study two widely used algorithms, Glauber dynamics and the Swendsen-Wang algorithm, on rectangular subsets of the hypercubic lattice Z d. We prove that under certain circumstances, the mixing time...
We give a characterization for isoperimetric invariants, including the Cheeger constant and the isoperimetric number of a graph. This leads to an isoperimetric inequality for the cartesian products...
Minimal completely separating systems of k-sets Andr'e Kundgen (2007)
Let n and k be fixed positive integers. A collection C of k-sets of [n] is a completely separating system if, for all distinct i; j 2 [n], there is an S 2 C for which i 2 S and j 62 S. Let R(n; k)...
Limits on the Efficiency of One-Way Permutation-Based Hash Functions (2007)
Jeong Han Kim, Jeong Han Kim, Daniel R. Simon, Daniel R. Simon, Prasad Tetali, ...
Naor and Yung show that a one-bit-compressing universal oneway hash function (UOWHF) can be constructed based on a one-way permutation. This construction can be iterated to build a UOWHF which...
Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali
A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H(k; n; p) be a random k-uniform hypergraph on a vertex set V of...
The correlation decay (CD) tree and strong spatial mixing in multi-spin systems (2007)
This paper deals with the construction of a correlation decay tree (hypertree) for interacting systems modeled using graphs (hypergraphs) that can be used to compute the marginal probability of any...
Information inequalities for joint distributions, with interpretations and applications (2007)
Mokshay Madiman, Prasad Tetali
Abstract — Upper and lower bounds are obtained for the joint entropy of a collection of random variables in terms of an arbitrary collection of subset joint entropies. These inequalities generalize...
Near Optimal Bounds for Collision in Pollard Rho for Discrete Log (2006)
Kim, Jeong Han, Montenegro, Ravi, Tetali, Prasad
We analyze a fairly standard idealization of Pollard's Rho algorithm for finding the discrete logarithm in a cyclic group G. It is found that, with high probability, a collision occurs in...
A Tight Bound for the Lamplighter Problem (2006)
Ganapathy, Murali K., Tetali, Prasad
We settle an open problem, raised by Y. Peres and D. Revelle, concerning the $L^2$ mixing time of the random walk on the lamplighter graph. We also provide general bounds relating the entropy decay...
Analysis of top-swap shuffling for genome rearrangements (2006)
Bhatnagar, Nayantara, Caputo, Pietro, Tetali, Prasad, Vigoda, Eric
We study Markov chains which model genome rearrangements. These models are useful for studying the equilibrium distribution of chromosomal lengths, and are used in methods for estimating genomic...
Mixing Time Bounds via the Spectral Profile (2006)
Tetali, Prasad; Georgia Institute Of Technology, USA; Siena.tetali@gmail.com
On complete, non-compact manifolds and infinite graphs, Faber-Krahn inequalities have been used to estimate the rate of decay of the heat kernel. We develop this technique in the setting of finite...
Approved by: Maximum Codes with the Identifiable Parent Property (2006)
Dr. Xingxing Yu Advisor, Dr. Luca Dieci, Tom Trotter, Michael Lacey, Prasad Tetali, ...
To my parents, my brothers and my husband. iii ACKNOWLEDGEMENTS There are many I would like to thank for helping me get this far. First and foremost are my family who carried the burden of supporting...
Sharp Transitions in Making Squares (2006)
Ernie Croot, Andrew Granville, Prasad Tetali
In many integer factoring algorithms, one produces a sequence of integers (created in a pseudo-random way), and wishes to determine a subsequence whose product is a square. A good model for how this...
Let Σ = (V, E) be a finite, d-regular bipartite graph. For any λ> 0 let πλ be the probability measure on the independent sets of Σ in which the set I is chosen with probability proportional...
Sharp Transitions in Making Squares (2006)
Ernie Croot, Andrew Granville, Prasad Tetali
In many integer factoring algorithms, one produces a sequence of integers (created in a pseudo-random way), and wishes to determine a subsequence whose product is a square. A good model for how this...
Analysis of Top-Swap Shuffling for Genome Rearrangements (2006)
Nayantara Bhatnagar, Pietro Caputo, Prasad Tetali, Eric Vigoda
Abstract: We study Markov chains which model genome rearrangements. These models are useful for studying the equilibrium distribution of chromosomal lengths, and are used in methods for estimating...
New Tools and Results in Graph Structure Theory Approved by: (2006)
Prof Robin Thomas, Advisor Prof, Prasad Tetali, Prof Richard, Duke Prof, Bill Cook
The desire to be right and the desire to have been right are two desires, and the sooner we separate them the better off we are. The desire to be right is the thirst for truth. On all accounts, both...
Approved by: New Capacity-Approaching Codes for Run-Length-Limited Channels (2006)
W. Mclaughlin, Dr. Faramarz Fekri, Dr. Prasad Tetali
To my parents
Mixing time bounds via the spectral profile (2006)
Sharad Goel, Ravi Montenegro, Prasad Tetali
Abstract. On complete, non-compact manifolds and infinite graphs, Faber-Krahn inequalities have been used to estimate the rate of decay of the heat kernel. We develop this technique in the setting of...
Let Σ = (V,E) be a finite, d-regular bipartite graph. For any λ>0letπλ be the probability measure on the independent sets of Σ in which the set I is chosen with probability proportional to λ...
Mixing Time Bounds via the Spectral Profile (2005)
Goel, Sharad, Montenegro, Ravi, Tetali, Prasad
On complete, non-compact manifolds and infinite graphs, Faber-Krahn inequalities have been used to estimate the rate of decay of the heat kernel. We develop this technique in the setting of finite...
Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains (2005)
Jerrum, Mark, Son, Jung-Bae, Tetali, Prasad, Vigoda, Eric
We consider finite-state Markov chains that can be naturally decomposed into smaller ``projection'' and ``restriction'' chains. Possibly this decomposition will be inductive, in that the restriction...
On the chromatic number of set systems (2005)
R Kostochka, Dhruv Mubayi, Vojtĕch Rödl, Prasad Tetali
An (r, l)-system is an r-uniform hypergraph in which every set of l vertices lies in at most one edge. Let mk(r, l) be the minimum number of edges in an (r, l)-system that is not k-colorable. Using...
Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains (2004)
Jerrum, Mark, Son, Jung-Bae, Tetali, Prasad, Vigoda, Eric
We consider finite-state Markov chains that can be naturally decomposed into smaller “projection” and “restriction” chains. Possibly this decomposition will be inductive, in that the...
On weighted graph homomorphisms (2004)
For given graphs G and H, let |Hom(G,H) | denote the set of graph homomorphisms from G to H. We show that for any finite, n-regular, bipartite graph G and any finite graph H (perhaps with loops),...
Milena Mihail, Amin Saberi, Prasad Tetali
Abstract — We show that in power law random graphs, a.s., the expected rate at which a random walk with lookahead discovers the nodes of the graph is sublinear. Searching a graph by simulating a...
A sharp threshold for random graphs with a monochromatic triangle in every edge coloring (2003)
Friedgut, Ehud, Rodl, Vojtech, Rucinski, Andrzej, Tetali, Prasad
Let $\R$ be the set of all finite graphs $G$ with the Ramsey property that every coloring of the edges of $G$ by two colors yields a monochromatic triangle. In this paper we establish a sharp...
Ramsey games against a one-armed bandit (2003)
Ehud Friedgut, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Ruciński, Prasad Tetali
We study the following one-person game against a random graph: the Player's goal is to 2-colour a random sequence of edges e1, e2,... of a complete graph on n vertices, avoiding a monochromatic...
A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring (2003)
Ehud Friedgut, Vojtech Rödl, Andrzej Rucinski, Prasad Tetali
Let R be the set of all nite graphs G with the Ramsey property that every coloring of the edges of G by two colors yields a monochromatic triangle. In this paper we establish a sharp threshold for...
Approximating Min-sum Set Cover (2003)
Uriel Feige, László Lovász, Prasad Tetali
this paper appeared in the conference proceedings of APPROX 2002
Approved by: Lorentz Lattice Gases on Graphs (2003)
M. Kreslavskiy, Leonid A. Bunimovich, Prasad Tetali, Dana Randall, Mihai Ciucu, Thomas Morley
To my parents,
The number of linear extensions of the boolean lattice (2003)
Graham R. Brightwell, Houghton St, Prasad Tetali
Let L(Qt) denote the number of linear extensions of the t-dimensional Boolean lattice Qt. We use the entropy method of Kahn to show that log(L(Qt))
Copyright c ○ 2003 by Dmitry M. KreslavskiyLorentz Lattice Gases on Graphs Approved by: (2003)
M. Kreslavskiy, Leonid A. Bunimovich, Prasad Tetali, Mihai Ciucu, Thomas Morley, Dana Randall
and to my grandfather, Roman Kreslavskiy, a manifestation of whose dream this thesis is. iii ACKNOWLEDGEMENTS First and foremost, I would like to thank my parents for the unending supply of...
A sharp threshold for random graphs with monochromatic triangle (2002)
Ehud Friedgut, Vojtech Rödl, Andrzej Ruciński, Prasad Tetali
Let R be the set of all finite graphs G with the Ramsey property that every coloring of the edges of G by two colors yields a monochromatic triangle. In this paper we establish a sharp threshold for...
Two-coloring Random Hypergraphs (2002)
Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali
A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H(k;n; p) be a random k-uniform hypergraph on a vertex set V of...
Two-coloring random hypergraphs (2002)
Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali
ABSTRACT: A 2-coloring of a hypergraph is a mapping from its vertex set to a set of two colors such that no edge is monochromatic. Let H = H�k � n � p � be a random k-uniform hypergraph on a...
Approximating min sum set cover (2002)
Uriel Feige, László Lovász, Prasad Tetali
The input to the min sum set cover problem is a collection of n sets that jointly cover m elements. The output is a linear order on the sets, namely, in every time step from 1 to n exactly one set is...
On the Chromatic Number of Set Systems (2001)
Alexandr Kostochka Dhruv, Alexandr Kostochka, Dhruv Mubayi, Prasad Tetali
An (r; l)-system is an r-uniform hypergraph in which every set of l vertices lies in at most one edge. Let m k (r; l) be the minimum number of edges in an (r; l)-system that is not k-colorable. Using...
On the sampling problem for H-colorings on the hypercubic lattice, pre-print (2000)
Christian Borgs, Jennifer T. Chayes, Martin Dyer, Prasad Tetali
We consider the problem of random H-colorings of rectangular subsets of the hypercubic lattice Z d, with weight λi ∈ (0, ∞) for the color i. First, we assume that H is non-trivial in the sense...
Design Of On-Line Algorithms Using Hitting Times (1999)
Random walks are well known for playing a crucial role in the design of randomized off-line as well as on-line algorithms. In this work we prove some basic identities for ergodic Markov chains (e.g.,...
Limits on the Efficiency of One-Way Permutation-Based Hash Functions (1999)
Jeong Han Kim, Daniel R. Simon, Prasad Tetali
Naor and Yung ([NY89]) show that a onebit -compressing universal one-way hash function (UOWHF) can be constructed based on a one-way permutation. This construction can be iterated to build a UOWHF...
Analyzing Glauber Dynamics by Comparison of Markov Chains (1999)
A popular technique for studying random properties of a combinatorial set is to design a Markov chain Monte Carlo algorithm. For many problems there are natural Markov chains connecting the set of...
Analyzing Glauber Dynamics by Comparison of Markov Chains (1997)
. A popular technique for studying random properties of a combinatorial set is to design a Markov chain Monte Carlo algorithm. For many problems there are natural Markov chains connecting the set of...
Ravi Kannan, Prasad Tetali, Santosh Vempala
) Ravi Kannan Prasad Tetali y Santosh Vempala z Abstract We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled...
Ravi Kannan, Prasad Tetali, Santosh Vempala
Ravi Kannan Prasad Tetali Santosh Vempala Abstract We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with...
Independence of Solution Sets and Minimal Asymptotic Bases (1994)
Paul Erdös, Melvyn B. Nathanson, Prasad Tetali
Let k 2. The set A of nonnegative integers is a minimal asymptotic basis of order k if every sufficiently large integer can be written as the sum of k elements of A, but no proper subset of A has...
Collisions among Random Walks on a Graph (1993)
Don Coppersmith, Prasad Tetali, Peter Winkler
A token located at some vertex v of a connected, undirected graph G on n vertices is said to be taking a "random walk" on G if, whenever it is instructed to move, it moves with equal...
A note on expected hitting times for birth and death chains
Palacios, JoséLuis, Tetali, Prasad
Using the electric network approach, we give closed form formulas for the expected hitting times in (finite and infinite) birth and death chains.