hero image
Prasad Tetali - Carnegie Mellon University. Pittsburgh, PA, US

Prasad Tetali

Professor and Department Head | Carnegie Mellon University


Prasad Tetali's research interests are in the areas of discrete math, probability and theory of computing.


Prasad Tetali's research interests are in the areas of discrete math, probability and theory of computing, Markov chains, isoperimetry and functional analysis, combinatorics, computational number theory and algorithms.

Areas of Expertise (7)

Probability and Theory of Computing

Isoperimetry and Functional Analysis

Computational Number Theory

Discrete Math

Markov Chains



Media Appearances (1)

Movie Math: Tetali's Equations Seen in Film

Carnegie Mellon University  online


In the movie, "Jerry & Marge Go Large," a man finds a legal loophole in lotteries. Carnegie Mellon University's Prasad Tetali wrote the on-screen calculations to explain how the math behind that loophole works.

view more



Prasad Tetali Publication Prasad Tetali Publication Prasad Tetali Publication



loading image


Finding Cliques with Few Probes  by Prasad Tetali Oded Schramm Memorial Conference: Day One, Session Three



Industry Expertise (1)


Accomplishments (3)

SIAM Fellow (professional)


Georgia Tech’s Regents Professor


Fellow of the American Mathematical Society


Education (2)

Courant Institute of Mathematical Sciences: Ph.D. 1991

Indian Institute of Science: M.S. 1987

Affiliations (3)

  • Society for Industrial and Applied Mathematics (SIAM)
  • American Association for the Advancement of Science (AAAS)
  • American Mathematical Society (AMS)

Event Appearances (5)

Seminar on Optimization

(2017) Simons Institute  Berkeley, CA

Plenary Speaker

(2017) Shanghai Conference on Combinatorics  China

Combinatorics Seminar

(2017) Stanford University  Palo Alto, CA

Recent Trends in Combinatorics (reunion)

(2016) AMS Special Session  Minneapolis, MN

Probabilistic and Extremal Combinatorics DownUnder

(2016) Monash Workshop  Melbourne, Australia

Research Grants (3)

“Collaborative Education: Data-driven Discovery and Alliance"

NSF Grant 1839339 TRIPODS+X:EDU $200,000

For 24 months, starting 1/1/2019

“Discrete convexity, curvature, and implications”

NSF Grant DMS-1811935 $190,000

For 36 months, starting 8/2/2018

On creating the “Transdisciplinary Institute for Advancing Data Science (TRIAD)”

NSF TRIPODS Grant (Phase 1) 1740776 $1,500,000

For 36 months, starting 9/1/2017

Articles (5)

On Min Sum Vertex Cover and Generalized Min Sum Set Cover

SIAM Journal on Computing

2023 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.

view more

On the bipartiteness constant and expansion of Cayley graphs

European Journal of Combinatorics

2022 Let G be a finite, undirected, d-regular graph and A (G) its normalized adjacency matrix, with eigenvalues 1= λ 1 (A)≥⋯≥ λ n≥− 1. It is a classical fact that λ n=− 1 if and only if G is bipartite. Our main result provides a quantitative separation of λ n from− 1 in the case of Cayley graphs, in terms of their expansion. Denoting h o u t by the (outer boundary) vertex expansion of G, we show that if G is a non-bipartite Cayley graph (constructed using a group and a symmetric generating set of size d) then λ n≥− 1+ c h o u t 2 d 2, for c an absolute constant.

view more

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

European Journal of Combinatorics

2022 We study the problems of bounding the number weak and strong independent sets in r-uniform, d-regular, n-vertex linear hypergraphs with no cross-edges. In the case of weak independent sets, we provide an upper bound that is tight up to the first order term for all (fixed) r≥ 3, with d and n going to infinity. In the case of strong independent sets, for r= 3, we provide an upper bound that is tight up to the second order term, improving on a result of Ordentlich–Roth (2004).

view more

Volume growth, curvature, and Buser-type inequalities in graphs

International Mathematics Research Notices

2021 We study the volume growth of metric balls as a function of the radius in discrete spaces and focus on the relationship between volume growth and discrete curvature. We improve volume growth bounds under a lower bound on the so-called Ollivier curvature and discuss similar results under other types of discrete Ricci curvature.

view more

Markov chain-based sampling for exploring RNA secondary structure under the nearest neighbor thermodynamic model and extended applications

Mathematical and Computational Applications

2020 Ribonucleic acid (RNA) secondary structures and branching properties are important for determining functional ramifications in biology. While energy minimization of the Nearest Neighbor Thermodynamic Model (NNTM) is commonly used to identify such properties (number of hairpins, maximum ladder distance, etc.), it is difficult to know whether the resultant values fall within expected dispersion thresholds for a given energy function.

view more