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
• Statistical physics
• Geometry

Selected publications

• Faster Mixing for Triangulations via Transport Flows

  ArXiv.org · 2026-05-03

  articleOpen accessSenior author

  We prove an $\widetilde O(n^2)$ bound for the \emph{relaxation time} and the \emph{log-Sobolev time} (inverse log-Sobolev constant) of the classical triangulation flip chain on a convex $(n+2)$-gon, implying a mixing time of $\widetilde O(n^2)$. The previous state of the art for the mixing time of this chain, due to Eppstein and Frishberg, was $\widetilde O(n^3)$, while the best known lower bound on the mixing time, due to Molloy, Reed, and Steiger, is $Ω(n^{3/2})$. Our relaxation time bound makes significant progress towards Aldous' conjectured bound of $Θ(n^{3/2})$ for the relaxation time. We improve upon the analysis of Eppstein and Frishberg by further developing the framework of \emph{transport flows} introduced in the work of Chen et al. In this light, our results can be seen as a more efficient way of using combinatorial decompositions to obtain functional inequalities for Markov chains. We hope our ideas will find other applications in the future.

  PublisherOA PDF

• Faster Mixing for Triangulations via Transport Flows

  arXiv (Cornell University) · 2026-05-03

  preprintOpen accessSenior author

  We prove an $\widetilde O(n^2)$ bound for the \emph{relaxation time} and the \emph{log-Sobolev time} (inverse log-Sobolev constant) of the classical triangulation flip chain on a convex $(n+2)$-gon, implying a mixing time of $\widetilde O(n^2)$. The previous state of the art for the mixing time of this chain, due to Eppstein and Frishberg, was $\widetilde O(n^3)$, while the best known lower bound on the mixing time, due to Molloy, Reed, and Steiger, is $Ω(n^{3/2})$. Our relaxation time bound makes significant progress towards Aldous' conjectured bound of $Θ(n^{3/2})$ for the relaxation time. We improve upon the analysis of Eppstein and Frishberg by further developing the framework of \emph{transport flows} introduced in the work of Chen et al. In this light, our results can be seen as a more efficient way of using combinatorial decompositions to obtain functional inequalities for Markov chains. We hope our ideas will find other applications in the future.

  PublisherDOI

• Note on the number of antichains in generalizations of the boolean lattice

  Combinatorial Theory · 2025-03-14

  articleOpen accessSenior author

  We give a short and self-contained argument that shows that, for any positive integers \(t\) and \(n\) with \(t =O\Bigl(\frac{n}{\log n}\Bigr)\), the number \(\alpha([t]^n)\) of antichains of the poset \([t]^n\) is at most \[{\exp_2\Bigl[\Bigl(1+O\Bigl(\Bigl(\frac{t\log^3 n}{n}\Bigr)^{1/2}\Bigr)\Bigr)N(t,n)\Bigr]}\,,\] where \(N(t,n)\) is the size of a largest level of \([t]^n\). This, in particular, says that if \({t \!\ll\! n/\log^3 \! n}\) as \(n \rightarrow \infty\), then \(\log\alpha([t]^n)=(1+o(1))N(t,n)\), giving a (partially) positive answer to a question of Moshkovitz and Shapira for \(t, n\) in this range. Particularly for \(t=3\), we prove a better upper bound: \[\log\alpha([3]^n)\le(1+4\log 3/n)N(3,n),\] which is the best known upper bound on the number of antichains of \([3]^n\).Mathematics Subject Classifications: 05A16, 06A07Keywords: Boolean lattice, antichains, entropy method

  PublisherOA PDFDOI

• ImProver: Agent-Based Automated Proof Optimization

  arXiv (Cornell University) · 2024-10-07

  preprintOpen access

  Large language models (LLMs) have been used to generate formal proofs of mathematical theorems in proofs assistants such as Lean. However, we often want to optimize a formal proof with respect to various criteria, depending on its downstream use. For example, we may want a proof to adhere to a certain style, or to be readable, concise, or modularly structured. Having suitably optimized proofs is also important for learning tasks, especially since human-written proofs may not optimal for that purpose. To this end, we study a new problem of automated proof optimization: rewriting a proof so that it is correct and optimizes for an arbitrary criterion, such as length or readability. As a first method for automated proof optimization, we present ImProver, a large-language-model agent that rewrites proofs to optimize arbitrary user-defined metrics in Lean. We find that naively applying LLMs to proof optimization falls short, and we incorporate various improvements into ImProver, such as the use of symbolic Lean context in a novel Chain-of-States technique, as well as error-correction and retrieval. We test ImProver on rewriting real-world undergraduate, competition, and research-level mathematics theorems, finding that ImProver is capable of rewriting proofs so that they are substantially shorter, more modular, and more readable.

  PublisherOA PDFDOI

• Note on the number of antichains in generalizations of the Boolean lattice

  arXiv (Cornell University) · 2023-05-25

  preprintOpen accessSenior author

  We give a short and self-contained argument that shows that, for any positive integers $t$ and $n$ with $t =O\Bigl(\frac{n}{\log n}\Bigr)$, the number $α([t]^n)$ of antichains of the poset $[t]^n$ is at most \[\exp_2\Bigl(1+O\Bigl(\Bigl(\frac{t\log^3 n}{n}\Bigr)^{1/2}\Bigr)\Bigr)N(t,n)\,,\] where $N(t,n)$ is the size of a largest level of $[t]^n$. This, in particular, says that if $t \ll n/\log^3 n$ as $n \rightarrow \infty$, then $\logα([t]^n)=(1+o(1))N(t,n)$, giving a (partially) positive answer to a question of Moshkovitz and Shapira for $t, n$ in this range. Particularly for $t=3$, we prove a better upper bound: \[\logα([3]^n)\le(1+4\log 3/n)N(3,n),\] which is the best known upper bound on the number of antichains of $[3]^n$.

  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 Set Cover (MSSC) studied by Feige, Lovász, and Tetali, and improving upon the previous best known bound of due to Im, Sviridenko, and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable kernel and applying randomized rounding. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Min Sum Vertex Cover (MSVC) is a well-known special case of MSSC in which the input hypergraph is a graph (i.e., ) and for every edge . We give a approximation for MSVC and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best approximation of Barenholz, Feige, and Peleg. Finally, we revisit MSSC and consider the norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of for all , giving another proof of the result of Golovin, Gupta, Kumar, and Tangwongsan, and showing its tightness up to NP-hardness. For , this gives yet another proof of the 4 approximation for MSSC.

  PublisherDOI

• 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 for bounded-degree hypergaphs by proving that all hypergraphs of maximum degree $\Delta$ have a zero-free disc almost as large as the optimal disc for graphs of maximum degree $\Delta$ established by Shearer (of radius $\sim 1/(e \Delta )$ ). Up to logarithmic factors in $\Delta$ this is optimal, even for hypergraphs with all edge sizes strictly greater than $2$ . We conjecture that for $k\ge 3$ , $k$ -uniform linear hypergraphs have a much larger zero-free disc of radius $\Omega (\Delta ^{- \frac{1}{k-1}} )$ . We establish this in the case of linear hypertrees.

  PublisherOA PDFDOI

• 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>σ</mml:mi> </mml:math> of the items (say [ n ]), i.e., $$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mo>min</mml:mo> <mml:mi>σ</mml:mi> </mml:msub> <mml:msub> <mml:mo>∑</mml:mo> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>[</mml:mo> <mml:mi>n</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:msub> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>E</mml:mi> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>σ</mml:mi> </mml:mrow> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , where $$E_{i,\sigma }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>E</mml:mi> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>,</mml:mo> <mml:mi>σ</mml:mi> </mml:mrow> </mml:msub> </mml:math> is the set of items mapped by $$\sigma $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>σ</mml:mi> </mml:math> to indices [ i ]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a $$(2-\frac{1+\ell _{f}}{1+|E|})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>2</mml:mn> <mml:mo>-</mml:mo> <mml:mfrac> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mi>f</mml:mi> </mml:msub> </mml:mrow> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mo>|</mml:mo> <mml:mi>E</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> </mml:mfrac> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximation for monotone submodular MLOP where $$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mi>f</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mfrac> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:msub> <mml:mo>max</mml:mo> <mml:mrow> <mml:mi>x</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>E</mml:mi> </mml:mrow> </mml:msub> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mo>{</mml:mo> <mml:mi>x</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:mfrac> </mml:mrow> </mml:math> satisfies $$1 \le \ell _f \le |E|$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>≤</mml:mo> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mi>f</mml:mi> </mml:msub> <mml:mo>≤</mml:mo> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>E</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . Our theory provides new approximation bounds for special cases of the problem, in particular a $$(2-\frac{1+r(E)}{1+|E|})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>2</mml:mn> <mml:mo>-</mml:mo> <mml:mfrac> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>r</mml:mi> <mml:mo>(</mml:mo> <mml:mi>E</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mo>|</mml:mo> <mml:mi>E</mml:mi> <mml:mo>|</mml:mo> </mml:mrow> </mml:mfrac> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> -approximation for the matroid MLOP, where $$f = r$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>=</mml:mo> <mml:mi>r</mml:mi> </mml:mrow> </mml:math> is the rank function of a matroid. We further show that minimum latency vertex cover is $$\frac{4}{3}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mn>4</mml:mn> <mml:mn>3</mml:mn> </mml:mfrac> </mml:math> -approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest.

  PublisherOA PDFDOI

• 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 matrix $\displaystyle \sum_{i\in S}v_{i}v_{i}^{\text{T}}$. Often, the set S of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint $(|S|\leq k)$ or matroid constraint $(S$ is a basis of a matroid defined on the vectors). In this paper, we give a polynomial-time deterministic algorithm that returns a $r^{O(r)}$-approximation for any matroid of rank $r \leq d$. This improves previous results that give $e^{O(r^{2})}$-approximation algorithms relying on $e^{O(r)}$-approximate estimation algorithms [4], [7] –[9] for any r$\leq$d. All previous results use convex relaxations and their relationship to stable polynomials and strongly $\log$-concave polynomials or non-convex relaxations for the problem [10]. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an alternating negative cycle in the exchange graph defined by the matroids. While the $\det(.)$ function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

  PublisherDOI

• Determinant Maximization via Matroid Intersection Algorithms

  arXiv (Cornell University) · 2022-07-09

  preprintOpen accessSenior author

  Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics \cite{pukelsheim2006optimal}, convex geometry \cite{Khachiyan1996}, fair allocations\linebreak \cite{anari2016nash}, combinatorics \cite{AnariGV18}, spectral graph theory \cite{nikolov2019proportional}, network design, and random processes \cite{kulesza2012determinantal}. In an instance of a determinant maximization problem, we are given a collection of vectors $U=\{v_1,\ldots, v_n\} \subset \RR^d$, and a goal is to pick a subset $S\subseteq U$ of given vectors to maximize the determinant of the matrix $\sum_{i\in S} v_i v_i^\top $. Often, the set $S$ of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint $\left(|S|\leq k\right)$ or matroid constraint ($S$ is a basis of a matroid defined on the vectors). In this paper, we give a polynomial-time deterministic algorithm that returns a $r^{O(r)}$-approximation for any matroid of rank $r\leq d$. This improves previous results that give $e^{O(r^2)}$-approximation algorithms relying on $e^{O(r)}$-approximate \emph{estimation} algorithms \cite{NikolovS16,anari2017generalization,AnariGV18,madan2020maximizing} for any $r\leq d$. All previous results use convex relaxations and their relationship to stable polynomials and strongly log-concave polynomials. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an \emph{alternating negative cycle} in the \emph{exchange graph} defined by the matroids. While the $\det(.)$ function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.

  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

• Random graph interpolation, Sumset inequalities and Submodular problems

  NSF · $200k · 2011–2014

• EAGER: Physical Flow and other Industrial Challenges

  NSF · $300k · 2014–2017

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