Two Sigma Fellowships recognize doctorate students who are expanding frontiers in a STEM field such as statistics, applied mathematics, computer science, and physics. In our series, The Fellowship Forum, we catch up with past and present Two Sigma Fellows to highlight the fascinating research they’re performing in their respective fields.
Our first feature is Huy Tuan Pham, a Two Sigma Fellow and doctoral student at Stanford’s Mathematics department. We spoke with Huy about how the Two Sigma Fellowship has supported his doctorate journey and his exciting achievement of proving a major open problem in probabilistic combinatorics: the Kahn-Kalai conjecture.
Huy Tuan Pham
Stanford University, Department of Mathematics
How did you first learn about the Two Sigma Fellowship?
I was first introduced to the Two Sigma Fellowship by my advisor, Jacob Fox, Professor of Mathematics at Stanford University.
What drew you to apply to the PhD fellowship?
The Two Sigma PhD Fellowship generously recognizes a broad spectrum of research areas in STEM fields. I felt that my research direction, which centers deeply in mathematics, but reaches out to applications in computer science and machine learning, might be a good fit for the fellowship.
What is your area of research?
My research lies at the intersection of combinatorics, probability theory, and theoretical computer science. The core of my work lies in studying randomness and random objects and utilizing them to understand discrete structures that arise in mathematics and computer science. In one direction, I study asymptotic structure and interesting properties of large random objects and systems such as random networks, randomized algorithms, or randomly initialized neural networks. In another direction, I utilize randomness to study large deterministic networks or arithmetic structures via their random-like components.
What excites you about your field?
What always excites me is how nice structures reveal themselves in random or arbitrary objects. The search for these structures can always be full of surprises, and once one finds a method or principle to extract and control those structures, one can sometimes hope to apply the insights across many different instances or applications where randomness is utilized. Randomness is a very powerful tool with a number of surprising applications; I am still very much excited by the idea of using randomness as a form of structure itself.
How has the Two Sigma PhD Fellowship supported your doctorate journey?
The Two Sigma PhD Fellowship has provided me an opportunity to fully engage and concentrate on challenging research problems in the past year. In fact, my recent works on the Kahn-Kalai conjecture and the related conjectures of Professor Michel Talagrand were both completed while I was supported by the Two Sigma PhD Fellowship.
What advice would you share with others who are considering pursuing a doctorate degree?
Pursuing a doctorate degree is certainly a heavy commitment, and along my on-going journey, I have certainly felt lost and disappointed many times. Nevertheless, I have been able to stay on the right path thanks to constant support and encouragement from my advisor, Jacob Fox. He has always been an amazing source of inspiration for me in mathematics and beyond. My whole journey was made possible because of him, and so from my (limited) experience, I think it is important to choose an advisor with a good match and foster that relationship.
Proving the Kahn-Kalai Conjecture
In April 2022, Huy and Stanford mathematician Jinyoung Park, a Szegö Assistant Professor, proved the Kahn-Kalai Conjecture. Developed in 2006 by Professors Jeff Kahn and Gil Kalai, the conjecture was a major open problem in probabilistic combinatorics that theorized that the threshold and expectation threshold for any monotone property are always within a logarithmic factor of each other. A Quanta Magazine article noted that Szegö Assistant Professor Park and Huy’s work “proves hundreds of more specific statements that would each be very difficult to prove on their own — and it has even deeper consequences for our understanding of random graphs and mathematical sets more broadly.”
“I would call their proof magical,” said Professor Fox in the Quanta Magazine article. “This is going to be a major part of the field going forward.”
What first drew you to attempting to prove the Kahn-Kalai Conjecture?
“Given a network property of interest, what is the density threshold at which a random network typically satisfies the property?” This is one of the most fundamental questions in random graph theory, and even the answer for specific examples of network properties has driven a number of challenging breakthrough works.
On the other hand, the Kahn-Kalai conjecture asserts that there is another quantity, often much easier to compute, which gives an accurate estimation of the threshold for virtually any property of interest. While being extremely general, in many challenging examples, quick applications of the Kahn-Kalai conjecture can pin down the threshold precisely. This is the beauty of the conjecture: it suggests a unifying and general principle behind thresholds that remains immensely powerful in specific instances.
Needless to say, despite the seemingly simple statement, the Kahn-Kalai conjecture is challenging, and the main problem is that there is no clear starting point. In 2019, building on the beautiful breakthrough on the sunflower problem, a weaker (“fractional”) version of the conjecture was resolved by Keith Frankston, Professor Kahn, Assistant Professor Bhargav Narayanan, and Szegö Assistant Professor Park, who was a doctoral student of Professor Kahn at the time. While one way forward to the full “integral” conjecture was to relate it with this fractional version, building this connecting path in general seemed far beyond reach.
When my coauthor, Szegö Assistant Professor Park, arrived at Stanford, we immediately connected. I found her story and pathway to mathematics as a middle school teacher and young mother from Korea very inspiring and resonated with my own experience. Coming from Vietnam, a small developing country, there were hardships to overcome in order to pursue serious mathematics at Stanford, and I could only do so thanks to generous external support and encouragement.
We never set out to prove the Kahn-Kalai conjecture from the beginning. Instead, we started to work on several beautiful conjectures of Professor Talagrand on suprema of stochastic processes, which also came in a weaker fractional version and a full integral version. The path towards the weaker fractional version of Professor Talagrand’s conjecture was bumpy and challenging. Through many months of slow steps in increasing generality and many failed attempts, I finally arrived at a set of ideas that prove this conjecture. It turns out that, in a fortuitous turn of events, one of those ideas provides a starting point towards the Kahn-Kalai conjecture.
What was your approach to proving the conjecture?
While working on the proof of the fractional version of Professor Talagrand’s conjecture, I came up with the idea of “minimal fragment” and how to use it to refine previous techniques. During a visit to a friend in Berkeley, I was playing with this idea in my head to see if it was useful for something else. While having dinner, I had a thought that this idea and its use did not seem confined to the fractional setting.
From that point, I could not stop myself and end up spending the night working out the proof of the integral version in full. By the end of the night, I was convinced that I found the proof to both the Kahn-Kalai conjecture and the full integral version of Professor Talagrand’s conjecture.
In hindsight, the main idea behind the proof of the Kahn-Kalai conjecture is simple and can be naturally motivated. Roughly speaking, the Kahn-Kalai conjecture can be rephrased as showing that, if a family of subnetworks is nice (in the sense that there are not too many small parts in the space where they localize), then a random network would likely contain a subnetwork from the family. Minimal fragments encode the most structured part of each subnetwork in the family based on its interaction with the random network, from which one can relate the nice property of the family of subnetworks to containment by a random network.
With this idea, it is not hard to prove the conjecture; the final proof is quite short and does not need any sophisticated tool. Nevertheless, we would have not been able to find the proof of the Kahn-Kalai conjecture had we not been guided by our attempt at Professor Talagrand’s conjecture.
What does proving the Kahn-Kalai Conjecture mean to you?
I was very happy when I thought that I could prove the Kahn-Kalai conjecture, but quickly had to leave the feelings behind to carefully work out the proof. The day after the night I wrote the first draft of the proof, I met my advisor and shared the news with him. The proof had not been verified by anyone at that point, but we were both ecstatic with the thought that it could work. The next day, I described the proof to my coauthor; looking at the whiteboard in my office, she was amazed that things worked out and couldn’t believe that the difficult question could be solved with a simple and elegant proof. We quickly wrote the paper just a few days after the first draft. In the end, the conjecture was resolved in a mere five pages!
It still excites me now to think about the journey towards the proof of the Kahn-Kalai conjecture. It is a rare, but extremely rewarding experience to see how all the pieces of the puzzle that were gathered from thinking about different questions fit together to sketch out the path towards the right idea.
Afterwards, I was happy to receive warm encouragement from many experts about the work, but it was also special for me to hear from young aspiring students from Vietnam. I hope that this could convince more aspiring mathematicians from developing countries to believe in their potential.
Have you connected with Professor Kahn and Professor Kalai to celebrate?
We reached out to Professor Kahn and Professor Kalai after the paper was finished and they were both excited with the progress. Professor Kalai wrote a nice blog post about the result.
We also got in touch with Professor Talagrand, whose insights and questions had given us crucial guidance throughout. He was happy to see the resolution of his conjectures, and pointed us to a number of important directions and beautiful questions for further investigation.
I am particularly grateful for their encouragement and the insights that they have shared. Insights and wisdom from them as well as many other researchers in the area have played a critical role in our work, and will certainly continue to guide the way to future developments.
What do you hope this means for the mathematical field moving forward?
I think that the resolution of the conjecture certainly does not signify the end of the path, but rather the beginning of a whole new set of directions and questions that are perhaps now inching closer to our reach. Now that we have a principle to estimate thresholds, we could start asking about more accurate estimates and finer aspects of the phenomenon. I think the simplicity and elegance of the proof of the conjecture suggest that we might hopefully be somewhere around the right understanding and starting point for further investigation and development.
What project are you excited about moving forward?
I am certainly very excited to explore the largely uncharted territory beyond the Kahn-Kalai conjecture. On the other hand, together with my advisor and other collaborators, I am also working on different long-standing conjectures in probabilistic and additive combinatorics, and continuing the study of various discrete structures through the lens of randomness. Who knows where the next surprising connection might be hiding?
Applications for Two Sigma fellowships are now open. Visit Academic Partnerships to learn more about the Two Sigma fellowship programs and other opportunities available to undergraduate, graduate students, and professors.