SO Re Co Di

Spectral and Optimization Techniques
for Robust Recovery, Combinatorial Constructions, and Distributed Algorithms

This project started in September, 2019, and is supported by the European Research Council. It applies techniques from linear algebra and from convex optimization to

problems of robust recovery and robust statistics;
the construction of combinatorial objects such as graph and hypergraph sparsifiers;
the analysis of probabilistic network processes.

People

Staff

Luca Trevisan: PI
Jonathan Shi: Postdoc, Sept. 1, 2019-present

Visitors

Antares Chen, Sept. 15 - Dec. 15, 2019
Hoeteck Wee, Oct. 2-5, 2019
Andrej Bogdanov, Dec. 9-14, 2019
Alon Rosen, Dec. 12-15, 2019

Jobs

Applications to our PhD program are due February 3, 2020 (application page)

Papers

Sam Hopkins, Tselil Schramm and Luca Trevisan
Subexponential LPs Approximate Max Cut
arXiv:1911.10304

Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco Pasquale, Giacomo Scornavacca and Luca Trevisan
Consensus vs Broadcast, with and w/o Noise
To appear in ITCS 2020, arXiv:1807.05626

Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan
Finding a Bounded-Degree Expander Inside a Dense One
In SODA 2020, arXiv:1811.10316

Theo McKenzie, Hermish Mehta, and Luca Trevisan
A New Algorithm for the Robust Semi-random Independent Set Problem
In SODA 2020, arXiv:1808.03633

Nikhil Bansal, Ola Svensson and Luca Trevisan
New Notions and Constructions of Sparsification for Graphs and Hypergraphs
In Proc. of FOCS 2019, arXiv:1905.01495