Prasad Tetali

Affiliations:
  • Georgia Institute of Technology, Atlanta, USA


According to our database1, Prasad Tetali authored at least 105 papers between 1990 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Hardness and approximation of submodular minimum linear ordering problems.
Math. Program., November, 2024

On the zeroes of hypergraph independence polynomials.
Comb. Probab. Comput., January, 2024

ImProver: Agent-Based Automated Proof Optimization.
CoRR, 2024

2023
Efficient sampling and counting algorithms for the Potts model on <i>ℤ</i><sup><i>d</i></sup> at all temperatures.
Random Struct. Algorithms, August, 2023

On Min Sum Vertex Cover and Generalized Min Sum Set Cover.
SIAM J. Comput., April, 2023

2022
On the bipartiteness constant and expansion of Cayley graphs.
Eur. J. Comb., 2022

On the number of independent sets in uniform, regular, linear hypergraphs.
Eur. J. Comb., 2022

Multi Purpose Routing: New Perspectives and Approximation Algorithms.
CoRR, 2022

Toppleable permutations, excedances and acyclic orientations.
Comb. Theory, 2022

Determinant Maximization via Matroid Intersection Algorithms.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021
Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Traveling Firefighter Problem.
Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms, 2021

2020
Finding cliques using few probes.
Random Struct. Algorithms, 2020

On the Complexity and Approximation of λ<sub>∞</sub> Spread Constant and Maximum Variance Embedding.
CoRR, 2020

Efficient sampling and counting algorithms for the Potts model on ℤᵈ at all temperatures.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019
Phase Coexistence for the Hard-Core Model on ℤ2.
Comb. Probab. Comput., 2019

Efficient sampling and counting algorithms for the Potts model on Z<sup>d</sup> at all temperatures.
CoRR, 2019

2018
Algebraic Connectivity Under Site Percolation in Finite Weighted Graphs.
IEEE Trans. Netw. Sci. Eng., 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.
Comput. Sci. Rev., 2017

On the Widom-Rowlinson Occupancy Fraction in Regular Graphs.
Comb. Probab. Comput., 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. Discret. Math., 2016

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

Inverse Expander Mixing for Hypergraphs.
Electron. J. Comb., 2016

2015
The game of survival: Sexual evolution in dynamic environments.
CoRR, 2015

2013
Distributed Random Walks.
J. ACM, 2013

The Distribution of Second Degrees in the Buckley-Osthus Random Graph Model.
Internet Math., 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

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

On Mimicking Networks Representing Minimum Terminal Cuts
CoRR, 2012

Matching with Commitments
CoRR, 2012

Algorithms for Sampling 3-Orientations of Planar Triangulations
CoRR, 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. Discret. Math., 2011

Special Section on Constraint Satisfaction Problems and Message Passing Algorithms.
SIAM J. Discret. Math., 2011

The Multistate Hard Core Model on a Regular Tree.
SIAM J. Discret. Math., 2011

Efficient Distributed Medium Access
CoRR, 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. Inf. Theory, 2010

G-parking functions, acyclic orientations and spanning trees.
Discret. Math., 2010

Tight Bounds for Mixing of the Swendsen-Wang Algorithm at the Potts Transition Point
CoRR, 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 A, 2009

Concentration on the Discrete Torus Using Transportation.
Comb. Probab. Comput., 2009

Near-Optimal Sublinear Time Bounds for Distributed Random Walks
CoRR, 2009

Entropy and set cardinality inequalities for partition-determined functions, with applications to sumsets
CoRR, 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 Math., 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

A sharp threshold for random graphs with a monochromatic triangle in every edge coloring.
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.
Found. Trends Theor. Comput. Sci., 2005

2004
A family of switch equivalent graphs.
Discret. Math., 2004

Isoperimetric Invariants For Product Markov Chains and Graph Products.
Comb., 2004

Approximating Min Sum Set Cover.
Algorithmica, 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

On the trade-off between rate and performance of expander codes on AWGN channels.
Proceedings of the 2004 IEEE International Symposium on Information Theory, 2004

2003
On Playing Golf with Two Balls.
SIAM J. Discret. Math., 2003

The Number of Linear Extensions of the Boolean Lattice.
Order, 2003

Ramsey Games Against a One-Armed Bandit.
Comb. Probab. Comput., 2003

Modified log-sobolev inequalities, mixing and hypercontractivity.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002
Two-coloring random hypergraphs.
Random Struct. Algorithms, 2002

2001
On the chromatic number of set systems.
Random Struct. Algorithms, 2001

Minimal Completely Separating Systems of k-Sets.
J. Comb. Theory A, 2001

Concentration Of Measure For Products Of Markov Kernels And Graph Products Via Functional Inequalities.
Comb. Probab. Comput., 2001

Random Sampling of Euler Tours.
Algorithmica, 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.
Discret. Math., 2000

lambda<sub>infty</sub> Vertex Isoperimetry and Concentration.
Comb., 2000

1999
A Markov chain model for an optical shared-memory packet switch.
IEEE Trans. Commun., 1999

Design of On-Line Algorithms Using Hitting Times.
SIAM J. Comput., 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 B, 1998

Isoperimetric Inequalities for Cartesian Products of Graphs.
Comb. Probab. Comput., 1998

Analyzing Glauber Dynamics by Comparison of Markov Chains.
Proceedings of the LATIN '98: Theoretical Informatics, 1998

1997
Score certificates for tournaments.
J. 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

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.
Discret. Appl. Math., 1995

1994
An Extension of Foster's Network Theorem.
Comb. Probab. Comput., 1994

1993
Collisions Among Random Walks on a Graph.
SIAM J. Discret. Math., 1993

Communication Complexity and Quasi Randomness.
SIAM J. Discret. Math., 1993

1991
Applications and Analysis of Probabilistic Techniques.
PhD thesis, 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


  Loading...