4 papers
A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
Maximilian Probst Gutenberg, Weixuan Yuan
Given an undirected graph , a Gomory-Hu tree (Gomory and Hu, 1961) is a tree on that preserves all-pairs mincuts of exactly. We present a simple and efficien…
A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan +1
Given an undirected graph , a Gomory-Hu tree (Gomory and Hu, 1961) is a tree on that preserves all-pairs mincuts of exactly. We present a simple, efficient r…
Deterministic Almost-Linear-Time Gomory-Hu Trees
Amir Abboud, Rasmus Kyng, Jason Li +5
Given an -edge, undirected, weighted graph , a Gomory-Hu tree (Gomory and Hu, 1961) is a tree over the vertex set such that all-pairs mincuts in are prese…
Assessing GPT Performance in a Proof-Based University-Level Course Under Blind Grading
Ming Ding, Rasmus Kyng, Federico Solda +1
As large language models (LLMs) advance, their role in higher education, particularly in free-response problem-solving, requires careful examination. This study assesses the perfor…