7 citations · 7 across the 1 of their papers we have counts for
3 papers
cs.IT2022★ 7 cited
The price of ignorance: how much does it cost to forget noise structure in low-rank matrix estimation?
Jean Barbier, TianQi Hou, Marco Mondelli +1
We consider the problem of estimating a rank-1 signal corrupted by structured rotationally invariant noise, and address the following question: how well do inference algorithms per…
cs.DS2021
Exact asymptotic characterisation of running time for approximate gradient descent on random graphs
Matthieu Jonckheere, Manuel Sáenz
In this work we study the time complexity for the search of local minima in random graphs whose vertices have i.i.d. cost values. We show that, for Erdös-Rényi graphs with connecti…
math.PR2018
Asymptotic optimality of degree-greedy discovering of independent sets in Configuration Model graphs
Matthieu Jonckheere, Manuel Sáenz
Finding independent sets of maximum size in fixed graphs is well known to be an NP-hard task. Using scaling limits, we characterise the asymptotics of sequential degree-greedy expl…