Skip to main content

All Questions

Filter by
Sorted by
Tagged with
5 votes
0 answers
167 views

Computing sums with linear conditions quickly

Let $f:\{1,\dotsc,N\}\to \mathbb{C}$, $\beta:\{1,\dotsc,N\}\to [0,1]$ be given by tables (or, what is basically the same, assume their values can be computed in constant time). For $0\leq \gamma_0\leq ...
H A Helfgott's user avatar
  • 20.2k
12 votes
1 answer
562 views

Fast convolution of sparse functions

Let $F:\mathbb{R}\to \mathbb{Z}$ be a step function with at most $k$ discontinuities, at given rationals $a_1<a_2<\dotsc<a_k$. Let $g:\mathbb{R}\to \mathbb{Z}$ be given as a linear ...
H A Helfgott's user avatar
  • 20.2k