BAD'16 Poster

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 k-uniform 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 polynomial-time 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 k-SAT refutation.


  The University of Bristol   EPSRC