Zobrazeno 1 - 10
of 42
pro vyhledávání: '"Xu, Yinzhan"'
Autor:
Aamand, Anders, Chen, Justin Y., Dalirrooyfard, Mina, Mitrović, Slobodan, Nevmyvaka, Yuriy, Silwal, Sandeep, Xu, Yinzhan
Given an undirected, weighted $n$-vertex graph $G = (V, E, w)$, a Gomory-Hu tree $T$ is a weighted tree on $V$ such that for any pair of distinct vertices $s, t \in V$, the Min-$s$-$t$-Cut on $T$ is also a Min-$s$-$t$-Cut on $G$. Computing a Gomory-H
Externí odkaz:
http://arxiv.org/abs/2408.01798
Single Source Shortest Paths ($\textrm{SSSP}$) is among the most well-studied problems in computer science. In the incremental (resp. decremental) setting, the goal is to maintain distances from a fixed source in a graph undergoing edge insertions (r
Externí odkaz:
http://arxiv.org/abs/2407.09651
Autor:
Alman, Josh, Duan, Ran, Williams, Virginia Vassilevska, Xu, Yinzhan, Xu, Zixuan, Zhou, Renfei
We present a new improvement on the laser method for designing fast matrix multiplication algorithms. The new method further develops the recent advances by [Duan, Wu, Zhou FOCS 2023] and [Vassilevska Williams, Xu, Xu, Zhou SODA 2024]. Surprisingly t
Externí odkaz:
http://arxiv.org/abs/2404.16349
Autor:
Jin, Ce, Xu, Yinzhan
In sparse convolution-type problems, a common technique is to hash the input integers modulo a random prime $p\in [Q/2,Q]$ for some parameter $Q$, which reduces the range of the input integers while preserving their additive structure. However, this
Externí odkaz:
http://arxiv.org/abs/2403.20326
We study the classic Text-to-Pattern Hamming Distances problem: given a pattern $P$ of length $m$ and a text $T$ of length $n$, both over a polynomial-size alphabet, compute the Hamming distance between $P$ and $T[i\, .\, . \, i+m-1]$ for every shift
Externí odkaz:
http://arxiv.org/abs/2310.13174
We provide a variety of lower bounds for the well-known shortcut set problem: how much can one decrease the diameter of a directed graph on $n$ vertices and $m$ edges by adding $O(n)$ or $O(m)$ of shortcuts from the transitive closure of the graph. O
Externí odkaz:
http://arxiv.org/abs/2310.12051
Autor:
Chan, Timothy M., Xu, Yinzhan
In this paper, we provide simpler reductions from Exact Triangle to two important problems in fine-grained complexity: Exact Triangle with Few Zero-Weight $4$-Cycles and All-Edges Sparse Triangle. Exact Triangle instances with few zero-weight $4$-cyc
Externí odkaz:
http://arxiv.org/abs/2310.11575
We study finding and listing $k$-cliques in a graph, for constant $k\geq 3$, a fundamental problem of both theoretical and practical importance. Our main contribution is a new output-sensitive algorithm for listing $k$-cliques in graphs, for arbitrar
Externí odkaz:
http://arxiv.org/abs/2307.15871
The main contribution of this paper is a new improved variant of the laser method for designing matrix multiplication algorithms. Building upon the recent techniques of [Duan, Wu, Zhou, FOCS 2023], the new method introduces several new ingredients th
Externí odkaz:
http://arxiv.org/abs/2307.07970
In this paper we carefully combine Fredman's trick [SICOMP'76] and Matou\v{s}ek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity: - Under the hypothesis that APSP for undirected graphs with edge weights
Externí odkaz:
http://arxiv.org/abs/2303.14572