2 papers
cs.DS2024
Algorithmic Universality, Low-Degree Polynomials, and Max-Cut in Sparse Random Graphs
Houssam El Cheairi, David Gamarnik
Universality, namely distributional invariance, is a well-known property for many random structures. For example, it is known to hold for a broad range of variational problems with…
math.PR2022
Densest Subgraphs of a Dense Erdös-Rényi Graph. Asymptotics, Landscape and Universality
Houssam El Cheairi, David Gamarnik
We consider the problem of estimating the edge density of densest -node subgraphs of an Erdös-Rényi graph . The problem is well-understood in the regime $K=Θ(…