Dirac's theorem says that any n-vertex graph with minimum degree at least n/2 contains a Hamiltonian cycle. A robust version of Dirac's theorem was obtained by Krivelevich, Lee and Sudakov: for such graphs, if we take a random subgraph where every edge is included with probability Clog(n)/n, for some large fixed constant C, then whp the resulting graph is still Hamiltonian. We will discuss some recent results along this line.

The hypergraph community detection problem asks us to find groups of related or similar entities in hypergraph data. While there are many approaches to this problem, this talk will focus on a spectral method that utilizes information from the eigenvectors of the nonbacktracking or Hashimoto matrix. The Hashimoto operator can be shown to be related to belief-propagation for statistical inference, and using this relationship we obtain a performant hypergraph community detection algorithm with well-understood regions of success and failure for the hypergraph stochastic block model. The talk will additionally pose some conjectures on the fundamental limits of community detection in hypergraphs.

Compressed sensing has been a very successful high-dimensional signal acquisition and recovery technique that relies on linear operations. However, the actual measurements of signals have to be quantized before storing or processing. 1(One)-bit compressed sensing is a heavily quantized version of compressed sensing, where each linear measurement of a signal is reduced to just one bit: the sign of the measurement. Once enough of such measurements are collected, the recovery problem in 1-bit compressed sensing aims to find the original signal with as much accuracy as possible. 

For recovery of sparse vectors, a popular reconstruction method from 1-bit measurements is the binary iterative hard thresholding (BIHT) algorithm. The algorithm is a simple projected sub-gradient descent method, and is known to converge well empirically, despite the nonconvexity of the problem. The convergence property of BIHT was not theoretically justified, except with an exorbitantly large number of measurements (i.e., a number of measurement greater than max{k^10,24^48,k^3.5/ϵ}, where k is the sparsity, ϵ denotes the approximation error, and even this expression hides other factors). In this paper we show that the BIHT algorithm converges with only Õ(k/ϵ) measurements. Note that, this dependence on k and ϵ is optimal for any recovery method in 1-bit compressed sensing. With this result, to the best of our knowledge, BIHT is the only practical and efficient (polynomial time) algorithm that requires the optimal number of measurements in all parameters (both k and ϵ). This is also an example of a gradient descent algorithm converging to the correct solution for a nonconvex problem, under suitable structural conditions.

Joint work with Nami Matsumoto.

The Hypergraph Stochastic Block Model (HSBM) is a complex, many-parameter model generalizing the well-known graph SBM--a paradigm for studying community detection. One of the main uses of the (H)SBM is that it allows us to develop guarantees for community detection algorithms by providing thresholds---parameter conditions that theoretically describe the necessary and sufficient requirements for community detection in the model. These thresholds naturally depend on the type of recovery desired.

I will talk about the most general conditions and thresholds we can develop, under various tweaks in the model, for almost exact and exact recovery in more, or less, general HSBM. This is joint work with Haixiao Wang and Yizhe Zhu.