Lev Reyzin : On Finding Planted Cliques and Solving Random Linear Equations

Posted by Isaac Goldbring , part of the Departmental Colloquium.

At

Sept. 20, 2013, 3 p.m.

In

SEO 636

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".