Undergraduate summer research project: The hidden clique problem
Sophia Zhang · 2013
We consider the problem of nding a hidden clique in a random graph. This problem was studied by Alon, Krivelevich and Sudakov in 1998. Using Matlab, we wrote two algorithms that are designed to nd a hidden clique. One of the algorithms was suggested by the work of Alon, Krivelevich and Sudakov. The other algorithm is a slight variation that seems to perform better in our experiments.