Search Results

Documents authored by Kızıldağ, Eren C.

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.68
Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs

Authors: Abhishek Dhawan, Nhi U. Dinh, Eren C. Kızıldağ, Neeladri Maitra, and Bayram A. Şahin

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
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 either the local or the low-degree polynomial (LDP) framework, and a rich literature has subsequently identified nearly sharp algorithmic thresholds within these classes by exploiting their stability. In the dense setting, however, the algorithmic paradigms are fundamentally different: they are online and thus need not be stable. Perhaps more crucially, even for the classical Erdős-Rényi random graph G(n,p), LDPs are conjectured to fail in the "easy" regime accessible to online algorithms, thereby challenging their viability for dense models. Our focus is on two models: (i) finding large independent sets in dense r-uniform Erdős-Rényi hypergraphs, where each size-r hyperedge is present independently with probability p, and (ii) the more challenging problem of finding large γ-balanced independent sets in dense r-uniform r-partite hypergraphs, where the vertex set is the disjoint union V_1 ⊔ ⋯ ⊔ V_r with |V_i| = n for all i, each hyperedge in V_1× ⋯ × V_r is present independently with probability p, and the i-th coordinate of γ ∈ ℚ^r specifies the proportion of vertices from V_i in the independent set. For both models, we pinpoint the size of the largest independent set and design online algorithms that achieve a multiplicative approximation factor of r^{1/(r-1)} in the uniform and (max_i γ_i)^{-1/(r-1)} in the r-partite model. Furthermore, we establish matching algorithmic lower bounds, showing that these computational gaps are sharp: no online algorithms can breach these gaps. Our results provide a detailed landscape for dense hypergraphs, thereby completing the picture for dense models in a manner parallel to the sparse counterparts developed recently. Our main technical contribution is twofold: a novel staged and bucketed greedy algorithm and a stopping-time argument tailored to the hypergraph and multipartite structure for algorithmic hardness, both of which may be of independent interest. The algorithms and proof techniques in the dense regime differ substantially from those in the sparse, yet the resulting computational gaps are remarkably analogous, pointing to a form of universality. More conceptually, our results corroborate a hypothesis from statistical mechanics linking glassy equilibrium to computational hardness: optimization problems become far more intricate in the presence of global constraints.
Cite as

Abhishek Dhawan, Nhi U. Dinh, Eren C. Kızıldağ, Neeladri Maitra, and Bayram A. Şahin. Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 68:1-68:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dhawan_et_al:LIPIcs.APPROX/RANDOM.2026.68,
  author =	{Dhawan, Abhishek and Dinh, Nhi U. and K{\i}z{\i}lda\u{g}, Eren C. and Maitra, Neeladri and \c{S}ahin, Bayram A.},
  title =	{{Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{68:1--68:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.68},
  URN =		{urn:nbn:de:0030-drops-277851},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.68},
  annote =	{Keywords: independent sets, random hypergraphs, online algorithms, overlap gap property, statistical-computational gap, Erd\H{o}s-R\'{e}nyi hypergraph}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.48
Sharp Thresholds for the Overlap Gap Property: Ising p-Spin Glass and Random k-SAT

Authors: Eren C. Kızıldağ

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
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 optimization landscapes and computational tractability. Both models exhibit hard regimes where all known polynomial-time algorithms fail and possess the multi Overlap Gap Property (m-OGP), an intricate geometrical property that rigorously rules out a broad class of algorithms exhibiting input stability. We establish that, in both models, the symmetric m-OGP undergoes a sharp phase transition, and we pinpoint its exact threshold. For the Ising p-spin glass, our results hold for all sufficiently large p; for the random k-SAT, they apply to all k growing mildly with the number of Boolean variables. Notably, our findings yield qualitative insights into the power of OGP-based arguments. A particular consequence for the Ising p-spin glass is that the strength of the m-OGP in establishing algorithmic hardness grows without bound as m increases. These are the first sharp threshold results for the m-OGP. Our analysis hinges on a judicious application of the second moment method, enhanced by concentration. While a direct second moment calculation fails, we overcome this via a refined approach that leverages an argument of Frieze [Frieze, 1990] and exploiting concentration properties of carefully constructed random variables.
Cite as

Eren C. Kızıldağ. Sharp Thresholds for the Overlap Gap Property: Ising p-Spin Glass and Random k-SAT. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kizildag:LIPIcs.APPROX/RANDOM.2025.48,
  author =	{K{\i}z{\i}lda\u{g}, Eren C.},
  title =	{{Sharp Thresholds for the Overlap Gap Property: Ising p-Spin Glass and Random k-SAT}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.48},
  URN =		{urn:nbn:de:0030-drops-244147},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.48},
  annote =	{Keywords: spin glasses, p-spin model, random constraint satisfaction problems, overlap gap property, phase transitions, computational complexity}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact