ERC Advanced Grant 834861 (2019-2024) "Spectral and Optimization Techniques for Robust Recovery Combinatorial Constructions and Distributed Algorithms" (SO-ReCoDi)

Research Team: Luca Trevisan (PI - Bocconi University and University of California, Berkeley), Jonathan Shi (Research Fellow)

Abstract:
This theoretical computer science proposal develops innovative applications of spectral techniques semidefinite programming and online optimization to three applications: robust algorithms for recovery problems construction of combinatorial objects (such as graph sparsifiers and pseudorandom generators) and distributed graph algorithms. Recovery problems such as finding a planted sparse vector in a random subspace or finding a planted clique in a random graph are motivated by unsupervised machine learning applications.

A robust recovery algorithm is one that works even in presence of adversarial corruptions of the input data. Robust recovery algorithms are motivated by safety and reliability concerns. Sum-of-squares semidefinite programs (a convex optimization technique) will be the main tool for this application domain. The second part of the proposal concerns the use of online optimization techniques together with the theory of semidefinite programming to construct new types of graph sparsifiers better hypergraph sparsifiers and various types of pseudorandom objects. The third part of the proposal concerns the use of spectral techniques and of random matrix analysis techniques related to the first part of the proposal to analyze the power and limitations of simple distributed network algorithms.