Eren C. Kizildag

collaborators

5 papers

cs.DS2026

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs

Abhishek Dhawan, Nhi U. Dinh, Eren C. KÄ±zÄ±ldaÄ +2

We study the algorithmic tractability of finding large independent sets in dense random hypergraphs. In the sparse regime, much of the natural algorithms can be formulated within e…

cs.DS2026

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 $G (n, p)$ . For constant $p$ and $b = 1/ (1 - p)$ , the largest independent set has…

cs.DS2025

Sharp Online Hardness for Large Balanced Independent Sets

Abhishek Dhawan, Eren C. KÄ±zÄ±ldaÄ, Neeladri Maitra

We study the algorithmic problem of finding large $I^^{3}$ -balanced independent sets in dense random bipartite graphs; an independent set is $I^^{3}$ -balanced if a $I^^{3}$ proportion of its v…

math.PR2025

Sharp Thresholds for the Overlap Gap Property: Ising $p$ -Spin Glass and Random $k$ -SAT

Eren C. KÄ±zÄ±ldaÄ

The Ising $p$ -spin glass and random $k$ -SAT are two canonical examples of disordered systems that play a central role in understanding the link between geometric features of optimi…

math.ST2025

Information-Theoretic Guarantees for Recovering Low-Rank Tensors from Symmetric Rank-One Measurements