Prasad Tetali
Professor and Department Head Carnegie Mellon University
- Pittsburgh PA
Prasad Tetali's research interests are in the areas of discrete math, probability and theory of computing.
Biography
Areas of Expertise
Media Appearances
Movie Math: Tetali's Equations Seen in Film
Carnegie Mellon University online
2022-09-26
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.
Media
Social
Industry Expertise
Accomplishments
SIAM Fellow
2009
Georgia Tech’s Regents Professor
2017
Fellow of the American Mathematical Society
2012
Education
Courant Institute of Mathematical Sciences
Ph.D.
1991
Indian Institute of Science
M.S.
1987
Affiliations
- Society for Industrial and Applied Mathematics (SIAM)
- American Association for the Advancement of Science (AAAS)
- American Mathematical Society (AMS)
Event Appearances
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
“Collaborative Education: Data-driven Discovery and Alliance"
NSF Grant 1839339 TRIPODS+X:EDU
For 24 months, starting 1/1/2019
“Discrete convexity, curvature, and implications”
NSF Grant DMS-1811935
For 36 months, starting 8/2/2018
On creating the “Transdisciplinary Institute for Advancing Data Science (TRIAD)”
NSF TRIPODS Grant (Phase 1) 1740776
For 36 months, starting 9/1/2017
Articles
On Min Sum Vertex Cover and Generalized Min Sum Set Cover
SIAM Journal on Computing2023
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.
On the bipartiteness constant and expansion of Cayley graphs
European Journal of Combinatorics2022
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.
On the number of independent sets in uniform, regular, linear hypergraphs
European Journal of Combinatorics2022
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).
Volume growth, curvature, and Buser-type inequalities in graphs
International Mathematics Research Notices2021
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.
Markov chain-based sampling for exploring RNA secondary structure under the nearest neighbor thermodynamic model and extended applications
Mathematical and Computational Applications2020
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.
