Tootfinder

Detecting LLM-Generated Short Answers and Effects on Learner Performance
Shambhavi Bhushan, Danielle R Thomas, Conrad Borchers, Isha Raghuvanshi, Ralph Abboud, Erin Gatz, Shivang Gupta, Kenneth Koedinger
https://arxiv.org/abs/2506.17196

Detecting LLM-Generated Short Answers and Effects on Learner Performance
The increasing availability of large language models (LLMs) has raised concerns about their potential misuse in online learning. While tools for detecting LLM-generated text exist and are widely used by researchers and educators, their reliability varies. Few studies have compared the accuracy of detection methods, defined criteria to identify content generated by LLM, or evaluated the effect on learner performance from LLM misuse within learning. In this study, we define LLM-generated text wit…

Deterministic Almost-Linear-Time Gomory-Hu Trees
Amir Abboud, Rasmus Kyng, Jason Li, Debmalya Panigrahi, Maximilian Probst Gutenberg, Thatchaphol Saranurak, Weixuan Yuan, Wuwei Yuan
https://arxiv.org/abs/2507.20354

Deterministic Almost-Linear-Time Gomory-Hu Trees
Given an $m$-edge, undirected, weighted graph $G=(V,E,w)$, a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree over the vertex set $V$ such that all-pairs mincuts in $G$ are preserved exactly in $T$. In this article, we give the first almost-optimal $m^{1+o(1)}$-time deterministic algorithm for constructing a Gomory-Hu tree. Prior to our work, the best deterministic algorithm for this problem dated back to the original algorithm of Gomory and Hu that runs in $nm^{1+o(1)}$ time (using current…

Shortest Paths in Multimode Graphs
Yael Kirkpatrick, Virginia Vassilevska Williams
https://arxiv.org/abs/2506.22261 https://arxiv.org…

Shortest Paths in Multimode Graphs
In this work we study shortest path problems in multimode graphs, a generalization of the min-distance measure introduced by Abboud, Vassilevska W. and Wang in [SODA'16]. A multimode shortest path is the shortest path using one of multiple `modes' of transportation that cannot be combined. This represents real-world scenarios where different modes are not combinable, such as flights operated by different airlines. More precisely, a $k$-multimode graph is a collection of $k$ graphs on the same v…

The perfect spinfluid
Nick Abboud, Lorenzo Gavassino, Rajeev Singh, Enrico Speranza
https://arxiv.org/abs/2506.19786 https://arxiv.or…

The perfect spinfluid
We present a new formulation of non-dissipative relativistic spin hydrodynamics that incorporates spin degrees of freedom into the divergence-type theory framework. Due to the divergence-type structure, it is straightforward to enforce non-linear causality and symmetric hyperbolicity of the equations of motion, ensuring local well-posedness of the initial-value problem and stability of the theory. Furthermore, in a specific realization based on spin kinetic theory, we prove that the equations o…

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
Amir Abboud, Shyan Akmal, Nick Fischer
https://arxiv.org/abs/2507.18845 https://arxi…

A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
We present the first truly subcubic, combinatorial algorithm for detecting an induced $4$-cycle in a graph. The running time is $O(n^{2.84})$ on $n$-node graphs, thus separating the task of detecting induced $4$-cycles from detecting triangles, which requires $n^{3-o(1)}$ time combinatorially under the popular BMM hypothesis. Significant work has gone into characterizing the exact time complexity of induced $H$-detection, relative to the complexity of detecting cliques of various sizes. Prior…

All-Pairs Shortest Paths with Few Weights per Node
Amir Abboud, Nick Fischer, Ce Jin, Virginia Vassilevska Williams, Zoe Xi
https://arxiv.org/abs/2506.20017

All-Pairs Shortest Paths with Few Weights per Node
We study the central All-Pairs Shortest Paths (APSP) problem under the restriction that there are at most $d$ distinct weights on the outgoing edges from every node. For $d=n$ this is the classical (unrestricted) APSP problem that is hypothesized to require cubic time $n^{3-o(1)}$, and at the other extreme, for $d=1$, it is equivalent to the Node-Weighted APSP problem. We present new algorithms that achieve the following results: 1. Node-Weighted APSP can be solved in time $\tilde{O}(n^{(3+ω…