# Prasad Tetali

According to our database

Collaborative distances:

^{1}, Prasad Tetali authored at least 75 papers between 1990 and 2018.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2018

Algebraic Connectivity Under Site Percolation in Finite Weighted Graphs.

IEEE Trans. Network Science and Engineering, 2018

2017

The Widom-Rowlinson model, the hard-core model and the extremality of the complete graph.

Eur. J. Comb., 2017

Approximation and online algorithms for multidimensional bin packing: A survey.

Computer Science Review, 2017

On the Widom-Rowlinson Occupancy Fraction in Regular Graphs.

Combinatorics, Probability & Computing, 2017

Mutation, Sexual Reproduction and Survival in Dynamic Environments.

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

Sampling and Counting 3-Orientations of Planar Triangulations.

SIAM J. Discrete Math., 2016

Inverse Expander Mixing for Hypergraphs.

Electr. J. Comb., 2016

2013

Distributed Random Walks.

J. ACM, 2013

The Distribution of Second Degrees in the Buckley-Osthus Random Graph Model.

Internet Mathematics, 2013

Support-theoretic subgraph preconditioners for large-scale SLAM.

Proceedings of the 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2013

Phase Coexistence and Slow Mixing for the Hard-Core Model on ℤ2.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Entropy and set cardinality inequalities for partition-determined functions.

Random Struct. Algorithms, 2012

Many sparse cuts via higher eigenvalues.

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Stochastic Matching with Commitment.

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Approximating Minimum Linear Ordering Problems.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Reconstruction and Clustering in Random Constraint Satisfaction Problems.

SIAM J. Discrete Math., 2011

Special Section on Constraint Satisfaction Problems and Message Passing Algorithms.

SIAM J. Discrete Math., 2011

The Multistate Hard Core Model on a Regular Tree.

SIAM J. Discrete Math., 2011

Randomized greedy: new variants of some classic approximation algorithms.

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Medium Access Using Queues.

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets.

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Algorithmic Extensions of Cheeger's Inequality to Higher Eigenvalues and Partitions.

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Information inequalities for joint distributions, with interpretations and applications.

IEEE Trans. Information Theory, 2010

G-parking functions, acyclic orientations and spanning trees.

Discrete Mathematics, 2010

Approximations for the isoperimetric and spectral profile of graphs and related parameters.

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Combinatorial approach to the interpolation method and scaling limits in sparse random graphs.

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Efficient distributed random walks with applications.

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

Reconstruction Threshold for the Hardcore Model.

Proceedings of the Approximation, 2010

2009

Matchings and independent sets of a fixed size in regular graphs.

J. Comb. Theory, Ser. A, 2009

Concentration on the Discrete Torus Using Transportation.

Combinatorics, Probability & Computing, 2009

How long does it take to catch a wild kangaroo?

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008

A Birthday Paradox for Markov Chains, with an Optimal Bound for Collision in the Pollard Rho Algorithm for Discrete Logarithm.

Proceedings of the Algorithmic Number Theory, 8th International Symposium, 2008

Running Time Predictions for Factoring Algorithms.

Proceedings of the Algorithmic Number Theory, 8th International Symposium, 2008

2007

Random Walks with Lookahead on Power Law Random Graphs.

Internet Mathematics, 2007

Simple deterministic approximation algorithms for counting matchings.

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Sandwich bounds for joint entropy.

Proceedings of the IEEE International Symposium on Information Theory, 2007

Near Optimal Bounds for Collision in Pollard Rho for Discrete Log.

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

On smoothed analysis in dense graphs and formulas.

Random Struct. Algorithms, 2006

Slow mixing of Glauber dynamics for the hard-core model on regular bipartite graphs.

Random Struct. Algorithms, 2006

2005

Mathematical Aspects of Mixing Times in Markov Chains.

Foundations and Trends in Theoretical Computer Science, 2005

2004

A family of switch equivalent graphs.

Discrete Mathematics, 2004

Isoperimetric Invariants For Product Markov Chains and Graph Products.

Combinatorica, 2004

Slow mixing of Glauber dynamics for the hard-core model on the hypercube.

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003

On Playing Golf with Two Balls.

SIAM J. Discrete Math., 2003

The Number of Linear Extensions of the Boolean Lattice.

Order, 2003

Ramsey Games Against a One-Armed Bandit.

Combinatorics, Probability & Computing, 2003

Modified log-sobolev inequalities, mixing and hypercontractivity.

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Approximating Min-sum Set Cover.

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001

On the chromatic number of set systems.

Random Struct. Algorithms, 2001

Minimal Completely Separating Systems of k-Sets.

J. Comb. Theory, Ser. A, 2001

Concentration Of Measure For Products Of Markov Kernels And Graph Products Via Functional Inequalities.

Combinatorics, Probability & Computing, 2001

On Weighted Graph Homomorphisms.

Proceedings of the Graphs, 2001

On the Sampling Problem for H-Colorings on the Hypercubic Lattice.

Proceedings of the Graphs, 2001

2000

Optimal linear arrangement of a rectangular grid.

Discrete Mathematics, 2000

lambda

_{infty}Vertex Isoperimetry and Concentration.
Combinatorica, 2000

Two-coloring Random Hypergraphs.

ICALP Satellite Workshops, 2000

1999

A Markov chain model for an optical shared-memory packet switch.

IEEE Trans. Communications, 1999

Simple Markov-chain algorithms for generating bipartite graphs and tournaments.

Random Struct. Algorithms, 1999

Limits on the Efficiency of One-Way Permutation-Based Hash Functions.

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics.

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

A Characterization of Unique Tournaments.

J. Comb. Theory, Ser. B, 1998

Isoperimetric Inequalities for Cartesian Products of Graphs.

Combinatorics, Probability & Computing, 1998

Analyzing Glauber Dynamics by Comparison of Markov Chains.

Proceedings of the LATIN '98: Theoretical Informatics, 1998

1997

Score certificates for tournaments.

Journal of Graph Theory, 1997

Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract).

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Random Sampling of Euler Tours.

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1997

On the mixing time of the triangulation walk and other Catalan structures.

Proceedings of the Randomization Methods in Algorithm Design, 1997

1995

Covering with Latin Transversals.

Discrete Applied Mathematics, 1995

1994

An Extension of Foster's Network Theorem.

Combinatorics, Probability & Computing, 1994

Design of On-line Algorithms Using Hitting Times.

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993

Collisions Among Random Walks on a Graph.

SIAM J. Discrete Math., 1993

Communication Complexity and Quasi Randomness.

SIAM J. Discrete Math., 1993

1991

On a Random Walk Problem Arising in Self-Stabilizing Token Management.

Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, 1991

1990

Representations of Integers as the Sum of k Terms.

Random Struct. Algorithms, 1990