Departmental Colloquium
Lev Reyzin
UIC
On Finding Planted Cliques and Solving Random Linear Equations
Abstract: I will describe the planted clique problem, a famous problem at the intersection of combinatorics and computer science. I will discuss progress on this problem, as well as recent hardness results we've been able to prove. I will also talk about its relationship to the problem of solving linear equations over GF(2), via what are known as "statistical queries".
Friday September 20, 2013 at 3:00 PM in SEO 636