

Bristol Algorithms Days 2016 Workshop on Efficient Algorithms and Lower Bounds
2  3 February 2016

Algorithms and barriers for random hypergraph partitioning
Will Perkins
I will discuss the algorithmic problem of finding a planted partition
in a random kuniform hypergraph. Unlike the case k=2 (the stochastic
block model), for k >=3 there are edge distributions that exhibit an
algorithmic gap: while O(n) edges are needed to find the partition
information theoretically, the best known polynomialtime algorithms
require n^{k/2} edges to find it. I will discuss algorithms,
algorithmic barriers, and connections to the related problems of
planted CSP's and random kSAT refutation.
Back
 