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
Visitors
Jobs
- Applications to our PhD program for the academic year 2021-22 will be available soon
- Applications for postdoc positions starting Fall 2021 will be available soon
Papers
- Antares Chen, Jonathan Shi and Luca Trevisan
Cut Sparsification of the Clique Beyond the Ramanujan Bound
Preprint, 2020,
arXiv:2008.05648
- Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan and Isabella Ziccardi
Expansion and Flooding in Dynamic Random Networks with Node Churn
Preprint, 2020,
arXiv:2007.14681
- Sam Hopkins, Tselil Schramm and Luca Trevisan
Subexponential LPs Approximate Max Cut
In Proc. of FOCS 2020, arXiv:1911.10304
- Andrea Clementi, Luciano Gualà, Emanuele Natale, Francesco
Pasquale, Giacomo Scornavacca and Luca Trevisan
Consensus vs Broadcast, with and w/o Noise
In Proc. of 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 Proc. of SODA 2020, arXiv:1811.10316
- Theo McKenzie, Hermish Mehta, and Luca Trevisan
A New Algorithm for the Robust Semi-random Independent Set Problem
In Proc. of 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