Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026★ 1 cited
Optimal Hardness of Online Algorithms for Large Independent Sets
David Gamarnik, Eren C. KızıldaÄ, Lutz Warnke
We study the algorithmic problem of finding a large independent set in the Erd{ö}s-Rényi random graph . For constant and , the largest independent set has…
cs.DS2025
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…