Prasad Tetali

About

Prasad Tetali is the Alexander M. Knaster Professor and Department Head of the Department of Mathematical Sciences at Carnegie Mellon University. He also holds adjunct positions at Emory University in the Math/CS department and at Georgia Institute of Technology in the Math/CoC department. His research focuses on combinatorics, probability, graph theory, and theoretical computer science, with significant contributions to the understanding of mixing times of Markov chains, graph expansion, and combinatorial optimization. Tetali has authored books on recent trends in combinatorics and the mathematical aspects of mixing times of Markov chains, and his extensive publication record includes influential papers on topics such as sampling algorithms, phase transitions in statistical physics models, and inequalities in graph theory. His work is characterized by a rigorous approach to complex problems in discrete mathematics and theoretical computer science, making him a prominent figure in these fields.

Research topics

• Computer Science
• Mathematics
• Political Science
• Sociology
• Statistics
• Physics
• Combinatorics
• Library science
• Law
• Algorithm

Selected publications

• On the zeroes of hypergraph independence polynomials

  Combinatorics Probability Computing · 2023-09-21 · 6 citations

  articleOpen accessSenior author

  Abstract We study the locations of complex zeroes of independence polynomials of bounded-degree hypergraphs. For graphs, this is a long-studied subject with applications to statistical physics, algorithms, and combinatorics. Results on zero-free regions for bounded-degree graphs include Shearer’s result on the optimal zero-free disc, along with several recent results on other zero-free regions. Much less is known for hypergraphs. We make some steps towards an understanding of zero-free regions f…

  PublisherOA PDFDOI

• Toppleable permutations, excedances and acyclic orientations

  Combinatorial Theory · 2022-03-29 · 3 citations

  articleOpen accessSenior author

  Recall that an excedance of a permutation $\pi$ is any position $i$ such that $\pi_i > i$. Inspired by the work of Hopkins, McConville and Propp (Elec. J. Comb., 2017) on sorting using toppling, we say that a permutation is toppleable if it gets sorted by a certain sequence of toppling moves. One of our main results is that the number of toppleable permutations on $n$ letters is the same as those for which excedances happen exactly at $\{1,\dots, \lfloor (n-1)/2 \rfloor\}$. Additionally, we s…

  PublisherOA PDFDOI

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

  SIAM Journal on Computing · 2023-03-09 · 2 citations

  articleSenior author

  We study the Generalized Min Sum Set Cover (GMSSC) problem, wherein given a collection of hyperedges with arbitrary covering requirements , the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge is considered covered by the first time when and many of its vertices appear in the ordering. We give a approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all ) of Min Sum S…

  PublisherDOI

• Determinant Maximization via Matroid Intersection Algorithms

  2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) · 2022-10-01 · 2 citations

  articleSenior author

  Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics [1], convex geometry [2], fair allocations [3], combinatorics [4], spectral graph theory [5], network design, and random processes [6]. In an instance of a determinant maximization problem, we are given a collection of vectors $U=\{v_{1},\cdots,\ v_{n}\}\subset \mathbb{R}^{d}$, and a goal is to pick a subset $S\subseteq U$ of given vectors to maximize the determinant of the…

  PublisherDOI

• Hardness and approximation of submodular minimum linear ordering problems

  Mathematical Programming · 2023-12-14 · 1 citations

  articleOpen access

  Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost $$f(\cdot )$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mo>·</mml:mo> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> due to an ordering $$\sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>σ</mm…

  PublisherOA PDFDOI

Recent grants

• Displacement Convexity, Curvature and Concentration in Discrete Settings

  NSF · $288k · 2014–2018

• Discrete Convexity, Curvature, and Implications

  NSF · $190k · 2018–2021

• Graph Homomorphisms, Stochastic Networks, Discrete Mass Transport

  NSF · $148k · 2004–2008

Frequent coauthors

• Uriel Feige

  32 shared

• Vijay V. Vazirani

  University of California, Irvine

  29 shared

• Ravi Montenegro

  University of Massachusetts Lowell

  29 shared

• Wen Huang

  University of Science and Technology of China

  27 shared

• Rui Che

  Hefei Institutes of Physical Science

  27 shared

• Yao Li

  University of Massachusetts Amherst

  26 shared

• Aranyak Mehta

  25 shared

• Gerio Brito

  Springer Nature (Germany)

  25 shared

Education

• M.S., Bangalore, India

  Indian Institute of Science

• Ph.D., New York University

  Courant Institute of Mathematical Sciences

Awards & honors

• AAAS Fellow
• Georgia Tech's Regents Professor
• Fellow of the American Mathematical Society
• SIAM Fellow

Similar researchers at Carnegie Mellon University

• Alan Friezeh-74
• Michael Youngh-57
• David Kinderlehrerh-45