Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time
{{output}}
We derandomize Valiant's (J ACM 62, Article 13, 2015) subquadratic-time algorithm for finding outlier correlations in binary data. This demonstrates that it is possible to perform a deterministic subquadratic-time similarity join of high dimensionality. Our de... ...
