Approximating Minimum Spanning Trees in Metrics under Semi-Random Corruptions
Aditya Anand, Anupam Gupta, Rajesh Jayaram, Euiwoong Lee, Ali Vakilian
AI 速览：研究在半随机损坏的度量空间中近似最小生成树，针对距离只增、只减和任意改变三种情形给出近似算法与下界。
We study the problem of finding minimum spanning trees in semi-random corrupted metrics. In this problem proposed by Bateni, Dharangutte, Jayaram, and Wang (COLT'24), we start with a metric space $\mathcal{M} = (X, d)$. The adversary independently corrupts each pairwise distance with probability $p$. The algorithm only observes these possibly corrupted distances and must output a spanning tree whose expected cost (in the true metric) is multiplicatively close to the minimum spanning tree cost. Prior work showed that losing a factor of $Ω(\log n)$ is necessary, even if the algorithm may adaptively select $O(n/\log n)$ points and probe the true distances between them. However, no upper bounds were known. We study three regimes based on whether the adversary can only increase, decrease, or arbitrarily change the corrupted distances. We show the following: (1) In the increase-only setting, we give a polynomial-time $O(1)$-approximation algorithm for any constant $0 \le p < 1$. (2) In the decrease-only setting, we give an $O(\log n)$-approximation algorithm for any constant $0 \le p < 1$. Additionally, we show an $O(\log^4 n)$-approximation algorithm that runs in quasi-polynomial time $n^{O(\log n)}$, for any constant $p \leq 0.1$. Moreover, we show that a polynomial-time algorithm computing an $n^{1/3-\varepsilon}$-approximation is unlikely to exist. (3) In the general setting, where the adversary can both increase and decrease distances, we show an $O(\log n)$-approximation algorithm for every $0 \leq p < \frac{1}{4}$. Further, we show that no $o(n)$-approximation is possible for $\frac{1}{2} \leq p < 1$. Our algorithms answer the main open question in Bateni et al.'s work; moreover, the $O(\log n)$-approximations in the latter two settings are information-theoretically optimal.
We present the first local FPT algorithm for finding important separators: Given an undirected graph $G$ with $n$ vertices and $m$ edges, vertices $s,t$ and parameters $k$ and $ν$, we can enumerate all $s$-$t$ important separators of size at most $k$ and volume at most $ν$ in time $\tilde{O}(ν2^{O(k)})$. Known approaches spend either $Ω(m)$ time (not local) or $ν^{Ω(k)}$ time (not FPT). Using this local algorithm, we show the following applications. (1) The first is an improved construction of unbreakable decomposition, a powerful generalization of tree decompositions. For any $k$, we can compute a $(5k,k)$-unbreakable decomposition with adhesion $4k$ in $\tilde{O}(k^{O(k)}m)$ time. This strictly subsumes the result of Anand, Lee, Li, Long, and Saranurak (SODA 2025) and is faster than the recent $O(k^{O(k^2)}m)$-time algorithm by Korhonen (STOC 2025) when $k = ω\Bigl(\sqrt{\frac{\log \log n}{\log \log \log n}}\Bigr)$. Our algorithm is also simpler than that of Korhonen (STOC 2025). (2) We give a near-linear time algorithm for single-sink important separators. For any sink $t$, we can list all $v$-$t$ important separators of size at most $k$ across all $v \in V(G)$ in time $\tilde{O}(2^{O(k)}m)$. Known approaches trivially compute $v$-$t$ important separators for each $v$, taking $Ω(4^k k mn)$ time. (3) Using the above result on single-sink important separators, we speed up undirected shadow removal and give the first almost-linear time FPT algorithm for Edge Multicut.
David P. Woodruff, Vincent Cohen-Addad, Lalit Jain, Jieming Mao, Song Zuo, MohammadHossein Bateni, Simina Branzei, Michael P. Brenner 等 36 位作者
Recent advances in large language models (LLMs) have opened new avenues for accelerating scientific research. While models are increasingly capable of assisting with routine tasks, their ability to contribute to novel, expert-level mathematical discovery is less understood. We present a collection of case studies demonstrating how researchers have successfully collaborated with advanced AI models, specifically Google's Gemini-based models (in particular Gemini Deep Think and its advanced variants), to solve open problems, refute conjectures, and generate new proofs across diverse areas in theoretical computer science, as well as other areas such as economics, optimization, and physics. Based on these experiences, we extract common techniques for effective human-AI collaboration in theoretical research, such as iterative refinement, problem decomposition, and cross-disciplinary knowledge transfer. While the majority of our results stem from this interactive, conversational methodology, we also highlight specific instances that push beyond standard chat interfaces. These include deploying the model as a rigorous adversarial reviewer to detect subtle flaws in existing proofs, and embedding it within a "neuro-symbolic" loop that autonomously writes and executes code to verify complex derivations. Together, these examples highlight the potential of AI not just as a tool for automation, but as a versatile, genuine partner in the creative process of scientific discovery.