2. On the chromatic number of random triangle-free graphs preprint (With Clayton Mizgerd, Will Perkins)
We give evidence of a statistical-computational gap for finding balanced independent sets in random bipartite graphs of average degree d, where d is a large constant. While balanced independent sets of density (2+o_d(1)) log d/d exist whp in such graphs, ther best known efficient algorithm (which is very simple) can only find balanced independent sets of half this size. We show that neither local algorithms nor low-degree algorithms can do better.
The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs, preprint(With Abhishek Dhawan)
We study the algorithmic task of finding large independent sets in Erdos-Renyi r-uniform hypergraphs on n vertices having average degree d. We show that the class of low-degree polynomial algorithms can find independent sets of density (logd(r−1)d)^(1/(r−1)) but no larger. we explore the universality of this gap by examining the problem of finding large balanced independent sets (independent sets containing the same number of vertices in each partition) in random r-partite hypergraphs with n vertices in each partition and average degree d.
We prove that the maximum determinant of an n × n matrix, with entries in {0, 1} and at most n + k nonzero entries, is at most 2^{k/3}, which is best possible when k is a multiple of 3.