[MPRI 2014] 1.24 Randomized Algorithms - Lecture 3 (Part C/C)

MPRI 1.24 - Randomized Algorithms - Nicolas Schabanel <br /> <br />Lecture 3 (Part C/C): Thursday Feb 6, 8:45-11:45 - Streaming, Property testing, Self-correction <br />• Streaming algorithm for computing the second moment of frequencies F2 : 4-wise independent hash functions <br />• Self-correcting integer product <br /> <br />Exercise session 3: PDF Due on Thursday Feb 13 before noon <br />• A Fixed Parameter Tractable algorithm for finding k disjoints triangles <br />• A deterministic algorithm for uniformity dectection <br />• Matrix multiplication testing