2 papers
cs.DS2023
Simpler Reductions from Exact Triangle
Timothy M. Chan, Yinzhan Xu
In this paper, we provide simpler reductions from Exact Triangle to two important problems in fine-grained complexity: Exact Triangle with Few Zero-Weight -Cycles and All-Edges…
cs.DS2023
Faster Algorithms for Text-to-Pattern Hamming Distances
Timothy M. Chan, Ce Jin, Virginia Vassilevska Williams +1
We study the classic Text-to-Pattern Hamming Distances problem: given a pattern of length and a text of length , both over a polynomial-size alphabet, compute the Ha…