计算语言学国际会议 COLING 2020(The 28th International Conference on Computational Linguistics)是计算语言学和自然语言处理领域的重要国际会议,由ICCL(International Committee on Computational Linguistics)主办,每两年举办一次,是CCF-B类推荐会议。本届COLING 2020将于2020年12月8日至13日以在线会议的形式举办。COLING 2020共计收到2180篇论文投稿,其中包括2021篇主会投稿、48篇Demo投稿、111篇工业论文投稿,最终有1900余篇论文进入审稿流程。官方Twitter公布了最佳论文。



Computing the convolution $A\star B$ of two length-$n$ integer vectors $A,B$ is a core problem in several disciplines. It frequently comes up in algorithms for Knapsack, $k$-SUM, All-Pairs Shortest Paths, and string pattern matching problems. For these applications it typically suffices to compute convolutions of nonnegative vectors. This problem can be classically solved in time $O(n\log n)$ using the Fast Fourier Transform. However, often the involved vectors are sparse and hence one could hope for output-sensitive algorithms to compute nonnegative convolutions. This question was raised by Muthukrishnan and solved by Cole and Hariharan (STOC '02) by a randomized algorithm running in near-linear time in the (unknown) output-size $t$. Chan and Lewenstein (STOC '15) presented a deterministic algorithm with a $2^{O(\sqrt{\log t\cdot\log\log n})}$ overhead in running time and the additional assumption that a small superset of the output is given; this assumption was later removed by Bringmann and Nakos (ICALP '21). In this paper we present the first deterministic near-linear-time algorithm for computing sparse nonnegative convolutions. This immediately gives improved deterministic algorithms for the state-of-the-art of output-sensitive Subset Sum, block-mass pattern matching, $N$-fold Boolean convolution, and others, matching up to log-factors the fastest known randomized algorithms for these problems. Our algorithm is a blend of algebraic and combinatorial ideas and techniques. Additionally, we provide two fast Las Vegas algorithms for computing sparse nonnegative convolutions. In particular, we present a simple $O(t\log^2t)$ time algorithm, which is an accessible alternative to Cole and Hariharan's algorithm. We further refine this new algorithm to run in Las Vegas time $O(t\log t\cdot\log\log t)$, matching the running time of the dense case apart from the $\log\log t$ factor.