Convolution Witness

Preprocess two vectors $X, Y \in \{0, 1\}^n$ such that upon query of an index $k$ the list of all witnesses $\{(i, j) \in [n]: i+j = k, X[i] = Y [j] = 1\}$ is returned.

Parameters

$n$ : length of vectors

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 5 of 5 reductions


Convolution 3SUM	Convolution Witness	2023
Convolution Witness	Partial Convolution	2016
Convolution Witness	Partial Convolution Indexing	2016
Convolution Witness	Partial Matrix Multiplication	2016
Convolution Witness	Partial Matrix Multiplication Indexing	2016

Other relevant algorithms