ECCC-Report TR12-006https://eccc.weizmann.ac.il/report/2012/006Comments and Revisions published for TR12-006en-usSun, 05 Feb 2012 01:04:11 +0200
Revision 2
| Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise |
Gregory Valiant
https://eccc.weizmann.ac.il/report/2012/006#revision2Given a set of $n$ random $d$-dimensional boolean vectors with the promise that two of them are $\rho$-correlated with each other, how quickly can one find the two correlated vectors? We present a surprising and simple algorithm which, for any constant $\epsilon>0$ runs in (expected) time $d n^{\frac{3 \omega}{4}+\epsilon} poly(\frac{1}{\rho})< d n^{1.8} \cdot poly(\frac{1}{\rho}),$ where $\omega<2.4$ is the exponent of matrix multiplication. This is the first subquadratic-time algorithm for this problem with polynomial dependence on $\frac{1}{\rho},$ and improves upon $O(d n^{2-O(\rho)}),$ given by Paturi et al., the `Locality Sensitive Hashing' approach of Gionis et al., and the `Bucketing Codes' approach of Dubiner.
This basic algorithm also applies to the adversarial setting, and extensions of this algorithm yield improved algorithms for several other problems, including learning sparse parities with noise, and learning juntas both with, and without noise.
Sun, 05 Feb 2012 01:04:11 +0200https://eccc.weizmann.ac.il/report/2012/006#revision2
Revision 1
| Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise |
Gregory Valiant
https://eccc.weizmann.ac.il/report/2012/006#revision1Given a set of $n$ random $d$-dimensional boolean vectors with the promise that two of them are $\rho$-correlated with each other, how quickly can one find the two correlated vectors? We present a surprising and simple algorithm which, for any constant $\epsilon>0$ runs in (expected) time $d n^{\frac{3 \omega}{4}+\epsilon} poly(\frac{1}{\rho})< d n^{1.8} \cdot poly(\frac{1}{\rho}),$ where $\omega<2.4$ is the exponent of matrix multiplication. This is the first subquadratic-time algorithm for this problem with polynomial dependence on $\frac{1}{\rho},$ and improves upon $O(d n^{2-O(\rho)}),$ given by Paturi et al., the `Locality Sensitive Hashing' approach of Gionis et al., and the `Bucketing Codes' approach of Dubiner.
This basic algorithm also applies to the adversarial setting, and extensions of this algorithm yield improved algorithms for several other problems, including learning sparse parities with noise, and learning juntas both with, and without noise.
Sun, 05 Feb 2012 01:03:05 +0200https://eccc.weizmann.ac.il/report/2012/006#revision1
Paper TR12-006
| Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise |
Gregory Valiant
https://eccc.weizmann.ac.il/report/2012/006Given a set of $n$ random $d$-dimensional boolean vectors with the promise that two of them are $\rho$-correlated with each other, how quickly can one find the two correlated vectors? We present a surprising and simple algorithm which, for any constant $\epsilon>0$ runs in (expected) time $d n^{\frac{3 \omega}{4}+\epsilon} poly(\frac{1}{\rho})< d n^{1.8} \cdot poly(\frac{1}{\rho}),$ where $\omega<2.4$ is the exponent of matrix multiplication. This is the first subquadratic-time algorithm for this problem with polynomial dependence on $\frac{1}{\rho},$ and improves upon $O(d n^{2-O(\rho)}),$ given by Paturi et al., the `Locality Sensitive Hashing' approach of Gionis et al., and the `Bucketing Codes' approach of Dubiner.
This basic algorithm also applies to the adversarial setting, and extensions of this algorithm yield improved algorithms for several other problems, including learning sparse parities with noise, and learning juntas with noise.
Tue, 24 Jan 2012 05:37:02 +0200https://eccc.weizmann.ac.il/report/2012/006