We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian as a proxy for robust inference. The previous best algorithms for this model succeed if the planted clique has size at least n^2/3 in a graph with n vertices. Our algorithms work for planted-clique sizes approaching n^1/2 --- the information-theoretic threshold in the semi-random model (Steinhard 2017) and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige and Steinhardt. Our algorithms rely on a new conceptual connection between planted cliques in the semi-random graph model and certificates of upper bounds on unbalanced biclique numbers in Erdős-Rényi random graphs. We show that higher-degree sum-of-squares polynomials allow us to obtain almost tight certificates of this kind. Based on a joint work with Rares-Darius Buhai and Pravesh K. Kothari.

We propose a unified approach to various counting problems in combinatorics (chromatic polynomial), statistics (ML-degree), optimization (algebraic degree of semidefinite programming) and algebraic geometry (characteristic numbers). This leads us to new, natural invariants of tensors. Our works is very much inspired by recent work of Huh (combinatorics and cohomology), Sturmfels and Uhler (ML-degree), Lascaux (symmetric polynomials) and Dimca and Papadima (topology).

In 1968 the Swiss mathematician Strassen attempted to show that the usual way we multiply nxn matrices (row-column, which costs on the order of n³ arithmetic operations) is the best possible. His spectacular failure led to tremendous advances over the next 20 years, which led to the astounding conjecture that as n grows, it becomes nearly as easy to multiply matrices as it is to add them! I will discuss recent approaches to this problem using algebraic geometry and representation theory.