Nate Veldt

My research focuses on combinatorial algorithms and computational methods for data analysis, especially data that can be modeled by a graph or network. This combines interests in CS theory, computational science, discrete mathematics,  and various data science applications.

New and Events

• November 1, 2023. I wrote an article on generalized hypergraph cut problems for this month’s edition of SIAM News. You can read it here or here.
• August 10, 2023. Nature Reviews Physics recently published a Research Spotlight about my research on hypergraph measures of homophily (joint work with Austin Benson and Jon Kleinberg). You can check out the spotlight here.
• August 5, 2023. Our paper on Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling was accepted for publication at CIKM. Congratulations to the lead author, Vedangi Bengali!
• May 16, 2023. My paper with Austin Benson and Jon Kleinberg on Augmented Sparsifiers for Hypergraph Cuts  has been accepted for publication in JMLR.
• April 24, 2023. My paper on improved approximation algorithms for edge-colored hypergraph clustering has been accepted for publication at ICML (Honolulu, HI, July 2023). Here’s a preprint of the paper.
• January 31, 2023. My paper on cut-matching games in hypergraphs was accepted for publication at The Web Conference, (Austin, TX, May 2023). A preprint is now on arXiv.
• January 6, 2023. Our research on “Combinatorial Characterizations and Impossibilities for Higher-order Homophily” (joint with Austin Benson and Jon Kleinberg) has been published in Science Advances. I had a chance to discuss some of this research as part of a recent article in the Communications of the ACM.
• January 5, 2023. I am honored to have been selected for the SIAM SIAG/ACDA Early Career Prize. I look forward to giving a talk on my research at the 2023 ACDA Conference in Seattle, Washington, May 31-June 2. Here’s the TAMU CSE Department news story and SIAM’s prize spotlight article.
• August 4, 2022. Our research on “Hypergraph Cuts with General Splitting Functions” (joint with Austin Benson and Jon Kleinberg) is now published in SIAM Review. Here is a summary by the section editor. My co-author Austin Benson talks a bit more about this research in a Quanta magazine article.
• April 11, 2022. I am honored to be awarded the 2022 Texas A&M Institute of Data Science Career Initiation Fellowship!

See here for earlier news and my news page for more detailed updates.

Broad Interests

Graph Algorithms, Combinatorial Optimization, Network Science,  Matrix Computations,  Data Science.

Recent Interests

• Hypergraph algorithms for higher-order data analysis
• Flow-based methods for community detection
• Approximation algorithms for correlation clustering