Showing 2024 · cs.DSShow all
2 papers · 2 filters
cs.DS2024
New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
Nick Fischer, Ce Jin, Yinzhan Xu
The 3SUM problem is one of the cornerstones of fine-grained complexity. Its study has led to countless lower bounds, but as has been sporadically observed before -- and as we will…
cs.DS2024
Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More
Ce Jin, Yinzhan Xu
In sparse convolution-type problems, a common technique is to hash the input integers modulo a random prime for some parameter , which reduces the range of the in…