Prasad Tetali

According to our database, Prasad Tetali authored at least 103 papers between 1990 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of one.

2024

On the zeroes of hypergraph independence polynomials.

David J. Galvin, Gwen McKinley, Will Perkins, Michail Sarantis, Prasad Tetali

Comb. Probab. Comput., January, 2024

2023

Efficient sampling and counting algorithms for the Potts model on <i>ℤ</i>^<i>d</i> at all temperatures.

Christian Borgs, Jennifer T. Chayes, Tyler Helmuth, Will Perkins, Prasad Tetali

Random Struct. Algorithms, August, 2023

On Min Sum Vertex Cover and Generalized Min Sum Set Cover.

Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali

SIAM J. Comput., April, 2023

2022

On the bipartiteness constant and expansion of Cayley graphs.

Nina Moorman, Peter Ralli, Prasad Tetali

Eur. J. Comb., 2022

On the number of independent sets in uniform, regular, linear hypergraphs.

Emma Cohen, Will Perkins, Michail Sarantis, Prasad Tetali

Eur. J. Comb., 2022

Multi Purpose Routing: New Perspectives and Approximation Algorithms.

Majid Farhadi, Jai Moondra, Prasad Tetali, Alejandro Toriello

CoRR, 2022

Determinant Maximization via Matroid Intersection Algorithms.

Adam Brown, Aditi Laddha, Madhusudhan Pittu, Mohit Singh, Prasad Tetali

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Hardness and Approximation of Submodular Minimum Linear Ordering Problems.

Majid Farhadi, Swati Gupta, Shengding Sun, Prasad Tetali, Michael C. Wigal

CoRR, 2021

Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover.

Nikhil Bansal, Jatin Batra, Majid Farhadi, Prasad Tetali

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Traveling Firefighter Problem.

Majid Farhadi, Alejandro Toriello, Prasad Tetali

Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms, 2021

2020

Finding cliques using few probes.

Uriel Feige, David Gamarnik, Joe Neeman, Miklós Z. Rácz, Prasad Tetali

Random Struct. Algorithms, 2020

On the Complexity and Approximation of λ_∞ Spread Constant and Maximum Variance Embedding.

Majid Farhadi, Anand Louis, Prasad Tetali

CoRR, 2020

Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures.

Christian Borgs, Jennifer T. Chayes, Tyler Helmuth, Will Perkins, Prasad Tetali

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

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

Antonio Blanca, Yuxuan Chen, David J. Galvin, Dana Randall, Prasad Tetali

Comb. Probab. Comput., 2019

Efficient sampling and counting algorithms for the Potts model on Z^d at all temperatures.

Christian Borgs, Jennifer T. Chayes, Tyler Helmuth, Will Perkins, Prasad Tetali

CoRR, 2019

2018

Algebraic Connectivity Under Site Percolation in Finite Weighted Graphs.

Sohail Bahmani, Justin Romberg, Prasad Tetali

IEEE Trans. Netw. Sci. Eng., 2018

2017

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

Emma Cohen, Péter Csikvári, Will Perkins, Prasad Tetali

Eur. J. Comb., 2017

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

Henrik I. Christensen, Arindam Khan, Sebastian Pokutta, Prasad Tetali

Comput. Sci. Rev., 2017

On the Widom-Rowlinson Occupancy Fraction in Regular Graphs.

Emma Cohen, Will Perkins, Prasad Tetali

Comb. Probab. Comput., 2017

Mutation, Sexual Reproduction and Survival in Dynamic Environments.

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, Vijay V. Vazirani

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

2016

Sampling and Counting 3-Orientations of Planar Triangulations.

Sarah Miracle, Dana Randall, Amanda Pascoe Streib, Prasad Tetali

SIAM J. Discret. Math., 2016

Phase Coexistence for the Hard-Core Model on ${\mathbb Z}^2$.

Antonio Blanca, Yuxuan Chen, David J. Galvin, Dana Randall, Prasad Tetali

CoRR, 2016

Inverse Expander Mixing for Hypergraphs.

Emma Cohen, Dhruv Mubayi, Peter Ralli, Prasad Tetali

Electron. J. Comb., 2016

2015

The game of survival: Sexual evolution in dynamic environments.

Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, Vijay V. Vazirani

CoRR, 2015

2013

Distributed Random Walks.

Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali

J. ACM, 2013

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

Andrey Kupavskii, Liudmila Ostroumova, Dmitry A. Shabanov, Prasad Tetali

Internet Math., 2013

Support-theoretic subgraph preconditioners for large-scale SLAM.

Yong-Dian Jian, Doru Balcan, Ioannis Panageas, Prasad Tetali, Frank Dellaert

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.

Antonio Blanca, David J. Galvin, Dana Randall, Prasad Tetali

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

2012

Entropy and set cardinality inequalities for partition-determined functions.

Mokshay M. Madiman, Adam W. Marcus, Prasad Tetali

Random Struct. Algorithms, 2012

Phase Coexistence and Slow Mixing for the Hard-Core Model on Z^2

Antonio Blanca, David J. Galvin, Dana Randall, Prasad Tetali

CoRR, 2012

On Mimicking Networks Representing Minimum Terminal Cuts

Arindam Khan, Prasad Raghavendra, Prasad Tetali, László A. Végh

CoRR, 2012

Matching with Commitments

Kevin P. Costello, Prasad Tetali, Pushkar Tripathi

CoRR, 2012

Algorithms for Sampling 3-Orientations of Planar Triangulations

Sarah Miracle, Dana Randall, Amanda Pascoe Streib, Prasad Tetali

CoRR, 2012

Many sparse cuts via higher eigenvalues.

Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala

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

Stochastic Matching with Commitment.

Kevin P. Costello, Prasad Tetali, Pushkar Tripathi

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

Approximating Minimum Linear Ordering Problems.

Satoru Iwata, Prasad Tetali, Pushkar Tripathi

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

2011

Reconstruction and Clustering in Random Constraint Satisfaction Problems.

Andrea Montanari, Ricardo Restrepo, Prasad Tetali

SIAM J. Discret. Math., 2011

Special Section on Constraint Satisfaction Problems and Message Passing Algorithms.

Marc Mézard, Prasad Tetali

SIAM J. Discret. Math., 2011

The Multistate Hard Core Model on a Regular Tree.

David J. Galvin, Fabio Martinelli, Kavita Ramanan, Prasad Tetali

SIAM J. Discret. Math., 2011

Efficient Distributed Medium Access

Devavrat Shah, Jinwoo Shin, Prasad Tetali

CoRR, 2011

Randomized greedy: new variants of some classic approximation algorithms.

Kevin P. Costello, Asaf Shapira, Prasad Tetali

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

Medium Access Using Queues.

Devavrat Shah, Jinwoo Shin, Prasad Tetali

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.

Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, Eric Vigoda, Linji Yang

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

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

Anand Louis, Prasad Raghavendra, Prasad Tetali, Santosh S. Vempala

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

2010

Information inequalities for joint distributions, with interpretations and applications.

Mokshay M. Madiman, Prasad Tetali

IEEE Trans. Inf. Theory, 2010

G-parking functions, acyclic orientations and spanning trees.

Brian Benson, Deeparnab Chakrabarty, Prasad Tetali

Discret. Math., 2010

Tight Bounds for Mixing of the Swendsen-Wang Algorithm at the Potts Transition Point

Christian Borgs, Jennifer T. Chayes, Prasad Tetali

CoRR, 2010

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

Prasad Raghavendra, David Steurer, Prasad Tetali

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

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

Mohsen Bayati, David Gamarnik, Prasad Tetali

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.

Prasad Tetali, Juan Carlos Vera, Eric Vigoda, Linji Yang

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

Efficient distributed random walks with applications.

Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali

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

Reconstruction Threshold for the Hardcore Model.

Nayantara Bhatnagar, Allan Sly, Prasad Tetali

Proceedings of the Approximation, 2010

2009

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

Teena Carroll, David J. Galvin, Prasad Tetali

J. Comb. Theory, Ser. A, 2009

Concentration on the Discrete Torus Using Transportation.

Marcus Sammer, Prasad Tetali

Comb. Probab. Comput., 2009

Near-Optimal Sublinear Time Bounds for Distributed Random Walks

Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali

CoRR, 2009

Entropy and set cardinality inequalities for partition-determined functions, with applications to sumsets

Mokshay M. Madiman, Adam Marcus, Prasad Tetali

CoRR, 2009

How long does it take to catch a wild kangaroo?

Ravi Montenegro, Prasad Tetali

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.

Jeong Han Kim, Ravi Montenegro, Yuval Peres, Prasad Tetali

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

Running Time Predictions for Factoring Algorithms.

Ernie Croot, Andrew Granville, Robin Pemantle, Prasad Tetali

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

2007

Random Walks with Lookahead on Power Law Random Graphs.

Milena Mihail, Amin Saberi, Prasad Tetali

Internet Math., 2007

Simple deterministic approximation algorithms for counting matchings.

Mohsen Bayati, David Gamarnik, Dimitriy A. Katz, Chandra Nair, Prasad Tetali

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

Sandwich bounds for joint entropy.

Mokshay M. Madiman, Prasad Tetali

Proceedings of the IEEE International Symposium on Information Theory, 2007

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

Jeong Han Kim, Ravi Montenegro, Prasad Tetali

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

2006

On smoothed analysis in dense graphs and formulas.

Michael Krivelevich, Benny Sudakov, Prasad Tetali

Random Struct. Algorithms, 2006

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

David J. Galvin, Prasad Tetali

Random Struct. Algorithms, 2006

A sharp threshold for random graphs with a monochromatic triangle in every edge coloring.

Ehud Friedgut, Vojtech Rödl, Andrzej Rucinski, Prasad Tetali

Memoirs of the American Mathematical Society 845, American Mathematical Society, ISBN: 978-0-8218-3825-9, 2006

2005

Mathematical Aspects of Mixing Times in Markov Chains.

Ravi Montenegro, Prasad Tetali

Found. Trends Theor. Comput. Sci., 2005

2004

A family of switch equivalent graphs.

Bertrand Guenin, Dhruv Mubayi, Prasad Tetali

Discret. Math., 2004

Isoperimetric Invariants For Product Markov Chains and Graph Products.

Christian Houdré, Prasad Tetali

Comb., 2004

Approximating Min Sum Set Cover.

Uriel Feige, László Lovász, Prasad Tetali

Algorithmica, 2004

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

David J. Galvin, Prasad Tetali

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

On the trade-off between rate and performance of expander codes on AWGN channels.

Souvik Dihidar, Steven W. McLaughlin, Prasad Tetali

Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

2003

On Playing Golf with Two Balls.

Ioana Dumitriu, Prasad Tetali, Peter Winkler

SIAM J. Discret. Math., 2003

The Number of Linear Extensions of the Boolean Lattice.

Graham R. Brightwell, Prasad Tetali

Order, 2003

Ramsey Games Against a One-Armed Bandit.

Ehud Friedgut, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Rucinski, Prasad Tetali

Comb. Probab. Comput., 2003

Modified log-sobolev inequalities, mixing and hypercontractivity.

Sergey G. Bobkov, Prasad Tetali

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

2002

Two-coloring random hypergraphs.

Dimitris Achlioptas, Jeong Han Kim, Michael Krivelevich, Prasad Tetali

Random Struct. Algorithms, 2002

2001

On the chromatic number of set systems.

Alexandr V. Kostochka, Dhruv Mubayi, Vojtech Rödl, Prasad Tetali

Random Struct. Algorithms, 2001

Minimal Completely Separating Systems of k-Sets.

André Kündgen, Dhruv Mubayi, Prasad Tetali

J. Comb. Theory, Ser. A, 2001

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

Christian Houdré, Prasad Tetali

Comb. Probab. Comput., 2001

Random Sampling of Euler Tours.

Prasad Tetali, Santosh S. Vempala

Algorithmica, 2001

On Weighted Graph Homomorphisms.

David J. Galvin, Prasad Tetali

Proceedings of the Graphs, 2001

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

Christian Borgs, Jennifer T. Chayes, Martin E. Dyer, Prasad Tetali

Proceedings of the Graphs, 2001

2000

Optimal linear arrangement of a rectangular grid.

Peter C. Fishburn, Prasad Tetali, Peter Winkler

Discret. Math., 2000

lambda_infty Vertex Isoperimetry and Concentration.

Sergey G. Bobkov, Christian Houdré, Prasad Tetali

Comb., 2000

1999

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

Peter D. Bergstrom Jr., Mary Ann Ingram, Andrew J. Vernon, Joseph L. A. Hughes, Prasad Tetali

IEEE Trans. Commun., 1999

Design of On-Line Algorithms Using Hitting Times.

Prasad Tetali

SIAM J. Comput., 1999

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

Ravi Kannan, Prasad Tetali, Santosh S. Vempala

Random Struct. Algorithms, 1999

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

Jeong Han Kim, Daniel R. Simon, Prasad Tetali

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

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

Christian Borgs, Jennifer T. Chayes, Alan M. Frieze, Jeong Han Kim, Prasad Tetali, Eric Vigoda, Van H. Vu

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

1998

A Characterization of Unique Tournaments.

Prasad Tetali

J. Comb. Theory, Ser. B, 1998

Isoperimetric Inequalities for Cartesian Products of Graphs.

Fan R. K. Chung, Prasad Tetali

Comb. Probab. Comput., 1998

Analyzing Glauber Dynamics by Comparison of Markov Chains.

Dana Randall, Prasad Tetali

Proceedings of the LATIN '98: Theoretical Informatics, 1998

1997

Score certificates for tournaments.

Jeong Han Kim, Prasad Tetali, Peter C. Fishburn

J. Graph Theory, 1997

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

Ravi Kannan, Prasad Tetali, Santosh S. Vempala

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

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

Lisa McShine, Prasad Tetali

Proceedings of the Randomization Methods in Algorithm Design, 1997

1995

Covering with Latin Transversals.

Noga Alon, Joel Spencer, Prasad Tetali

Discret. Appl. Math., 1995

1994

An Extension of Foster's Network Theorem.

Prasad Tetali

Comb. Probab. Comput., 1994

1993

Collisions Among Random Walks on a Graph.

Don Coppersmith, Prasad Tetali, Peter Winkler

SIAM J. Discret. Math., 1993

Communication Complexity and Quasi Randomness.

Fan R. K. Chung, Prasad Tetali

SIAM J. Discret. Math., 1993

1991

Applications and Analysis of Probabilistic Techniques.

Prasad Tetali

PhD thesis, 1991

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

Prasad Tetali, Peter Winkler

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

1990

Representations of Integers as the Sum of k Terms.

Paul Erdös, Prasad Tetali

Random Struct. Algorithms, 1990